Decompression speed: zip vs lzo

I have created a big tar from linux tree:

linux-2.6.tar   300,0 MB

Then I have created to compressed files with zip and lzop utility (the latter uses the lzo compression algorithm):

linux-2.6.zip  70,1 MB

linux-2.6.tar.lzo  108,0 MB

Then I have tested the decompression speed:

$ time unzip -p linux-2.6.zip > /dev/null 3.95user 0.09system 0:04.05elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+189minor)pagefaults 0swaps

$ time lzop -d -c linux-2.6.tar.lzo > /dev/null 2.10user 0.07system 0:02.18elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+234minor)pagefaults 0swaps

So bottom line is that lzo decompression speed is almost the double of zip.

Marco

P.S: Compression size is better for zip but a more realistic test would be to try with a delta packaged repo instead of a simple tar of source files. Because delta packaged is already compressed in his way perhaps difference in final file sizes is smaller.

"Marco Costalba" <mcostalba@gmail.com> writes:

Note that the space nor time performance of compressing and uncompressing a single huge blob is not as interesting in the context of git as compressing/uncompressing millions of small pieces whose total size is comparable to the specimen of "huge single blob" experiment. Obviously loose object files are compressed individually, and packfile contents are also individually and independently compressed. Set-up cost for individual invocation of compression and uncompression on smaller data matters a lot more than an experiment on compressing and uncompressiong a single huge blob (this applies to both time and space).

Junio C Hamano wrote:

Yes - and lzo will almost certainly win on all those counts!

I think to go forward this would need a prototype and benchmark figures for things like "annotate" and "fsck --full" - but bear in mind it would be a long road to follow-up to completion, as repository compatibility would need to be a primary concern and this essentially would create a new pack type AND a new *object* type. Not only that, but currently there is no header in the objects on disk which can be used to detect a gzip vs. an lzop stream. Not really worth it IMHO - gzip is already fast enough on even the most modern processor these days.

Sam.

Hi,

On Thu, 10 Jan 2008, Sam Vilain wrote:

No new object type. Why should it? But it has to have a config variable which says what type of packs/loose objects it has (and you will not be able to mix them).

I agree that gzip is already fast enough.

However, pack v4 had more goodies than just being faster; it also promised to have smaller packs. And pack v4 would need to have the same infrastructure of repacking if the client does not understand v4 packs.

Ciao, Dscho

Johannes Schindelin wrote:

I meant loose object. However this is configured, it affects things like HTTP push/pull. Configuring like that would be a bit too fragile for my tastes.

Ineed - I think it would be a lot easier to implement if it didn't bother with loose objects. It can just be a new pack version with more compression formats. For when you know you're going to be doing a lot of analysis you'd already run "git-repack -a -f" to shorten the deltas, so this might be a useful option for some - but again I'd want to see figures first.

I do really like LZOP as far as compression algorithms go. It seems a lot faster for not a huge loss in ratio.

Sam.

Sam Vilain wrote:

Coincidentally, I read this today on an algorithm (LZMA - same as 7zip) which is very slow to compress, high ratio but quick decompression:

  http://use.perl.org/~acme/journal/35330

Which sounds excellent for squeezing those "archive packs" into even more ridiculously tiny spaces.

Samn.

On Thu, Jan 10, 2008 at 07:02:39AM +0000, Sam Vilain wrote:

Well, lzma is excellent for *big* chunks of data, but not that impressive for small files:

$ ll git.c git.c.gz git.c.lzma git.c.lzop -rw-r--r-- 1 madcoder madcoder 12915 2008-01-09 13:47 git.c -rw-r--r-- 1 madcoder madcoder 4225 2008-01-10 10:00 git.c.gz -rw-r--r-- 1 madcoder madcoder 4094 2008-01-10 10:00 git.c.lzma -rw-r--r-- 1 madcoder madcoder 5068 2008-01-10 09:59 git.c.lzop

And lzma performs really bad if you have few memory available. The "big" secret of lzma is that it basically works with a huge window to check for repetitive data, and even decompression needs quite a fair amount of memory, making it a really bad choice for git IMNSHO.

Though I don't agree with you (and some others) about the fact that gzip is fast enough. It's clearly a bottleneck in many log related commands where you would expect it to be rather IO bound than CPU bound. LZO seems like a fairer choice, especially since what it makes gain is basically the compression of the biggest blobs, aka the delta chains heads. It's really unclear to me if we really gain in compressing the deltas, trees, and other smallish informations.

And when it comes to times, for a big file enough to give numbers, here are the
decompression times (best of 10 runs, smaller is better, second number is the
size of the packed data, original data was 7.8Mo):
  * lzma: 0.374s (2.2Mo)
  * gzip: 0.127s (2.9Mo)
  * lzop: 0.053s (3.2Mo)

For a 300k original file:
  * lzma: 0.022s (124Ko)
  * gzip: 0.008s (144Ko)
  * lzop: 0.004s (156Ko) /* most of the samples were actually 0.005 */

What is obvious to me is that lzop seems to take 10% more space than gzip, while being around 1.5 to 2 times faster. Of course this is very sketchy and a real test with git will be better.

On Thu, 10 Jan 2008, Pierre Habouzit wrote:

This is really the big point here. Git uses _lots_ of *small* objects, usually much smaller than 12KB. For example, my copy of the gcc repository has an average of 270 _bytes_ per compressed object, and objects must be individually compressed.

Performance with really small objects should be the basis for any Git compression algorithm comparison.

The delta heads, though, are far from being the most frequently accessed objects. First they're clearly in minority, and often cached in the delta base cache.

Remember that delta objects represent the vast majority of all objects. For example, my kernel repo currently has 555015 delta objects out of 677073 objects, or 82% of the total. There is actually only 25869 non deltified blob objects which are likely to be the larger objects, but they represent only 4% of the total.

But just let's try not compressing delta objects so to check your assertion with the following hack:

On Thu, 10 Jan 2008, Nicolas Pitre wrote:

It's probably worth doing those statistics on some other projects.

The kernel has for the last five+ years very much encouraged people to make series of small changes, so I would not be surprised if it turns out that the deltas for the kernel are smaller than average, if only because the whole development process has encouraged people to send in a series of ten patches rather than a single larger one.

And there are basically *no* generated files in the kernel source repo.

Maybe the difference to other repositories isn't huge, and maybe the kernel *is* a good test-case, but I just wouldn't take that for granted.

Yes, delta's are bound to compress much less well than non-deltas, and especially for tree objects (which is a large chunk of them) they probably compress even less (because a big part of the delta is actually just the SHA1 changes), but if it's 11% on the kernel, it could easily be 25% on something else.

Try with the gcc repo, especially the one that has deep delta chains (so it has even *more* deltas in relation to full objects than the kernel has)

		Linus

On Thu, 10 Jan 2008, Linus Torvalds wrote:

Obviously.

This was a really crud test, and my initial goal was to quickly dismiss Pierre's assertion. Turns out that he wasn't that wrong after all, and if a significant increase in access speed by avoiding zlib for 82% of object accesses can also be demonstrated for the kernel, then we have an opportunity for some optimization tradeoff with no backward compatibility concerns.

Right. But again this is not worth pursuing if a significant speed increase in repo access is not demonstrated at least with the kernel.

Nicolas

On Thu, Jan 10, 2008 at 09:30:59PM +0000, Nicolas Pitre wrote:

  Well that wasn't a random assertion, I made it, because I assumed that
a delta is usually less than a few hundred bytes, and as compression is
applied only to the delta without context, you end up packing 500 bytes
per 500 bytes which will seldomly have excellent compression ratios.

  Well, one could use the fact that deltas are not packed to avoid
copying them around, and that will _necessarily_ become a gain (you can
read them where they have been mmapped for instance). The number that
were given for git annotate use a compression of `0' which doesn't use
that fact, and I wouldn't be surprised to see a noticeable gain if one
does that.

  And actually, maybe that it's not the deltas we should not pack, but
objects under a certain size (say 512 bytes e.g. ?), whichever type they
have, and to have the code exploit that fact for real, and avoid copies.
With this criterion, I expect the repository to not grow a lot larger
(I'd say quite less than the 10% you had, as even in the kernel, there
_are_ some larger deltas, and we definitely loose space for them, I'd
expect less than a 5% size variation), and I _think_ it's worth
investigating. At least I expect visible results on commands (like blame
of even log[0]) that go through a lot of small objects to see 10 to 20%
increase speed (backed up by some experience I have in avoiding copies
in not-so-similar cases though, so it may be less, and I'll stand
corrected -- and disappointed, a bit).

  [0] If I'm correct commit messages are "objects" on their own, and I
      don't expect them to be very often over 512 octets.

Linus Torvalds wrote:

For reference, 20 years of Perl with very deep deltas:

wilber:~/src/perl-preview$ du -sk .git 73274 .git wilber:~/src/perl-preview$ git-repack -a Counting objects: 244360, done. Compressing objects: 100% (55493/55493), done. Writing objects: 100% (244360/244360), done. Total 244360 (delta 181061), reused 244360 (delta 181061) wilber:~/src/perl-preview$ du -sk .git/objects/pack/ 75389 .git/objects/pack/ wilber:~/src/perl-preview$

There are a few generated files in this history, but really only yacc files etc. It is in general also a lot of small changes.

Sam.

On Fri, 11 Jan 2008, Sam Vilain wrote:

Hmm. I'm not sure I understand what this was supposed to show?

You reused all the old deltas, and you did "du -sk" on two different things before/after (and didn't do a "-a -d" to repack the old pack either). So does the result actually have anything to do with any compression algorithm?

Use "-a -d -f" to repack a whole archive.

			Linus

Linus Torvalds wrote:

Drat, guess that means I'll have to recompute the deltas - I was trying to avoid that.

Ok, see you in an hour or two, hopefully sans bonehead mistakes this time :)

Sam.

On Fri, 11 Jan 2008, Sam Vilain wrote:

Well, you could try to reuse the delta base information itself, but then recompute the actual delta data contents. It would require some source-code changes, but that may be faster (and result in a more accurate before/after picture) than actually recomputing the deltas.

			Linus

Linus Torvalds wrote:

Yes, it would - but my runs have finished.

Without compression of deltas:

wilber:~/src/perl-preview$ git-repack -a -d -f --window=250 --depth=100 Compressing objects: 100% (236554/236554), done. Writing objects: 100% (244360/244360), done. Total 244360 (delta 182343), reused 0 (delta 0) wilber:~/src/perl-preview$ du -sk .git/objects/pack/ 86781 .git/objects/pack/

With compression of deltas:

wilber:~/src/perl-preview$ time git-repack -a -d -f --window=250 --depth=100 Counting objects: 244360, done. Compressing objects: 100% (236554/236554), done. Writing objects: 100% (244360/244360), done. Total 244360 (delta 182343), reused 0 (delta 0)

real 20m34.985s user 20m1.003s sys 0m25.558s wilber:~/src/perl-preview$ du -sk .git/objects/pack/ 72907 .git/objects/pack/

wilber:~/src/perl-preview$ git --version git version 1.5.4.rc2.7.g079c9-dirty

Of course those compression parameters are quite insane.

And as a side note either repack-objects got significantly better about memory use between 1.5.3.5 and that version (the OOM killer fired - killing first firefox and thunderbird :)) or apparently running git-repack with a ulimit stops it from allocating too much VM.

Sam.

On Fri, 11 Jan 2008, Sam Vilain wrote:

Ok, so non-compressed deltas are 20% bigger.

That may well be a perfectly acceptable trade-off if the end result is then a lot faster. Has somebody done performance numbers? I may have missed them.. The best test is probably something like "git blame" on a file that takes an appreciable amount of time.

			Linus

Linus Torvalds wrote:

The difference seems only barely measurable;

wilber:~/src/perl-preview$ time git annotate sv.c >/dev/null

real 0m8.130s user 0m6.712s sys 0m1.412s

wilber:~/src/perl-preview-loose$ time git annotate sv.c >/dev/null

real 0m7.930s user 0m6.480s sys 0m1.408s

(each one is last of three runs - dual-core x86_64 @ 2.1GHz w/512KB cache)

sv.c has about 1500 revisions, though the oldest line is I also tried annotate and log on the YACC generated parser which only has about 165 revisions, with similar results - a very minor difference or no difference.

Sam

Sam Vilain wrote:

only about 900 revisions old.

On Fri, 11 Jan 2008, Sam Vilain wrote:

Ok. 

It may be that it might help other cases, but that seems unlikely.

The more likely answer is that it's either of:

 - yes, zlib uncompression is noticeable in profiles, but that the 
   cold-cache access is simply the bigger problem, and getting rid of zlib 
   just moves the expense to whatever other thing that needs to access it 
   (memcpy, xdelta apply, whatever)

or

 - I don't know exactly which patch you used (did you just do the 
   "core.deltacompression=0" thing?), and maybe zlib is fairly expensive 
   even for just the setup crud, even when it doesn't really need to be.

but who knows..

		Linus

Linus Torvalds wrote:

Well, my figures agree with Pierre I think - 6-10% time savings for 'git annotate'.

I think Pierre has hit the nail on the head - that skipping compression for small objects is a clear win. He saw the obvious criterion, really. I've knocked it up as a config option that doesn't change the default behaviour below.

I can't help but speculate what benefits having a range of one or two of the most elite compression algorithms (eg, lzop or even lzma for the larger blobs) available would be, in general. eg, if gzip takes a stream longer than X kb to offer substantial benefits over lzop, lzop the ones shorter than that.

If the uncompressed objects are clustered in the pack, then they might stream compress a lot better, should they be tranmitted over a http transport with gzip encoding. In packs which should be as small as possible, with a format change they could be distributed as one compressed resource. The ordering of the objects would ideally be selected such that it results in optimum compression - which could add a savings akin to bzip2 vs gzip, at the expense of having to scan the small objects for mini-deltas and arrange them clustering objects which share these mini-deltas.

Well, interesting ideas anyway :)

Subject: [PATCH] pack-objects: add compressionMinSize option

Objects smaller than a page don't save much space when compressed, and cause some overhead. Allow the user to specify a minimum size for objects before they are compressed.

Credit: Pierre Habouzit <madcoder@debian.org>
Signed-off-by: Sam Vilain <sam.vilain@catalyst.net.nz>
---
 Documentation/config.txt |    5 +++++
 builtin-pack-objects.c   |    7 ++++++-
 2 files changed, 11 insertions(+), 1 deletions(-)

On Sat, 12 Jan 2008, Sam Vilain wrote:

Sorry to rain on your parade, but to me 6-10% time saving is not a clear win at all, given the equal increase in repository size. This is simply not worth it.

And a 50% time saving on an operation, such a git log, which takes less than 2 seconds in absolute time, is not worth the repo size increase either. Going from 2 seconds down to one second doesn't make enough of a user experience difference.

If git blame was to go from 10 seconds down to 4 then I'd say this is a clear win. But this is not the case.

Nicolas

Nicolas Pitre wrote:

Agree.

Disagree. Going as much as twice as fast for many history operations for 10% added space sounds like a clear win to me. We can easily agree to disagree though - making it a disabled by default config option allows the user to unroll their packs if they want.

What do you mean? 1 second waiting is far better than 2 seconds waiting. And the mmap optimizations have not even begun yet - that could result in boosts from zero-copy, such as a lighter VM footprint.

This is an awesome boost!  Everything feels snappier already :)

maia:~/src/perl.clean$ time git-log | LANG=C wc
 288927  894027 8860916

real    0m0.839s
user    0m0.824s
sys     0m0.144s
maia:~/src/perl.clean$ cd ../perl.clean.loose/
maia:~/src/perl.clean.loose$ time git-log | LANG=C wc
 288927  894027 8860916

real 0m0.515s user 0m0.504s sys 0m0.136s

maia:~/src/perl.clean.loose$ du -sk .git/objects/pack/ 113484 .git/objects/pack/ maia:~/src/perl.clean.loose$ cd - /home/samv/src/perl.clean maia:~/src/perl.clean$ du -sk .git/objects/pack/ 107040 .git/objects/pack/ maia:~/src/perl.clean$

Want me to try this on kde.git?

Sam.

On Sat, 12 Jan 2008, Sam Vilain wrote:

If you can come with a real life scenario, and not simply a simple test having little relevance with typical usage, that shows a clear reduction in execution time which is human perceptible, then I'll agree with you. But doing a full history log taking one second instead of two isn't a good enough argument to me for making the repository many megabytes larger. Again if it was 'git blame' using 5 seconds instead of 10 then I would agree that this is a clear win, even if this is also a 50% execution time reduction. But human perception is way more important when it is 10 secs down to 5 compared to 2 secs down to 1.

This proposed change isn't free, because you have to introduce a regression in one place in order to make a gain somewhere else. The pack v4 format that I developed with Shawn, though, was showing _both_ a speed gain and a repository size reduction, hence there is no regression for the added improvements. *That* is a clear win.

I suppose we do.

Nicolas

Hi,

On Sat, 12 Jan 2008, Nicolas Pitre wrote:

I have to agree with Nicolas. A full history log is such a rare occasion that it is not worth optimising for.

When I call "git log", it typically shows me the first commit _instantaneously_, which is plenty fast enough for me, especially given that I quit it right away or after a few pages more often than not.

Ciao, Dscho

Sam Vilain <sam@vilain.net> writes:

That would only have been a sensible optimization in older native pack protocol, where we always exploded the transferred packfile. However, these days, we tend to keep the packfile and re-index at the receiving end (http transport never exploded the packfile and it still doesn't). When used that way, choosing object layout in packfile in such a way to ignore recency order and cluster objects by their delta chain, which you are advocating to reduce the transfer overhead, is a bad tradeoff. Your packs will be kept in the form you chose for transport, which is a layout that hurts the runtime performance. And you keep using that suboptimal packs number of times, getting hurt every time.

I very much like the simplicity of the patch. If such a simple approach can give us a clear performance gain, I am all for it.

Benchmarks on different repositories need to back that up, though.

On Jan 10, 2008 9:39 PM, Nicolas Pitre <nico@cam.org> wrote:

The first thing I would like to test when zlib abstraction is ready is to test with NULL compressor, i.e. not compression/decompression at all and see if 'git log' and friends are happy.

BTW would be possible to test git with zlib disabled also now? I mean there is a quick hack to disable zlib not only in writing but also in reading, so that we can see what happens when running a repository packed without compression?

Thanks Marco

Marco Costalba wrote:

See Nicholas Pitre's hack on another branch of this thread - it won't cut out zlib entirely, but at least it's just configuring it to do plain pass-through. You can probably just replace pack_compression_level with 0.

Sam

On Thu, 10 Jan 2008, Marco Costalba wrote:

Easy: git config core.compression 0

Nicolas

On Thu, Jan 10, 2008 at 08:39:07PM +0000, Nicolas Pitre wrote:

  Using as a PoC a test that is if (size <= 512) instead, I get:

vanilla git:

$ du -k .git/**/*.pack 180808 .git/objects/pack/pack-7bc9f383c92cbffe366da2d2a62b67bb33a53365.pack $ repeat 5 time git blame MAINTAINERS >|/dev/null git blame MAINTAINERS >| /dev/null 7,34s user 0,09s system 99% cpu 7,433 total git blame MAINTAINERS >| /dev/null 7,31s user 0,16s system 100% cpu 7,475 total git blame MAINTAINERS >| /dev/null 7,35s user 0,08s system 100% cpu 7,431 total git blame MAINTAINERS >| /dev/null 7,30s user 0,18s system 99% cpu 7,482 total git blame MAINTAINERS >| /dev/null 7,33s user 0,16s system 99% cpu 7,492 total

With a compression disabled for sizes <= 512:

$ du -k .git/**/*.pack 188840.git/objects/pack/pack-7bc9f383c92cbffe366da2d2a62b67bb33a53365.pack $ repeat 5 time git blame MAINTAINERS >|/dev/null git blame MAINTAINERS >| /dev/null 7,06s user 0,09s system 100% cpu 7,150 total git blame MAINTAINERS >| /dev/null 7,08s user 0,13s system 99% cpu 7,209 total git blame MAINTAINERS >| /dev/null 7,07s user 0,08s system 99% cpu 7,168 total git blame MAINTAINERS >| /dev/null 7,02s user 0,15s system 99% cpu 7,177 total git blame MAINTAINERS >| /dev/null 7,07s user 0,13s system 99% cpu 7,243 total

Okay, the size doesn't even budge, it's not even near being fun. Though we gain 3% of wall clock time

Let's try with a limit of 1024 then !

$ du -k .git/**/*.pack 201725 .git/objects/pack/pack-7bc9f383c92cbffe366da2d2a62b67bb33a53365.pack $ repeat 5 time git blame MAINTAINERS >|/dev/null git blame MAINTAINERS >| /dev/null 6,93s user 0,16s system 77% cpu 9,109 total git blame MAINTAINERS >| /dev/null 6,88s user 0,08s system 99% cpu 6,965 total git blame MAINTAINERS >| /dev/null 6,84s user 0,10s system 99% cpu 6,952 total git blame MAINTAINERS >| /dev/null 6,86s user 0,12s system 99% cpu 6,983 total git blame MAINTAINERS >| /dev/null 6,81s user 0,18s system 99% cpu 6,994 total

Okay, the packs grows 10%, and the blame takes 6% less time.

Okay the numbers are still not that impressive, but my patch doesn't touches _only_ deltas, but also log comments I said, so I've redone my tests with git log and *TADAAAA*:

vanilla git:
    repeat 5 time git log >|/dev/null
    git log >| /dev/null  2,54s user 0,12s system 99% cpu 2,660 total
    git log >| /dev/null  2,52s user 0,12s system 99% cpu 2,653 total
    git log >| /dev/null  2,57s user 0,07s system 99% cpu 2,637 total
    git log >| /dev/null  2,56s user 0,09s system 99% cpu 2,659 total
    git log >| /dev/null  2,54s user 0,10s system 99% cpu 2,660 total

with the 512 octets limit:

    $ repeat 5 time git log >|/dev/null
    git log >| /dev/null  2,10s user 0,10s system 99% cpu 2,193 total
    git log >| /dev/null  2,08s user 0,10s system 99% cpu 2,189 total
    git log >| /dev/null  2,06s user 0,11s system 100% cpu 2,162 total
    git log >| /dev/null  2,04s user 0,13s system 100% cpu 2,172 total
    git log >| /dev/null  2,06s user 0,13s system 99% cpu 2,198 total

    That's already a 20% time reduction.

with the 1024 octets limits:
    $ repeat 5 time git log >|/dev/null
    git log >| /dev/null  1,39s user 0,12s system 99% cpu 1,512 total
    git log >| /dev/null  1,38s user 0,12s system 100% cpu 1,498 total
    git log >| /dev/null  1,41s user 0,10s system 99% cpu 1,514 total
    git log >| /dev/null  1,41s user 0,10s system 100% cpu 1,506 total
    git log >| /dev/null  1,40s user 0,10s system 100% cpu 1,504 total

    Yes that's 43% time reduction !

  As a side note, repacking with the 1024 octets limits takes 4:06 here,
and 4:26 without the limit at all, which is 8% less time. I know it
doesn't matters a lot as repack is a once time operation, but still, it
would speed up git gc --auto which is not something to neglect
completely.

I say it's worth investigating a _lot_, and the patch is that complicated:

On Fri, 11 Jan 2008, Pierre Habouzit wrote:

Well, sorry but that doesn't count to me. The whole 'git log' taking around 2 seconds is already hell fast for what it does, and IMHO this is not worth increasing the repository storage size for this particular work load.

If that was 43% reduction of a 10 second operation then sure I would agree, like the blame operation typically is. But otherwise the significant storage size increase is not worth the reduction of less than a second in absolute time.

No, I doubt it would. The bulk of 'git gc --auto' will reuse existing pack data which is way different from 'git repack -f'.

Well, I was initially entousiastic about this avenue, but the speed performance difference is far from impressive IMHO, given the tradeoff.

Nicolas

If it so happens that one algorithm does much better on small objects while another does better on large objects, there really is nothing that prevents using both in a repository. It's a bit of code bloat, of course.

Morten

On Wed, 9 Jan 2008, Johannes Schindelin wrote:

Right, like not having to compress tree objects and half of commit objects at all.

Nicolas

On Jan 10, 2008 4:41 AM, Nicolas Pitre <nico@cam.org> wrote:

Decompression speed has been shown to be a bottle neck on some tests involving mainly 'git log'.

Regarding back compatibility I really don't know at what level git functions actually need to know the compression format, looking at the code I would say at very low level, functions that deal directly with inflate() and friends are few [1] and not directly connected to UI, nor to git config. Is this compression format something user should know/care? and if yes why?

In my tests the assumption of a source files tar ball is unrealistic, to test the final size difference I would like testing different compressions on a big already packaged but still not zipped file. Someone could be so kind to hint me on how to create such a package with good quality, i.e. with packaging levels similar to what is done for public repos?

This does not realistically tests speed because as Junio pointed out the real decompressing schema is different: many calls on small objects, not one call on a big one. But if final size is acceptable we can go on more difficult tests.

Marco

[1] where inflate() is called:

-inflate_it() in builtin-apply.c -check_pack_inflate() in builtin-pack-objects.c -get_data() in builtin-unpack-objects.c -fwrite_sha1_file() in http-push.c and http-walker.c [mmm interesting same function in two files, also the signature and the contents seems the same....] -unpack_entry_data() in index-pack.c -unpack_sha1_header(), unpack_sha1_rest(), get_size_from_delta(), unpack_compressed_entry, write_sha1_from_fd() in sha1_file.c

On Jan 10, 2008 7:55 AM, Marco Costalba <mcostalba@gmail.com> wrote:

Looking at the git sources I have found that zip routines are candidate for a cleaning up, as example the more or less very similar lines of code are repeated many times in git files:

memset(&stream, 0, sizeof(stream)); deflateInit(&stream, pack_compression_level); maxsize = deflateBound(&stream, size); out = xmalloc(maxsize); stream.next_out = out; stream.avail_out = maxsize;

So what I'm planning to do to test with different algorithms is first a cleanup work that is more or less the following

- Remove #include <zlib.h> from cache.h and substitute with #include
"compress.h"

- Add #include <zlib.h> where it is "really" intended as example archive-zip.c

- Rename inflate()/deflate() and other zlib calls with corresponding
  zlib_inflate()
  zlib_deflate()

and declared in compress.h

- Define zlib_inflate() and friends as simple wrappers to
corresponding zlib function

- Test if everything is ok (should be only code shuffling/renaming until now)

- Start cleaning up as example adding a do_deflateInit() that wraps
all the code I have reported above and that involves deflateInit()

- When compression routines are cleaned up add new functions

do_inflate(), do_deflate() instead of zlib_* ones that wrap the compression alghorithm dispatching logic.

Dispatching could be choose in different ways going from

- compile time (at #define level)
- config (some configuration value stored in some global variable)
- dynamic (at run time, with no configuration needed, I have some
ideas on this ;-)

Comments?

Thanks Marco

Hi,

On Thu, 10 Jan 2008, Marco Costalba wrote:

No. We will always need zlib for compatibility. You cannot just replace zlib usage in git.

We have a long tradition to have the system includes in cache.h.

Besides, if you have "compress.h" included in cache.h, which in turn has to include "zlib.h", what is the use of putting it also in archive-zip.c?

Ciao, Dscho

On Jan 10, 2008 1:12 PM, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:

Ok. This was just to check what is broken by removing zlib.h so that I'm sure to renaming all the zlib related stuff.

But I agree this is most a development detail and I can do this just in my private tree to help me hacking the patches.

Thanks Marco

On Jan 9, 2008 10:55 PM, Marco Costalba <mcostalba@gmail.com> wrote:

Thanks for looking into this,  in this email and your subsequent ones.

I agree that zip time is an issue. I was looking into reducing the _number_ of zip calls on the same data, but work and personal crises have reduced me from an infrequent contributor to an occasional gadfly for the moment.

The approach you're taking (here and in following emails) of being able to make zip/lzo selection and measure the results should be enlightening. For the vast majority of git users, Junio's scenario is the most relevant.

Of additional interest to me is handling enormous objects more quickly. I would like to replace some p4 usage here with git, but most users will only notice the speed difference and not use git's extra features. Thus they will compare git add/git commit/git push unfavorably to p4 edit/p4 submit, because the former effectively does zip/unzip/zip/send, while the latter only does zip/send (git's extra "unzip/zip" comes from loose objects not being directly copyable into packs). This speed difference is irrelevant for small to normal files, but a killer when commiting a collection of say 100MB files.

Your lzo option could reduce this performance degradation vs p4 from 3x to close to 1.5x. If you get it accepted, I'd love to then "fix" the loose object copying "problem" making git _faster_ than p4 on large files! 2 simple forms for this "fix" would be to use the once-and-future "new" loose object format (an idea already rejected), or to encode all loose objects as singleton packs under .git/objects/xx (so that all (re)packing, in the absence of new deltification, becomes pack-to-pack copying). This latter idea is a modification of an idea from Nicolas Pitre. It certainly adds less code than other approaches for such a "fix".

Thanks,

Sam Vilain <sam@vilain.net> writes:

For the compression type detection, I was hoping that we could do something like sha1_file.c::legacy_loose_object(), but I tend to agree it is not probably worth it.