From: Johannes Schindelin <Johannes.Schindelin@gmx.de>
To: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Junio C Hamano <gitster@pobox.com>,
Alberto Bertogli <albertito@gmail.com>,
git@vger.kernel.org, Johan Herland <johan@herland.net>
Subject: Re: [REVISED PATCH 2/6] Introduce commit notes
Date: Thu, 19 Jul 2007 10:50:17 +0100 (BST) [thread overview]
Message-ID: <Pine.LNX.4.64.0707191048030.14781@racer.site> (raw)
In-Reply-To: <alpine.LFD.0.999.0707181949490.27353@woody.linux-foundation.org>
Hi,
On Wed, 18 Jul 2007, Linus Torvalds wrote:
> 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
next prev parent reply other threads:[~2007-07-19 9:50 UTC|newest]
Thread overview: 42+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-07-15 23:19 [PATCH 0/6] Introduce commit notes Johannes Schindelin
2007-07-15 23:22 ` [PATCH 1/6] Rename git_one_line() to git_line_length() and export it Johannes Schindelin
2007-07-15 23:23 ` [PATCH 2/6] Introduce commit notes Johannes Schindelin
2007-07-15 23:36 ` Junio C Hamano
2007-07-15 23:52 ` Johannes Schindelin
2007-07-16 0:05 ` Junio C Hamano
2007-07-16 5:11 ` Junio C Hamano
2007-07-19 2:30 ` [REVISED PATCH " Johannes Schindelin
2007-07-19 3:28 ` Linus Torvalds
2007-07-19 5:13 ` Junio C Hamano
2007-07-19 9:34 ` Junio C Hamano
2007-07-19 9:57 ` Adam Hayek
2007-07-19 10:58 ` Andy Parkins
2007-07-19 11:10 ` Johannes Schindelin
2007-07-19 14:33 ` Andy Parkins
2007-07-19 17:42 ` Linus Torvalds
2007-07-20 0:20 ` Junio C Hamano
2007-07-20 4:59 ` Shawn O. Pearce
2007-07-19 17:20 ` Linus Torvalds
2007-07-19 9:50 ` Johannes Schindelin [this message]
2007-07-19 10:34 ` Olivier Galibert
2007-07-19 17:50 ` Linus Torvalds
2007-07-19 9:05 ` Wincent Colaiuta
2007-07-19 9:24 ` Johannes Schindelin
2007-07-19 9:54 ` Sven Verdoolaege
2007-07-15 23:23 ` [PATCH 3/6] Add git-notes Johannes Schindelin
2007-07-16 5:11 ` Junio C Hamano
2007-07-19 2:31 ` [REVISED PATCH " Johannes Schindelin
2007-07-19 2:54 ` Johannes Schindelin
2007-07-15 23:24 ` [PATCH 4/6] Add a test script for "git notes" Johannes Schindelin
2007-07-16 5:11 ` Junio C Hamano
2007-07-19 2:32 ` [REVISED PATCH " Johannes Schindelin
2007-07-15 23:24 ` [PATCH 5/6] Document git-notes Johannes Schindelin
2007-07-15 23:26 ` [WIP PATCH 6/6] notes: add notes-index for a substantial speedup Johannes Schindelin
2007-07-15 23:33 ` Johannes Schindelin
2007-07-16 6:01 ` Shawn O. Pearce
2007-07-16 16:29 ` Johannes Schindelin
2007-07-16 7:57 ` [PATCH 0/6] Introduce commit notes Andy Parkins
2007-07-16 8:11 ` Junio C Hamano
2007-07-16 16:26 ` Johannes Schindelin
2007-07-16 17:56 ` Junio C Hamano
2007-07-19 1:34 ` Johannes Schindelin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Pine.LNX.4.64.0707191048030.14781@racer.site \
--to=johannes.schindelin@gmx.de \
--cc=albertito@gmail.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=johan@herland.net \
--cc=torvalds@linux-foundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).