I suspect the bulk of the file will be the base blobs. A zlib
dictionary would help more with the trees and the 120K copies of the
GPL in the files.
Here's what I got by taking the output of verify-pack -v run
against the 430 MiB Mozilla pack and running that through a simple
Perl script:
COUNT BASE commit: 197613
COUNT BASE tree: 154496
COUNT BASE blob: 49860
COUNT BASE tag: 1203
COUNT DELTA commit: 3308
COUNT DELTA tree: 976712
COUNT DELTA blob: 579780
COUNT DELTA tag: 353
Those are just raw numbers of objects of each type broken out by
base and delta. We gotta alotta objects. :-)
We probably also have around 49,860 copies of the identical license
text (one per base object). I'm just assuming the xdelta algorithm
would recognize the identical run in the dependent object and
copy it from the base rather than use a literal insert command.
Thus I'm assuming the 579,780 deltas don't contain the license text.
UNCOMP BASE commit: 55 MiB
UNCOMP BASE tree: 30 MiB
UNCOMP BASE blob: 597 MiB
UNCOMP BASE tag: 0 MiB
UNCOMP DELTA commit: 0 MiB
UNCOMP DELTA tree: 44 MiB
UNCOMP DELTA blob: 190 MiB
UNCOMP DELTA tag: 0 MiB
These are the sizes of the objects and deltas prior to using zlib
to deflate them (aka the decompression buffer size, stored in the
object header).
ZIPPED BASE commit: 38 MiB
ZIPPED BASE tree: 26 MiB
ZIPPED BASE blob: 164 MiB
ZIPPED BASE tag: 0 MiB
ZIPPED DELTA commit : 0 MiB
ZIPPED DELTA tree: 73 MiB
ZIPPED DELTA blob: 126 MiB
ZIPPED DELTA tag: 0 MiB
These are the sizes of the objects within the pack, determined by
computing the difference in adjacent objects' offsets.
55 MiB of commits compressed into 38 MiB (saved 30%).
We can probably do better.
30 MiB of tree bases compressed into 26 MiB (saved 13.3%).
With 154,496 tree bases I think we can do better _somehow_. It may
just mean using more deltas so we have less bases. We don't have
154k unique directories. It may just mean using a tree specific
pack dictionary is enough.
44 MiB of tree deltas compressed into 73 MiB (saved -65.9%).
Ouch! We wasted 29 MiB by trying to compress tree deltas.
Way to go zlib!
Blob bases were 597 MiB uncompressed, 164 MiB compressed (saved 72%).
Blob deltas were 190 MiB uncompressed, 126 MiB compressed (saved 33%).
We might be able to do better here, but we're already fairing pretty
well.
To compare a .tar.gz of the ,v files from CVS is around 550 MiB.
We're already smaller than that in a pack file. But ,v is not the
most compact representation. I hoped we could do even better than
430 MiB.
I ran the same script against my Git pack. There I'm seeing the
same explosion of tree deltas: uncompressed they are 1380174 bytes,
compressed they are 1620439 bytes (-17.4% saved).
We may well have a general problem here with always compressing
tree deltas. It appears to be a minor dent in the space required
for a pack but its certainly a non-trivial amount on the larger
Mozilla pack. The wasted space is 2% of the Git pack and its 6.7%
of the Mozilla pack.
--
Shawn.
We may well have a general problem here with always compressing
tree deltas. It appears to be a minor dent in the space required
for a pack but its certainly a non-trivial amount on the larger
Mozilla pack. The wasted space is 2% of the Git pack and its 6.7%
of the Mozilla pack.
Whoops.
mugwump (Sam Vilain) just pointed out on #git that I didn't account
for the 20 byte base when comparing the offset differences (claimed
compressed size) and the uncompressed size. Nor did I account for
the variable sized headers.
I stated that 29 MiB of the Mozilla pack was wasted by 976712
tree deltas. Of that 29 MiB we know that 18.6 MiB must be the
20 byte base-SHA1 header. That leaves 10.4 MiB unaccounted for.
But we also have the variable length header; lets say the average
uncompressed length of a tree delta is 44 MiB/976712 so 47 bytes.
That average length can be encoded in two header bytes, so that's
another 1.8 MiB. Which leaves us with 8.6 MiB of wasted space.
Which is clearly not the 29 MiB I previously stated. But we're
still wasting a small amount of space over not compressing them.
--
Shawn.
From: Jon Smirl <hidden> Date: 2016-06-15 22:42:38
sha1s are effectively 20 byte pointer addresses into the pack. With 2M
objects you can easily get away with 4 byte address and a mapping
table. Another idea would be to replace the 20 byte sha1 in tree
objects with 32b file offsets - requiring that anything the tree
refers to has to already be in the pack before the tree entry can be
written.
On 8/29/06, Shawn Pearce [off-list ref] wrote:
Jon Smirl [off-list ref] wrote:
quoted
I suspect the bulk of the file will be the base blobs. A zlib
dictionary would help more with the trees and the 120K copies of the
GPL in the files.
Here's what I got by taking the output of verify-pack -v run
against the 430 MiB Mozilla pack and running that through a simple
Perl script:
COUNT BASE commit: 197613
COUNT BASE tree: 154496
COUNT BASE blob: 49860
COUNT BASE tag: 1203
COUNT DELTA commit: 3308
COUNT DELTA tree: 976712
COUNT DELTA blob: 579780
COUNT DELTA tag: 353
Those are just raw numbers of objects of each type broken out by
base and delta. We gotta alotta objects. :-)
We probably also have around 49,860 copies of the identical license
text (one per base object). I'm just assuming the xdelta algorithm
The Mozilla license has changed at least five times. That makes 250K
copies of licenses.
would recognize the identical run in the dependent object and
copy it from the base rather than use a literal insert command.
Thus I'm assuming the 579,780 deltas don't contain the license text.
UNCOMP BASE commit: 55 MiB
UNCOMP BASE tree: 30 MiB
UNCOMP BASE blob: 597 MiB
UNCOMP BASE tag: 0 MiB
UNCOMP DELTA commit: 0 MiB
UNCOMP DELTA tree: 44 MiB
UNCOMP DELTA blob: 190 MiB
UNCOMP DELTA tag: 0 MiB
These are the sizes of the objects and deltas prior to using zlib
to deflate them (aka the decompression buffer size, stored in the
object header).
ZIPPED BASE commit: 38 MiB
ZIPPED BASE tree: 26 MiB
ZIPPED BASE blob: 164 MiB
ZIPPED BASE tag: 0 MiB
ZIPPED DELTA commit : 0 MiB
ZIPPED DELTA tree: 73 MiB
ZIPPED DELTA blob: 126 MiB
ZIPPED DELTA tag: 0 MiB
These are the sizes of the objects within the pack, determined by
computing the difference in adjacent objects' offsets.
55 MiB of commits compressed into 38 MiB (saved 30%).
We can probably do better.
30 MiB of tree bases compressed into 26 MiB (saved 13.3%).
With 154,496 tree bases I think we can do better _somehow_. It may
just mean using more deltas so we have less bases. We don't have
154k unique directories. It may just mean using a tree specific
pack dictionary is enough.
I suspect a tree specific zlib dictionary will be a good win. But
those trees contain a lot of uncompressible data, the sha1. Those
sha1s are in binary not hex, right?
44 MiB of tree deltas compressed into 73 MiB (saved -65.9%).
Ouch! We wasted 29 MiB by trying to compress tree deltas.
Way to go zlib!
The git tools can be modified to set the compression level to 0 before
compressing tree deltas. There is no need to change the decoding code.
Even with compression level 0 they still get slightly larger because
zlib tacks on a header.
Blob bases were 597 MiB uncompressed, 164 MiB compressed (saved 72%).
Blob deltas were 190 MiB uncompressed, 126 MiB compressed (saved 33%).
We might be able to do better here, but we're already fairing pretty
well.
To compare a .tar.gz of the ,v files from CVS is around 550 MiB.
We're already smaller than that in a pack file. But ,v is not the
most compact representation. I hoped we could do even better than
430 MiB.
I ran the same script against my Git pack. There I'm seeing the
same explosion of tree deltas: uncompressed they are 1380174 bytes,
compressed they are 1620439 bytes (-17.4% saved).
We may well have a general problem here with always compressing
tree deltas. It appears to be a minor dent in the space required
for a pack but its certainly a non-trivial amount on the larger
Mozilla pack. The wasted space is 2% of the Git pack and its 6.7%
of the Mozilla pack.
I'm still interested in getting an idea of how much a Clucene type
dictionary compression would help. It is hard to see how you can get
smaller than that method. Note that you don't want to include the
indexing portion of Clucene in the comparison. Just the part where
everything gets tokenized into a big dictionary, arithmetic encoded
based on usage frequency, and then the strings in the orginal
documents are replaced with the codes. You want to do the diffs before
replacing everything with codes. Encoding this way is a two pass
process so it is easiest to work from an existing pack.
The indexing phase then constructs a bit vector for each word
representing all of the documents in the archive and whether they
contain the word or not. The vectors are then compressed using
something similar to zlib. To query you and/or/not the word vectors
together to identify candidate documents. There are algorithms for
combining the compressed vectors without decompressing them.
--
Jon Smirl
jonsmirl@gmail.com
sha1s are effectively 20 byte pointer addresses into the pack. With 2M
objects you can easily get away with 4 byte address and a mapping
table. Another idea would be to replace the 20 byte sha1 in tree
objects with 32b file offsets - requiring that anything the tree
refers to has to already be in the pack before the tree entry can be
written.
I've thought of that, but when you transfer a "thin" pack over the
wire the base object may not even be in the pack. Thus you can't
use an offset to reference it. Otherwise there's probably little
reason why the base couldn't be referenced by its 4 byte offset
rather than its full 20 byte object ID. Added up over all deltas
in the mozilla pack it saves a whopping 23 MiB.
The Mozilla license has changed at least five times. That makes 250K
copies of licenses.
Cute.
I suspect a tree specific zlib dictionary will be a good win. But
those trees contain a lot of uncompressible data, the sha1. Those
sha1s are in binary not hex, right?
Yup, binary.
The git tools can be modified to set the compression level to 0 before
compressing tree deltas. There is no need to change the decoding code.
Even with compression level 0 they still get slightly larger because
zlib tacks on a header.
See my followup email to myself; I think we're talking a zlib
overhead of 9.2 bytes on average per tree delta. That's with a
compression level of -1 (default, which is 6).
I'm still interested in getting an idea of how much a Clucene type
dictionary compression would help. It is hard to see how you can get
smaller than that method. Note that you don't want to include the
indexing portion of Clucene in the comparison. Just the part where
everything gets tokenized into a big dictionary, arithmetic encoded
based on usage frequency, and then the strings in the orginal
documents are replaced with the codes. You want to do the diffs before
replacing everything with codes. Encoding this way is a two pass
process so it is easiest to work from an existing pack.
From what I was able to gather I don't think Clucene stores the
documents themselves as the tokenized compressed data. Or if it
does you lose everything between the tokens. There's a number of
things we want to preserve in the original "document" like whitespace
that would be likely stripped when constructing tokens.
But it shouldn't be that difficult to produce a rough estimate of
what that storage size would be.
--
Shawn.
From: Jon Smirl <hidden> Date: 2016-06-15 22:42:38
On 8/29/06, Shawn Pearce [off-list ref] wrote:
Jon Smirl [off-list ref] wrote:
quoted
sha1s are effectively 20 byte pointer addresses into the pack. With 2M
objects you can easily get away with 4 byte address and a mapping
table. Another idea would be to replace the 20 byte sha1 in tree
objects with 32b file offsets - requiring that anything the tree
refers to has to already be in the pack before the tree entry can be
written.
I've thought of that, but when you transfer a "thin" pack over the
wire the base object may not even be in the pack. Thus you can't
use an offset to reference it. Otherwise there's probably little
reason why the base couldn't be referenced by its 4 byte offset
rather than its full 20 byte object ID. Added up over all deltas
in the mozilla pack it saves a whopping 23 MiB.
Every time an object goes on the wire these 'pack internal'
optimizations need to be undone. If you are sending the whole pack
everything can be sent as is.
These intense compression schemes are meant for archival level data.
Everybody should end up with a copy of the entire archive and that
will be the end of those objects moving on the wire.
From what I was able to gather I don't think Clucene stores the
documents themselves as the tokenized compressed data. Or if it
does you lose everything between the tokens. There's a number of
things we want to preserve in the original "document" like whitespace
that would be likely stripped when constructing tokens.
I can't remember if the Clucene code includes the ability to compress
using the dictionary. I had thought that the code was in there but
maybe not. Things that aren't in the dictionary use an escape code and
are copied intact. I have the Lucene book on my desk, I'll flip
through it and see what it says.
Might be worthwhile to poke around on the net and see if you can come
up with an existing dictionary based compressor. There has got to be
one out there, this is a 30 year old concept.
But it shouldn't be that difficult to produce a rough estimate of
what that storage size would be.
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:42:38
On Tue, 29 Aug 2006, Shawn Pearce wrote:
Jon Smirl [off-list ref] wrote:
quoted
The git tools can be modified to set the compression level to 0 before
compressing tree deltas. There is no need to change the decoding code.
Even with compression level 0 they still get slightly larger because
zlib tacks on a header.
See my followup email to myself; I think we're talking a zlib
overhead of 9.2 bytes on average per tree delta. That's with a
compression level of -1 (default, which is 6).
In fact, the bulk of a tree delta is most likely to contain the
literal sha1 of one or more directory entries that changed, and this is
hardly compressible. There is nothing to gain by forcing zlib level to
0 for tree deltas since it never makes the deflated stream smaller from
the tests I've performed in the past. It seems that zlib is smart
enough not to attempt any compression when there is no gain. That
leaves the zlib header as the only overhead.
And the zlib header contains a CRC which we're about to use for
validating the data when doing delta data reuse in order to prevent pack
corruption propagation like the one recently posted on the list.
Without that a pack corruption (from a bad disk sector for example) is
likely to go unnoticed when doing a repack. The data could be validated
by expanding deltas and verifying the sha1 on the end result but this is
a really expensive operation if performed on all deltas which is best
left to git-fsck-objects --full. So I think the small overhead relative
to total pack size might be worth it for better data integrity.
Using an offset instead of a sha1 to reference a delta base object is
certainly a good idea though. But I'd use the same variable encoding as
the object size to avoid the 32-bit limit issue. When generating a thin
pack the real sha1 of the delta object could be substituted for the
offset quite easily if the base object is not sent a part of the same
pack.
Nicolas