* Re: Mozilla .git tree
From: Jon Smirl @ 2006-08-30 3:27 UTC (permalink / raw)
To: Shawn Pearce; +Cc: git
In-Reply-To: <20060830031029.GA23967@spearce.org>
On 8/29/06, Shawn Pearce <spearce@spearce.org> wrote:
> Jon Smirl <jonsmirl@gmail.com> wrote:
> > 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.
--
Jon Smirl
jonsmirl@gmail.com
^ permalink raw reply
* Re: Mozilla .git tree
From: Shawn Pearce @ 2006-08-30 3:10 UTC (permalink / raw)
To: Jon Smirl; +Cc: git
In-Reply-To: <9e4733910608291958l45c0257dla6e5ebd4176f7164@mail.gmail.com>
Jon Smirl <jonsmirl@gmail.com> wrote:
> 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.
^ permalink raw reply
* Re: Mozilla .git tree
From: Jon Smirl @ 2006-08-30 2:58 UTC (permalink / raw)
To: Shawn Pearce; +Cc: git
In-Reply-To: <20060830015122.GE22935@spearce.org>
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 <spearce@spearce.org> wrote:
> Jon Smirl <jonsmirl@gmail.com> wrote:
> > 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
^ permalink raw reply
* Re: Mozilla .git tree
From: Shawn Pearce @ 2006-08-30 2:25 UTC (permalink / raw)
To: Jon Smirl; +Cc: git
In-Reply-To: <20060830015122.GE22935@spearce.org>
Shawn Pearce <spearce@spearce.org> wrote:
> 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.
^ permalink raw reply
* Re: Mozilla .git tree
From: Shawn Pearce @ 2006-08-30 1:51 UTC (permalink / raw)
To: Jon Smirl; +Cc: git
In-Reply-To: <9e4733910608291807q9b896e4sdbfaa9e49de58c2b@mail.gmail.com>
Jon Smirl <jonsmirl@gmail.com> wrote:
> 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.
^ permalink raw reply
* Ask us for credit you
From: algeria @ 2006-08-29 20:47 UTC (permalink / raw)
To: git
How are you Guys?!
Your credit doesn't matter to us!
If you OWN real estate and want IMMEDIATE cash to spend ANY way you
like, or simply wish to LOWER your monthly payments by a third or more, here are the deals we have TODAY:
$488,000.00 at a 3.67% fixed-rate
$372,000.00 at a 3.90% variable-rate
$492,000.00 at a 3.21% interest-only
$248,000.00 at a 3.36% fixed-rate
$198,000.00 at a 3.55% variable-rate
Hurry, we have requests limits, so when these deals are gone, they are
gone!
We have one-mimute form to apply the request,
please CLICK HERE
http://J8MTH.capitalpartnerusa.com/?ncache=103790
Don't worry about approval, your credit will not disqualify you!
Approval Manager.
^ permalink raw reply
* Re: Why do base objects appear behind the delta in packs?
From: Jon Smirl @ 2006-08-29 19:23 UTC (permalink / raw)
To: Shawn Pearce; +Cc: Nicolas Pitre, git
In-Reply-To: <20060829183239.GH21729@spearce.org>
On 8/29/06, Shawn Pearce <spearce@spearce.org> wrote:
> I don't have Jon's cvs2svn code and I don't know if its ready for
> public consumption yet. git-fast-import however looks like its
> almost there, so I'm making the URL publicly available for those
> that may be interested in it.
If anyone is interested in cvs2svn mods let me know (they are in
Python) and I will send you a snap shot. The current code gets all the
blobs, tree and commits into a pack via fast-import, but the trees not
being generated correctly for complex branching when there are issues
with the symbols in CVS.
--
Jon Smirl
jonsmirl@gmail.com
^ permalink raw reply
* git-fsck-objects: lacking default references should not be fatal
From: Linus Torvalds @ 2006-08-29 18:47 UTC (permalink / raw)
To: Junio C Hamano, Git Mailing List
The comment added says it all: if we have lost all references in a git
archive, git-fsck-objects should still work, so instead of dying it should
just notify the user about that condition.
This change was triggered by me just doing a "git-init-db" and then
populating that empty git archive with a pack/index file to look at it.
Having git-fsck-objects not work just because I didn't have any references
handy was rather irritating, since part of the reason for running
git-fsck-objects in the first place was to _find_ the missing references.
However, "--unreachable" really doesn't make sense in that situation, and
we want to turn it off to protect anybody who uses the old "git prune"
shell-script (rather than the modern built-in). The old pruning script
used to remove all objects that were reported as unreachable, and without
any refs, that obviously means everything - not worth it.
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
---
diff --git a/fsck-objects.c b/fsck-objects.c
index ae0ec8d..24286de 100644
--- a/fsck-objects.c
+++ b/fsck-objects.c
@@ -425,8 +425,23 @@ static int fsck_handle_ref(const char *r
static void get_default_heads(void)
{
for_each_ref(fsck_handle_ref);
- if (!default_refs)
- die("No default references");
+
+ /*
+ * Not having any default heads isn't really fatal, but
+ * it does mean that "--unreachable" no longer makes any
+ * sense (since in this case everything will obviously
+ * be unreachable by definition.
+ *
+ * Showing dangling objects is valid, though (as those
+ * dangling objects are likely lost heads).
+ *
+ * So we just print a warning about it, and clear the
+ * "show_unreachable" flag.
+ */
+ if (!default_refs) {
+ error("No default references");
+ show_unreachable = 0;
+ }
}
static void fsck_object_dir(const char *path)
^ permalink raw reply related
* Re: Why do base objects appear behind the delta in packs?
From: Shawn Pearce @ 2006-08-29 18:32 UTC (permalink / raw)
To: Nicolas Pitre; +Cc: git
In-Reply-To: <Pine.LNX.4.64.0608291410290.9796@xanadu.home>
Nicolas Pitre <nico@cam.org> wrote:
> I look forward to being able to use your (and Jon's) fast-import work in
> order to play with (re)generation of big packs myself.
My repository is here:
http://www.spearce.org/projects/scm/git.git
branch 'refs/heads/sp/fastpack'.
I'd appreciate it if folks didn't clone directly from me but instead
used an existing clone to pull the branch down into. Its based on
a fairly recent 'next' branch. Anything not available via Junio's
'next' on kernel.org is loose objects in this repository and are
specific to my fast-import work.
Documentation of the protocol used to stuff a pack is in the
header of fast-import.c. Its a relatively trivial stream format.
It should be quite simple to generate a random large project and
pipe it into fast-import to get a resulting pack to play with.
I don't have Jon's cvs2svn code and I don't know if its ready for
public consumption yet. git-fast-import however looks like its
almost there, so I'm making the URL publicly available for those
that may be interested in it.
[Junio: please do the lazy thing and don't pull this into Git just
yet, I don't think this branch is ready for that, not even for pu.]
--
Shawn.
^ permalink raw reply
* Re: Why do base objects appear behind the delta in packs?
From: Nicolas Pitre @ 2006-08-29 18:16 UTC (permalink / raw)
To: Shawn Pearce; +Cc: git
In-Reply-To: <20060829174448.GD21729@spearce.org>
On Tue, 29 Aug 2006, Shawn Pearce wrote:
> So I'm probably going to wind up spending some time doing research
> and experimentation on pack storage. I may just discover we're
> as good as we can get. Or I may find that doing something else
> saves us only 5% at the cost of far too much complexity and thus
> isn't really worth doing. Or I may get lucky and discover a way
> to improve on what we have.
I'm periodically looking for improvements on packing performances
myself.
I look forward to being able to use your (and Jon's) fast-import work in
order to play with (re)generation of big packs myself.
Nicolas
^ permalink raw reply
* Re: Why do base objects appear behind the delta in packs?
From: Shawn Pearce @ 2006-08-29 17:44 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <7v8xl7moo7.fsf@assigned-by-dhcp.cox.net>
Junio C Hamano <junkio@cox.net> wrote:
> Shawn Pearce <spearce@spearce.org> writes:
>
> >> 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.
> >...
> > 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.
>
> I think that may be a sensible thing to do (no sarcasm -- I
> think this measurement is long overdue).
>
> The code was initially proposed just like you suggested but is
> in the current form precisely for the reason of avoiding
> back-seek. I distinctly remember me asking Linus "does mmap()
> favor forward scan by doing readahead? I thought its point was
> to allow random access" (the answer is "yes" and "yes but
> forward is the common case").
>
> The pack-using side in sha1_file.c used to read deltified object
> (both header and delta) in full, pick up and read base, and
> apply delta to base. This was thought to be memory hungry on a
> longer delta chain, so the current code reads only the header of
> a deltified object, reads base, then reads the delta to apply.
> The last step involves seeking back, and might make the
> back-seek avoidance less effective than before.
Thank you. That was the sort of response I was looking for. :-)
I know Jon wants to shrink that ~500 MB Mozilla pack to something
a lot smaller, and I'd like to help him do that without losing huge
amounts of performance on the read. Very long delta chains (5000!)
are simply impossible to wade through for even one object; doing it
for an entire commit to checkout the files is something I wouldn't
want to wish on anyone.
So I'm probably going to wind up spending some time doing research
and experimentation on pack storage. I may just discover we're
as good as we can get. Or I may find that doing something else
saves us only 5% at the cost of far too much complexity and thus
isn't really worth doing. Or I may get lucky and discover a way
to improve on what we have.
More on this thread (maybe) in a few months. I have other stuff
I should be doing right now. :)
--
Shawn.
^ permalink raw reply
* Re: Why do base objects appear behind the delta in packs?
From: Junio C Hamano @ 2006-08-29 17:34 UTC (permalink / raw)
To: Shawn Pearce; +Cc: git
In-Reply-To: <20060829162747.GA21729@spearce.org>
Shawn Pearce <spearce@spearce.org> writes:
>> 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.
>...
> 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.
I think that may be a sensible thing to do (no sarcasm -- I
think this measurement is long overdue).
The code was initially proposed just like you suggested but is
in the current form precisely for the reason of avoiding
back-seek. I distinctly remember me asking Linus "does mmap()
favor forward scan by doing readahead? I thought its point was
to allow random access" (the answer is "yes" and "yes but
forward is the common case").
The pack-using side in sha1_file.c used to read deltified object
(both header and delta) in full, pick up and read base, and
apply delta to base. This was thought to be memory hungry on a
longer delta chain, so the current code reads only the header of
a deltified object, reads base, then reads the delta to apply.
The last step involves seeking back, and might make the
back-seek avoidance less effective than before.
^ permalink raw reply
* Re: Why do base objects appear behind the delta in packs?
From: Shawn Pearce @ 2006-08-29 16:27 UTC (permalink / raw)
To: Jakub Narebski; +Cc: git
In-Reply-To: <ed1kn3$c3r$1@sea.gmane.org>
Jakub Narebski <jnareb@gmail.com> wrote:
> 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?
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.
^ permalink raw reply
* Re: Why do base objects appear behind the delta in packs?
From: Jakub Narebski @ 2006-08-29 14:58 UTC (permalink / raw)
To: git
In-Reply-To: <20060829134233.GA21335@spearce.org>
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
^ permalink raw reply
* Re: Why do base objects appear behind the delta in packs?
From: Nicolas Pitre @ 2006-08-29 14:40 UTC (permalink / raw)
To: Shawn Pearce; +Cc: git
In-Reply-To: <20060829134233.GA21335@spearce.org>
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.
> >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
^ permalink raw reply
* Why do base objects appear behind the delta in packs?
From: Shawn Pearce @ 2006-08-29 13:42 UTC (permalink / raw)
To: git
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;
}
^ permalink raw reply related
* Re: Starting to think about sha-256?
From: Florian Weimer @ 2006-08-29 6:17 UTC (permalink / raw)
To: git
In-Reply-To: <44F1DCB7.6020804@garzik.org>
* Jeff Garzik:
> * likely more CPU cycles per hash, though I haven't measured.
According to a quick test using "openssl speed", it's a factor of two
to four, depending on the input size (the difference is less
pronounced for small input sizes).
> Maybe sha-256 could be considered for the next major-rev of git?
And in 2008, you'd have to rewrite history again, to use the next
"stronger" hash function? Do you think that's really necessary or
desirable? Most users will have good control over what data enters
their repositories, so they can spot the evil twins thanks to their
high-entropy contents. Obviously, a second preimage attack would
mattr, but even for MD5, we aren't close to that one AFAIK.
^ permalink raw reply
* Re: [PATCH] Add a newline before appending "Signed-off-by: " line
From: Franck Bui-Huu @ 2006-08-29 11:37 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git, Franck Bui-Huu, Linus Torvalds
In-Reply-To: <7vr6zkjmeq.fsf@assigned-by-dhcp.cox.net>
Junio,
Sorry for replying sooooooo lately.
Junio C Hamano wrote:
> From: Franck Bui-Huu <vagabon.xyz@gmail.com>
>
> Whef the last line of the commit log message does not end with
> "^[-A-Za-z]+: [^@]+@", append a newline after it to separate
> the body of the commit log message from the run of sign-off and
> ack lines. e.g. "Signed-off-by: A U Thor <au.thor@example.com>" or
> "Acked-by: Me <myself@example.org>".
>
> Signed-off-by: Junio C Hamano <junkio@cox.net>
what about this patch on top of yours ?
Franck
-- >8 --
Subject: log-tree.c: cleanup a bit append_signoff()
This patch clean up append_signoff() by moving specific code that
looks up for "^[-A-Za-z]+: [^@]+@" pattern into a function.
It also stops the primary search when the cursor oversteps
'buf + at' limit.
This patch changes slightly append_signoff() behaviour too. If we
detect any Signed-off-by pattern during the primary search, we
needn't to do a pattern research after.
Signed-off-by: Franck Bui-Huu <vagabon.xyz@gmail.com>
---
log-tree.c | 116 ++++++++++++++++++++++++++++++++++--------------------------
1 files changed, 66 insertions(+), 50 deletions(-)
diff --git a/log-tree.c b/log-tree.c
index 54cdaa4..36f0d75 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -12,10 +12,58 @@ static void show_parents(struct commit *
}
}
+/*
+ * Search for "^[-A-Za-z]+: [^@]+@" pattern. It usually matches
+ * Signed-off-by: and Acked-by: lines.
+ */
+static int detect_any_signoff(char *letter, int size)
+{
+ char ch, *cp;
+ int seen_colon = 0;
+ int seen_at = 0;
+ int seen_name = 0;
+ int seen_head = 0;
+
+ cp = letter + size;
+ while (letter <= --cp && (ch = *cp) == '\n')
+ continue;
+
+ while (letter <= cp) {
+ ch = *cp--;
+ if (ch == '\n')
+ break;
+
+ if (!seen_at) {
+ if (ch == '@')
+ seen_at = 1;
+ continue;
+ }
+ if (!seen_colon) {
+ if (ch == '@')
+ return 0;
+ else if (ch == ':')
+ seen_colon = 1;
+ else
+ seen_name = 1;
+ continue;
+ }
+ if (('A' <= ch && ch <= 'Z') ||
+ ('a' <= ch && ch <= 'z') ||
+ ch == '-') {
+ seen_head = 1;
+ continue;
+ }
+ /* no empty last line doens't match */
+ return 0;
+ }
+ return seen_head && seen_name;
+}
+
static int append_signoff(char *buf, int buf_sz, int at, const char *signoff)
{
- int signoff_len = strlen(signoff);
static const char signed_off_by[] = "Signed-off-by: ";
+ int signoff_len = strlen(signoff);
+ int has_signoff = 0;
char *cp = buf;
/* Do we have enough space to add it? */
@@ -23,58 +71,26 @@ static int append_signoff(char *buf, int
return at;
/* First see if we already have the sign-off by the signer */
- while (1) {
- cp = strstr(cp, signed_off_by);
- if (!cp)
- break;
+ while ((cp = strstr(cp, signed_off_by))) {
+
+ has_signoff = 1;
+
cp += strlen(signed_off_by);
- if ((cp + signoff_len < buf + at) &&
- !strncmp(cp, signoff, signoff_len) &&
- isspace(cp[signoff_len]))
- return at; /* we already have him */
+ if (cp + signoff_len >= buf + at)
+ break;
+ if (strncmp(cp, signoff, signoff_len))
+ continue;
+ if (!isspace(cp[signoff_len]))
+ continue;
+ /* we already have him */
+ return at;
}
- /* Does the last line already end with "^[-A-Za-z]+: [^@]+@"?
- * If not, add a blank line to separate the message from
- * the run of Signed-off-by: and Acked-by: lines.
- */
- {
- char ch;
- int seen_colon, seen_at, seen_name, seen_head, not_signoff;
- seen_colon = 0;
- seen_at = 0;
- seen_name = 0;
- seen_head = 0;
- not_signoff = 0;
- cp = buf + at;
- while (buf <= --cp && (ch = *cp) == '\n')
- ;
- while (!not_signoff && buf <= cp && (ch = *cp--) != '\n') {
- if (!seen_at) {
- if (ch == '@')
- seen_at = 1;
- continue;
- }
- if (!seen_colon) {
- if (ch == '@')
- not_signoff = 1;
- else if (ch == ':')
- seen_colon = 1;
- else
- seen_name = 1;
- continue;
- }
- if (('A' <= ch && ch <= 'Z') ||
- ('a' <= ch && ch <= 'z') ||
- ch == '-') {
- seen_head = 1;
- continue;
- }
- not_signoff = 1;
- }
- if (not_signoff || !seen_head || !seen_name)
- buf[at++] = '\n';
- }
+ if (!has_signoff)
+ has_signoff = detect_any_signoff(buf, at);
+
+ if (!has_signoff)
+ buf[at++] = '\n';
strcpy(buf + at, signed_off_by);
at += strlen(signed_off_by);
--
1.4.2
^ permalink raw reply related
* [PATCH] Remove uneeded #include
From: Johannes Schindelin @ 2006-08-29 11:02 UTC (permalink / raw)
To: git, junkio
Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
---
peek-remote.c | 1 -
receive-pack.c | 1 -
2 files changed, 0 insertions(+), 2 deletions(-)
diff --git a/peek-remote.c b/peek-remote.c
index 2b30980..87f1543 100644
--- a/peek-remote.c
+++ b/peek-remote.c
@@ -1,7 +1,6 @@
#include "cache.h"
#include "refs.h"
#include "pkt-line.h"
-#include <sys/wait.h>
static const char peek_remote_usage[] =
"git-peek-remote [--exec=upload-pack] [host:]directory";
diff --git a/receive-pack.c b/receive-pack.c
index 2015316..78f75da 100644
--- a/receive-pack.c
+++ b/receive-pack.c
@@ -2,7 +2,6 @@ #include "cache.h"
#include "refs.h"
#include "pkt-line.h"
#include "run-command.h"
-#include <sys/wait.h>
static const char receive_pack_usage[] = "git-receive-pack <git-dir>";
--
1.4.2.ga16ff-dirty
^ permalink raw reply related
* [PATCH] Makefile: fix typo
From: Johannes Schindelin @ 2006-08-29 10:51 UTC (permalink / raw)
To: git, junkio
We checked NO_SETENV instead of NO_UNSETENV to decide if unsetenv
is available.
Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
---
Makefile | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/Makefile b/Makefile
index 19d62ee..ff1ec6e 100644
--- a/Makefile
+++ b/Makefile
@@ -524,7 +524,7 @@ ifdef NO_SETENV
COMPAT_CFLAGS += -DNO_SETENV
COMPAT_OBJS += compat/setenv.o
endif
-ifdef NO_SETENV
+ifdef NO_UNSETENV
COMPAT_CFLAGS += -DNO_UNSETENV
COMPAT_OBJS += compat/unsetenv.o
endif
--
1.4.2.g0f6b-dirty
^ permalink raw reply related
* [PATCH] unpack-objects: remove unused variable "eof"
From: Johannes Schindelin @ 2006-08-29 10:50 UTC (permalink / raw)
To: git, junkio
Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
---
builtin-unpack-objects.c | 4 +---
1 files changed, 1 insertions(+), 3 deletions(-)
diff --git a/builtin-unpack-objects.c b/builtin-unpack-objects.c
index ca0ebc2..0c180b5 100644
--- a/builtin-unpack-objects.c
+++ b/builtin-unpack-objects.c
@@ -15,7 +15,7 @@ static const char unpack_usage[] = "git-
/* We always read in 4kB chunks. */
static unsigned char buffer[4096];
-static unsigned long offset, len, eof;
+static unsigned long offset, len;
static SHA_CTX ctx;
/*
@@ -26,8 +26,6 @@ static void * fill(int min)
{
if (min <= len)
return buffer + offset;
- if (eof)
- die("unable to fill input");
if (min > sizeof(buffer))
die("cannot fill %d bytes", min);
if (offset) {
--
1.4.2.g0f6b-dirty
^ permalink raw reply related
* Re: [PATCH] gitweb: Add local time and timezone to git_print_authorship
From: Jakub Narebski @ 2006-08-29 10:15 UTC (permalink / raw)
To: git
In-Reply-To: <7vu03voqss.fsf@assigned-by-dhcp.cox.net>
Junio C Hamano wrote:
> (3) I'd like to eventually get rid of the abbreviated commit
> object name from blame output, so the setting in gitweb.css
> for table.blame td.age[012] (different colors and font
> styles) is not appropriate for what I am shooting at.
What do you want to replace it with? Link can be to "commit" or "commitdiff"
view, but some marker for commit (perhaps 'git-name-rev --tags'?) is
needed.
--
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git
^ permalink raw reply
* Re: [PATCH] Check if pack directory exists prior to descending into it
From: Junio C Hamano @ 2006-08-29 9:17 UTC (permalink / raw)
To: Matthias Kestenholz; +Cc: git
In-Reply-To: <20060829091214.GA10155@spinlock.ch>
Makes sense. Thanks.
^ permalink raw reply
* [PATCH] Check if pack directory exists prior to descending into it
From: Matthias Kestenholz @ 2006-08-29 9:12 UTC (permalink / raw)
To: junkio, git
This fixes the following warning:
git-repack: line 42: cd: .git/objects/pack: No such file or directory
This happens only, when git-repack -a is run without any packs in the
repository.
Signed-off-by: Matthias Kestenholz <matthias@spinlock.ch>
---
git-repack.sh | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/git-repack.sh b/git-repack.sh
index 9da92fb..584a732 100755
--- a/git-repack.sh
+++ b/git-repack.sh
@@ -38,7 +38,7 @@ case ",$all_into_one," in
pack_objects=
# Redundancy check in all-into-one case is trivial.
- existing=`cd "$PACKDIR" && \
+ existing=`test -d "$PACKDIR" && cd "$PACKDIR" && \
find . -type f \( -name '*.pack' -o -name '*.idx' \) -print`
;;
esac
--
1.4.2.g2f76
^ permalink raw reply related
* [PATCH] gitweb: show age and author in blame output
From: Junio C Hamano @ 2006-08-29 9:07 UTC (permalink / raw)
To: Jakub Narebski; +Cc: git
The commit object name link on each link uses "title", which
shows the author and age of the particular line when hovered
over.
The background of these links are painted on darker color as
they become older and the links on younger lines are shown on
lighter background.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
gitweb/gitweb.css | 6 ++++++
gitweb/gitweb.perl | 27 +++++++++++++++++++++++----
2 files changed, 29 insertions(+), 4 deletions(-)
diff --git a/gitweb/gitweb.css b/gitweb/gitweb.css
index eb9fc38..f3211c2 100644
--- a/gitweb/gitweb.css
+++ b/gitweb/gitweb.css
@@ -215,6 +215,12 @@ td.sha1 {
font-family: monospace;
}
+table.blame td.age-week { color: #0000ff; background-color: #ffffff; }
+table.blame td.age-month { color: #0000ff; background-color: #ddddee; }
+table.blame td.age-season { color: #0000ff; background-color: #bbbbdd; }
+table.blame td.age-year { color: #0000ff; background-color: #9999cc; }
+table.blame td.age-old { color: #0000ff; background-color: #7777bb; }
+
td.error {
color: red;
background-color: yellow;
diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index 5c82d3f..0265a82 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -2171,12 +2171,26 @@ sub git_tag {
}
sub flush_blame_lines {
- my ($color, $file_name, @line) = @_;
+ my ($color, $file_name, $now, @line) = @_;
my $full_rev = shift @line;
+
+ my ($author, $timestamp, $zone) =
+ ($line[0] =~
+ /^[0-9a-f]{40}\s\((.*?)\s+(\d+)\s([-+\d]{5})\s+\d+\)/);
+ my $age = $now - $timestamp;
+ my $ago = age_string($age);
+ my $pop = 'title="' . esc_html("$author, $ago") . '"';
+ my $agegroup =
+ (($age < 60*60*24*7) ? "age-week" :
+ ($age < 60*60*24*30) ? "age-month" :
+ ($age < 60*60*24*120) ? "age-season" :
+ ($age < 60*60*24*360) ? "age-year" : "age-old");
+
my $rev = substr($full_rev, 0, 8);
my $cnt = scalar @line;
my $this = 0;
+
for (@line) {
$this++;
unless (/^[0-9a-fA-F]{40}.*?(\d+)\)\s(.*)/) {
@@ -2188,11 +2202,12 @@ sub flush_blame_lines {
print "<tr class=\"$color\">\n";
if ($this == 1) {
+ my $cls = "class=\"sha1 $agegroup\"";
if (1 < $cnt) {
- print "<td class=\"sha1\" rowspan=\"$cnt\">";
+ print "<td $cls $pop rowspan=\"$cnt\">";
}
else {
- print "<td class=\"sha1\">";
+ print "<td $cls $pop>";
}
print $cgi->a({-href => href(action=>"commit",
hash=>$full_rev,
@@ -2228,7 +2243,8 @@ sub git_blame2 {
if ($ftype !~ "blob") {
die_error("400 Bad Request", "Object is not a blob");
}
- open ($fd, "-|", git_cmd(), "blame", '-l', $file_name, $hash_base)
+ open ($fd, "-|", git_cmd(), "blame", '-l', '-t',
+ $file_name, $hash_base)
or die_error(undef, "Open git-blame failed");
git_header_html();
my $formats_nav =
@@ -2242,6 +2258,7 @@ sub git_blame2 {
git_print_page_path($file_name, $ftype, $hash_base);
my @rev_color = (qw(light2 dark2));
my $num_colors = scalar(@rev_color);
+ my $now = time();
my $current_color = 0;
my @current_group = ();
print <<HTML;
@@ -2260,6 +2277,7 @@ HTML
$current_color = ++$current_color % $num_colors;
flush_blame_lines($rev_color[$current_color],
$file_name,
+ $now,
@current_group);
}
else {
@@ -2273,6 +2291,7 @@ HTML
$current_color = ++$current_color % $num_colors;
flush_blame_lines($rev_color[$current_color],
$file_name,
+ $now,
@current_group);
}
print "</table>\n";
--
1.4.2.g39ee
^ permalink raw reply related
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox