A Fast IPv4 Parser, in Swift A new scalar IPv4 parsing algorithm implemented in Swift parses an address in 75 instructions and 15 CPU cycles, reaching roughly 3 nanoseconds on an M6 processor, according to the author's write-up accompanying the open-source swift-endpoint project. The implementation avoids lookup tables and the null-byte or 16-byte padding contracts common in other high-performance parsers, aiming for more predictable performance and less binary size, and parts of swift-endpoint are slated to land in Swift's new swift-networking-types package. The author credits prior research by Daniel Lemire and Wojciech Muła as the foundation for the approach. A Very Fast IPv4 Parser, in Swift How can we parse an IPv4 address with a throughput of 75 instructions in 15 CPU cycles, taking as low as ~3ns on an M6 processor? I know what you're trying to figure out. No. This blog post is not AI generated. With that out of the way ... As of writing this article, Swift doesn't have a unified or high quality platform-independent stack of basic networking types, with implementations being scattered across Apple's proprietary Network framework https://developer.apple.com/documentation/network and the open-source swift-nio https://github.com/apple/swift-nio . That’s why lately I've been working on swift-endpoint https://github.com/swift-dns/swift-endpoint , parts of which are going to make it to Swift’s new swift-networking-types https://github.com/swiftlang/swift-networking-types . At a minimum swift-networking-types https://github.com/swiftlang/swift-networking-types will provide similar functionality to Go's net/netip https://pkg.go.dev/net/netip , parts of Rust's std::net https://doc.rust-lang.org/std/net/index.html , and parts of Boost's Asio https://www.boost.org/doc/libs/latest/doc/html/boost asio/reference.html 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 https://github.com/swift-dns/swift-endpoint performance of swift-endpoint's README, where the APIs are compared to Darwin and glibc's inet APIs as reference points. 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 https://github.com/lemire and Wojciech Muła https://github.com/WojciechMula , 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 S et 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 https://github.com/swiftlang/swift-foundation/pull/2236 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. 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. S ingle- I nstruction- M ultiple- D ata SIMD W ithin 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 UInt64 s. So as an example, via SWAR techniques you can cram 8 UInt8 s into one UInt64 so next operations are performed only once on 1 UInt64 , instead of 8 times on each of the UInt8 s. 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. - This has the effect of making it obvious that - 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. js /// 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