Re: [PATCH 1/2] sha1_file: drop experimental GIT_USE_LOOKUP search

Jeff King [off-list ref] writes:

This lets us remove sha1_entry_pos() entirely, as the .idx
lookup code was the only caller.  Note that sha1-lookup.c
still contains sha1_pos(), which differs from
sha1_entry_pos() in two ways:

  - it has a different interface; it uses a function pointer
    to access sha1 entries rather than a size/offset pair
    describing the table's memory layout

  - it only scales the initial selection of "mi", rather
    than each iteration of the search

We can't get rid of this function, as it's called from
several places. It may be that we could replace it with a
simple binary search, but that's out of scope for this patch
(and would need benchmarking).

Thanks for reducing the count of binary search functions by one.

I think the "just one round of newton-raphson" in sha1_pos() comes
from [*1*]; I agree that it needs benchmarking before tweaking it.

We may want to tell libgit2 folks about this change, though [*2*].
I think they too are carrying dead code that is only used under CPP
macro GIT_USE_LOOKUP, which they do not seem to define.


[Reference]

*1* https://public-inbox.org/git/7v38vso8kz.fsf@alter.siamese.dyndns.org/
*2* https://github.com/libgit2/libgit2/commit/dd453c4dbf9a1fa38530b1f51e079852736b8f66

On Wed, Aug 09, 2017 at 11:12:19AM -0700, Junio C Hamano wrote:

Thanks for reducing the count of binary search functions by one.

I think the "just one round of newton-raphson" in sha1_pos() comes
from [*1*]; I agree that it needs benchmarking before tweaking it.

Actually, it's weirder than that. You mentioned it in that thread, but
the code dates back much further. It was moved to the file in 96beef8,
but that was just a copy from patch-ids.c. The original seems to be from
5d23e133d2 (Refactor patch-id filtering out of git-cherry and
git-format-patch., 2007-04-09), which predates the sha1_entry_pos()
experiment.

I always thought those two sha1-lookup functions came in the opposite
order, but I guess was wrong. Or possibly you are a time traveler.

We may want to tell libgit2 folks about this change, though [*2*].
I think they too are carrying dead code that is only used under CPP
macro GIT_USE_LOOKUP, which they do not seem to define.

Good thinking. It looks like they could use all three of the patches
under discussion. I opened some PRs:

  https://github.com/libgit2/libgit2/pull/4326
  https://github.com/libgit2/libgit2/pull/4327
  https://github.com/libgit2/libgit2/pull/4328

-Peff