Hello,
There have been a few threads on making git more space efficient, and
eventually someone mentions tiny files and space fragmentation. Now that git
object names are decoupled from their compression, it's easier to consider a
a variety of compression algorithms. I whipped up a really silly "pack files
together" compression.
This would maintain the write once semantics but allow a simple mechanism
where objects are combined together. Choosing which objects to combine is
easy, things put together into update-cache go together. This gives us more
space efficiency and no seeks when reading that packed file off disk.
A natural extension to this is to make update-cache --commit-tree, which
includes the files produced by write-tree and commit-tree into the same
packed file. (I haven't coded this).
The layout works like this:
1) a new object type "packed" is added.
2) new objects are buffered into a packed object, until it gets to around 32k
in size. This is complete arbitrary but felt about right.
3) The packed object is writting to git storage and then hard links are made
to the packed object from the sha1 filename of each object inside.
4) read_sha1_file is changed to recognize the packed object and search inside.
I did a simple test on the 2.6.11 tree with my 100 patches applied. Without
packing, .git is 99MB. With packing it only needs 62MB:
read speeds don't suffer with this, time to read-tree ; checkout-cache -a -f
from a cold cache were the same. I could get the times lower with the patch
by caching the uncompressed data, since in theory I should be faster here.
Using this on data you care about would be a really bad idea right now. I'm
only posting the patch to get the basic idea across for benchmarking and
discussion.
-chris
On Thu, 21 Apr 2005, Chris Mason wrote:
There have been a few threads on making git more space efficient, and
eventually someone mentions tiny files and space fragmentation. Now that git
object names are decoupled from their compression, it's easier to consider a
a variety of compression algorithms. I whipped up a really silly "pack files
together" compression.
Careful.
This is something that needs history to tell whether it's effective. In
particular, if one file changes and another one does not, your packed
archive now ends up being a new blob, so while you "saved space" by having
just one blob for the object, in reality you didn't save any space at all
because with the <x> files changing, you just guaranteed that the packed
blob changes <x> times more often.
See? Your "packing in space" ends up also resulting in "packing in time",
and you didn't actually win anything.
(If you did a good job of packing, you hopefully didn't _lose_ anything
either - you needed 1:<x> number of objects that took 1:<x> the space if
the packing ended up perfect - but since you needed <x> times more of
these objects unless they all change together, you end up with exactly the
same space usage).
So the argument is: you can't lose with the method, and you _can_ win.
Right?
Wrong. You most definitely _can_ lose: you end up having to optimize for
one particular filesystem blocking size, and you'll lose on any other
filesystem. And you'll lose on the special filesystem of "network
traffic", which is byte-granular.
I don't want to pee on peoples parades, and I'm all for gathering numbers,
but the thing is, the current git isn't actually all that bad, and I
guarantee that it's hard to make it better without using delta
representation. And the current thing is really really simple.
Linus
On Thursday 21 April 2005 11:41, Linus Torvalds wrote:
On Thu, 21 Apr 2005, Chris Mason wrote:
quoted
There have been a few threads on making git more space efficient, and
eventually someone mentions tiny files and space fragmentation. Now that
git object names are decoupled from their compression, it's easier to
consider a a variety of compression algorithms. I whipped up a really
silly "pack files together" compression.
Careful.
This is something that needs history to tell whether it's effective. In
particular, if one file changes and another one does not, your packed
archive now ends up being a new blob, so while you "saved space" by having
just one blob for the object, in reality you didn't save any space at all
because with the <x> files changing, you just guaranteed that the packed
blob changes <x> times more often.
The packed blob lives in git but never makes it into a tree. Lets say that I
have a packed blob with files "a, b, c", and another packed blob with files
"x, y, z". Someone changes files, b and z and then runs update-cache b z.
Now we have 2 unchanged packed blobs: "a, b, c", "x, y, z", and one new
packed blob: "b_new, z_new". This means that in order for the packing to
help, we have to change more then one file at a time. That's why it would be
good to have update-cache include the write-tree and commit-tree.
See? Your "packing in space" ends up also resulting in "packing in time",
and you didn't actually win anything.
(If you did a good job of packing, you hopefully didn't _lose_ anything
either - you needed 1:<x> number of objects that took 1:<x> the space if
the packing ended up perfect - but since you needed <x> times more of
these objects unless they all change together, you end up with exactly the
same space usage).
So the argument is: you can't lose with the method, and you _can_ win.
Right?
Wrong. You most definitely _can_ lose: you end up having to optimize for
one particular filesystem blocking size, and you'll lose on any other
filesystem. And you'll lose on the special filesystem of "network
traffic", which is byte-granular.
The patch does have one extra directory entry (for the packed blob), but from
a network point of view roughly the same number of bytes should be copied.
The hardlinks won't play nice with rsync though, soft links might be better.
packing isn't just about filesystem block sizes, it's about locality. All the
hashing means pretty much every access in git is random. With packing we can
at least try to put a single changeset together on disk. Right now it
doesn't matter much, but when the git tree is 6GB in two years we'll feel the
pain.
I don't want to pee on peoples parades, and I'm all for gathering numbers,
but the thing is, the current git isn't actually all that bad, and I
guarantee that it's hard to make it better without using delta
representation. And the current thing is really really simple.
Grin, if I thought you wanted the patch I might have tried to pretty it up a
little. The point is that all the discussions about ways to make git use
less space end up stuck in "but wait, that'll make a bunch of tiny files and
filesystems aren't good at that". So I believe some kind of packing is a
required building block for any kind of delta storage.
-chris