Hi everyone, I'm Jeroen, well I'm going to tell you something about parsing some files
really fast and I worked for NL netlabs, oh yeah, so some numbers, there's some caveats
here, so the fifth, I did not do measurements because I made finished the slides like today,
so I did the measurements on the train so, but I think the 50 megabytes is actually slower,
I'm pretty sure the 700 megabytes is correct and we will go beyond and I'm going to tell
you how, so yeah, so basically the motivation is that currently the parser NSD isn't very
fast and we have an operator where someone only takes the better part of an hour and
at that point it stops being practical, so yeah, that's the motivation and I actually
like to take you on a journey so that I went through, I will also show you the new algorithms
but I also want to tell you why parsing some files currently in NSD at least is really
slow and to do that we have to tell you a bit on parsing, so I've included an example
with a whole world sea program and the NSD parser is based on lexing jak and that's really
useful if you want to parse things like a computer language where each token has a meaning
of in and of itself, for some files however that is definitely not a case, so if you look
at the, also in this case I provide an example but everyone in the room will probably make
out that on the last line I try to define an A record with a corresponding IP address
and then what the zone parser actually does is it takes the A, it makes that the owner
and then throws a syntax error because well an IP address is not really a valid record
type obviously, so yeah lexing jak is really not a good choice but then there's also the
fact that I think zone files are only more or less standardized, they're not really standardized
and putting it modally and when you combine the two that just leads to a lot of trouble
and well the first thing I did was analyze why the current parser is slow and the current
parser is slow well, it's actually inherent to the tool because they're just not a good
fit because what the lexer does is it gives you each token and then passes on to the parser
but it does so by matching a whole bunch of inputs and then taking the longest one, the
longest match and then executing corresponding action in which in the case of the NSD zone
file parser means that you can, that it copies the token then tries to unescape it and for
names it tries to, it needs the dots right because they have meaning in domain names
and what it does there is that it actually splits the input and passes each label separately,
that is of course copied and the parser then concatenates that all back together and that
is not really a fast process.
So my first thought was well what if I just change the process a bit and scrap lexen
yak and cut all the memory allocations that gave us better numbers but they're not the
numbers that I wanted to see right because under the 8 megabytes is, I mean you can express
it in gigabytes a second but then it becomes even less impressive right than under megabytes
a second so.
So yeah I started looking into that and I will show you the algorithms that I used and
I came up with in a minute but to make you understand why these algorithms work it's
important that each and every one of you knows that your CPU is a pipeline CPU and all modern
CPUs are pipeline CPUs and what that means is that each executing each instruction is
not a single step it's actually a multi-stage process.
So there's a fetch and decode step and there's a lot more to it in practice but this is a
mechanism that was designed so that you to optimize performance in the CPU and the premise
on getting fast codes is that you keep the pipeline nice and full.
That does not always happen especially or one case where that doesn't happen is when
you get a pipeline install and that happens essentially when there's when the next instruction
that you want to execute depends on the result of the instruction that you're currently executing
and in that case the CPU has installed a pipeline it has to wait until the result is printed
back it can then go on to decode and then only then execute your instruction and you'll
take a hit of a couple cycles.
Then there's of course the well-known pipeline flashes and those happen essentially if there's
a conditional jump for instance an F statement and the CPU goes on to load the instructions
that come after that and if it turns out that it actually needs to execute other instructions
then it needs to flush the pipeline and only then can it go on to execute your code.
And there's bronze prediction that is used to improve the flow and modern CPUs actually
do a pretty good job of that but well it's prediction so it's not it's not always right.
And it turns out so if we look at that information then we can analyze why a parser is the process
of parsing is just inherently slow because if we go over it byte by byte like the NSDE
shown parser for example then before you can analyze the next byte you have to wait until
you know you have to resolve the new state of your current byte.
And also it turns out that as far as the CPU is concerned the zone files are just random
right that anything can happen at any time so it's hard to predict branches in that case.
Right so the base of the new instructions that I'm using at base is a thing called
a CND or single instruction multiple data and my interest in all of this was really
sparked by the CND JSON project and it caught my attention because they expressed their
throughput in gigabytes a second.
Now in the next slide I'm going to tell you something about the algorithms but I'm not
going to go into them in great depth because there's not a whole lot of time so if you
want to know more on that then I would advise you to watch the talk or just read the paper.
CND what that is is actually an instruction set and what it does it adds factor in registers
and instructions to operate on those registers and what that allows us to do is to classify
blocks instead of just bytes and there's some trick re-involved and there's a super simple
example on the slide but basically we can classify 16, 32 or 64 bytes in one go depending
on your CPU and then we repeat that multiple times for each input that we actually want
to know about and the idea is that we can cut branches and dependencies.
So what's good to know about CND is that it's all vertical non-horizontal so it's really
it's really an instruction that is executed for each of the inputs so you can actually
do logic in CND and the way to work around that is to convert the inputs to a mask.
So we would get a 64 bit mask for each of the inputs that we checked and with those
bit masks in hand then the first thing that we are going to do is to classify all the
escape bits because there's some files allow for escaping and this is actually an algorithm
that CND JSON guys came up with and basically what we do is that for each uneven number
of backslashes we take the next character and so that bit then represents the character
that is actually escaped and we need that information so that we can identify the quoted
sections or in the case of some zone files also the comment sections and this was actually
kind of a hard problem because they don't have this problem in JSON documents but in
zone files comments can cancel out quoted sections and quoted sections can contain semicolons
and then new lines they limit comments but we only want the new lines that actually delimits
the comment because what we really want to do is that we want to find out which of the
characters that we identify as structural characters are contained in quoted sequences
or in comments and there's a simple example in the bottom there so oh yeah I did a number
of experiments but in the end it turned out that if there's a semicolon in the input we
just branch so we have a slow path assuming that there's not too many comments in zone
files which for generated zone files I guess it's okay and once we have that information
all the bits that remain automatically belong to the non quoted strings and then and this
is oversimplifying it but if we shift right and do an XOR then that would get us all the
transitions and with that information we can then go on to create indexes of those because
your CPU does not only provide SIMD instructions it also provides bit manipulation instructions
really fast bit manipulation instructions so the first thing that it does is it takes
the population count to find out how many transitions are actually in your input block
and then we use the trailing zero count to find out the relative position of the bit
and if we combine it with the index then that should give us the pointer to the exact input
byte and there's some more trickery involved here because of course for zone files if there's
an error we want to report that error and to do that we need a line count and quoted
sections of course may contain just new lines but we don't want to worry about those in
the parser because that would mean that each parse function would possibly need to update
a line count and that would just not be very convenient so what we do there is we take an
unlikely branch if there's new line in the quoted section which really doesn't happen
it's an edge case in the case of zone files and we take the slope path to count all the
new lines in the input or at least the one in the quoted sections and then once we generate
a token for the actual, the limiting new line we add the number of new lines that we found
in quoted sections yeah and that gives us basically that gives us a fast scanner in
my initial measurements and I think it's a little bit fast now that would get me a scanning
of two gigabytes a second for zone files at least with an older.com zone etc etc so there's
caveats there too but it turns out that the rest of the DNS data because we of course
we have to parse it we only now tokenize it we also have to parse it the rest of the DNS
data allows for optimizations using cindy as well and of course we want to start with
the data that occurs the most and that is of course the main names and with the cindy
instruction we actually just repeat the scanning process we quickly identify all the dots we
turn that into a bit mask and then use the bit manipulation instructions to go over the
domain name because most of the time if we just fill in the length on the dot then that
would give us a proper Y format and of course there's a slow path for edge cases as well
there and next of course is the record type and normally I guess you would hash I'd initially
just use binary search which is faster than just linear search of course but that took
away quite some performance so we want a perfect actually we want a hash but then a hash table
is pretty big and so I figured I want a perfect hash and it turns out we can do we can do
that so if you take the first character of the records because there's not that many
record types right and there's certainly if you take the first character there's never
more than that many record never more than like eight or nine record types that start
with the first letter so if you then take the last character and at length then it turns
out that doesn't give me any collisions so we can also the hash of collisions occur but
I mean for all the record types and what for 40 years it doesn't give me collisions so
I guess we're good on that from with a number no for each record type someone asked if this
only works for record types and then the number and answer is no it works for all record types
because they're all closely they're all really close together right so they're and they're
alphanumeric most of the time sometimes there's numbers so we just I think our uppercase or
downcase it and then multiply together a good distribution and then just add length and that
gives me that gives that gives me a unique key without collisions and from there I can
just do a use in the instruction to do compare equal so I can do the exact right string compare
and that gives me a really nice nice speed up yeah and it and the people who worked on
some DJs and actually do a lot of did a lot of projects like using Cindy for for decoding
base 64 so the plan is to incorporate all those things as well and then there's one
tricky part your CPU actually supports multiple instructions that at least if you have modern
CPU if you have like a pending for then you only get SSC 42 but we want our software to
be able to run and all those devices without recompiling so we actually compile it four
times in the case of xx86 then use the CPU ID instruction to pick the right one and then
well it's still in progress projects I have hoped to be a little bit further along but
unfortunately not it will be a standalone library because it might actually be useful
to other people and that will make it easy to integrate into other projects it was initially
just intended for NSD yeah the numbers are so far pretty good at least quite a bit better
than what we have now I think it's possible to go to one gigabyte a second yeah so if
you want to check it out there's a link in there and finally I want to there's slide
with acknowledgement because these people help me a lot I just send them on unsolicited
email at first and then I happen to get answers back and they help me and they even took a
look at my presentation help me there as well so thanks to Jeff Daniel and all the sim
DJs and people and with that I actually finished in time it's time for questions yes oh no but
that's the slow path and exactly there the hash doesn't work but that's the slow path
so we do a slow path sorry I should repeat the question what the person in the audience
was actually referring to what happens if you we use a generic type notation where we start
the type by type followed by a number and obviously it doesn't work there but it does
the slow path so we have a slow path there is the person so complete that you can parse
an output and you get the same output as a parsed in really good because I would so if
the parser is good enough that to give you the exact same output as you put in no it
does not do that no well you you I mean do you mean by access to white space exact or
just yeah no it doesn't do that no and then but it's also not it does also strip comments
yes yes yes yes yes yes yes how do you handle escape decimals because in the example you
gave you strip and you have looked where the backslashes are yeah and then take the next
character but if you have like backslash 003 then you need those four characters as a single
unit to encode in the final I'm not actually I just do the I just really good yeah you're
gonna have to I hope there's no more questions because you're gonna have to keep doing that
but what I so what happens if I guess for certain type of input I record like a backslash
003 which encodes the byte with a value 3 single byte yeah how do you do that with your algorithm
that just takes the next character when you have backslashes but that's just to that's
just to so the question is what do I do with escape characters or with escape sequences
and so what I explained on the what I do what happens with backslashes is just to tokenize
so I don't strip any data I just mark out the starts in the ends of each string field
and then the parsing comes after that so there's no data actually stripped yeah so the question
is so the question is what's the output format and the output format in this case is just
DNS wire format so the the idea here is that for each record it will invoke a callback
and it will just give you wire format with pointers to where all the fields are in the
like an internal description of the field so that you know the length and you know the
type of the field yeah there is definitely value to large effectors because it takes
less instructions so if you can do something so I did not look into using the GPU but yeah
that might benefit so if you know I have not so the question is why do why does parsing
zone files have to be fast well because they're they get reloaded quite a lot of times each
time there's an update to a zone you need to reload you need to reload the zone so we
want to yeah the so that happens multiple times like an hour it differs per zone right
but in our case if it takes more than an hour and the operator actually or it takes the
better part of an hour and the operator wants to lead more wants to reload more often then
that becomes a problem right so we just need to be faster but then there's all the end
so there's other benefits as well so NSD for instance we support zone verification where
just before the zone goes live you can have a focus program to verify that your DNS stack
data is correct and there you can use an AXFR or you can let the NSD feed you the zone data
in which case you just get text representation and if the zone is big enough then you want
that to be fast because it's in the critical path right yeah well actually if the question
was if splitting the files and multi-threading is something that we consider well splitting
the files no but split on them yeah well new lines yeah that can be tricky because
zone files can contain parentheses which would then mean that the record continues on the
next line but a colleague actually did do a parallel zone loading implementation and
I guess we can even do that with with this implementation right because there the it
was actually quite a bit faster but the scanning process still takes a long time because you
go over it by by bite but now that we have a fast scanner there's no reason why we cannot
also include like parallel parsing yeah that could work yeah so the question is if we did
it