From: Junio C Hamano <gitster@pobox.com>
Date: Thu, 29 Sep 2011 21:57:53 GMT
Subject: Re: [PATCH] refs: Use binary search to lookup refs faster
Message-ID: <7vzkhnqae6.fsf@alter.siamese.dyndns.org>
In-Reply-To: <20110929041811.5363.33396.julian@quantumfyre.co.uk>

Julian Phillips <julian@quantumfyre.co.uk> writes:

> Currently we linearly search through lists of refs when we need to
> find a specific ref.  This can be very slow if we need to lookup a
> large number of refs.  By changing to a binary search we can make this
> faster.
>
> In order to be able to use a binary search we need to change from
> using linked lists to arrays, which we can manage using ALLOC_GROW.
>
> We can now also use the standard library qsort function to sort the
> refs arrays.
>
> Signed-off-by: Julian Phillips <julian@quantumfyre.co.uk>
> ---
>
> Something like this?
>
>  refs.c |  328 ++++++++++++++++++++++++++--------------------------------------
>  1 files changed, 131 insertions(+), 197 deletions(-)
>
> diff --git a/refs.c b/refs.c
> index a49ff74..e411bea 100644
> --- a/refs.c
> +++ b/refs.c
> @@ -8,14 +8,18 @@
>  #define REF_KNOWS_PEELED 04
>  #define REF_BROKEN 010
>  
> -struct ref_list {
> -	struct ref_list *next;
> +struct ref_entry {
>  	unsigned char flag; /* ISSYMREF? ISPACKED? */
>  	unsigned char sha1[20];
>  	unsigned char peeled[20];
>  	char name[FLEX_ARRAY];
>  };
>  
> +struct ref_array {
> +	int nr, alloc;
> +	struct ref_entry **refs;
> +};
> +

Yeah, I can say "something like that" without looking at the rest of the
patch ;-) The rest should naturally follow from the above data structures.