Re: [PATCH] binary-tree-based objects.

From: Junio C Hamano <junkio@cox.net>
Date: Feb 12, 2006, 06:07 UTC
Message-ID: <7vaccxdsaf.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <7v1wy9f7q4.fsf@assigned-by-dhcp.cox.net>

Junio C Hamano <junkio@cox.net> writes:

Show 11 quoted lines

> Linus Torvalds <torvalds@osdl.org> writes:
>
>> On Sat, 11 Feb 2006, Linus Torvalds wrote:
>>> 
>>> 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