Hello everyone, thanks for coming.
In this talk, I will explain you how we improve the performance on some double-valor
operation maker by a lot with simple things.
So macroeal, if you don't know what it is, which is most people, it's a distributed source
control tool, like Git, same generation.
It's cut-base is in Python, C and Rust.
The cut-base is 20 years old, because the tool is 20 years old, and I'm a contributor
to it since 2010, and I'm now one of the maintenance of it.
So let's talk about data compression.
We're doing a fashion controls.
We have multiple version of the same file, and the most naivety-store, multiple version
of the same file, and it's to store multiple version of the same files as full text.
However, this is not very efficient in terms of space.
So one way to solve that is to use delta compression, where you store a full version of your
text initially, and then you compute a small difference, and you store a delta which
is just a small edit instruction to get the second version of the file for the first one.
Then you can do another delta that apply on the second one, and let's change of delta
that is going to have a pretty good compression.
However, if your chain of delta is endless, you're going to have a bad time when you try
to restore the content, because you have to do a lot of preparation to get there.
So there is way to solve that, like doing full snapshots of the content from time to time.
So you can still get a good compression, but you can also control the amount of time
and that I need to restore your content.
And of course, it's not as simple even for one chain, because it's distributed version
control.
So you have bunching, merging, and the version of your file are not just linear.
You have like, branches.
So you end up building more tree, where you have delta that applies.
Again, other delta, not necessarily linearly, so you have other question regarding memory
density and thing like that, but you have a better compression, good restoration time.
And you can get even more complicated, as you try to solve more and more problems.
Eventually, like right now, in my career, you have something where you have this full snapshots,
you have delta trees, and then we collapse some of the delta, but not full text.
And so we have also a tree of intermediate snapshots, and more delta tree on them, and it gets
complicated, and I'm not going to dive too much into the details of that.
It's worse here of like, computer science, academic paper, that we are actually working on.
So I'm not going to dive too much into that.
So material use delta encoding, and it does that on the fly.
So when you do a commit or when you receive revisions, you're going to do the delta encoding
at that time.
Which means that you don't need maintenance operation like feedback.
It's a important part of the material design, and how you get it to scale.
It can actually be very good compression for some content.
The nice case we like to show is like, we have a file that has so many versions that
all the full text would be one petabyte, and we can store them into like a bit less than
20 gigabyte, which is like 50,000 compression, which we are happy about.
And the nice thing with the delta is that the delta you computed on one repo, you can
basically exchange them as is for another repo that is going to be able to apply them
as is, and it's mostly the case, but it's not always the case, because sometimes you
have some delta that are going to be weird, because we are cliented them, sometimes
you don't take action to snapshot, and you also have server that are in our annoying mode
that are going to be compute everything to make sure that they have the base to rage, because
they don't really treasure the client.
And that can grow up to be a significant preference problem, because computing a delta
is kind of expensive, and so when you extend that, you can underpine the situation where
most of the time, you spend doing delta computation instead of actually like, it's
like something that out, but, and it takes a lot of time, because computing delta is slow,
and it's slow, because this thing is an older n-square kind of problem, so of course it's
like a conceptually slow, and it's a fundamental problem, so the solution to walk around
this fundamental problem of dipping is slow, that you have fancy ID, you can create
better delta chain, that is going to be better delta 3, that are going to be easier to
exchange, you can have a richer exchange so that the server and the client better collaborate
to create a good tree, and you can do a lot of refructuring and our deep computer science
is going to mean that you're going to do less dipping, and so you're going to have less
preference problem from dipping, so I did a bunch of that, and when you we walk the
tree, it means you have to re-compute the delta for a lot of things, and for huge
people, it can take like a couple of days, and it's kind of slow and annoying when you're
trying with a two-day feedback loop, and so I'm sitting there, and I start asking me a
question that I should ask myself a long time ago, like, why is dipping slow actually
in practice when I run it, so I can take a profiler and look at what is the
computer actually doing, and I realize that it's mostly doing decompression, because
the delta and the full-text on this are compressed, and we have a cache for not
tweeting the data over and over, but we don't have a cache for not decompressing
data over and over, to impractice we're doing the very same operation in loop over and
over, and that's kind of sealing, so there is simple solution from that, we had a small
LSU cache, and it's already significantly faster. After that, we realized that we spend
most of the time competing with Shawan, because in Miyakayal when you restore a content,
like you want to get the full version of a file, typically to write it on disk, but also
when you want to get a version of a file to defeat it again another file, they default your
compute it's Shawan, and it's not really useful here, because when you receive the delta
that you reuse as is, you're not checking the Shawan of the full-text at that time, you're
going to check the Shawan of the full-text when you actually restore it, and so why do you
check Shawan of content with an expensive operation, only a few percent of the time, it doesn't
give you any future compared to not doing it at all, so we can still do it when we do these
data computation, and it seems quite significantly, and the profile again showed a compression,
because when we wrote that, we forgot to cache the data we've write on disk, so when we
receive a delta, and it's good, we've got it on disk, and then we add to, like we compress it,
we've got it on disk, and then we add to we did it from this, they compress it and put it in the cache,
which is kind of silly, so we think that too, and at that point, I finally see the different part
in my profile, already speeding up by a few x solving very simple thing, and we can now ask
ourselves the question, do you think the differing is because the algorithm is elsewhere,
or do you think it's because the differing code has been written in 2005, and it's just doing
everything manually, or you think there is more low-ungined fit, like if you think this is the algorithm
raise your end, okay, if you think this is the secret raise your end, if you people, if you're
long in fit, more people, okay, congratulations, you're right, surprisingly,
when we do use the differing, we have to get the text we want to this, then there is an optimization
that's fine, the common part, without doing differing, like at the beginning, in certain things,
and then we do that real differing on the, on the part, we know is different,
typically we do memory comparison to detect the common prefix, and after that we have to
ash lines so that we can do actual differing algorithm, and so if you do simple memory
comparison for the prefix, you keep a lot of line-hashing and you simplify the size of the
differing algorithm, and it's good, so for a long time, we have been doing
prefix comparison to speed things up, but we have never done prefix comparison before, so you can
just take the cut for the prefix check, and you put it for also the prefix check, and again,
you have a pretty significant speed up, because you are just doing the same thing over, so at that
point, depending on the workload that we are, I kind of already five time faster for, like,
ingesting data where we compute the diff, and we really didn't do anything fancy, like,
all the parts are super simple, because either you do less work, that you didn't need to do,
or you do work that you already did elsewhere, and it's, you have a performance gain,
we didn't change the language used to implement anything, we didn't actually use any of the
fancy AD, because the five X is on the older version, like, without the fancy AD, and we didn't
add to refactor or anything round or change anything in terms of active architecture, and yet,
we save, like, 80% at the time already, so it's kind of these are pointing in the match of
mass, against just looking at what is going on in practice, and not doing stupid things.
So, now, the diff code is taking the most of the time, and that diff code is secured from canal
developers, so it's probably good in terms of efficiency when it was written, but it was written
20 years ago. It does everything manually, because it doesn't have any dependency that we,
it doesn't use any optimized work from anyone, it doesn't have sweat safety, because it's in
C, it's not really relevant for performance right now, but it's definitely useful for other stuff,
and it's looping over things by, by, by and thing like that. So, I just move that piece of code
to rest, I used an existing diffing library, because I didn't want to sing too hard about
diffing for now. The comparison for the prefix and suffix, I can write normal code, and it's
going to be turned into SIM decode when you compare it from rest or dramatically, like, I don't
actually call SIMD myself, I just say, conferred this thing blog by blog, and rest is going to do
to do the writing. I get sweat safety in the process, and in practice just doing that is giving
me a preference boost and the dipping part, between 1.5 and 5x, just because mostly just because
the SIMD and more efficient generation from rest. I'm not even sure the dipping library is that
smart and that preference, but at that point it's not really the main part of why we're spending
time in the dipping. At that point, we move from this to this, where, getting the text, and then
I truly working the memory is most of the time. So, let's think a bit about what happens,
like, let's open the box about getting the text. So, I talked about before the fact that we have
the full text and then a list of delta. If you were to just take the full text, apply the first
it to get another full text and then apply the other delta to get another full text. It would be
quite inefficient, where you could be memory over and over and think like that. So, we don't do that
in reality all the time. We do something like delta folding and we do it in 2x2 because it seems
a problem. So, we take this to patch just by looking at the metadata, we get a bigger patch and
2x2 and kill, we just have a large patch that we have to apply to the full text and that's more efficient.
And our efficient is that's called actually, but just looking a bit at what is happening
with it. We rely that we can be a bit more efficient by pre-processing the delta before doing the
processing because we get more like if we gather the metadata together, we have a better memory
locality, we skip random access. And then when we have this tree of things that we
merge together over and over, we can pre-size the vector so that we know we have that much element
on one side and that much element on the other side and so we have a ballpark estimator, our
big is going to be the result. So, instead of starting with a small vector, we can pre-size the
vector or to avoid the cost of residing it over and over. And we can limit allocation by using the
delta that we know your needs to build the vector from the delta we know your needs to build the
new ones. Like, there is nothing fancy in it. Like, this is kind of basics, performance stuff,
you would get from any compound things, but they were not done in the initial code. And part of
that is, when someone we've got parts of material in rest, usually just rewarding it in rest,
make it significantly faster and so they stop there. But at some point, we could go back and
look at what they did and actually realize that there is a bunch of long-infits for optimization
that go there. So, doing this, the delta folding is going to be significantly faster.
So, we are really now in the deep thing. Like, we have a full text, we need to find the
command part and we need to compute the deep from it. So, let's look back at the delta chain.
In practice, when you have two content, the content A and the content B, there is a good chance
that they share a common part in their delta chain because in practice, the delta chain
are like, which people unreads a delta long. And so, we can look at, oh, there is a lot of things
in common and the small things that are exclusive to A and the small things that are exclusive to B.
And we know how to fold things, so, instead of folding everything on each side, we can do
these kind of things where we have a delta for all the command parts, a delta for all the
exclusive part of A and the Italy's part of B. Just using tool, we already have and we already use.
This means that after that, we can see what it would take like the full text exist.
But we have a delta for A, we just made that out about when it stopped touching the base
and made that out about when it stopped touching the base. And the same for B. And so, we can
know in the full text, in the base full text, more the common part, when we're going to start
touching it and when we're going to stop touching it, which means that we know without having to look at
a memory or whatever, that this part is the same. And this part is the same. And they could
put, we could probably find part that are the same in the middle, but there is some ambiguity in the
diff, and so, let's not get into that now. We're just doing the same thing, but.
So, looking a bit at the data we have, we can find the command section just walking on the
middle and now from the delta themselves. So, we could be less memory, because we don't need to
be the memory of the common parts. And we walk less memory, because we don't need to walk that
memory to realize that it's the same. We already know it. And another important part is that the
section we are going to run the wall algorithm on and the wall dipping on is significantly smaller.
And being significantly smaller means that it is significantly more cash friendly and more efficient
overall. There is something that I didn't say so far. Most of the time we spend
consulting delta in order to provide, I was looking at, is about the material of manifest.
The material of the manifest is equivalent to git trees. It store the state of a revision for
every commit. But it's done as a list of full paths and the ash for the version of that file.
It's not a recursive tree of the directories. It's just the full list of every file in the revision.
So, it's significantly bigger, because if you have 1 million file in your commit, then you
will have 1 million file in the manifest. It has some advantage to have a flat structure and some
disadvantage, like you have a 100 megabyte of things to deal with when you do all this computation
and all this restoration. However, it has different properties than just generic
dipping that we were doing so far. So, all the work we did so far, benefit everything. Even if
it's the manifest, it's the files, even if it's pretty much all-strong, we still. However,
the manifest is quite quite different. It's a short list of unique item, which means that
we can have, there is a lot of files and the delta actually small, because people, if you have
a million files, people don't do commit that commit long files all the time. They only touch
maybe 3, maybe 10, maybe 100, even 100 file, it's not that much. Even the 1,000 for 1 million,
it's small. It's a small element. It's this kind of pattern, like last content and small delta,
apply to others to not just the material manifest. We see this in config file and packaging
definition, so having better performance here helps a bit more people. But we're going to
focus on the specific manifest here. Because it's a short at least, we don't need to do the
generic end square dipping when we do thing. We can just walk the thing in order and as a
you see something on one side and not on the other or you see something different. You can just
walk your content and you have a diff that is much simpler to produce. At that point, specializing
the manifest code is more efficient. We have the linear time dipping. The common part that we see
when we look at the metadata are unambiguous, because there is no, something will be before or after,
there is no ambiguity about that. So we can leverage the common parts that we detect from
the metadata even more. Which means that we don't need to restore content to run generic diff.
We can just look at the individual delta directly and have a zero-copy dipping except for producing
the delta. At that point, the delta computation that was the majority of the time when you
do a pro that goes wrong is now a small part of the pro. It's still sharp in the profile,
but there are a lot of other things like opening files, the Python logic that drives all the
delta's writing that I'm disk. And spinning that further is not going to give
large speed up. All these things, I already know that there is silly things
and long-interest that we could do and also more advanced things we could do to speed them up.
But it's not what I'm here for. It's more okay, delta computation seems to be a solved problem.
And when I see a solved problem is, if I take a quite extreme case of pulling 1,000 revisions
in a modular repo with the old code and the best case scenario where you can reuse as many
delta as you can. I mean, we move from about 8 minutes to about 2 minutes, which is
over you for x on the top level operation. And if we're in the paranoid case where you want to
recompute absolutely everything, we were about 4 hours before and we're still about 2 minutes now,
which is 1 under a time faster. Basically, the problem is no longer really a problem,
especially if you look at the fact that all the, if you look at this number, which is a bit less
than 2 minutes. And this number, which is a bit more than 2 minutes, you see that there is
pretty much no difference. We're computing absolutely all delta and it's not 1,000 delta. It's
1,000 delta for the manifest and 1,000 and there is file, so there is more than 1,000 delta
to compute over all. And the delta is like kind of no longer in the picture anyway. That's why
also could develop in the profile at that point. It doesn't mean that we could not do the delta
faster. The way we fold them, we already know we could have more efficient algorithm. The way
we start the delta and disk, we know the format is not ideal. And we know we could optimize the
common part a bit more for not just doing the prefix and the sticks. There is a lot of things
we could do more, but it really doesn't matter anymore in terms of how do I improve the
performance of that specific operation right now. So if we take a bit of a step back on what
happens here, we did just a lot of small things that are not that advanced. We are very doing use
this work. We made the machine app by doing things like memory locality, fewer allocation.
We looked a bit at the data structure we add to leverage them by looking at the data to detect
the common part. It's not we didn't invent a new data structure or a new algorithm. Like we already
add that it's basically a few line on code to start at the beginning of the first one and
the beginning of the end one and that's it. And yet we still have a lot of things we could keep
improving over time. That the whole thing is not really concerned because the top level operation
is one over time faster, but it's one over time faster because the delta computation dot
about 500 times faster in that area, which is if it was a problem now and it took 500 times more
before you would kind of not really be able to run it because if it was taking one hour or now
it would mean it would take like 20 day before and would be in practical and practical to do at all.
And this all started by all we should do fancy stuff to avoid this costly operation because
this costly operation is inherently complicated because the math say it's in square, so if it's
slow it's because the math say it's in square, right? But no, it wasn't.
So like just doing basic profiling to understand if thing like what is actually happening,
doing tracing to see how many of some operation you do, like if things trigger when they should
not and this kind of things, challenging the work that everything do. It walks for all this,
that earlier as this means we've sped up a G committee by about 10% because we realized that
we were computing the shy one of something and then checking that this content at the
shy one we just computed because we can't 20 years of development, the code grew organically
and there is this kind of stupid thing that can emerge. Thinking a bit about your data can
give quick speed up as we see with detecting common parts from the data structure.
And you do that for your code, but you should probably do that for your dependency too,
like you're calling a library and the code to that library takes times, maybe it's what
it's worth looking at why is this library called text time instead of trying to work around it.
It walks also for the links canal, reading data from this is slow and so maybe you do it
but is it slow because reading data from this is inherently slow or is it because you're
having a lot of page fault and therefore you do all the friendships of the channel because you
didn't warm your and map properly or because you're doing committee reads and think like that.
There's a bunch of case where you think that oh this is just a canal being slow or the
this being slow and actually know like look at what is actually happening before doing things.
And the last interesting lesson I think is that code ages. You could have code that has been
carefully written by smart people a long time ago but the hardware change, the programming language
change, the usage change and so something that was efficient 20 years ago might not be
efficient today doesn't use some of the new optimization and think like that so even if something
was good in the past maybe it's not good now and during during this whole talk I said that
Diffing is an end square algorithm and therefore it's slow and this was true in 2005 but
it's longer the case like in 2015 someone came up with linear algorithm for Diffing that would
be faster would allow us to have a different structure and model for delta that would be even
more efficient and it's been that even the mathematics that we work on can be a box and sometimes
things move in that area too and of course I'm not saying that if you're currently slow you should
get go get a PhD in computer science to make it faster but there are people where the PhD in
computer science and there are making things faster and so you can check what they're doing
from time to time and sometimes you can speak to them and they will have good idea about your problems
so thank you for coming to MacLeod I hope it was useful for you and if you have any questions
don't hesitate to ask them
Thank you for the talk Life I have one question about the delta because in your graph
you had your your starting point you have your small delta and then you put all together and
so in a really convenient to go to the tip of your branch but if you want to go in the middle of
your branch to just look at the history obviously your big delta you have to apply just a subset of it
you mean that yeah it was about that the big drop now after that
I was seeing about the big yellow drop the big yellow drop
number one yeah okay and so watch your questions so here if you want to go if you want to
check out to A it's simple you apply C and A but if you want to go to somewhere inside C how you
do this oh so there's not about checking out the content there could be more of the things before
and like if you have a chain like if I want to get this content I need to apply this delta and this
but if I want to get this content I just need to apply this chain to this and so forth
here the point is that you have two arbitrary revisions that have something in common
and you can come to a difference between these two revisions efficiently with that without adding
to restore the full content of them that makes sense yes but the big drop the C big drop so
that's not yeah it's big thing yes what I understand it's like a really big patch that you can
apply to the red part yes and so if you want to apply a subset of this thing because you want to go somewhere
in the history yeah the way it works is that since we know which part A and B are going to touch
we don't need to restore the full text and then just take that part we can just take a small part of it
no yeah okay okay I think other questions okay then thank you for your talk
you