From: Junio C Hamano Date: Mon, 18 Mar 2013 18:40:12 GMT Subject: Re: Make GIT_USE_LOOKUP default? Message-ID: <7v38vso8kz.fsf@alter.siamese.dyndns.org> In-Reply-To: <20130318171949.GB15924@sigill.intra.peff.net> Jeff King writes: > 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?