# [PATCH 0/4] start refactoring binary search function

2 messages from 2009-04-04 to 2009-04-05. Participants: Christian Couder, Junio C Hamano.
Thread: https://gitlist.dev/t/18719

## Christian Couder, 2009-04-04 20:59

Subject: [PATCH 0/4] start refactoring binary search function
Message-ID: <20090404225920.6a10fe78.chriscool@tuxfamily.org>
URL: https://gitlist.dev/e/20090404225920.6a10fe78.chriscool%40tuxfamily.org

```
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(-)

```

## Junio C Hamano, 2009-04-05 09:45

Subject: Re: [PATCH 0/4] start refactoring binary search function
Message-ID: <7veiw7wi1o.fsf@gitster.siamese.dyndns.org>
URL: https://gitlist.dev/e/7veiw7wi1o.fsf%40gitster.siamese.dyndns.org
In-Reply-To: <20090404225920.6a10fe78.chriscool@tuxfamily.org>

```
Christian Couder <chriscool@tuxfamily.org> writes:

> 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

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.

```