Re: [PATCH 0/4] start refactoring binary search function

From: Junio C Hamano <gitster@pobox.com>
Date: Apr 5, 2009, 09:45 UTC
Message-ID: <7veiw7wi1o.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <20090404225920.6a10fe78.chriscool@tuxfamily.org>

Christian Couder <chriscool@tuxfamily.org> writes:

Show 16 quoted lines

> 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.