Re: [REVISED PATCH 2/6] Introduce commit notes

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Jul 19, 2007, 09:50 UTC
Message-ID: <Pine.LNX.4.64.0707191048030.14781@racer.site>
In-Reply-To: <alpine.LFD.0.999.0707181949490.27353@woody.linux-foundation.org>

Hi,

On Wed, 18 Jul 2007, Linus Torvalds wrote:

Show 12 quoted lines

> On Thu, 19 Jul 2007, Johannes Schindelin wrote:
> >
> > There is one severe shortcoming, though.  Since tree objects can 
> > contain file names of a variable length, it is not possible to do a 
> > binary search for the correct base name in the tree object's contents.
> 
> Well, I've been thinking about this, and that's not really entirely 
> correct.
> 
> It *is* possible to do a binary search, it's just a bit complicated, 
> because you have to take the "halfway" thing, and find the beginning of 
> an entry.

I will try to work from your proposal, and do some timings. But for the notes, I really, really like the average constant running time of the hash map. As you can see from my timings in

http://thread.gmane.org/gmane.comp.version-control.git/52598/focus=52603

it does make a difference, compared to binary search.

Ciao, Dscho