Re: [PATCH 6/6] [RFC] subvert sorted-array to replace binary-search in unpack-objects.

From: Junio C Hamano <gitster@pobox.com>
Date: Dec 10, 2010, 23:00 UTC
Message-ID: <7vmxodb5d3.fsf@alter.siamese.dyndns.org>
In-Reply-To: <1291848695-24601-7-git-send-email-ydirson@altern.org>

Yann Dirson <ydirson@altern.org> writes:

Show 21 quoted lines

> Signed-off-by: Yann Dirson <ydirson@altern.org>
> ---
>  builtin/unpack-objects.c |   40 +++++++++++++++++++++++++---------------
>  1 files changed, 25 insertions(+), 15 deletions(-)
>
> diff --git a/builtin/unpack-objects.c b/builtin/unpack-objects.c
> index f63973c..6d7d113 100644
> --- a/builtin/unpack-objects.c
> +++ b/builtin/unpack-objects.c
> @@ -157,7 +158,24 @@ struct obj_info {
>  #define FLAG_OPEN (1u<<20)
>  #define FLAG_WRITTEN (1u<<21)
>  
> -static struct obj_info *obj_list;
> +/*
> + * FIXME: obj_info is a sorted array, but we read it as a whole, we
> + * don't need insertion features.  This allows us to abuse unused
> + * obj_info_nr later as a means of specifying an upper bound for
> + * binary search.  obj_info_alloc shall be eliminated by the compiler
> + * as unused.
> + */

I was scratching my head when I read "subvert" on your Subject line and FIXME above for the first time, but after thinking about it, I think I got it, and more importantly, I think you realized and shared with me the "too rigid and brittle" I mentioned in my response to [1/6] earlier, if not "overengineered" part.

As pack stream is read in, obj_list is built into an array that is sorted by its "offset" field up to "nr"-th element. And assigning the current number of elements in the array to obj_list_nr is not a "kludge to bound the search" as you said in the comment, but is the right thing to do given the structure of your API. "nr" is "up to this index the array is filled and used", "alloc" is "this many is allocated", and at the point of that assignment, "nr" is indeed what it is.

The only reason it might seem kludgy is because the API is not designed to anticipate that there is a way to add new elements at the end by feeding elements in the already sorted order, and that facility does so without calling the functions your API autogenerates.

I think the most bothersome repetition with the current codebase around binary searchable tables is the binary search loops. Perhaps introducing a macro that lets us write them in a more structured way, without trying to build an elaborate top-level declarations that do everything (and failing to do so), may give you a better payback?