That’s why lately I've been working on swift-endpoint, parts of which are going to make it to Swift’s new swift-networking-types.
At a minimum swift-networking-types will provide similar functionality to Go's net/netip, parts of Rust's std::net, and parts of Boost's Asio APIs.

As part of my work on swift-endpoint, I've been looking for elegant API shapes as well as performant implementations for IP address parsing and serializations, results of which are visible in the Performance section of swift-endpoint's README, where the APIs are compared to Darwin and glibc's inet APIs as reference points.

Yet Another IPv4 Parser

There are already lots of high-performance implementations in this space. Many people have contributed to these implementations over the years, be it in form of research, smart bit hacks, or completely new implementations. Most of the research can be attributed to Daniel Lemire and Wojciech Muła, although many more have also been involved.

The majority of the existing IPv4 parsing implementations are pretty clever and have implemented different kinds of tricks, bit hacks, and vectorizations to achieve high performance.
This new algorithm would not be possible without their prior art.

However, the bulk of the top-performing implementations make assumptions and decisions that don't fit Swift:

• An IPv4 address can be as short as 7 bytes (for 1.1.1.1) and as long as 15 bytes (for 255.255.255.255).
  • Lots of the other implementations rely on the existence of an 8th null byte, or they need padding, or they require 16 bytes upfront as a contract.
  • In context of the Swift language, this would be very unexpected. Contracts need to be enforced at API level. Null byte is not a thing outside interoperability with C/C++.
• Some of the top-performing implementations use lookup tables.
  • Benchmark results of implementations that use lookup tables assume that the L1 cache is already populated with the hot cache lines of those lookup tables. That's not always the case.
  • In reality, the preference is to achieve maximum performance without lookup tables, hopefully matching or beating an implementation that uses lookup tables.
  • Not using lookup tables typically means less binary size, less memory bandwidth usage, less reliance on memory latency or CPU cache statuses, thus more predictable performance.
  • However, it's still hard to come up with metrics about when and where and how much to use lookup tables.
    • In a lot of cases table lookups are actually worth it and can result in big performance wins.
• SIMD instructions can differ a lot on different CPUs.
  • In contrast, scalar implementations tend to be better supported by compilers and require little to no manual intrinsic function calls while being highly portable.
  • This is not true about the highest performing vectorized codes which tend to use the latest and greatest instructions provided by a given CPU generation, therefore taking hits on portability.
  • On the bright side it's also possible to write code that optimizers such as LLVM can typically resolve to well-performing auto-vectorized code, without getting deep into I*nstruction *Set *A*rchitectures (ISAs) of different CPU generations or having to write multiple implementations to support different CPU generations.
  • A good example of auto-vectorized code's performance wins is this PR to increase performance of swift-foundation's Base64 encoding by ~3 times. I plan to share my experience with auto-vectorization in another post.

Knowing all those, I was still in search of some better-fitting IP address parsing/serializing implementations.
That's how I ended up thinking more about them, and eventually came up with a new idea for a new IPv4 parsing algorithm. One that also performs well.

A New IPv4 Parsing Algorithm

Here are some IPv4 addresses that a correct algorithm would need to successfully parse, each containing 4 segments separated by dots:

• 1.1.1.1
• 192.168.1.1
• 255.255.255.255
• 127.0.0.1
• 203.0.113.5

The keys to the algorithm are to enable high parallelism for the CPU so it can perform multiple calculations at once. In this implementation, we use the following 2 major techniques:

1. Writing code in a way that the CPU core can run multiple (independent) instructions in the same cycle.
2. Single-*Instruction-Multiple-Data (SIMD) Within *A *R*egister (SWAR).

The first key is unlocked by the fact that although we’re not sure about where exactly each segment is, we still know their whereabouts.
For example, in any correct IPv4 text, the first segment and its following dot must be in the first 4 characters. Be it a 1. or a 192. or a 127..
So theoretically, if we fetch the first 4 bytes, we already have the first IPv4 segment, just that it’s neither validated nor as a number just yet.

The second key is unlocked by clever bit hacks.
We won't dive into SWAR in this post, but the bottom line is that today's processors usually come in 64-bit architectures.
This means they have general-purpose registers that are 64 bits wide.
One implication of such wide registers is that it makes little difference to the CPU if you're for example adding 2 UInt8 (unsigned 8-bit integer) together, or 2 UInt64s.
So as an example, via SWAR techniques you can cram 8 UInt8s into one UInt64 so next operations are performed only once on 1 UInt64, instead of 8 times on each of the UInt8s.
SWAR typically adds some overhead to the operation to ensure that, as an example the values don't overflow into each other. However it often results in noticeable performance wins anyways.

We also know that a valid IPv4 text cannot be smaller than 7 characters.

With those in mind, we admit the following facts about a valid IPv4 text:

1. The 1st IP segment must be present in indices 0…2.
2. The 4th IP segment must be present in indices 0…2 when reading backwards, from the end.
3. The 2nd IP segment must be present in indices 2…6.
4. The 3rd IP segment must be present in indices 2…6 when reading backwards.

We'll implement the algorithm similar to the following code, exploiting the fact that numbers 0…9 correspond to ASCII codes 0x30 to 0x39.

• For implementation detail reasons, we're also intentionally fetching some dots instead of only caring about the digits.
• We also XOR each window with a mask of 0x30 for each lane (here, a byte) which drops the 3 from numbers like 0x39.
  • This has the effect of making it obvious that 0x39 is a 0x09 == 9, which will help in the parsing process.
• loadUInt32(from:at:) loads 4 bytes of the from span into a 32-bit unsigned integer, starting from the index provided by at.
  • Loading multiple bytes at once is typically more performant than loading bytes one by one.

/// The amount of bytes that we've received to parse an IPv4 from.
let count = span.count
/// The shortest possible IPv4 address is "0.0.0.0" with 7 bytes.
guard count >= 7 else { return false }

/// `0x30` == ASCII `0`
let m30: UInt64 = 0x3030_3030_3030_3030
let m30_u32: UInt32 = 0x3030_3030

/// Read 1 window per segment, each also covering some dots around each segment.
///
/// XORing with `m30` turns the ASCII codes of `0`...`9` into the numbers `0x00`...`0x09`, and
/// the ASCII code of `.` (`0x2E`) into `0x1E`. So among digits and dots, only the dots have
/// their 5th bit (`0x10`) set. Invalid bytes are rejected later on.
///
/// Example for "192.168.1.98" (Notice little-endian byte-order):
/// `window1`: bytes 0...3 ("192.") -> `0x1E_02_09_01`.
/// `window2`: bytes 2...7 ("2.168.") -> `0x30_30_1E_08_06_01_1E_02` (in lanes 0...5).
/// `window3`: bytes 5...11 ("68.1.98") -> `0x08_09_1E_01_1E_08_06_30` (in lanes 1...7).
/// `window4`: bytes 8...11 ("1.98") -> `0x08_09_1E_01`.

/// Reads the "192." part.
/// We know `count >= 7` so this won't be an out-of-bounds read.
let w1 = loadUInt32(from: span, at: 0)
let window1 = w1 ^ m30_u32
/// Reads the "2.168." part.
/// With `count == 7` a read at byte 4 would go out of bounds, so it starts at byte 3.
/// "2." from `w1` | "168." << 16 == "2.168.".
let w2_p2 = loadUInt32(from: span, at: min(4, count &- 4))
let window2 = (UInt64(w1 >> 16) | (UInt64(w2_p2) << 16)) ^ m30
/// Similar to the `window1`, but read from the end.
/// Reads the "1.98" part.
let w4 = loadUInt32(from: span, at: count &- 4)
let window4 = w4 ^ m30_u32
/// Similar to the `window2`, but read from the end.
/// Reads the "68.1" part, and `w4` adds the "1.98" part, so `window3` is "68.1.98".
let w3_p1 = loadUInt32(from: span, at: count &- 7)
let window3 = (UInt64(w3_p1) << 8) | (UInt64(w4) << 32) ^ m30

/// ...

/// Reads 4 bytes at `offset` as a `UInt32` with the byte at `offset` in the lowest lane.
func loadUInt32(from span: Span<UInt8>, at offset: Int) -> UInt32 {
    unsafe span.bytes.unsafeLoadUnaligned(
        fromUncheckedByteOffset: offset,
        as: UInt32.self
    ).littleEndian
}

Now hold on a second. Allow me to not lose you. We will not dive too deep into the algorithm in this post.

However, I'll continue to explain the algorithm a little bit more as well as the optimizations that were made.

With the 4 windows above, what we'll need to do next is to find the position of the dots, strip the dots, and keep the digits.

However, in an IP address, there are only 3 dots (think: 1.1.1.1).
The matter of fact is, we don't need to parse 4 windows to find 3 dots. We only need 3 windows for that.
So an optimization that was made was to ignore window3 and parse the other 3 windows and find all the 3 dots, and later simply load a more-restricted window3 from memory considering we know it's before the 3rd dot (and after the 2nd):

let count = span.count
let m30: UInt64 = 0x3030_3030_3030_3030
let m30_u32: UInt32 = 0x3030_3030

/// Example for "192.168.1.98" (Notice little-endian byte-order):
/// `window1`: bytes 0...3 ("192.") -> `0x1E_02_09_01`.
/// `window2`: bytes 2...7 ("2.168.") -> `0x30_30_1E_08_06_01_1E_02` (in lanes 0...5).
/// `window4`: bytes 8...11 ("1.98") -> `0x08_09_1E_01`.

let w1 = loadUInt32(from: span, at: 0)
let window1 = w1 ^ m30_u32
let w2_p2 = loadUInt32(from: span, at: min(4, count &- 4))
let window2 = (UInt64(w1 >> 16) | (UInt64(w2_p2) << 16)) ^ m30
let w4 = loadUInt32(from: span, at: count &- 4)
let window4 = w4 ^ m30_u32

/// ...

/// The 3rd and last segment is between the 2nd and 3rd dots, which are both found by now.
/// `thirdDotBitCount` is 4, 12 or 20, so this only reads within bytes `count - 7`...`count - 2`.
/// `thirdDotBitCount >> 3` == `thirdDotBitCount / 8`.
let w3_idx = count &- 7 &+ (thirdDotBitCount >> 3)
/// Example for "192.168.1.98": bytes 6...9 ("8.1.") -> `0x1E_01_1E_08`.
let w3 = loadUInt32(from: span, at: w3_idx)
let window3 = w3 ^ m30_u32

/// Later strip the remaining garbage from window3.

This helped the performance by a few cycles. However this was not the end.

After more trials and back and forth with my LLM of choice, I settled on the following selection of window-finding algorithm as it resulted in the most performant implementation:

let count = span.count
let m30: UInt64 = 0x3030_3030_3030_3030
let m30_u32: UInt32 = 0x3030_3030

/// Example for "192.168.1.98" (Notice little-endian byte-order):
/// `window1`: bytes 0...3 ("192.") -> `0x1E_02_09_01`.
/// `window12`: bytes 0...7 ("192.168.") -> `0x1E_08_06_01_1E_02_09_01`.
/// `window4`: bytes 8...11 ("1.98") -> `0x08_09_1E_01`.
let w1 = loadUInt32(from: span, at: 0)
let window1 = w1 ^ m30_u32
let w2 = loadUInt32(from: span, at: (count >> 1) & 4)
/// "192." | "168." << 32 == "192.168.".
let window12 = (UInt64(w1) | (UInt64(w2) << 32)) ^ m30
let w4 = loadUInt32(from: span, at: count &- 4)
let window4 = w4 ^ m30_u32

/// Parse the 3rd segment from window3 later.

This brought the whole implementation down to around 75 instructions and 15 cycles for a valid IPv4 text on an M6 processor.

For the curious reader, the final implementation is available here and it contains enough documentation comments to be able to hopefully decipher it.
The implementation passes swift-endpoint's truly extensive test suite, as well as passing some fuzz-tests I've run on it.

How So Fast?

Having 3 or 4 different windows that can be operated on simultaneously is of great importance to performance of the algorithm.
Modern processors have CPU cores where each core contains multiple Arithmetic Logic Units (ALUs). This means they can execute multiple arithmetic operations in a single cycle when given the opportunity. You can see where this is going.

By having multiple different windows and having little sequential dependency between them, we enable our CPU cores to perform multiple calculations in each clock cycle, in what is called "Instruction-level parallelism". This is crucial to achieving maximum performance.
As mentioned, on my M6 processor this algorithm’s throughput is 75 instructions per 15 cycles for a single IP address. That's an average of 5 instructions in each cycle. A small part of that comes from the CPU executing multiple iterations of the benchmark loop simultaneously.

As discussed in the previous section, SWAR techniques also help a ton in lowering the number of instructions required to parse an IPv4.
This is thanks to the fact that each digit in an IP segment's text is only 1 ASCII byte, but we know we can handle up to 8 ASCII bytes at once on a 64-bit processor.

Benchmark Results

• The shapes columns refer to running the benchmarks against 4 million random valid IP addresses.
  • 4 million is big enough that branch predictors of neither M6 nor AMD processors can keep up with, which would skew the results.
• The real32 columns refer to running the benchmarks against a pre-determined set of 32 popular IPs.
  • To confuse branch predictors the order is randomly driven using George Marsaglia's xorshift algorithms via a constant seed. Specifically 13/7/17 variant of xorshift64 as defined on the Wikipedia page.
  • The RNG overhead is low and has not been deducted from the numbers.
• While the performance can differ with different corpora of IPv4s, the top 5 rankings are not affected.

Click to see all real32 addresses

127.0.0.1
1.1.1.1
8.8.8.8
9.9.9.9
255.255.255.255
192.168.1.1
10.0.0.1
172.16.0.1
100.64.0.1
208.67.222.222
185.199.108.153
151.101.1.140
104.16.132.229
142.250.185.78
13.107.42.14
23.185.0.2
0.0.0.0
224.0.0.1
169.254.169.254
8.8.4.4
1.0.0.1
149.112.112.112
208.67.220.220
172.217.16.142
140.82.121.4
198.41.0.4
192.33.4.12
193.0.14.129
199.7.83.42
93.184.215.14
20.190.160.14
34.107.221.82

Here are the specifications of the benchmarking environments:

Apple M6

The implementations that use SSE were run using sse2neon. They are indicated in the table via → NEON.

Ratios are compared to swift-endpoint.

AMD Zen 5

Ratios are compared to swift-endpoint.

Conclusions

• Daniel Lemire's sse_inet_aton implementation is very fast. But keep in mind it makes significant use of lookup tables and requires wide inputs by contract.
• swift-endpoint's parser ranks 2nd on M6, and 3rd on AMD Zen 5.

That's It?

This is the first post on my blog. I do realize there are some shortcomings.
Please let me know if you've noticed any ways to improve the blog, be it technical or non-technical.

Currently I plan to take a shot at the following:

• Publish a clean version of the source code of the benchmarks. Likely starting from some future post.
• Run the x86_64 benchmarks on more modern processors.
  • The benchmarking machines are not free so I'll have to find a cost-effective way to achieve that.
• Provide easy "one-click" ways to run the benchmarks on your own AWS account on an ephemeral EC2 instance.
• Make more improvements to the blog's UX without making it too complicated or unnecessarily shiny.
  • Likely open-source the blog as well, including the infrastructure-related code.