Okay, so welcome to my talk, called UltraFast, Lua Jason Parsing.
It's called UltraFast, because at the time when I was submitting the proposal, I still
wasn't sure how fast it's going to be, so we will see.
So yeah, a bit about me, why I'm interested about Lua and Jason.
I'm mass software engineer at BMG. It's a video game, because in later we have a close source
engine, unfortunately, but the Lua code, which is most of the logic, is open source with an open source
license, you have to buy it though. And my focus there is on the Linux port, security, so we are
unboxing some user code and also a bit of like hacking on LuaJet, so if you want to talk about
any of this, I would be happy to. So what is LuaJet if you didn't hear? It's a compiler, just in time
compiler for Lua programming language, and Lua is really commonly used in game development.
LuaJet comes also with a hyper from an interpreter written in C, but it's compatible with
the Lua API, and why do we use it for the game, because these logic virtual machines are
very small, and we run lots of them in threats, so forever vehicle, we run a single logic VM,
which then they communicate with each other, and LuaJet is also fast, we have quite high update
rate, so some systems in the game run up to two kilohertz, and this is the problem.
Okay, this might be bad. Okay, this is the problem. So Jason, you know, it's a notation
how to or a format, how to exchange data, is a strength format, and Lua is a program language,
so this program language has basically only one complex data type, which is both
an associative array, and also sequential array, so it has this like keys and values,
and yeah, this is not, we are not interested on the speed, on the pure speed of the Jason
parsing, but also in the creation of the Lua object, because in the end, both of these parts
need to be fast enough, for the use case, because we need to work with this object, not just
parse the representation into an intermediate structure. So of course, there are so many Jason
libraries available in C++, or even in Lua, there is a lot of libraries available, or you can
combine this, because Lua has a CAPI, so or some people made this publicly available, or you can
also do it on your own, you can take any C++ library, and then use some sort of Lua bindings
with C or C++. They exist, of course, but let's go by one by one. So with this pure Lua libraries,
which are available on the internet, you can integrate it into your cultural easily,
but at least the ones that I tested are just not performant enough, because Lua is still a dynamic
scripting language, or these implementations are not focused frequently on performance.
So let's go for the C++ libraries, and then here I think the state of the art is Cindy Jason,
which is very fast based on their own benchmark. They say they can parse Jason at gigabytes per second.
Of course, for this, you need the extra bindings, which might make the whole thing slower.
And the biggest problem for our use case, of course, you can use Cindy Jason for Jason parsing,
but our Jason format is actually not strict Jason, and we have some extra features in there,
so which I will talk about later. And then you have like the middle ground, these bindings
they suffer from the same problems as the pure C++ libraries. So it means like for example,
if you extend Lua's Cindy Jason, you still have the problem that it's like a strict parser.
And some of them, for example, also the Lua's Cindy Jason, which is public available,
they use the Lua's C API, and this might be a surprise, but using the Lua's C API is
not so perform, and it actually hurts the parsing a lot, as we will see.
So it's time to reinvent the wheel and write a Jason parser again.
And this is our format, it's called Jbim, but in the end it's just Jason with comments,
or as Jason, there are some, you might see this file, it kind of looks weird, we can check all the
differences. So you have comments, which you don't do anything, but you have to parse them,
you can have equal signs instead of columns just for like whatever sake.
Cmas are fully optional, they are treated as white space, and also you don't need to cove your
strengths when they are the keys of the dictionaries. Just basically it. Yes, so you can find
this format, it was used in multiple other kind of source first, but there is not one single
exact specification for this. So we wrote our own parser, and first we wrote it in Lua,
because that is easy. And it's already used in the game for the past 10 years, for example,
so it's well, but it's small, you can write the parser in 300 lines of code.
And it also parsed Jason because as Jason or the Jbim
is only a superset of Jason. But of course, it has some caveats, it is not a validating parser,
because for example, it fully ignores Cmas, so it cannot tell you whether Jason files
a false specification or not, so it also parses some files which are not strict Jason,
and it was written to be Jet Friendly as we used logic. So let's just, yes, or there is going to be
some quite of source code. So let's see the basics. This is the basic function, and
yeah, we start like doing some tricks to be faster. So logic is or Lua is a garbage collected
language, so for the duration of the parsing, we disable garbage collection, because it's
much faster when we are working with lots of new objects, so that is trig number one.
And then skipping white spaces is a big part of the Jason parsing, because there can be quite
a bit of useless white space in Jason, of course, not if your Jason is modified, but in this case,
we have like semantic meaning in all these comments, so we want to keep them. And Jason parsing
is just going through all the characters, basically, and checking whether they are a space or
whether they are a comma. As you can see, we have the ASCII values for this, because Lua
just doesn't have a character data type, so you would have to use a one-character string, which is
much slower, so to go faster use numbers. And the important takeaway, white space skipping can
take a lot of time. We will see later that some optimizations are related to white space skipping,
and the core of this algorithm of the Jason parsing is this peak table, which only loops
at the next character, and basically what you need to parse, if you have written a parser before
Jason is really easy, you don't need to look far ahead, you just get to see the one single
next character, and this is the full full record, like full implementation of the parsing,
like if you see the next character, it can only be null or it's invalid Jason, the same for
some Boolean values, I especially because you can have infinity, which is the number,
and then on these strings and for our use case comments. So our peak table, it just loops again
at the ASCII values, and based on that, for example, if it encounters the value of t, then it just
checks if the next three values are RE, so true, and if not, then it fails. And the only like
more complex functions are the one that parses your objects or arrays. So you see that first
we like allocate a new table, then just read the key, which is a string in Jason,
then skip Y space, read the value, which can be anything, so here is the recursion, and
does it, that's basically it, but again there are some optimizations done. For example, this
table new function, you specify the number of values, then what they should have pre-allocated.
So you can, and logic tables are special in this way, that they have the sequential array part,
and then the hash part, which is the ASCII array. And we specify,
yeah, we specify the three values, because it was a value selected by benchmarking, of course,
but it's important to focus on this if you are optimizing, and another of the tricks
is actually like we have skipped Y space function, I showed it to you, but it's proved to be faster
to copy this, skip Y space implementation into the code, because logic or logic in general
has over it for a function calls. So sorry, so inlining gives you some extra performance boost.
Now let's focus on the benchmarking. I used the latest commit of logic, because it's
continuously developed project, this is my CPU, my system doesn't matter, too much.
I made this benchmarking protocol on the go, yeah, this is my kind of like first time benchmarking
project, so of course like you have probably seen the talk before, how to measure performance
reliably, so followed it. But in the end, I got some of these things right. I run passes
through some adjacent data sets, and I run either, I get some number of these passes, or some
timeout runs out, and I do some things for this to not for the runs not to be dependent to much
on each other, and I collect the garbage before I measure, and I also flush the jit cache,
which means like the jit has a clean state, so in theory, it shouldn't be influenced by the fact
that I already like parsed this JSON file one thousand times before, because otherwise we would
just have ever think in the jit cache. I take the mean time of the pass, and I repeat everything,
so I have like some inter, these like inter runs, I repeat everything five times, take the mean of
the means, and calculate throughput out of it. I also was looking at the minimum and maximum,
but I didn't include it in these numbers, to many numbers, and to further reduce the variance
of on my machine, yes, I set the priority to the maximum, and it also helped a bit to
always force the same CPU core, like the same CPU affinity using tasks. So let's talk a bit about
the data sets I used. The first one is the jit beam data sets, so this is the file that we actually
wanted to parse. These are the S JSON files, which are mostly numbers, some positions, and short strings,
and they represent the structure of the physical structure of these vehicles. So, they tell
which of these nodes, which have IDs are connected to each other, and the strength of these
connections for the purpose of the simulation. And I did the benchmark, and our parser is the fastest,
because the other parsers do not parse as JSON, because there are commands, so this does not tell
as much. Therefore, I made the JSON data set, which contains some testing files, which
simply JSON is all using. So, 20 files with different sizes, different context, different structures,
and I run it again in total 15 megabytes, and our parser is not the fastest anymore.
You see with jit, it still reaches like reasonable performance, but loss in JSON is faster. We don't
get the gigabytes per second. They were advertising, but in the end, it's okay, but we were not happy
with it. Also, when you look at the number with jit off, which is a realistic situation,
there are some platforms where jit is not available, then the performance is really bad.
And yeah, this is just an extra one file data set. I wanted to see the difference between these
all like 20 files and one file that I already like understand what's inside, so these are just like
Twitter statuses, it's really commonly used, and the numbers are quite similar, or at least the
positions of these parsers. So, we have this loop parser, which you have bits of
very pure loop parsers, but the SIMD JSON is very, and also the performance of the loop parser
relies on jit, and this is the point of the talk, if we can go closer to the source code and
get a faster implementation. Just a bit about logic source code, it's not, it's not large, it's
around 70, 70 c files, and some handwriting assembly, but in the end, if we just want to
hack on it a bit, we are interested in two files, and the one which does serialization of some
internal logic format and string buffers. So, string buffers are, let's say, a module in
logic, which allows you to have mutable strings, because normal logic strings are not mutable,
and are also interned, and this is the serialization function that logic already has. So, you
encode a table, you see this is the same as encoding a table, for example, to JSON, but it
comes to a different format, and you can also take this format and decode it simple, but we can
steal the source code of this, and basically implement it like to generate JSON and deco JSON instead
of this. So, it's almost the same, you see the same primitive skipping white space, and again
like peeking on the next value, is the same, here we go, just like character, like character.
So, here are some simple things, I will start skipping a bit, because, okay, and here is really similar
to the implementation. Again, you need to pre-licate some memory, with the type of new function,
it does the same thing, except this number is in the C function is one more, because in the
CAPI index from zero, and in the normal one from one, and then it writes the lower values.
So, we did it like this knife implementation, and it's much better when the JSON is soft,
like, and the performance doesn't matter on the jet, but it's, we didn't get, we didn't get an
speed up, or it's even worse. So, what optimizations can we do? Branch predictor hints are
over a part of, of logic, and we can basically say, like give a hint to the compiler that this
shouldn't happen, so you should always like, yeah, you should expect that the likely part
is happening. So, for example, here, every time we encounter an error flow, like an invalid
invalid JSON, or the end of the file, we don't need to care about it, like, if it's slower fast.
So, it's, it's unlikely to happen for us. Then, the initial number parsing, I, I use the
logic function, which deals with all sorts of formats, but I did some profiling, and it show
that it's not, it's not super-formant. So, I simplified the code, I really wrote like the
knife implementation, where it just like parsed the digits until you encounter the
digit dot, and then you put the fraction value, it was, it was much faster. For some of these
scientific numbers, I still use the original function, because I'm lazy, but these numbers
are not common, in our use case. Then, in lining, we saw it in the Lua API, but here, Lua
Jit already contains the macros, so we can use them, and I want to really like, hard with the
inlining, because I can, because I also wanted to have the functions real module, but in the
end, in the compiled code, I want everything to be in light, so most of the functions in the parsers
are in light. And then, yeah, I don't forget to use a profiler, and I saw a lot of the time
is spent like while resizing the tables, the Lua tables, and this happens before, because when I'm
parsing, I tell the initial size of the table, and then I parse the children, but there can be,
for example, like, 5,000 children, and I only allocate this space for three elements, so this means
I will have to reload from three, and probably double the value a lot of times, and it's
going to copy a lot of values. So, there is this branch buffer, which is just a way, which is just
a dynamic stack for these like temporary values. It's important that yeah, it is there for all
the recursion levels, because we parse up to 100 levels of recursion depth, and you still, of course,
need to copy the values from the buffer, but you don't really look anymore, so it helps.
And then, yeah, this is like the cherry on the top for white-specific other implementations,
such as representation, do some intrinsic, so there are two functions where it's proof to be useful,
might be more, but again, I'm lazy. So, yeah, for white-specific, when you are parsing commands,
you just need to find either the end of the line, or for multi-line commands, you need to find the
next star, asterisk, and for string, and you either need to find the matching quote, or there
can be escape characters, and then you go to the slow path. So, yeah, I just show the SSC
for version, which basically, like you set up the search set of the values I want to find,
and the improvement is like I scan through 16 values at once, so this primitive gives me the
index of the first match, or if I don't find a match, then I go to find the next 16 characters,
but it operates on 16 bytes at once, so it provides some speed-up, the same benchmark,
and our parser is faster. Now, we got like some, yeah, 33% improvement, but like,
which one of these optimizations was helpful, you might ask, or not, so I did some
ablations study, I disabled, yeah, the final version is the one that is published, I disabled
these optimizations, but one by one, and basically, you can see that probably all of them are in
some way helpful, and if you go to the SSC for inference, you even might get some small boost,
but the default version uses SSC too, because they are available on every x64 CPU.
And on the JSON parsing data set, this is important, we beat loss in the JSON, so out of the
known parser, that I knew at the time of making this, and still this should be the fastest
widget parser, and on 15 JSON is the same. So, we gain some speed-up, 50% speed-up, one jit is on,
but like one jit is off, which might be a real important for some platforms, we get more than 10 times
speed-up, so for these files, like parsing them, can take, yeah, instead of three seconds,
it can take 0.3 seconds, and on the JSON data set, we are faster, and much faster than the
other implementations. So, some tips at the end, try to combine these tricks, but you have to
measure them, use the profiler, minimize coping, and yeah, like focus on your files, if you are
writing a parser yourself, if your files are not using scientific numbers or escape characters,
then you can make the implementation slow, and you will save some time. So, there are also limitations,
yeah, like the only thing I like which we care about is the JSON parsing of the file for the
first time, but like it's very hard to measure the cold parsing time. So, in the end, we just take
this like proxy, a measurement, of course, it's a big limitation, and yeah, I had problems, like with some
unstable terraformant numbers, in the end, like loads of these tricks helped, but there are still
problems. If you run the benchmark yourself, you will probably get a bit different values,
even if you had the same CPU and system as me. So, I think that is, are we finished? This
slides would say no, but I say yes, because we still have JSON encoding, but it's really simple.
Our encoder happens to also be fast, but I never put any thoughts into the optimization. So,
thank you for bearing with me. Yeah, and if you have questions, then.
Now it's time for a question, if you have one.
Just a small question. So, for the assembly part, did you rely on compiler intrinsic, or did you use
like lupant authorization stuff? Oh, yes, I relied entirely on intrinsic, yeah, for example,
the SSE4 version I'm using the intrinsic here, no else like compiler options, or anything.
I'm not sure if it's relevant, but did you consider, did you had cases where you had
a chunk parsing that you had to parse it part, and then maybe wait on some data, and then
had to parse again. So, has three processing? Yeah, okay. In this case, in this case, no,
like you already need to have all the contents in the buffer, it would be an interesting optimization
in the cases where you are, yeah, it is something to look into, but no, this works only when everything
is already in memory.
Have you considered totally teaching the JSON part, and just writing your data in lupant file,
the RIT? Of course, there might be optimal format, more optimal format.
The problem is, like, this JSON files are there since the beginning, the code basis,
like, more than 10 years old. So, in the end, like, the format is not going away.
We might introduce something like jbm version 2, which might be more performant data format,
but, like, from, like, the relive, like, as if our respective, like, it would be hard to transition
the format. So, we're going to break the JSON.
Are there questions? So, it's look like we are done. Thank you again. Okay, thank you.