
A 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?
以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。
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?
Table Of Contents
Is This Post ...?
What Happened?
Yet Another IPv4 Parser
A New IPv4 Parsing Algorithm
How So Fast?
Benchmark Results
Apple M6
AMD Zen 5
Conclusions
That's It?
Is This Post ...?
I know what you're trying to figure out. No. This blog post is not AI generated.
What Happened?
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 and the open-source swift-nio.
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:
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:
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:
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:
We'll implement the algorithm similar to the following code, exploiting the fact that numbers 0…9 correspond to ASCII codes 0x30 to 0x39.
/// 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. The
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。