git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: Make GIT_USE_LOOKUP default?

From
Junio C Hamano <gitster@pobox.com>
Date
Mar 18, 2013, 18:40 UTC
Message-ID
<7v38vso8kz.fsf@alter.siamese.dyndns.org>
In-Reply-To
<20130318171949.GB15924@sigill.intra.peff.net>
Jeff King <peff@peff.net> writes:
Show 7 quoted lines
> I do not see anything obviously wrong in it, though I did not walk
> through all of the ofs calculation to look for any clever speedups.
> However, I think it is clear from the other timings and Ingo's thread
> that glibc 2.11's memcmp does not perform very well on many short reads.
> And sha1_entry_pos will do memcmps even smaller than 20 bytes.
>
> What happens if you do this?
The overall trend is the same.

[without GIT_USE_LOOKUP] real 0m40.044s real 0m40.054s real 0m40.072s real 0m40.097s real 0m40.159s

[with GIT_USE_LOOKUP] real 0m40.257s real 0m40.281s real 0m40.311s real 0m40.366s real 0m40.407s

I suspect that after the first few rounds the range shrinks small enough that the difference between a simple "mi = (hi + lo)/2" and convoluted ofs computation becomes dominant. Perhaps we should only do N-R for the initial midpoint selection and then fall back to a stupid binary search?

Previous: Jeff KingNext: Duy Nguyen
Message 8 of 10 in “Make GIT_USE_LOOKUP default?”
  1. Duy NguyenMar 17, 2013
  2. Junio C HamanoMar 17, 2013
  3. Jeff KingMar 18, 2013
  4. Junio C HamanoMar 18, 2013
  5. Jeff KingMar 18, 2013
  6. Junio C HamanoMar 18, 2013
  7. Jeff KingMar 18, 2013
  8. Junio C HamanoMar 18, 2013
  9. Duy NguyenMar 19, 2013
  10. Jeff KingMar 19, 2013

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.