Making DNS_Erlang Fast: Binary Tricks for the Beam
You can ask the compiler where binary optimisations apply, and where they don't. Compile with erlc +bin_opt_info, or ERL_COMPILER_OPTIONS=bin_opt_info mix compile --force in Elixir, and it will report every match contex…
以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。
You can ask the compiler where binary optimisations apply, and where they don't. Compile with erlc +bin_opt_info, or ERL_COMPILER_OPTIONS=bin_opt_info mix compile --force in Elixir, and it will report every match context it keeps and every place it has to give one up.
Every number below comes from Benchee on two very different machines (an Apple M4 Pro and an AMD Ryzen 9 9950X3D), on OTP 29 with the JIT, measuring time, memory and reductions. Every change also went through a parity harness proving the new code byte-for-byte identical to the old, down to the errors raised on malformed input: 26,434 cases for name decoding alone. And we kept the experiments that lost, with their numbers; we'll get to them.
Encoding a DNS response means writing a header, the question, and then every record in the answer, authority and additional sections. The old encoder built each section as its own binary and then copied it onto the message. Each record's data (its RDATA) was also built as a separate binary, measured to write its length, and copied in.
Each of those intermediate binaries is allocated, filled, copied and thrown away. The append optimisation can't help, because we keep starting new binaries instead of extending one.
In #100 and #139 we turned the whole encoder around: a single accumulator flows through every section, and each record appends itself straight onto it. Even the RDATA length is computed from the parts and written in the same append as the data:
%% Before: the RDATA is built on its own, measured, then copied in. encode_rr(Acc, RR) -> Data = encode_rrdata(RR), <<Acc/binary, (byte_size(Data)):16, Data/binary>>.
%% After: the length and the data go onto the message in one append. encode_mx(Acc, Pref, Exchange) -> <<Acc/binary, (2 + byte_size(Exchange)):16, Pref:16, Exchange/binary>>.
There was one more wrinkle. A DNS message starts with a 12-byte header whose counters (how many answers, how many authority records, and so on) we only know at the end. So the accumulator starts with 12 zero bytes as a placeholder. Every section is appended after it, and because the placeholder is already there, the accumulator's size is always the current position in the final message, which is exactly what name compression pointers need. When the message is complete, the real header is built and placed in front of the body, in the only copy of the body the whole encoding makes.
On the UDP response path, measured on the M4 Pro, a simple response went from 708 ns to 583 ns and from 1.89 KB to 1.23 KB allocated, and a typical DNSSEC response from 1.33 µs to 1.13 µs.
Decoding has the mirror-image problem: it's easy to accidentally force the BEAM to materialise terms it never needed.
A good example is TXT records, which carry a list of length-prefixed strings. The old code delegated each string to a helper that returned a {Rest, String} tuple. That's one tuple allocation per string, and because Rest escapes inside the tuple, the compiler must create a real sub-binary for it. In #135 we match the string directly in the loop's head, so the match context survives:
%% Before: a helper returns a tuple, and Rest escapes inside it. decode_text(<<>>) -> []; decode_text(Bin) -> {Rest, Str} = decode_string(Bin), [Str | decode_text(Rest)].
decode_string(<<Len, Str:Len/binary, Rest/binary>>) -> {Rest, Str}.
%% After: match the string in the loop's own head. decode_text(<<Len, Str:Len/binary, Rest/binary>>) -> [Str | decode_text(Rest)]; decode_text(<<>>) -> [].
The same pull request found a less obvious copy: the decoder stored each section into the #dns_message{} record as soon as it was decoded. Records are immutable tuples, so every update copies the whole thing, and this record is 19 words. Updating it four times per message (questions, answers, authority, additional) meant four copies. Passing the sections along as function arguments and building the record once at the end cut 11% of the reductions and 10% of the allocation for decoding a query, which is exactly what every incoming packet goes through.
Domain names are case-insensitive, so dns_erlang lowercases them a lot. The old to_lower/1 used binary comprehensions over 8, 7, 6, … 2-byte chunks, picking the largest chunk size that evenly divided the input:
to_lower_chunk(Data) when byte_size(Data) rem 8 =:= 0 -> ...; to_lower_chunk(Data) when byte_size(Data) rem 7 =:= 0 -> ...; to_lower_chunk(Data) when byte_size(Data) rem 6 =:= 0 -> ...; %% ... down to rem 2, then one byte at a time
It looks reasonable. Then we looked at what the JIT actually generates for it. On x86-64, rem 8, rem 4 and rem 2 compile to cheap bit masks, but rem 7, rem 6, rem 5 and rem 3 each compile to an idiv instruction, which costs somewhere between 20 and 90 cycles. A name whose length isn't a multiple of 8 (most of them) paid for up to four divisions just to choose a strategy, and a prime length paid for all four and then went byte by byte anyway.
The rewrite in #114 uses plain function clauses that match large chunks first and fall back to smaller ones. A clause like <<B0, ..., B7, Rest/binary>> compiles to a single size comparison, with no division anywhere:
lower(<<A, B, C, D, E, F, G, H, Rest/binary>>, Acc) -> lower(Rest, <<Acc/binary, (l(A)), (l(B)), (l(C)), (l(D)), (l(E)), (l(F)), (l(G)), (l(H))>>); lower(<<A, Rest/binary>>, Acc) -> lower(Rest, <<Acc/binary, (l(A))>>); lower(<<>>, Acc) -> Acc.
Funnily enough, this wasn't the first time that dispatch had shipped. Years ago I contributed the very same trick to OTP's hex encoding in erlang/otp#4690, where it made binary:encode_hex/1 two to three times faster than the original implementation. It survived the addition of binary:encode_hex/2 in erlang/otp#6297, until Björn Gustavsson replaced it in erlang/otp#6869: a size not divisible by anything from 2 to 7 took about three times longer than the best case, so the new code encodes the largest multiple of 8 bytes in one comprehension and finishes the last few bytes one at a time. The same pull request made binary:decode_hex/1 almost ten times faster. In other words, the OTP team had already found and fixed this exact pattern in my own code, three years before I found it again in dns_erlang.
The lesson isn't really about rem. It's that the BEAM JIT is now good enough that the generated machine code is worth reading. Start Erlang with +JDdump true (or ERL_FLAGS="+JDdump true" for Elixir) and it writes the assembly of every loaded module to disk. Ten minutes in those files can explain a benchmark that hours of guessing can't.
This one started with Daniel Lemire's post on detecting special characters with SWAR, and a simple question: can we do that on the BEAM?
SWAR stands for SIMD Within A Register. Instead of looking at bytes one at a time, you load several bytes into one integer and use ordinary arithmetic and bitwise operations to test all of them at once. The classic trick answers "does this word contain a zero byte?" without looking at any byte individually:
has_zero(V) = (V - 0x0101...01) band (bnot V) band 0x8080...80
Subtracting 1 from each byte only borrows into a byte's high bit when that byte was zero, so the result is non-zero exactly when some byte of V is zero. To ask whether a word contains a specific byte, say ., XOR the word with that byte repeated in every lane first: matching bytes become zero.
On most platforms you'd use a 64-bit word. On the BEAM that would be a mistake, because a 64-bit value doesn't fit in a small integer: the arithmetic would allocate bignums on the heap, and the JIT can't emit plain machine instructions for it. The largest whole number of bytes that fits is 7, so we use 56-bit words. All the intermediate values stay small integers, and every band, bxor, + and - compiles to a bare instruction with no type checks.
Best of all, the whole test is legal in a guard. Here's how dns_erlang escapes a label while decoding a name: seven bytes at a time when they contain neither . nor , byte by byte only around the ones that need escaping.
-define(ONES, 16#01010101010101). -define(HIGHS, 16#80808080808080). -define(HAS_ZERO(V), ((((V) - ?ONES) band bnot (V)) band ?HIGHS)). -define(CLEAN(W), (0 =:= (?HAS_ZERO((W) bxor (?ONES * $.)) bor ?HAS_ZERO((W) bxor (?ONES * $\))))).
escape_label(<<W:56, Rest/binary>>, Acc) when ?CLEAN(W) -> escape_label(Rest, <<Acc/binary, W:56>>); escape_label(<<$., Rest/binary>>, Acc) -> escape_label(Rest, <<Acc/binary, "\.">>); escape_label(<<$\, Rest/binary>>, Acc) -> escape_label(Rest, <<Acc/binary, "\\">>); escape_label(<<C, Rest/binary>>, Acc) -> escape_label(Rest, <<Acc/binary, C>>); escape_label(<<>>, Acc) -> Acc.
In Elixir, defguardp plays the role of those macros, so the same guard reads just as naturally there.
Notice how all the previous patterns are in there too: the label is only ever matched, so it stays a match context; the output is a single append-only accumulator; and the clauses go from the biggest chunk to the smallest.
The same idea makes case conversion branch-free. With a couple more subtractions you can find every byte between A and Z in the word, and flip their 0x20 bit in one go. That's how to_lower/1, to_upper/1 and the case-insensitive comparisons in dns_erlang work today (#124).
The fun part is that this didn't stay in our library. The same week it landed in dns_erlang, we took the trick upstream, to Erlang/OTP and Elixir themselves:
All three shipped in OTP 29 and Elixir 1.20. If you're on those versions, you're already running this code.
And then the community ran with it. Over the following months, other people brought SWAR to more corners of the ecosystem:
It's a nice reminder of how an idea travels in an open ecosystem: from a blog post about C, to a DNS library, to the standard libraries, and from there to code that most Elixir applications run on every request.
DNS has its own compression scheme: when a name, or the tail of a name, already appears earlier in the message, you write a 2-byte pointer to it instead of the name. The encoder keeps a map from every name suffix it has written to its position in the message.
The old map was keyed on lists of lowercased labels: [<<"www">>, <<"example">>, <<"com">>]. Every lookup had to hash or compare a deep term, and a name couldn't be looked up at all until it had been split, validated and lowercased, even when the answer was going to be "use this 2-byte pointer".
Two rounds of work changed that. In #133 the encoder stopped splitting every name twice, and stopped growing the map one key at a time. Inserting into a small map copies it, so inserting a key per label meant one copy per label; the encoder now collects a name's suffixes and inserts them in one batch. For a name with 50 one-character labels, encoding went from 211 µs to 9.4 µs, 22 times faster. More importantly, an ordinary 8-label name went from 1.51 µs to 0.54 µs.
Then in the next round the keys themselves changed: each suffix is now the lowercased name as a binary, and each one is a sub-binary of the same name, so they cost nothing to produce and a single memcmp to compare. As a result, the raw input name is its own first key, and a name that's already in the map is answered before any splitting or lowercasing happens. That's the common case in a real response: every record in a set repeats the owner name, the answer repeats the question, and glue records repeat the nameserver names. Whole-message encoding got between 1.1 and 8.9 times faster, depending on how much the message repeats itself.
Some of our favourite ideas lost, and the numbers were very clear about it:
The lesson: the BEAM is often smarter than you'd expect, and the only way to know is to measure.
Micro-benchmarks are nice, but what we care about is the nameserver. So we built a test that looks like production:
The summer work (the single accumulator, the decoder changes, the compression keys and SWAR in name decoding) shows up clearly: 12% less C
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。