* Re: gitview: Use monospace font to draw the branch and tag name
From: Aneesh Kumar @ 2006-02-25 7:00 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <7vzmkg6kj7.fsf@assigned-by-dhcp.cox.net>
On 2/25/06, Junio C Hamano <junkio@cox.net> wrote:
>
> >> I have an impression that hardcoding UI policy like this is
> >> generally frowned upon.
> >
> > But with that changes branch and the tag name looks neat.
>
> The point being that it only looks neat on your display, with
> its size and resolution, and to your eye.
>
> People have different tastes and equipments. One thing I really
> liked gitk (I do not know if gitview does this as well -- if so
> I am happy) is I can do - and + to change the text size
> depending on what display I am working on.
>
>
Point taken. Right now gitview doesn't support + and - key binding. I
will try to add that. For the time being can you can drop my font and
font size related changes and apply rest of the patches.
-aneesh
^ permalink raw reply
* Re: [PATCH] git-rm: Fix to properly handle files with spaces, tabs, newlines, etc.
From: Junio C Hamano @ 2006-02-25 6:05 UTC (permalink / raw)
To: Alex Riesen; +Cc: git, Carl Worth, Krzysiek Pawlik
In-Reply-To: <81b0412b0602240523l1b10c910q6e5d2e3cef82e306@mail.gmail.com>
"Alex Riesen" <raa.lkml@gmail.com> writes:
> On 2/23/06, Carl Worth <cworth@cworth.org> wrote:
>> +# Setup some files to be removed, some with funny characters
>> +touch -- foo bar baz 'space embedded' 'tab embedded' 'newline
>> +embedded' -q
>> +git-add -- foo bar baz 'space embedded' 'tab embedded' 'newline
>> +embedded' -q
>> +git-commit -m "add files"
>
> This doesn't work on some exotic filesystems (ntfs and fat):
Sorry to have applied this without thinking. Yes, we had
disabled a test that uses tab for this exact reason, but I have
forgotten about it.
^ permalink raw reply
* Re: gitview: Use monospace font to draw the branch and tag name
From: Junio C Hamano @ 2006-02-25 6:05 UTC (permalink / raw)
To: Aneesh Kumar; +Cc: git
In-Reply-To: <cc723f590602240829y3ebffaf9mdd7de0cd2a9051e@mail.gmail.com>
"Aneesh Kumar" <aneesh.kumar@gmail.com> writes:
> On 2/24/06, Junio C Hamano <junkio@cox.net> wrote:
>> "Aneesh Kumar K.V" <aneesh.kumar@gmail.com> writes:
>>
>> > This patch address the below:
>> > Use monospace font to draw branch and tag name
>> > set the font size to 13.
>>
>> I have an impression that hardcoding UI policy like this is
>> generally frowned upon.
>
> But with that changes branch and the tag name looks neat.
The point being that it only looks neat on your display, with
its size and resolution, and to your eye.
People have different tastes and equipments. One thing I really
liked gitk (I do not know if gitview does this as well -- if so
I am happy) is I can do - and + to change the text size
depending on what display I am working on.
^ permalink raw reply
* Re: FYI: git-am allows creation of empty commits.
From: Junio C Hamano @ 2006-02-25 6:04 UTC (permalink / raw)
To: Eric Wong; +Cc: Eric W. Biederman, git, Martin Langhoff, Matthias Urlichs
In-Reply-To: <20060224131922.GA19401@localdomain>
Eric Wong <normalperson@yhbt.net> writes:
>> I think 99.9% of the time it is a mistake if a single-parented
>> commit has the same tree as its parent commit has, so having a
>> check in commit-tree may not be a bad idea.
>
> This would break importers, more than 0.1% I think... Arch
> definitely allows empty commits for getting log messages in.
> SVN forbids them from their POV, but they also have things
> that we can't see when we import (properties like: mime,
> externals, eol-style) causing us to write the same tree twice.
> Not sure about CVS...
>
> Maybe a flag such as --force could be added.
Good point perhaps. Maybe an explicit --no-empty should ask for
it, and git-am should use it. As to git-commit I am unsure.
In the meantime I'd drop the patch.
^ permalink raw reply
* Re: [PATCH] diff-delta: produce optimal pack data
From: Nicolas Pitre @ 2006-02-25 5:35 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, git, Carl Baldwin
In-Reply-To: <Pine.LNX.4.64.0602242326381.31162@localhost.localdomain>
OOps.... Forgot to complete one paragraph.
On Sat, 25 Feb 2006, Nicolas Pitre wrote:
> I of course looked at the time to pack vs the size reduction in my
> tests. And really like I said above the cost is well balanced. The
> only issue is that smaller blocks are more likely to trap into
> patological data sets. But that problem does exist with larger blocks
> too, to a lesser degree of course but still. For example, using a 16
> block size with adler32, computing a delta between two files
... as provided by Carl takes up to _nine_ minutes for a _single_ delta !
So regardless of the block size used, the issue right now has more to do
with that combinatorial explosion than the actual block size. And
preventing that patological case from expending out of bounds is pretty
easy to do.
OK I just tested a tentative patch to trap that case and the time to
delta those two 20MB files passed from over 9 minutes to only 36 seconds
here, with less than 10% in delta size difference. So I think I might
be on the right track. Further tuning might help even further.
Nicolas
^ permalink raw reply
* Re: [PATCH] diff-delta: produce optimal pack data
From: Nicolas Pitre @ 2006-02-25 5:10 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, git, Carl Baldwin
In-Reply-To: <Pine.LNX.4.64.0602241952140.22647@g5.osdl.org>
On Fri, 24 Feb 2006, Linus Torvalds wrote:
>
>
> On Fri, 24 Feb 2006, Nicolas Pitre wrote:
> >
> > Well, that's the compromize to make. By default the version with
> > adler32 used 16 byte blocks to index the reference buffer. That means
> > you can match target data against the reference only if whole 16 byte
> > blocks match. Then, if you fix a typo in the target buffer then you'll
> > inevitably need 16 literal bytes in the delta instead of only
> > one because you won't be able to resynchronize with the reference buffer
> > until the next 16 byte block.
>
> That shouldn't be true. Once you find a 16-byte match, you can search
> forward (in theory you should be able to search backwards too, but by that
> time we've already expanded the non-matching previous bytes, I think).
Obviously, but that's not my point. What I mean is that small changes
will kind of sabotage the match since you'll have to scan forward
(adding literal bytes to the delta output in the mean time) until you
find another 16 byte block that matches. This is harder to find than a
3 byte block. Hence you'll end up adding more literal bytes (up to 16
of them) until you can match the reference buffer again even if you only
flipped one byte in the target buffer. In some cases that makes up for
deltas that are twice as large.
> > What I've made in my last delta patch is to reduce that 16 byte block to
> > only 3 bytes. Why 3 bytes? Because less than that produces smaller
> > delta data if done with literal bytes directly, and 3 bytes provided
> > enough bits to hash.
>
> On the other hand, the cost is that your lookups _are_ going to be more
> expensive. Regardless of how good the hash is, basically you have 16/3
> more hash-entries to look up, so you've made compression more expensive in
> footprint, at least (I assume you've made the hash appropriately larger).
Yes, the hash is larger. There is a cost in memory usage but not really
in CPU cycles.
> Also, at 3 bytes, insertion is at least equally dense (three bytes of data
> vs three bytes of offset into the source), and can be worse (the offset
> might be 5 bytes, no?). So it would seem like you'd be better off with 4+
> bytes, at which point the delta should be a win.
The code already discriminate the space of a block copy notation given
the offset and size vs the space for the equivalent literal bytes. So
the optimal encoding is always chosen already.
In fact, if you want to copy up to 15 bytes from offset 0 that will be
encoded with only 2 bytes in the delta. The only case that is
suboptimal is when you want to copy only two bytes from offset 0 (2
delta bytes) but only two bytes is mever matched by the hash lookup
since the hash is computed with 3 bytes. In that case 2 literal bytes
will be added to the delta plus opcode = 3 bytes. I considered that
special case not worth it. However copying a block of 3 bytes that gets
encoded into 3 bytes of delta is quite common (that'd take 4 bytes of
delta if they were literals).
As for using more bytes for block hashing, that increase thenumber of
cycles to compute the hash. The adler32 version reads 16 bytes for
every byte offset in the target file while my latest version only reads
3 bytes for every byte offset. So in effect my target hash computation
is faster than the adler32 one. However there is potentially more
entries in the same hash bucket to validate especially with repetitive
data.
> Have you tried some half-way point, like ~8 bytes?
Yes, and while the needed cycles tend to remain the same on average, the
resulting pack gets larger.
> > Now the problem comes when indexing a reference file full of:
> >
> > 0x46f8, 0x000b, 0x42fe, 0x0000, 0xffc0, 0x0001, 0xff00, 0x0008,
> ...
> >
> > There is a bunch of ", 0x" that get hashed to the same thing.
>
> You'll find a lot of that in any file: three or four bytes of similarity
> just doesn't sound worthwhile to go digging after.
Well after having experimented a lot with multiple parameters I think
they are worth it after all. Not only they provide for optimal deltas,
but their hash is faster to compute than larger blocks which seems to
counter balance for the cost of increased hash list.
> > The adler32 made that particular example a non issue since the
> > likelyhood of many 16 byte blocks to be the same is pretty low in this
> > case. But the flaw remains if for example there is lots of similar 16
> > byte blocks, like a binary file with lots of zeroes for example. In
> > fact, the performance problem Carl is having does use the diff-delta
> > version still using adler32.
>
> Agreed. I think limiting the hash length is a fine idea regardless, I just
> think it sounds dangerous with the three-byte thing where a lot of matches
> should be expected (never mind ", 0x", just things like newlines and tabs
> in source code).
They are usually less than the number of lines. Yet if you have a 1000
line source file and let's suppose that we keep only 50 hashed "\n\t\t"
this is sufficient to provide enough opportunities for matching that
plus common patterns like a following "if (" for example.
> Only considering 16-byte sequences of similarities is a trade-off of
> packing cost vs win.. Not saying other block-sizes aren't worth testing,
> but I suspect trying too hard is going to be too costly.
I of course looked at the time to pack vs the size reduction in my
tests. And really like I said above the cost is well balanced. The
only issue is that smaller blocks are more likely to trap into
patological data sets. But that problem does exist with larger blocks
too, to a lesser degree of course but still. For example, using a 16
block size with adler32, computing a delta between two files
> Especially as deltas compress _worse_ the smaller they are. Bigger
> "insert" chunks probably compress a lot better than a copy chunk.
Yes, but given that we favor deltas from larger to smaller already those
inserts are already not making much differences. They have to be quite
large to effectively provide better zlib compression.
> Have you looked at the delta size vs compression?
That's certainly an additional test worth adding to try_delta().
max_size should be smaller than the original object deflated size making
sure we won't store deltas that might end up larger than the undeltified
object.
Nicolas
^ permalink raw reply
* Re: [PATCH] diff-delta: produce optimal pack data
From: Linus Torvalds @ 2006-02-25 4:05 UTC (permalink / raw)
To: Nicolas Pitre; +Cc: Junio C Hamano, git, Carl Baldwin
In-Reply-To: <Pine.LNX.4.64.0602242130030.31162@localhost.localdomain>
On Fri, 24 Feb 2006, Nicolas Pitre wrote:
>
> Well, that's the compromize to make. By default the version with
> adler32 used 16 byte blocks to index the reference buffer. That means
> you can match target data against the reference only if whole 16 byte
> blocks match. Then, if you fix a typo in the target buffer then you'll
> inevitably need 16 literal bytes in the delta instead of only
> one because you won't be able to resynchronize with the reference buffer
> until the next 16 byte block.
That shouldn't be true. Once you find a 16-byte match, you can search
forward (in theory you should be able to search backwards too, but by that
time we've already expanded the non-matching previous bytes, I think).
But I'm no xdelta expert, so I migt be wrong.
> What I've made in my last delta patch is to reduce that 16 byte block to
> only 3 bytes. Why 3 bytes? Because less than that produces smaller
> delta data if done with literal bytes directly, and 3 bytes provided
> enough bits to hash.
On the other hand, the cost is that your lookups _are_ going to be more
expensive. Regardless of how good the hash is, basically you have 16/3
more hash-entries to look up, so you've made compression more expensive in
footprint, at least (I assume you've made the hash appropriately larger).
Also, at 3 bytes, insertion is at least equally dense (three bytes of data
vs three bytes of offset into the source), and can be worse (the offset
might be 5 bytes, no?). So it would seem like you'd be better off with 4+
bytes, at which point the delta should be a win.
Have you tried some half-way point, like ~8 bytes?
> Now the problem comes when indexing a reference file full of:
>
> 0x46f8, 0x000b, 0x42fe, 0x0000, 0xffc0, 0x0001, 0xff00, 0x0008,
...
>
> There is a bunch of ", 0x" that get hashed to the same thing.
You'll find a lot of that in any file: three or four bytes of similarity
just doesn't sound worthwhile to go digging after.
> The adler32 made that particular example a non issue since the
> likelyhood of many 16 byte blocks to be the same is pretty low in this
> case. But the flaw remains if for example there is lots of similar 16
> byte blocks, like a binary file with lots of zeroes for example. In
> fact, the performance problem Carl is having does use the diff-delta
> version still using adler32.
Agreed. I think limiting the hash length is a fine idea regardless, I just
think it sounds dangerous with the three-byte thing where a lot of matches
should be expected (never mind ", 0x", just things like newlines and tabs
in source code).
Only considering 16-byte sequences of similarities is a trade-off of
packing cost vs win.. Not saying other block-sizes aren't worth testing,
but I suspect trying too hard is going to be too costly.
Especially as deltas compress _worse_ the smaller they are. Bigger
"insert" chunks probably compress a lot better than a copy chunk.
Have you looked at the delta size vs compression?
Linus
^ permalink raw reply
* Re: [PATCH] diff-delta: produce optimal pack data
From: Nicolas Pitre @ 2006-02-25 3:53 UTC (permalink / raw)
To: Carl Baldwin; +Cc: Junio C Hamano, git
In-Reply-To: <20060224225023.GA28538@hpsvcnb.fc.hp.com>
On Fri, 24 Feb 2006, Carl Baldwin wrote:
> > If you can add them into a single .tgz with instructions on how
> > to reproduce the issue and provide me with an URL where I can fetch it
> > that'd be perfect.
>
> I will do this in an email off of the list because these files really
> shouldn't be available on a public list.
OK I have the files, and I can confirm that your problem is of the same
combinatorial explosion type I already talked about, _even_ with the
version using adler32. This is really O(m*n) where m and n being the
size of two consecutive versions of the files. But since m and n are
both _huge_ then the delta code really goes out to lunch.
I'm working on a patch to cap this to something like O(m+n).
Stay tuned.
Nicolas
^ permalink raw reply
* Re: [PATCH] diff-delta: produce optimal pack data
From: Nicolas Pitre @ 2006-02-25 3:07 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, git, Carl Baldwin
In-Reply-To: <Pine.LNX.4.64.0602241637480.22647@g5.osdl.org>
On Fri, 24 Feb 2006, Linus Torvalds wrote:
>
>
> On Fri, 24 Feb 2006, Nicolas Pitre wrote:
> >
> > Currently, diff-delta takes blocks of data in the reference file and
> > hash them. When the target file is scanned, it uses the hash to match
> > blocks from the target file with the reference file.
> >
> > If blocks are hashed evenly the cost of producing a delta is at most
> > O(n+m) where n and m are the size of the reference and target files
> > respectively. In other words, with good data set the cost is linear.
>
> Assuming the hash is good, of course.
>
> I think this was the problem with you trying something simpler than
> adler32..
Well, that's the compromize to make. By default the version with
adler32 used 16 byte blocks to index the reference buffer. That means
you can match target data against the reference only if whole 16 byte
blocks match. Then, if you fix a typo in the target buffer then you'll
inevitably need 16 literal bytes in the delta instead of only
one because you won't be able to resynchronize with the reference buffer
until the next 16 byte block.
What I've made in my last delta patch is to reduce that 16 byte block to
only 3 bytes. Why 3 bytes? Because less than that produces smaller
delta data if done with literal bytes directly, and 3 bytes provided
enough bits to hash. I also made those 3 byte blocks overlap so
indexing would start at any offset with byte precision. This really
allows for optimal deltas so that they cannot be smaller.
Now the problem comes when indexing a reference file full of:
0x46f8, 0x000b, 0x42fe, 0x0000, 0xffc0, 0x0001, 0xff00, 0x0008,
0x03e0, 0x0009, 0x0f01, 0x0003, 0x8072, 0x0000, 0x0400, 0x0000,
0x0046, 0x0003, 0x9180, 0x0001, 0x0003, 0x0008, 0x02eb, 0x0003,
0x8072, 0x0000, 0x0400, 0x0000, 0x8010, 0x0008, 0x0010, 0x0000,
0x0361, 0x0003, 0x037e, 0x0004, 0x3941, 0x0002, 0x0b0f, 0x0003,
0x8072, 0x0000, 0x0400, 0x0000, 0x000a, 0x000b, 0x0346, 0x000c,
0x11fe, 0x0000, 0x3717, 0x0003, 0x8072, 0x0000, 0x0400, 0x0000,
0x8010, 0x0008, 0x000e, 0x0000, 0x0361, 0x0003, 0x8060, 0x0000,
There is a bunch of ", 0x" that get hashed to the same thing. And when
the second phase i.e. trying to find the best match into the reference
buffer for each occurrence of the same many ", 0x" in the target buffer
you get a conbinatorial explosion.
The adler32 made that particular example a non issue since the
likelyhood of many 16 byte blocks to be the same is pretty low in this
case. But the flaw remains if for example there is lots of similar 16
byte blocks, like a binary file with lots of zeroes for example. In
fact, the performance problem Carl is having does use the diff-delta
version still using adler32.
> > But if many blocks from the reference buffer do hash to the same bucket
> > then for each block in the target file many blocks from the reference
> > buffer have to be tested against, making it tend towards O(n^m) which is
> > pretty highly exponential.
> >
> > The solution I'm investigating is to put a limit on the number of
> > entries in the same hash bucket so to bring the cost back to something
> > more linear. That means the delta might miss on better matches that
> > have not been hashed but still benefit from a limited set.
>
> Sounds fair enough.
Testing appear to show that this is a worthwhile safety valve. And in
most case that safety valve should not be activated at all.
> However, you migt also want to consider another approach..
>
> One of the biggest costs for the xdelta algorithm is probably just the
> "delta_prepare()", but at the same time, that is constant wrt the source
> buffer.
Actually it is not that costly. Much much less than computing the sha1
of the same buffer for example.
> Now, the sad part is that when I wrote pack-objects, I didn't really
> understand the diff-delta algorithm, I just plugged it in. Which means
> that when I did it, I made the (obvious and simple) decision to keep the
> _result_ that we are looking at constant, and try to delta against
> different sources.
>
> HOWEVER.
>
> I suspect you already see where this is going..
>
> We _could_ switch the "pack-objects" window handling around, and instead
> of looking at the object we want to pack, and looking at the ten (or
> "window") previous objects to delta against, we could do it the other way
> around: keep the object we delta against constant, and see what deltas we
> could prepare for the ten next objects.
>
> And since the source would now be constant, you'd need to do the
> "delta_prepare()" just _once_ per window, instead of every single time.
Might be worth trying. Actually, this can be tested without even
changing the window handling just yet, since diff-delta() could return
the index data instead of freeing it, and pack-objects can store it
along side with the object data it tries to delta against. That
wouldn't be memory efficient, but at least that would give an idea of
the magnitude of the saving on CPU time. But I really doubt that'll
save more than a few percent.
>
> Now, I haven't done any profiling on the diff-delta code, and maybe my
> guess that delta_prepare() is a pretty expensive part is wrong, and maybe
> it wouldn't help to switch the window probing around. But I thought I'd
> mention it as one thing to explore..
Just to give you an idea, the bulk of my current "prepare" code looks
like this:
/* then populate the index */
data = buf + bufsize - 2;
while (data > buf) {
entry->ptr = --data;
i = (data[0] << hshift) ^ data[1];
i ^= (i << hshift) ^ data[2];
entry->next = hash[i];
hash[i] = entry++;
}
As you can see it is pretty lightweight.
But that would probably be a worthwhile optimization to have even if it
saves 10% of CPU time.
Nicolas
^ permalink raw reply
* Re: git-annotate
From: Nicolas Vilz 'niv' @ 2006-02-25 1:21 UTC (permalink / raw)
To: GIT Mailing List
In-Reply-To: <118833cc0602240721s1c64219y161cc0536fb361e4@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 668 bytes --]
Morten Welinder wrote:
> git-annotate ought to call usage() if it doesn't get its file.
Full Ack.
>>git annotate
>
> Use of uninitialized value in open at
> /scratch/welinder/git/git-annotate line 40.
> Failed to open filename: No such file or directory at
> /scratch/welinder/git/git-annotate line 40.
oh yes, that was something, i slipped over today, didn't have the time
to report it myself.
additionally i got following with git-annotate --help
niv@hermes ~ $ git-annotate --help
/usr/bin/git-annotate version [unknown] calling Getopt::Std::getopts
(version 1.05 [paranoid]),
running under Perl version 5.8.8.
i don't know if that should happen so.
Nicolas
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]
^ permalink raw reply
* Re: [PATCH] diff-delta: produce optimal pack data
From: Linus Torvalds @ 2006-02-25 0:45 UTC (permalink / raw)
To: Nicolas Pitre; +Cc: Junio C Hamano, git, Carl Baldwin
In-Reply-To: <Pine.LNX.4.64.0602241613030.31162@localhost.localdomain>
On Fri, 24 Feb 2006, Nicolas Pitre wrote:
>
> Currently, diff-delta takes blocks of data in the reference file and
> hash them. When the target file is scanned, it uses the hash to match
> blocks from the target file with the reference file.
>
> If blocks are hashed evenly the cost of producing a delta is at most
> O(n+m) where n and m are the size of the reference and target files
> respectively. In other words, with good data set the cost is linear.
Assuming the hash is good, of course.
I think this was the problem with you trying something simpler than
adler32..
> But if many blocks from the reference buffer do hash to the same bucket
> then for each block in the target file many blocks from the reference
> buffer have to be tested against, making it tend towards O(n^m) which is
> pretty highly exponential.
>
> The solution I'm investigating is to put a limit on the number of
> entries in the same hash bucket so to bring the cost back to something
> more linear. That means the delta might miss on better matches that
> have not been hashed but still benefit from a limited set.
Sounds fair enough.
However, you migt also want to consider another approach..
One of the biggest costs for the xdelta algorithm is probably just the
"delta_prepare()", but at the same time, that is constant wrt the source
buffer.
Now, the sad part is that when I wrote pack-objects, I didn't really
understand the diff-delta algorithm, I just plugged it in. Which means
that when I did it, I made the (obvious and simple) decision to keep the
_result_ that we are looking at constant, and try to delta against
different sources.
HOWEVER.
I suspect you already see where this is going..
We _could_ switch the "pack-objects" window handling around, and instead
of looking at the object we want to pack, and looking at the ten (or
"window") previous objects to delta against, we could do it the other way
around: keep the object we delta against constant, and see what deltas we
could prepare for the ten next objects.
And since the source would now be constant, you'd need to do the
"delta_prepare()" just _once_ per window, instead of every single time.
Now, I haven't done any profiling on the diff-delta code, and maybe my
guess that delta_prepare() is a pretty expensive part is wrong, and maybe
it wouldn't help to switch the window probing around. But I thought I'd
mention it as one thing to explore..
Linus
^ permalink raw reply
* Re: [PATCH] diff-delta: produce optimal pack data
From: Junio C Hamano @ 2006-02-24 23:55 UTC (permalink / raw)
To: Nicolas Pitre; +Cc: git
In-Reply-To: <Pine.LNX.4.64.0602241029360.23719@localhost.localdomain>
Nicolas Pitre <nico@cam.org> writes:
> On Fri, 24 Feb 2006, Junio C Hamano wrote:
>
>> In Linux 2.6 repository, these object pairs take forever to
>> delta.
>>
>> blob 9af06ba723df75fed49f7ccae5b6c9c34bc5115f ->
>> blob dfc9cd58dc065d17030d875d3fea6e7862ede143
>> size (491102 -> 496045)
>> 58 seconds
>>
>> blob 4917ec509720a42846d513addc11cbd25e0e3c4f ->
>> blob dfc9cd58dc065d17030d875d3fea6e7862ede143
>> size (495831 -> 496045)
>> 64 seconds
>
> Thanks for this. I'll see what I can do to tweak the code to better
> cope with those. Just keep my fourth delta patch in the pu branch for
> now.
If apply this on top of pack-objects.c, you can find more of
them yourself.
---
diff --git a/pack-objects.c b/pack-objects.c
index be7a200..3f88e86 100644
--- a/pack-objects.c
+++ b/pack-objects.c
@@ -62,6 +62,7 @@ static const char *base_name;
static unsigned char pack_file_sha1[20];
static int progress = 1;
static volatile int progress_update = 0;
+static volatile int progress_update_cnt = 0;
/*
* The object names in objects array are hashed with this hashtable,
@@ -826,6 +827,7 @@ static int try_delta(struct unpacked *cu
struct object_entry *old_entry = old->entry;
int old_preferred = (old_entry->preferred_base ||
old_entry->based_on_preferred);
+ int last_up;
unsigned long size, oldsize, delta_size, sizediff;
long max_size;
void *delta_buf;
@@ -890,8 +892,17 @@ static int try_delta(struct unpacked *cu
}
if (sizediff >= max_size)
return -1;
+ last_up = progress_update_cnt;
delta_buf = diff_delta(old->data, oldsize,
cur->data, size, &delta_size, max_size);
+ if (last_up + 1 < progress_update_cnt) {
+ /* It took more than one second */
+ fprintf(stderr, "%d -> %d: %s -> ",
+ last_up, progress_update_cnt,
+ sha1_to_hex(old_entry->sha1));
+ fprintf(stderr, "%s (%lu -> %lu)\n",
+ sha1_to_hex(cur_entry->sha1), oldsize, size);
+ }
if (!delta_buf)
return 0;
cur_entry->delta = old_entry;
@@ -906,6 +917,7 @@ static void progress_interval(int signum
{
signal(SIGALRM, progress_interval);
progress_update = 1;
+ progress_update_cnt++;
}
static void find_deltas(struct object_entry **list, int window, int depth)
^ permalink raw reply related
* [PATCH] Add missing programs to ignore list
From: Shawn Pearce @ 2006-02-24 22:51 UTC (permalink / raw)
To: git
Added recently added programs to the default exclude list.
---
I found these were missing in master. pg won't let me work in a
directory if there are untracked files laying around which aren't
excluded by an ignore pattern.
.gitignore | 4 ++++
1 files changed, 4 insertions(+), 0 deletions(-)
base 809da5f8a21a10112eece4ee9be55fe64371ce68
last 9752e066a00144fc1b7657e6d54569e9d9764092
diff --git a/.gitignore b/.gitignore
index 94f66d5a1ef9d1e2bec2c14b392565ee5bf98dd6..5be239a4aa95f78cb09e4921459e1678b9f3c36e 100644
--- a/.gitignore
+++ b/.gitignore
@@ -2,6 +2,7 @@ GIT-VERSION-FILE
git
git-add
git-am
+git-annotate
git-apply
git-applymbox
git-applypatch
@@ -22,6 +23,7 @@ git-convert-objects
git-count-objects
git-cvsexportcommit
git-cvsimport
+git-cvsserver
git-daemon
git-diff
git-diff-files
@@ -53,6 +55,7 @@ git-mailsplit
git-merge
git-merge-base
git-merge-index
+git-merge-tree
git-merge-octopus
git-merge-one-file
git-merge-ours
@@ -60,6 +63,7 @@ git-merge-recursive
git-merge-resolve
git-merge-stupid
git-mktag
+git-mktree
git-name-rev
git-mv
git-pack-redundant
--
1.2.3.g809d
^ permalink raw reply related
* Re: [PATCH] diff-delta: produce optimal pack data
From: Carl Baldwin @ 2006-02-24 22:50 UTC (permalink / raw)
To: Nicolas Pitre; +Cc: Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.64.0602241544270.31162@localhost.localdomain>
On Fri, Feb 24, 2006 at 04:12:14PM -0500, Nicolas Pitre wrote:
> On Fri, 24 Feb 2006, Carl Baldwin wrote:
> > After the twelve large objects were packed into individual packs the
> > rest of the packing went very quickly and git v1.2.3's date reuse worked
> > very well. This was sort of my attempt at simulating how things would
> > be if git avoided deltification of each of these large files. I'm sorry
> > to have been so harsh earlier I just didn't understand that
> > incrementally packing one-by-one was going to help this much.
>
> Hmmmmmmm....
>
> I don't think I understand what is going on here.
>
> You say that, if you add those big files and incrementally repack after
> each commit using git repack with no option, then it requires only about
> one second each time. Right?
Well, actually I was packing them individually by calling
git-pack-objects directly on each blob.
I'll try doing it exactly as you describe...
Ok, I tried it. Basically I do the following.
% mkdir test
% cd test
% git init-db
% cp ../files/binfile.1 binfile
% time git add binfile
real 0m2.459s
user 0m2.443s
sys 0m0.019s
% git commit -a -m "Rev 1"
% time git repack
[snip]
real 0m1.111s
user 0m1.046s
sys 0m0.061s
% for i in $(seq 2 12); do
cp ../files/binfile.$i binfile
time git commit -a -m "Rev $i"
time git repack
done
Each commit takes around 2.8-3.5 seconds and each repack takes about
1.2-1.5 seconds. These are prettly reasonable.
Now, I try 'git repack -a -f' (or even without -f) and it goes out to
lunch. I think it would take on the order of a day to actually finish
because it wasn't very far after an hour.
[snip]
> How many files besides those 12 big blobs do you have?
This repository has been completely stripped to the 12 revisions of the
one file. So, there are 36 objects.
12 blobs.
12 trees.
12 commits.
That is all.
[snip]
> If you can add them into a single .tgz with instructions on how
> to reproduce the issue and provide me with an URL where I can fetch it
> that'd be perfect.
I will do this in an email off of the list because these files really
shouldn't be available on a public list.
Carl
--
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Carl Baldwin RADCAD (R&D CAD)
Hewlett Packard Company
MS 88 work: 970 898-1523
3404 E. Harmony Rd. work: Carl.N.Baldwin@hp.com
Fort Collins, CO 80525 home: Carl@ecBaldwin.net
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
^ permalink raw reply
* [PATCH] git ls files recursively show ignored files
From: Shawn Pearce @ 2006-02-24 22:02 UTC (permalink / raw)
To: git
Make git-ls-files --others --ignored recurse into non-excluded
subdirectories.
Typically when asking git-ls-files to display all files which are
ignored by one or more exclude patterns one would want it to recurse
into subdirectories which are not themselves excluded to see if
there are any excluded files contained within those subdirectories.
---
I found this issue while trying to find temporary garbage that was
created within a tracked subdirectory:
touch a/b/foo#1
git-ls-files --others --ignored --exclude='*#1'
would never display a/b/foo#1 as the directory 'a' was not itself
excluded. It would be rather nice if git-ls-files actually
showed it.
ls-files.c | 7 +++++--
1 files changed, 5 insertions(+), 2 deletions(-)
base 98214e96be00c5132047ae80bca20d4690933c33
last 809da5f8a21a10112eece4ee9be55fe64371ce68
diff --git a/ls-files.c b/ls-files.c
index 90b289f03d987c6c90214fc12d00c30b4e28bb27..df25c8c012a96a8277413ca3a81490b81b7dc067 100644
--- a/ls-files.c
+++ b/ls-files.c
@@ -279,8 +279,11 @@ static void read_directory(const char *p
continue;
len = strlen(de->d_name);
memcpy(fullname + baselen, de->d_name, len+1);
- if (excluded(fullname) != show_ignored)
- continue;
+ if (excluded(fullname) != show_ignored) {
+ if (!show_ignored || DTYPE(de) != DT_DIR) {
+ continue;
+ }
+ }
switch (DTYPE(de)) {
struct stat st;
--
1.2.3.g809d
^ permalink raw reply related
* Re: [PATCH] New git-seek command with documentation and test.
From: J. Bruce Fields @ 2006-02-24 21:57 UTC (permalink / raw)
To: Johannes Schindelin
Cc: Carl Worth, Andreas Ericsson, Junio C Hamano, git, Linus Torvalds
In-Reply-To: <Pine.LNX.4.63.0602242246430.11479@wbgn013.biozentrum.uni-wuerzburg.de>
On Fri, Feb 24, 2006 at 10:48:46PM +0100, Johannes Schindelin wrote:
> git-seek shares so many characteristics with git-seek, you could make
> git-seek just another command line option to checkout (like "--temporary"
> and "--go-back").
Well, as a user interface, git-seek seems a bit simpler (e.g., easier to
remember).--b.
^ permalink raw reply
* Re: [PATCH] diff-delta: produce optimal pack data
From: Nicolas Pitre @ 2006-02-24 21:48 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git, Linus Torvalds, Carl Baldwin
In-Reply-To: <Pine.LNX.4.64.0602241613030.31162@localhost.localdomain>
On Fri, 24 Feb 2006, Nicolas Pitre wrote:
> If blocks are hashed evenly the cost of producing a delta is at most
> O(n+m) where n and m are the size of the reference and target files
> respectively. In other words, with good data set the cost is linear.
>
> But if many blocks from the reference buffer do hash to the same bucket
> then for each block in the target file many blocks from the reference
> buffer have to be tested against, making it tend towards O(n^m) which is
> pretty highly exponential.
Well, actually this is rather O(n*m) not O(n^m), but bad nevertheless.
Nicolas
^ permalink raw reply
* Re: [PATCH] New git-seek command with documentation and test.
From: Johannes Schindelin @ 2006-02-24 21:48 UTC (permalink / raw)
To: Carl Worth; +Cc: Andreas Ericsson, Junio C Hamano, git, Linus Torvalds
In-Reply-To: <87oe0wrg29.wl%cworth@cworth.org>
Hi,
On Fri, 24 Feb 2006, Carl Worth wrote:
> On Fri, 24 Feb 2006 11:00:29 +0100, Andreas Ericsson wrote:
> >
> > I've said it before, and I'll say it again. This tool provides less
> > flexibility and much less power than "git checkout -b branch
> > <commit-ish>"
>
> Yes, that's by design. It's not intended to be a replacement for git
> checkout -b.
I do not really understand why.
git-seek shares so many characteristics with git-seek, you could make
git-seek just another command line option to checkout (like "--temporary"
and "--go-back").
Hth,
Dscho
^ permalink raw reply
* Re: [PATCH] diff-delta: produce optimal pack data
From: Nicolas Pitre @ 2006-02-24 21:39 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git, Linus Torvalds, Carl Baldwin
In-Reply-To: <7vpslc8oni.fsf@assigned-by-dhcp.cox.net>
On Fri, 24 Feb 2006, Junio C Hamano wrote:
> I haven't looked at Nico's original or updated code closely at
> all, but two things come to mind.
>
> (1) if we could tell the particular data is intrinsically
> diff_delta unfriendly and diff_delta would waste too much
> time when tried to delta against almost _any_ other blob,
> then it might help to give an interface in diff-delta.c for
> the caller to check for such a blob without even trying
> diff_delta.
>
> (2) otherwise, if diff_delta could detect it would spend too
> many cycles to finish its work for a particular input early
> on, we might want it to bail out instead of trying a
> complete job.
I have a patch that implements an hybrid approach.
Currently, diff-delta takes blocks of data in the reference file and
hash them. When the target file is scanned, it uses the hash to match
blocks from the target file with the reference file.
If blocks are hashed evenly the cost of producing a delta is at most
O(n+m) where n and m are the size of the reference and target files
respectively. In other words, with good data set the cost is linear.
But if many blocks from the reference buffer do hash to the same bucket
then for each block in the target file many blocks from the reference
buffer have to be tested against, making it tend towards O(n^m) which is
pretty highly exponential.
The solution I'm investigating is to put a limit on the number of
entries in the same hash bucket so to bring the cost back to something
more linear. That means the delta might miss on better matches that
have not been hashed but still benefit from a limited set. Experience
seems to show that the time to deltify the first two blobs you found to
be problematic can be reduced by 2 orders of magnitude with about only
10% increase in the resulting delta size, and still nearly 40% smaller
than what the current delta code produces.
The question is how to determine the best limit on the number of entries
in the same hash bucket.
Nicolas
^ permalink raw reply
* Re: Removal of "--merge-order"?
From: Johannes Schindelin @ 2006-02-24 21:37 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Randy.Dunlap, Junio C Hamano, Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0602240957430.22647@g5.osdl.org>
Hi,
On Fri, 24 Feb 2006, Linus Torvalds wrote:
> Now, rev-list.c is not the biggest file (apply.c is about twice the size),
> but in many ways it's the most complex one by far. It's also the most
> performance-critical one, and the one that it would be really nice if we
> were to be able to libify it.
This is what I wanted to try today, but unfortunately I had to do real
work :-(
> For example, instead of the horrid scriping language, I _think_ I could
> almost libify it by just hooking into "show_commit", and using a callback
> function for that (and then the stand-alone program would just make the
> callback function be one that prints out the commit).
I don't find the scripting language you invented particularly horrid.
Maybe some odd things (like "if" branching to the "else" block whenever
*any* argument was passed), but not horrid.
But in the end I would prefer a libified git, if only to get rid of
double parsing (if you pipe the output of git-rev-list to another git
program, chances are that you parse the commit objects at least twice).
> That would possibly be a simpler way to get away from using nonportable
> scripts. Plain C really does remain one of the most portable things out
> there.
Yes.
Ciao,
Dscho
^ permalink raw reply
* Re: [PATCH] diff-delta: produce optimal pack data
From: Nicolas Pitre @ 2006-02-24 21:12 UTC (permalink / raw)
To: Carl Baldwin; +Cc: Junio C Hamano, git
In-Reply-To: <20060224204022.GA15962@hpsvcnb.fc.hp.com>
On Fri, 24 Feb 2006, Carl Baldwin wrote:
> On Fri, Feb 24, 2006 at 03:02:07PM -0500, Nicolas Pitre wrote:
> > Well that is probably a bit tight. Ideally it should be linear with the
> > size of the data set to process. If you have 10 files 10MB each it
> > should take about the same time to pack than 10000 files of 10KB each.
> > Of course incrementally packing one additional 10MB file might take more
> > than a second although it is only one file.
>
> Well, I might not have been fair here. I tried an experiment where I
> packed each of the twelve large blob objects explicitly one-by-one using
> git-pack-objects. Incrementally packing each single object was very
> fast. Well under a second per object on my machine.
>
> After the twelve large objects were packed into individual packs the
> rest of the packing went very quickly and git v1.2.3's date reuse worked
> very well. This was sort of my attempt at simulating how things would
> be if git avoided deltification of each of these large files. I'm sorry
> to have been so harsh earlier I just didn't understand that
> incrementally packing one-by-one was going to help this much.
Hmmmmmmm....
I don't think I understand what is going on here.
You say that, if you add those big files and incrementally repack after
each commit using git repack with no option, then it requires only about
one second each time. Right?
But if you use "git-repack -a -f" then it is gone for more than an hour?
I'd expect something like 2 * (sum i for i = 1 to 10) i.e. in the 110
second range due to the combinatorial effect when repacking everything.
This is far from one hour and something appears to be really really
wrong.
How many files besides those 12 big blobs do you have?
> This gives me hope that if somehow git were to not attempt to deltify
> these objects then performance would be much better than acceptible.
>
> [snip]
> > However, if you could let me play with two samples of your big file I'd
> > be grateful. If so I'd like to make git work well with your data set
> > too which is not that uncommon after all.
>
> I would be happy to do this. I will probably need to scrub a bit and
> make sure that the result shows the same characteristics. How would you
> like me to deliver these files to you? They are about 25 MB deflated.
If you can add them into a single .tgz with instructions on how
to reproduce the issue and provide me with an URL where I can fetch it
that'd be perfect.
Nicolas
^ permalink raw reply
* Re: [PATCH] diff-delta: produce optimal pack data
From: Junio C Hamano @ 2006-02-24 20:53 UTC (permalink / raw)
To: Nicolas Pitre; +Cc: git, Linus Torvalds, Carl Baldwin
In-Reply-To: <Pine.LNX.4.64.0602241152290.22647@g5.osdl.org>
Linus Torvalds <torvalds@osdl.org> writes:
> NOTE! Every SINGLE one of those heuristics are just totally made up by
> yours truly, and have no testing behind them. They're more of the type
> "that sounds about right" than "this is how it must be". As mentioned,
> Nico has already been playing with the heuristics - but he wanted better
> packs, not better CPU usage, so he went the other way from what you would
> want to try..
I haven't looked at Nico's original or updated code closely at
all, but two things come to mind.
(1) if we could tell the particular data is intrinsically
diff_delta unfriendly and diff_delta would waste too much
time when tried to delta against almost _any_ other blob,
then it might help to give an interface in diff-delta.c for
the caller to check for such a blob without even trying
diff_delta.
(2) otherwise, if diff_delta could detect it would spend too
many cycles to finish its work for a particular input early
on, we might want it to bail out instead of trying a
complete job.
^ permalink raw reply
* Re: git-mailinfo doesn't get installed any more
From: Linus Torvalds @ 2006-02-24 20:42 UTC (permalink / raw)
To: Tony Luck; +Cc: Git Mailing List
In-Reply-To: <12c511ca0602241206jaea9f75pce4ca687f5b2fd3c@mail.gmail.com>
On Fri, 24 Feb 2006, Tony Luck wrote:
>
> 2) What's the cute 1-line git way to see when this was broken. I'm
> guessing that it involves using a --pickaxe.
You've actually found an interesting misfeature in git. There's a merge
error, and you can't see it in the diffs by default because it wasn't due
to a _clashing_ content thing, but two edits that were far enough away
from each other.
That "git-mailinfo" thing is there in rev 2a3763ef, but it's not there in
the current Makefile. And doing a
git-whatchanged -p 2a3763ef.. | grep git-mailinfo
results in nothing. Which is not good.
Anyway, the way to handle that is to do "git bisect" (and use "grep
git-mailinfo Makefile" in between bisection points to see if git-mailinfo
is still part of the list of programs):
git-bisect start
# bad: [20d23f554d6cd40ffa0d41ccc9416bca867667e0] gitview: Bump the rev
git-bisect bad 20d23f554d6cd40ffa0d41ccc9416bca867667e0
# good: [2a3763ef3d26eb38c0a47997b8e5fd2a7c5214cc] avoid makefile override warning
git-bisect good 2a3763ef3d26eb38c0a47997b8e5fd2a7c5214cc
# bad: [ee072260dbff6914c24d956bcc2d46882831f1a0] Merge branch 'jc/nostat'
git-bisect bad ee072260dbff6914c24d956bcc2d46882831f1a0
# good: [551ce28fe1f2777eee7dd9c02bd44f55f4b32361] git-svn: 0.9.1: add --version and copyright/license (GPL v2+) information
git-bisect good 551ce28fe1f2777eee7dd9c02bd44f55f4b32361
# good: [5508a616631fb41531b638f744bd92c701727014] New test to verify that when git-clone fails it cleans up the new directory.
git-bisect good 5508a616631fb41531b638f744bd92c701727014
# bad: [712b1dd389ad5bcdbaab0279641f0970702fc1f1] Merge branch 'js/portable'
git-bisect bad 712b1dd389ad5bcdbaab0279641f0970702fc1f1
# good: [d800795613a710fb18353af53730e75185861f41] gitview: Use monospace font to draw the branch and tag name
git-bisect good d800795613a710fb18353af53730e75185861f41
# good: [b992933853ccffac85f7e40310167ef7b8f0432e] Fix "gmake -j"
git-bisect good b992933853ccffac85f7e40310167ef7b8f0432e
resulting in:
712b1dd389ad5bcdbaab0279641f0970702fc1f1 is first bad commit
which shows that there was a bad merge by Junio.
You can use
git show -c -p 712b1dd389ad5bcdbaab0279641f0970702fc1f1
to see why. It merged the thing perfectly fine, but sadly, incorrectly.
Somebody should probably look at whether we could have done things better,
but I suspect that merge errors are inevitable with any automated process.
Anyway, it might be worth remembering that 712b1dd3 merge for future
testing. Make a test-case out of it.
Linus
^ permalink raw reply
* Re: [PATCH] diff-delta: produce optimal pack data
From: Carl Baldwin @ 2006-02-24 20:40 UTC (permalink / raw)
To: Nicolas Pitre; +Cc: Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.64.0602241438521.31162@localhost.localdomain>
On Fri, Feb 24, 2006 at 03:02:07PM -0500, Nicolas Pitre wrote:
> Well that is probably a bit tight. Ideally it should be linear with the
> size of the data set to process. If you have 10 files 10MB each it
> should take about the same time to pack than 10000 files of 10KB each.
> Of course incrementally packing one additional 10MB file might take more
> than a second although it is only one file.
Well, I might not have been fair here. I tried an experiment where I
packed each of the twelve large blob objects explicitly one-by-one using
git-pack-objects. Incrementally packing each single object was very
fast. Well under a second per object on my machine.
After the twelve large objects were packed into individual packs the
rest of the packing went very quickly and git v1.2.3's date reuse worked
very well. This was sort of my attempt at simulating how things would
be if git avoided deltification of each of these large files. I'm sorry
to have been so harsh earlier I just didn't understand that
incrementally packing one-by-one was going to help this much.
This gives me hope that if somehow git were to not attempt to deltify
these objects then performance would be much better than acceptible.
[snip]
> However, if you could let me play with two samples of your big file I'd
> be grateful. If so I'd like to make git work well with your data set
> too which is not that uncommon after all.
I would be happy to do this. I will probably need to scrub a bit and
make sure that the result shows the same characteristics. How would you
like me to deliver these files to you? They are about 25 MB deflated.
Carl
--
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Carl Baldwin RADCAD (R&D CAD)
Hewlett Packard Company
MS 88 work: 970 898-1523
3404 E. Harmony Rd. work: Carl.N.Baldwin@hp.com
Fort Collins, CO 80525 home: Carl@ecBaldwin.net
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
^ permalink raw reply
* Re: [PATCH] diff-delta: produce optimal pack data
From: Nicolas Pitre @ 2006-02-24 20:19 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Carl Baldwin, Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.64.0602241152290.22647@g5.osdl.org>
On Fri, 24 Feb 2006, Linus Torvalds wrote:
> The other thing to look at is "max_size": right now it initializes that to
> "size / 2 - 20", which just says that we don't ever want a delta that is
> larger than about half the result (plus the 20 byte overhead for pointing
> to the thing we delta against). Again, if you feel that normal compression
> compresses better than half, you could try changing that to
>
> ..
> max_size = size / 4 - 20;
> ..
Like I mentioned, max_size should also be caped with the deflated
undeltified object
size. This value is easy to get since plain objects are already
deflated.
> NOTE! Every SINGLE one of those heuristics are just totally made up by
> yours truly, and have no testing behind them. They're more of the type
> "that sounds about right" than "this is how it must be". As mentioned,
> Nico has already been playing with the heuristics - but he wanted better
> packs, not better CPU usage, so he went the other way from what you would
> want to try..
Actually it's a good balance I'm after.
Using 30% more CPU for 10% smaller packs is OK I'd say.
Using 100 times the CPU for 50% saving on only one particular delta is
not acceptable.
And using more than one hour for 200MB of data with the current window
default is not acceptable either.
Nicolas
^ permalink raw reply
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