Sorry but this really is a pretty stupid question on my part:
In builtin-pack-objects.c write_one(), why is the base object written
behind the first delta that depends on it (if it hasn't been written
already) rather than BEFORE the first delta that depends on it?
If the base always had to appear before any delta that uses it then
unpack-objects wouldn't need to cache a delta in memory waiting
for the base to get unpacked.
From a data locality perspective putting the base object before
or after the delta shouldn't matter, as either way the delta
is useless without the base. So placing the base immediately
before the delta should perform just as well as placing it after.
Either way the OS should have the base in cache by the time the
delta is being accessed.
In other words, why not apply this patch and make it a requirement
of the pack file format?
diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c
index 46f524d..5dd97b9 100644
--- a/builtin-pack-objects.c
+++ b/builtin-pack-objects.c
@@ -341,11 +341,11 @@ static unsigned long write_one(struct sh
* if it is written already.
*/
return offset;
- e->offset = offset;
- offset += write_object(f, e);
/* if we are deltified, write out its base object. */
if (e->delta)
offset = write_one(f, e->delta, offset);
+ e->offset = offset;
+ offset += write_object(f, e);
return offset;
}
On Tue, 29 Aug 2006, Shawn Pearce wrote:
Sorry but this really is a pretty stupid question on my part:
In builtin-pack-objects.c write_one(), why is the base object written
behind the first delta that depends on it (if it hasn't been written
already) rather than BEFORE the first delta that depends on it?
Most of the time the base object will have been written already since we
favor backward deltas, and newer objects are written first. But that
might not always be the case.
If the base always had to appear before any delta that uses it then
unpack-objects wouldn't need to cache a delta in memory waiting
for the base to get unpacked.
Like mentioned above this is not the common case. And deltas are small
anyway. And when you think about it the delta and base objects have to
be both in memory so this doesn't change anything in the end. So in
practice there is no really special caching.
quoted
From a data locality perspective putting the base object before
or after the delta shouldn't matter, as either way the delta
is useless without the base. So placing the base immediately
before the delta should perform just as well as placing it after.
Either way the OS should have the base in cache by the time the
delta is being accessed.
Not necessarily. In fact if you checkout a particular revision with
such a case, putting the base first will force a seek over it since what
is referenced first is the delta, then seek back to the base. If it is
right after the delta then there is no need to seek back and some read
ahead might have picked the base by the time it is referenced. OK since
all this is mmap()'ed there might not be much difference in practice,
but in theory the current arrangement could have a slight advantage.
In other words, why not apply this patch and make it a requirement
of the pack file format?
I don't think this should be a requirement.
Nicolas
Shawn Pearce wrote:
From a data locality perspective putting the base object before
or after the delta shouldn't matter, as either way the delta
is useless without the base. So placing the base immediately
before the delta should perform just as well as placing it after.
Either way the OS should have the base in cache by the time the
delta is being accessed.
_Should_ perform? Have you got any measurements of speed of creating "base
before delta" pack, and reading objects from this kind of pack?
--
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git
Jakub Narebski [off-list ref] wrote:
Shawn Pearce wrote:
quoted
From a data locality perspective putting the base object before
or after the delta shouldn't matter, as either way the delta
is useless without the base. So placing the base immediately
before the delta should perform just as well as placing it after.
Either way the OS should have the base in cache by the time the
delta is being accessed.
_Should_ perform? Have you got any measurements of speed of creating "base
before delta" pack, and reading objects from this kind of pack?
No, not yet. It just seemed odd to me that the base was put behind
the delta which then forces unpack-objects to hold a delta in memory
until it finds the corresponding base later in the stream when it
could have been just as simple to require the base appear before
the delta. I wondered what the rationale was for the additional
complexity in unpack-objects.
Nicolas' reply pointed out that the current arrangement of base
after delta may actually offer improved performance due to the
OS performing read-ahead when you seek to the delta. But he also
pointed out this base after delta situtation should be rather rare
as we try to delta older objects against newer objects and we try to
place newer objects at the front of the pack, so it likely shouldn't
matter that much.
I just instrumented builtin-pack-objects.c to count how many times
we put the delta before the base and then repacked a current Git
repo with `git repack -a -d -f`. 28167 objects, 19170 deltas. 6003
deltas appeared before their base objects. So 31% of the time.
That's certainly not the common case but it does occur with some
frequency. However resorting the output of verify-pack -v by offset
and visually looking at the entries you can clearly see it doesn't
happen very often early in the pack. Most of the objects in the
front of the pack are undeltafied commits.
This particular Git repository has 6723 commits and 905 trees that
weren't deltafied. That's a total of 4 MiB of uncompressed data,
most of which appears at the front of the pack. Only 68 commits
were deltas but 8067 trees were made into deltas. The compressed
commits seemed to occupy the first 2 MiB of the pack file; that's
25% of the 8 MiB pack. A commit-specific pack local dictionary
could be interesting here as it might some pack space.
I'm going to shutup now and not say anything further on the subject
unless I've got some hard results indicating a different organization
is better or worse than what we have right now.
--
Shawn.