{"thread":{"id":"43511","subject":"Re: Computing delta sizes in pack files","startedAt":"2006-11-21T05:39:42Z","lastAt":"2006-11-25T07:33:38Z","messageCount":3,"participants":["Shawn Pearce","Jonas Fonseca"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"296446","messageId":"20061121053942.GA3149@spearce.org","threadId":"43511","inReplyTo":null,"subject":"Computing delta sizes in pack files","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-11-21T05:39:42Z","receivedAt":"2006-11-21T05:39:42Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Recently I wanted to know how well Git's pack files were doing at\nstoring rather large JAR files.  So I wrote the attached script to\nparse the output of `git verify-pack -v` and use that to determine\nhow many bytes are needed for each revision of any given file.\n\nFor example running it on builtin-blame.c:\n\n  $ perl ../delta-sizes.pl builtin-blame.c \n  Caching cache-cdc41646a9de201b06a936fc3bddcbd51aeb532c.v...\n  Pack index cache created.\n  \n  builtin-blame.c\n  16660221... s 2         44\n  066dee74... s 1         62\n  176f51a4...   0      12797\n  ----------------------------------------\n           3 revs         12 KiB\n  \n           3 revs         12 KiB\n\nThere are 3 revisions of this file, totalling 12 KiB in disk space\nwithin the pack files.  One of those revisions uses 44 bytes and the\nother uses 62 bytes.  Given that this includes the complete overhead\n(including the 20 byte OBJ_REF_DELTA header) we're talking about\n~20 bytes of delta data in revision 16660221.  Pretty good.  :)\n\nOf course this only looks at a single blob object and does not take\ninto account the tree and commit overheads for a given revision,\nbut it does give a really good idea of what is going on.\n\n-- \nShawn.\n\n\n#!/usr/bin/perl\n\nuse strict;\n\nunless ($ENV{GIT_DIR})\n{\n\t$ENV{GIT_DIR} = '.git' if -f '.git/config';\n}\nunless ($ENV{GIT_DIR})\n{\n\t$ENV{GIT_DIR} = shift || die \"usage: $0 gitdir file...\\n\";\n}\n\nmy %revs_by_path;\nmy %path_by_rev;\nmy %by_hash;\n\nopen(R, \"git rev-list --objects --all |\");\nwhile (<R>)\n{\n\tchomp;\n\tmy ($sha1, $path) = split / /, $_, 2;\n\tnext unless $path;\n\tpush(@{$revs_by_path{$path}}, $sha1);\n\t$path_by_rev{$sha1}{$path} = 1;\n}\nclose R;\n\nsub index_pack\n{\n\tmy $idx = shift;\n\tmy $pack = $idx;\n\tlocal *R, *V, $_;\n\n\t$pack =~ s/\\.idx$/.pack/;\n\t$pack =~ /pack-([a-z0-9]{40})\\.pack$/;\n\tmy $cache = \"cache-$1.v\";\n\tmy @objects;\n\n\tunless (open(R, $cache))\n\t{\n\t\tprint STDERR \"Caching $cache...\\n\";\n\t\topen(R, \">$cache\");\n\t\topen(V, \"git verify-pack -v $idx|\");\n\t\tprint R while $_ = <V>;\n\t\tclose V;\n\t\tclose R;\n\t\tprint STDERR \"Pack index cache created.\\n\\n\";\n\t\topen(R, $cache);\n\t}\n\n\twhile (<R>)\n\t{\n\t\tlast if /^chain length/;\n\t\tchomp;\n\t\tmy ($sha1, $type, $size, $offset, $depth, $base) = split /\\s+/;\n\t\tmy $o = {\n\t\t\tsha1 => $sha1,\n\t\t\ttype => $type,\n\t\t\tuncompressed_size => $size,\n\t\t\toffset => $offset,\n\t\t\tdepth => $depth,\n\t\t\tbase => $base,\n\t\t};\n\t\tpush @objects, $o;\n\t\t$by_hash{$sha1} = $o;\n\t}\n\tclose R;\n\n\tmy $last = undef;\n\tforeach my $o (sort {$a->{offset} <=> $b->{offset}} @objects)\n\t{\n\t\t$last->{pack_size} = $o->{offset} - $last->{offset} if $last;\n\t\t$last = $o;\n\t}\n\t$last->{pack_size} = ((-s $pack) - 20) - $last->{offset};\n}\n\nopendir(D, \"$ENV{GIT_DIR}/objects/pack\");\nwhile (my $entry = readdir D)\n{\n\tnext unless $entry =~ /^pack-[a-z0-9]{40}\\.idx$/;\n\tindex_pack \"$ENV{GIT_DIR}/objects/pack/$entry\";\n}\nclosedir D;\n\nif (@ARGV)\n{\n\tmy $g_total = 0;\n\tmy $g_revs = 0;\n\n\tforeach my $path (@ARGV)\n\t{\n\t\tprint $path, \"\\n\";\n\n\t\tmy $total = 0;\n\t\tmy $revs = 0;\n\t\tforeach my $sha1 (\n\t\t\tsort {$by_hash{$b}{depth} <=> $by_hash{$a}{depth}}\n\t\t\tgrep {$by_hash{$_}}\n\t\t\t@{$revs_by_path{$path}})\n\t\t{\n\t\t\tmy $o = $by_hash{$sha1};\n\t\t\tprintf \"%8s... %1s%2i %10i\\n\",\n\t\t\t\tsubstr($sha1, 0, 8),\n\t\t\t\t($o->{depth}\n\t\t\t\t\t? ($path_by_rev{$o->{base}}{$path}\n\t\t\t\t\t\t? 's'\n\t\t\t\t\t\t: 'o')\n\t\t\t\t\t: ''),\n\t\t\t\t$o->{depth},\n\t\t\t\t$o->{pack_size};\n\t\t\t$total += $o->{pack_size};\n\t\t\t$revs++;\n\t\t}\n\n\t\t$g_total += $total;\n\t\t$g_revs += $revs;\n\n\t\tmy $units = 'bytes';\n\t\tif ($total >= 1024)\n\t\t{\n\t\t\t$units = 'KiB';\n\t\t\t$total /= 1024;\n\n\t\t\tif ($total >= 1024)\n\t\t\t{\n\t\t\t\t$units = 'MiB';\n\t\t\t\t$total /= 1024;\n\t\t\t}\n\t\t}\n\n\t\tprint '-'x40, \"\\n\";\n\t\tprintf \"%15s %10i %s\\n\",\n\t\t\t\"$revs revs\",\n\t\t\t$total, $units;\n\t\tprint \"\\n\";\n\t}\n\n\tmy $units = 'bytes';\n\tif ($g_total >= 1024)\n\t{\n\t\t$units = 'KiB';\n\t\t$g_total /= 1024;\n\n\t\tif ($g_total >= 1024)\n\t\t{\n\t\t\t$units = 'MiB';\n\t\t\t$g_total /= 1024;\n\t\t}\n\t}\n\n\tprintf \"%15s %10i %s\\n\",\n\t\t\"$g_revs revs\",\n\t\t$g_total, $units;\n}\nelse\n{\n\tforeach my $path (sort keys %revs_by_path)\n\t{\n\t\tmy $total = 0;\n\t\tmy $revs = 0;\n\t\tforeach my $sha1 (\n\t\t\tsort {$by_hash{$b}{depth} <=> $by_hash{$a}{depth}}\n\t\t\tgrep {$by_hash{$_}}\n\t\t\t@{$revs_by_path{$path}})\n\t\t{\n\t\t\t$total += $by_hash{$sha1}{pack_size};\n\t\t\t$revs++;\n\t\t}\n\n\t\tmy $units = 'bytes';\n\t\tif ($total >= 1024)\n\t\t{\n\t\t\t$units = 'KiB';\n\t\t\t$total /= 1024;\n\n\t\t\tif ($total >= 1024)\n\t\t\t{\n\t\t\t\t$units = 'MiB';\n\t\t\t\t$total /= 1024;\n\t\t\t}\n\t\t}\n\t\t$total = int $total;\n\n\t\tprintf \"%3i revs %10i %-5s %s\\n\",\n\t\t\t$revs,\n\t\t\t$total, $units,\n\t\t\t$path;\n\t}\n}\n"},{"id":"295303","messageId":"2c6b72b30611220844t4b341284q4bff914b91eac48d@mail.gmail.com","threadId":"43511","inReplyTo":"20061121053942.GA3149@spearce.org","subject":"Re: Computing delta sizes in pack files","fromName":"Jonas Fonseca","fromEmail":"jonas.fonseca@gmail.com","sentAt":"2006-11-22T16:44:11Z","receivedAt":"2006-11-22T16:44:11Z","isPatch":false,"sender":{"key":"jonas.fonseca@gmail.com","avatar":"https://gravatar.com/avatar/9b7fa23cce50269e5d164312b6ac5ae818a180f837b38f28f3bdf689dd7f96cd?d=mp&s=160"},"body":"On 11/21/06, Shawn Pearce <spearce@spearce.org> wrote:\n> Of course this only looks at a single blob object and does not take\n> into account the tree and commit overheads for a given revision,\n> but it does give a really good idea of what is going on.\n\nI have some numbers that also includes the other object types. They are\nbased on running a set of scripts in 5 different repositories. First,\neach repository has been both packed and unpacked with respect to the\ndifferent object types to show the compression level and disk-space\nsaving. The main results are compression level for the different object\ntypes and a test to see which pack sizes provide \"optimal\" packing. I\nwill not post the numbers here. They are available in\nhttp://jonas.nitro.dk/tmp/stats.pdf for those interested. The following\nis my \"analysis\" of the numbers.\n\nIt can be seen that the blob objects generally control the overall\npacking properties of the repository, especially when it comes to the\ncompression level. Generally, there are more tree objects than blob\nobjects, which can be due to the fact that both the ELinks and Linux\nkernel tree are structured into many subdirectories containing few\nfiles.  The Tig repository is exceptional in that it has only few files\nand one tree object per revision, which has the effect of reducing the\ntree object compression level.  At 83% on average, tree objects compress\nvery well and in the general case better than blob objects.  As\nexpected, the randomness of the content of both commit and tag objects\nresults in a very poor packing performance of only 2%.  In terms of\ndisk-space usage between packed and unpacked object stores, it is\nobvious that the overhead of many small object files is unavoidable.\n\nNext, is the examination of how different pack sizes affect the\ncompression level. This also includes looking at how the size of the\nindex file varies.  The columns on per-object sizes are of interest. The\nper-object sizes can be compared with the average object size of each\nproject to get a rough idea of the compression level. In some of the\ntables, rows are missing because not all repositories contain enough\nobjects with respect to the pack sizes being examined.\n\nThe data show that for minimal index files, the packs need to contain\nmore than 2500 objects. The 24 bytes per-object for the optimal case\nincludes 20-bytes for the object SHA1, and thus cannot be expected to\nbecome lower. For commit objects, the numbers show that there is almost\nno difference between small and big packs. The same is assumed to be the\ncase for tag objects. For tree objects, it becomes very clear that in\nrepositories with structured source trees, the tree objects compress\nmuch better for big packs, whereas a project, such as Git, does not save\nmuch after pack files reach a size of 250 objects.  Across all\nrepositories, bigger packs always leads to better compression and fewer\nbytes per object, but only for blob objects.\n\nIn conclusion, the heuristic of packing based on object type is very\ngood. Neither commit nor tag objects compress very well when packed.\nWhile both tree and blob objects compress well, tree objects do not\nrequire bigger packs to provide better compression. The pack index files\ndo not require many objects to become optimal. It should also be noted\nfrom looking at the columns containing numbers about the minimum and\nmaximum pack sizes that they can vary a lot compared to the average\nsize.\n\n-- \n"},{"id":"295220","messageId":"20061125073338.GF4528@spearce.org","threadId":"43511","inReplyTo":"2c6b72b30611220844t4b341284q4bff914b91eac48d@mail.gmail.com","subject":"Re: Computing delta sizes in pack files","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-11-25T07:33:38Z","receivedAt":"2006-11-25T07:33:38Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jonas Fonseca <jonas.fonseca@gmail.com> wrote:\n> I will not post the numbers here. They are available in\n> http://jonas.nitro.dk/tmp/stats.pdf for those interested. The following\n> is my \"analysis\" of the numbers.\n\nThanks, this was interesting stuff.\n\n> As expected, the randomness of the content of both commit and tag objects\n> results in a very poor packing performance of only 2%.\n\nThis is one reason why Jon Smirl was pushing the idea of dictionary based\ncompression.  git.git has only 276 unique author lines, yet 37 of them\nare really the top committers.  Not surprisingly Junio C Hamano leads\nthe pack with 3529+ commits...  :-)\n\nA dictionary based compression would allow us to easily compress\nJunio's authorship line away from those 3529+ commits into a single\nstring, getting much better compression on the commits.\n\nIn trees this may work very well too for very common file names, e.g.\n\"Makefile\".  Yes each tree delta compresses very well against its\nbase (and likely copies the file name from the base even when the\nSHA1 changed) but if the bases were able to use a common dictionary\nthat would help even more.\n \n> The data show that for minimal index files, the packs need to contain\n> more than 2500 objects. The 24 bytes per-object for the optimal case\n> includes 20-bytes for the object SHA1, and thus cannot be expected to\n> become lower.\n\nThis is just a fundamental property of the pack index file format.\nThe file *MUST* be 1064 bytes of fixed overhead, with 24 bytes of\ndata per object indexed.  So the fixed overhead amortizes very\nquickly over the individual object entries, at which point its\nexactly 24 bytes per entry.  This all of course assumes a 32 bit\nindex (which is the current format).\n\nThe thing is the Mozilla index is 44 MiB.  That's roughly 1.9 million\nobjects.  The index itself is larger than the entire git.git pack.\nOn a large repository the index ain't trivial...  yet its essential\nto performance!\n\nOn the other hand the 1064 bytes of fixed overhead in the index\nis nothing compared to the overhead in say an RCS file.  Or an\nSVN repository...  :-)\n\nWhat I failed to point out in my script (or in my email) is that\nthe 24 bytes of index entry cannot be eliminated, and thus must\nbe added to the \"revision cost\".  In some cases its about the same\nsize as the deltafied revision in the pack file.  :-(\n\n-- \n"}]}