From: Junio C Hamano <hidden> Date: 2016-06-15 22:45:19
Linus Torvalds [off-list ref] writes:
Interestingly, it turns out that git also hits a sad performance downside
of using zlib.
We always tend to set "stream.avail_out" to the exact size of the expected
output. And it turns out that that means that the fast-path case of
inffast.c doesn't trigger as often as it could. This (idiotic) patch
actually seems to help performance on git rev-list by about 5%.
But maybe it's just me seeing things. But I did this because of the entry
assumptions in inflate_fast(), that code only triggers for the case of
strm->avail_out >= 258.
Sad, if true.
This is reproducible "rev-list --objects --all" in my copy of the kernel
repo takes around 47-48 seconds user time, and with the (idiotic) patch it
is cut down to 41-42 seconds.
(with patch)
41.41user 0.51system 0:41.93elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+134411minor)pagefaults 0swaps
(without patch)
47.21user 0.64system 0:47.85elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+134935minor)pagefaults 0swaps
One funny thing about your patch is that it also reduces the number of
minor faults; I would have expected that the additional memory wastage
(even though most of the allocated object buffer memory would be freed
immediately as soon as the caller is done with it) would result in larger
number of faults, not smaller, which is puzzling.
This is reproducible "rev-list --objects --all" in my copy of the kernel
repo takes around 47-48 seconds user time, and with the (idiotic) patch it
is cut down to 41-42 seconds.
So I had forgotten about that patch since nobody reacted to it.
I think the patch is wrong, please don't apply it, even though it does
help performance.
The reason?
Right now we depend on "avail_out" also making zlib understand to stop
looking at the input stream. Sad, but true - we don't know or care about
the compressed size of the object, only the uncompressed size. So in
unpack_compressed_entry(), we simply set the output length, and expect
zlib to stop when it's sufficient.
Which it does - but the patch kind of violates that whole design.
Now, it so happens that things seem to work, probably because the zlib
format does have enough synchronization in it to not try to continue past
the end _anyway_, but I think this makes the patch be of debatable value.
I'm starting to hate zlib. I actually spent almost a week trying to clean
up the zlib source code and make it something that gcc can compile into
clean code, but the fact is, zlib isn't amenable to that. The whole "shift
<n> bits in from the buffer" approach means that there is no way to make
zlib generate good code unless you are an insanely competent assembly
hacker or have tons of registers to keep all the temporaries live in.
Now, I still do think that all my reasons for choosing zlib were pretty
solid (it's a well-tested piece of code and it is _everywhere_ and easy to
use), but boy do I wish there had been alternatives.
Linus
From: Jon Smirl <hidden> Date: 2016-06-15 22:45:19
On 9/6/08, Linus Torvalds [off-list ref] wrote:
I'm starting to hate zlib. I actually spent almost a week trying to clean
up the zlib source code and make it something that gcc can compile into
clean code, but the fact is, zlib isn't amenable to that. The whole "shift
<n> bits in from the buffer" approach means that there is no way to make
zlib generate good code unless you are an insanely competent assembly
hacker or have tons of registers to keep all the temporaries live in.
Now, I still do think that all my reasons for choosing zlib were pretty
solid (it's a well-tested piece of code and it is _everywhere_ and easy to
use), but boy do I wish there had been alternatives.
Some alternative algorithms are here...
http://cs.fit.edu/~mmahoney/compression
It is possible to beat zlib by 2x at the cost of CPU time and memory.
Of course switching to these algorithms would involve a lot of testing
and benchmarking. I'm also not sure how PAQ would fare on lots of
small git objects instead of large files.
Turning a 500MB packfile into a 250MB has lots of advantages in IO
reduction so it is worth some CPU/memory to create it.
You can even win 50'000€ for a better algorithm.
http://prize.hutter1.net/
--
Jon Smirl
jonsmirl@gmail.com
Jon, you're missing the point.
The problem with zlib isn't that it doesn't compress well. It's that it's
too _SLOW_.
Turning a 500MB packfile into a 250MB has lots of advantages in IO
reduction so it is worth some CPU/memory to create it.
..and secondly, there's no way you'll find a compressor that comes even
close to being twice as good. 10% better yes - but then generally much
MUCH slower.
Take a look at that web page you quote, and then sort things by
decompression speed. THAT is the issue.
And no, LZO isn't even on that list. I haven't tested it, but looking at
the code, I do think LZO can be fast exactly because it seems to be
byte-based rather than bit-based, so I'd not be surprised if the claims
for its uncompression speed are true.
The constant bit-shifting/masking/extraction kills zlib performance (and
please realize that zlib is at the TOP of the list when looking at the
thing you pointed to - that silly site seems to not care about compressor
speed at all, _only_ about size). So "kills" is a relative measure, but
really - we're looking for _faster_ algorithms, not slower ones!
Linus
From: Jon Smirl <hidden> Date: 2016-06-15 22:45:19
On 9/6/08, Linus Torvalds [off-list ref] wrote:
On Sat, 6 Sep 2008, Jon Smirl wrote:
>
> Some alternative algorithms are here...
> http://cs.fit.edu/~mmahoney/compression
> It is possible to beat zlib by 2x at the cost of CPU time and memory.
Jon, you're missing the point.
The problem with zlib isn't that it doesn't compress well. It's that it's
too _SLOW_.
When I was playing with those giant Mozilla packs speed of zlib wasn't
a big problem. Number one problem was the repack process exceeding 3GB
which forced me to get 64b hardware and 8GB of memory. If you start
swapping in a repack, kill it, it will probably take a month to
finish.
I'm forgetting the numbers now but on a quad core machine (with git
changes to use all cores) and 8GB I believe I was able to repack the
Mozilla repo in under an hour. At that point I believe I was being
limited by disk IO.
Size and speed are not unrelated. Buy reducing the pack size in half
you reduce the IO and memory demands (cache misses) a lot. For example
if we went to no compression we'd be killed by memory and IO
consumption. It's not obvious to me what's the best trade off for git
without trying several compression algorithms and comparing. They were
feeding 100MB into PAQ on that site, I don't know what PAQ would do
with a bunch of 2K objects.
Most delta chains in the Mozilla data were easy to process. There was
a single 2000 delta chain that consumed 15% of the total CPU time to
process. Something causes performance to fall apart on really long
chains.
> Turning a 500MB packfile into a 250MB has lots of advantages in IO
> reduction so it is worth some CPU/memory to create it.
..and secondly, there's no way you'll find a compressor that comes even
close to being twice as good. 10% better yes - but then generally much
MUCH slower.
Take a look at that web page you quote, and then sort things by
decompression speed. THAT is the issue.
And no, LZO isn't even on that list. I haven't tested it, but looking at
the code, I do think LZO can be fast exactly because it seems to be
byte-based rather than bit-based, so I'd not be surprised if the claims
for its uncompression speed are true.
The constant bit-shifting/masking/extraction kills zlib performance (and
please realize that zlib is at the TOP of the list when looking at the
thing you pointed to - that silly site seems to not care about compressor
speed at all, _only_ about size). So "kills" is a relative measure, but
really - we're looking for _faster_ algorithms, not slower ones!
Linus
When I was playing with those giant Mozilla packs speed of zlib wasn't
a big problem. Number one problem was the repack process exceeding 3GB
which forced me to get 64b hardware and 8GB of memory. If you start
swapping in a repack, kill it, it will probably take a month to
finish.
.. and you'd make things much much WORSE?
Size and speed are not unrelated.
Jon, go away.
Go and _look_ at those damn numbers you tried to point me to.
Those "better" compression models you pointed at are not only hundreds of
times slower than zlib, they take hundreds of times more memory too!
Yes, size and speed are definitely not unrelated. And in this situation,
when it comes to compression algorithms, the relationship is _very_ clear:
- better compression takes more memory and is slower
Really. You're trying to argue for something, but you don't seem to
realize that you argue _against_ the thing you think you are arguing for.
Linus
From: Mike Hommey <hidden> Date: 2016-06-15 22:45:19
On Sat, Sep 06, 2008 at 06:46:29PM -0700, Linus Torvalds wrote:
On Sat, 6 Sep 2008, Junio C Hamano wrote:
quoted
This is reproducible "rev-list --objects --all" in my copy of the kernel
repo takes around 47-48 seconds user time, and with the (idiotic) patch it
is cut down to 41-42 seconds.
So I had forgotten about that patch since nobody reacted to it.
I think the patch is wrong, please don't apply it, even though it does
help performance.
The reason?
Right now we depend on "avail_out" also making zlib understand to stop
looking at the input stream. Sad, but true - we don't know or care about
the compressed size of the object, only the uncompressed size. So in
unpack_compressed_entry(), we simply set the output length, and expect
zlib to stop when it's sufficient.
Which it does - but the patch kind of violates that whole design.
Now, it so happens that things seem to work, probably because the zlib
format does have enough synchronization in it to not try to continue past
the end _anyway_, but I think this makes the patch be of debatable value.
I'm starting to hate zlib. I actually spent almost a week trying to clean
up the zlib source code and make it something that gcc can compile into
clean code, but the fact is, zlib isn't amenable to that. The whole "shift
<n> bits in from the buffer" approach means that there is no way to make
zlib generate good code unless you are an insanely competent assembly
hacker or have tons of registers to keep all the temporaries live in.
Now, I still do think that all my reasons for choosing zlib were pretty
solid (it's a well-tested piece of code and it is _everywhere_ and easy to
use), but boy do I wish there had been alternatives.
I know at least 7-zip has its own gzip compression/decompression code
(though it's C++). Maybe some other tools have theirs too.
Anyways, if it can make a speed difference, it might be worth having a
minimalist custom gzip compression/decompression "library" embedded
withing git.
Mike
From: Andreas Ericsson <hidden> Date: 2016-06-15 22:45:19
Linus Torvalds wrote:
Take a look at that web page you quote, and then sort things by
decompression speed. THAT is the issue.
And no, LZO isn't even on that list. I haven't tested it, but looking at
the code, I do think LZO can be fast exactly because it seems to be
byte-based rather than bit-based, so I'd not be surprised if the claims
for its uncompression speed are true.
Some lzo vs zlib benchmark figures (for git) are available here:
http://www.gelato.unsw.edu.au/archives/git/0504/1700.html
LZO also ships their "minilzo.[ch]" fileset for easy inclusion in other
projects. I've used it a couple of times with decent results.
As for testing, both have been thoroughly vetted by NASA. LZO is used for
communication with satellites and that spacestation thing they had some
time ago, while zlib is being used for sending data back from Hubble and
other large data gatherers.
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
From: Jon Smirl <hidden> Date: 2016-06-15 22:45:19
On 9/7/08, Linus Torvalds [off-list ref] wrote:
On Sat, 6 Sep 2008, Jon Smirl wrote:
>
quoted
When I was playing with those giant Mozilla packs speed of zlib wasn't
> a big problem. Number one problem was the repack process exceeding 3GB
> which forced me to get 64b hardware and 8GB of memory. If you start
> swapping in a repack, kill it, it will probably take a month to
> finish.
.. and you'd make things much much WORSE?
My observations on the Mozilla packs indicated that the problems were
elsewhere in git, not in the decompression algorithms. Why does a
single 2000 delta chain take 15% of the entire pack time? Something
isn't right when long chains are processed which triggers far more
decompressions than needed.
> Size and speed are not unrelated.
Jon, go away.
Go and _look_ at those damn numbers you tried to point me to.
Those "better" compression models you pointed at are not only hundreds of
times slower than zlib, they take hundreds of times more memory too!
Yes, size and speed are definitely not unrelated. And in this situation,
when it comes to compression algorithms, the relationship is _very_ clear:
- better compression takes more memory and is slower
Really. You're trying to argue for something, but you don't seem to
realize that you argue _against_ the thing you think you are arguing for.
Linus
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:45:19
On Sun, 7 Sep 2008, Jon Smirl wrote:
On 9/7/08, Linus Torvalds [off-list ref] wrote:
quoted
On Sat, 6 Sep 2008, Jon Smirl wrote:
>
quoted
When I was playing with those giant Mozilla packs speed of zlib wasn't
> a big problem. Number one problem was the repack process exceeding 3GB
> which forced me to get 64b hardware and 8GB of memory. If you start
> swapping in a repack, kill it, it will probably take a month to
> finish.
.. and you'd make things much much WORSE?
My observations on the Mozilla packs indicated that the problems were
elsewhere in git, not in the decompression algorithms. Why does a
single 2000 delta chain take 15% of the entire pack time? Something
isn't right when long chains are processed which triggers far more
decompressions than needed.
Please have a look at commit eac12e2d4d7f. This fix improved things for
my gcc repack tests.
Nicolas
From: Jon Smirl <hidden> Date: 2016-06-15 22:45:19
On 9/7/08, Nicolas Pitre [off-list ref] wrote:
On Sun, 7 Sep 2008, Jon Smirl wrote:
> On 9/7/08, Linus Torvalds [off-list ref] wrote:
> >
> >
> > On Sat, 6 Sep 2008, Jon Smirl wrote:
> > >
> >
> > > When I was playing with those giant Mozilla packs speed of zlib wasn't
> > > a big problem. Number one problem was the repack process exceeding 3GB
> > > which forced me to get 64b hardware and 8GB of memory. If you start
> > > swapping in a repack, kill it, it will probably take a month to
> > > finish.
> >
> >
> > .. and you'd make things much much WORSE?
>
> My observations on the Mozilla packs indicated that the problems were
> elsewhere in git, not in the decompression algorithms. Why does a
> single 2000 delta chain take 15% of the entire pack time? Something
> isn't right when long chains are processed which triggers far more
> decompressions than needed.
Please have a look at commit eac12e2d4d7f. This fix improved things for
my gcc repack tests.
Do you have any test numbers for something like a 2000 delta chain
before and after?
You can get to Mozilla CVS with rsync.
https://wiki.mozilla.org/How_to_Create_a_CVS_Mirror
I think it was the master Mozilla makefile with the 2000 deltas.
The whole repo is 15GB so you probably just want the Makefile,v
There's no point in working with Mozilla except for testing purposes
since they went with Mercurial and abandoned their history.
--
Jon Smirl
jonsmirl@gmail.com
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:45:19
On Sun, 7 Sep 2008, Jon Smirl wrote:
On 9/7/08, Nicolas Pitre [off-list ref] wrote:
quoted
Please have a look at commit eac12e2d4d7f. This fix improved things for
my gcc repack tests.
Do you have any test numbers for something like a 2000 delta chain
before and after?
What kind of number do you want?
Before that change I wasn't able to repack an already tightly packed
(about 340MB) gcc repository on my machine while the same but sparsely
packed (3GB or so) repository could be repacked just fine.
You can get to Mozilla CVS with rsync.
https://wiki.mozilla.org/How_to_Create_a_CVS_Mirror
I think it was the master Mozilla makefile with the 2000 deltas.
The whole repo is 15GB so you probably just want the Makefile,v
I have a test Mozilla repo dating back to the time you were playing with
it too (I think). Its directory date is 2007-04-12. It was quite
tightly packed already, but I just ran a "git repack -a -d -f
--window=100 --depth=2000" on it and now have a 380MB pack file for it.
Nicolas
From: Jon Smirl <hidden> Date: 2016-06-15 22:45:19
On 9/8/08, Nicolas Pitre [off-list ref] wrote:
On Sun, 7 Sep 2008, Jon Smirl wrote:
> On 9/7/08, Nicolas Pitre [off-list ref] wrote:
quoted
quoted
Please have a look at commit eac12e2d4d7f. This fix improved things for
> > my gcc repack tests.
>
> Do you have any test numbers for something like a 2000 delta chain
> before and after?
What kind of number do you want?
See if repacking a 2000 chain delta still takes 30 minutes. It can be
any 2000 chain delta.
Before that change I wasn't able to repack an already tightly packed
(about 340MB) gcc repository on my machine while the same but sparsely
packed (3GB or so) repository could be repacked just fine.
> You can get to Mozilla CVS with rsync.
> https://wiki.mozilla.org/How_to_Create_a_CVS_Mirror
> I think it was the master Mozilla makefile with the 2000 deltas.
> The whole repo is 15GB so you probably just want the Makefile,v
I have a test Mozilla repo dating back to the time you were playing with
it too (I think). Its directory date is 2007-04-12. It was quite
tightly packed already, but I just ran a "git repack -a -d -f
--window=100 --depth=2000" on it and now have a 380MB pack file for it.
Nicolas
From: Jon Smirl <hidden> Date: 2016-06-15 22:45:19
On 9/8/08, Jon Smirl [off-list ref] wrote:
On 9/8/08, Nicolas Pitre [off-list ref] wrote:
> On Sun, 7 Sep 2008, Jon Smirl wrote:
>
> > On 9/7/08, Nicolas Pitre [off-list ref] wrote:
>
> > > Please have a look at commit eac12e2d4d7f. This fix improved things for
> > > my gcc repack tests.
> >
> > Do you have any test numbers for something like a 2000 delta chain
> > before and after?
>
>
> What kind of number do you want?
See if repacking a 2000 chain delta still takes 30 minutes. It can be
any 2000 chain delta.
Time for repacking a 2000 chain delta would be a good thing to monitor
as part of the testing process. It amplifies any small performance
problems and makes them obvious.
--
Jon Smirl
jonsmirl@gmail.com