From: Junio C Hamano <junkio@cox•net>
To: Linus Torvalds <torvalds@linux-foundation•org>
Cc: Geert Bosch <bosch@adacore•com>, Nicolas Pitre <nico@cam•org>,
"Shawn O. Pearce" <spearce@spearce•org>,
Dana How <danahow@gmail•com>,
git@vger•kernel.org
Subject: Re: [RFC] Packing large repositories
Date: Sat, 31 Mar 2007 13:54:07 -0700 [thread overview]
Message-ID: <7vslbl8780.fsf@assigned-by-dhcp.cox.net> (raw)
In-Reply-To: <Pine.LNX.4.64.0703311033290.6730@woody.linux-foundation.org> (Linus Torvalds's message of "Sat, 31 Mar 2007 11:36:35 -0700 (PDT)")
Linus Torvalds <torvalds@linux-foundation•org> writes:
> In other words, the 256-entry fan-out was meant to avoid the first eight
> levels of binary lookup. But the thing is, we should be able to generally
> do a *lot* better than any binary lookup by just doing a LINEAR SEARCH,
> which is also more cache-friendly, and prefetches much better when it's
> not in the cache.
> ...
> - use newton-raphson to iterate closer. It should be a much faster way to
> find the rough area for the entry we're searching for than binary
> search. Two or three iterations should get us there, easily.
This is another egg of columbus moment that makes me feel it was
worth to have been in git community ;-).
I like it.
next prev parent reply other threads:[~2007-03-31 20:54 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-03-28 7:05 [RFC] Packing large repositories Dana How
2007-03-28 16:53 ` Linus Torvalds
2007-03-30 6:23 ` Shawn O. Pearce
2007-03-30 13:01 ` Nicolas Pitre
2007-03-31 11:04 ` Geert Bosch
2007-03-31 18:36 ` Linus Torvalds
2007-03-31 19:02 ` Nicolas Pitre
2007-03-31 20:54 ` Junio C Hamano [this message]
2007-03-31 21:20 ` Linus Torvalds
2007-03-31 21:56 ` Linus Torvalds
2007-04-02 6:22 ` Geert Bosch
2007-04-03 5:39 ` Shawn O. Pearce
2007-03-31 18:51 ` Nicolas Pitre
2007-04-02 21:19 ` Dana How
2007-04-02 1:39 ` Sam Vilain
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=7vslbl8780.fsf@assigned-by-dhcp.cox.net \
--to=junkio@cox$(echo .)net \
--cc=bosch@adacore$(echo .)com \
--cc=danahow@gmail$(echo .)com \
--cc=git@vger$(echo .)kernel.org \
--cc=nico@cam$(echo .)org \
--cc=spearce@spearce$(echo .)org \
--cc=torvalds@linux-foundation$(echo .)org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
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