3 messages, 2 authors, 2016-06-15 · open the first message on its own page
From: Junio C Hamano <hidden>
Date: 2016-06-15 22:42:18
Linus Torvalds [off-list ref] writes:
On Sat, 11 Feb 2006, Linus Torvalds wrote:quoted
If somebody shows that the other approaches are faster, then I guess I'll just have to sulk in a corner and grown quietly at people.growl. growL. With an 'L'!
I do not get it. But my impression was the circular hash with trivial fixes were the fastest. I am benching them now.
From: Junio C Hamano <hidden>
Date: 2016-06-15 22:42:18
Junio C Hamano [off-list ref] writes:
Linus Torvalds [off-list ref] writes:quoted
On Sat, 11 Feb 2006, Linus Torvalds wrote:quoted
If somebody shows that the other approaches are faster, then I guess I'll just have to sulk in a corner and grown quietly at people.growl. growL. With an 'L'!I do not get it. ...
I first suspected you just meant the typo (s/grown/growl/) but
it probably is that you really meant GROWL (and sulk).
It turns out that Johannes (with my patch to fix possible
unsigned int alignment issue and the initial call to
find_object()) is the clear winner.
base - tip of "master"
lt-obj - the binary tree without balancing
aj-obj - Alexandre's 256-way buckets
js-obj - Johannes' circular hash
Although I have _not_ double checked the correctness of them, I
did not see major flaw in any of them.
base/git-rev-list --objects v2.6.14..linus
real 2m32.088s user 2m2.830s sys 0m0.890s
real 2m6.614s user 2m1.860s sys 0m0.660s
real 2m13.776s user 2m2.450s sys 0m0.590s
real 2m6.062s user 2m2.420s sys 0m0.690s
real 2m15.567s user 2m3.170s sys 0m0.900s
lt-obj/git-rev-list --objects v2.6.14..linus
real 0m42.889s user 0m40.170s sys 0m0.570s
real 0m44.247s user 0m40.320s sys 0m0.530s
real 0m40.891s user 0m40.110s sys 0m0.500s
real 0m41.874s user 0m40.090s sys 0m0.530s
real 0m41.596s user 0m40.050s sys 0m0.600s
aj-obj/git-rev-list --objects v2.6.14..linus
real 0m36.842s user 0m36.200s sys 0m0.490s
real 0m37.178s user 0m36.740s sys 0m0.390s
real 0m37.222s user 0m36.540s sys 0m0.610s
real 0m36.924s user 0m36.410s sys 0m0.360s
real 0m37.341s user 0m36.150s sys 0m0.620s
js-obj/git-rev-list --objects v2.6.14..linus
real 0m24.689s user 0m24.120s sys 0m0.390s
real 0m24.753s user 0m24.020s sys 0m0.360s
real 0m27.650s user 0m24.470s sys 0m0.440s
real 0m33.480s user 0m24.030s sys 0m0.460s
real 0m25.329s user 0m24.490s sys 0m0.390s
base/git-name-rev --all
real 0m4.193s user 0m4.060s sys 0m0.130s
real 0m4.179s user 0m4.100s sys 0m0.080s
real 0m4.210s user 0m4.040s sys 0m0.150s
real 0m4.162s user 0m4.100s sys 0m0.060s
real 0m4.697s user 0m4.100s sys 0m0.120s
lt-obj/git-name-rev --all
real 0m2.199s user 0m2.120s sys 0m0.080s
real 0m2.186s user 0m2.110s sys 0m0.080s
real 0m2.187s user 0m2.150s sys 0m0.040s
real 0m2.817s user 0m2.150s sys 0m0.070s
real 0m2.323s user 0m2.170s sys 0m0.050s
aj-obj/git-name-rev --all
real 0m2.136s user 0m2.050s sys 0m0.080s
real 0m2.164s user 0m2.080s sys 0m0.060s
real 0m2.143s user 0m2.070s sys 0m0.070s
real 0m2.141s user 0m2.080s sys 0m0.060s
real 0m2.154s user 0m2.070s sys 0m0.090s
js-obj/git-name-rev --all
real 0m2.047s user 0m2.010s sys 0m0.040s
real 0m2.040s user 0m1.970s sys 0m0.070s
real 0m2.025s user 0m1.970s sys 0m0.060s
real 0m2.170s user 0m2.020s sys 0m0.030s
real 0m2.046s user 0m2.010s sys 0m0.030s
From: Linus Torvalds <torvalds@osdl.org>
Date: 2016-06-15 22:42:18
On Sat, 11 Feb 2006, Junio C Hamano wrote:
It turns out that Johannes (with my patch to fix possible unsigned int alignment issue and the initial call to find_object()) is the clear winner.
Having looked at it, I will have to agree. Johannes' approach looks pretty clean, and has the same memory overhead mine has (two pointers per object in the hash - one used, one empty), but has a lot fewer memcmp() calls and pointer chasing. So I'll growl softly but concur. Johannes' code isn't even very complex. Linus