patch, 4 partsstart refactoring binary search function

There are many binary search functions in the code base and I have been asked to refactor them in these message:

http://thread.gmane.org/gmane.comp.version-control.git/105363/focus=105436 http://thread.gmane.org/gmane.comp.version-control.git/114735/focus=115391

so here is a start

The following patch applies on top of pu where they can be squashed into other patches:

  sha1-lookup: add new "sha1_pos" function to efficiently lookup sha1
  patch-ids: use the new generic "sha1_pos" function to lookup sha1
  bisect: use the new generic "sha1_pos" function to lookup sha1
  replace_object: use the new generic "sha1_pos" function to lookup
    sha1

 bisect.c         |   23 +++++-------
 patch-ids.c      |   93 +++-----------------------------------------------
 replace_object.c |   24 +++++--------
 sha1-lookup.c    |  101 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 sha1-lookup.h    |    7 ++++
 5 files changed, 131 insertions(+), 117 deletions(-)

Christian Couder <chriscool@tuxfamily.org> writes:

I think the refactoring itself does make sense. Less duplicated code has better chance to be improved further if there is demonstrated need, and I like the series for that "clean-up" value alone.

In the last two patches, however, you advertised the use of this new API for gaining better performance (in exchange for simpler copy-pasted implementation), but changing a simple (base + index * sizeof(struct that contains the sha-1 field)) into a call to a function whose address is passed _may_ have larger negative impact to the performance, than what is gained by the better initial midpoint selection the new code uses.

If the extra indirect call turns to degrade the performance too much, we could always reimplement it as a macro, I think, but let's not go there before somebody runs benchmarks and demonstrates that it is a problem.

I've restructured your existing two branches to take advantage of the first two patches.

Thanks.