mhagger@xxxxxxxxxxxx writes:
> From: Michael Haggerty <mhagger@xxxxxxxxxxxx>
>
> Keep track of how many entries in a ref_dir are already sorted. In
> sort_ref_dir(), only call qsort() if the dir contains unsorted
> entries.
>
> We could store a binary "sorted" value instead of an integer, but
> storing the number of sorted entries leaves the way open for a couple
> of possible future optimizations:
>
> * In sort_ref_dir(), sort *only* the unsorted entries, then merge them
> with the sorted entries. This should be faster if most of the
> entries are already sorted.
>
> * Teach search_ref_dir() to do a binary search of any sorted entries,
> and if unsuccessful do a linear search of any unsorted entries.
> This would avoid the need to sort the list every time that
> search_ref_dir() is called, and (given some intelligence about how
> often to sort) could significantly improve the speed in certain
> hypothetical usage patterns.
The elegance (which I think is the right word for this case as it is both
simple and clever) of the above strategy is not fully appreciated unless
you explain that your plan for "lazily add new entries and keep the
directory unsorted" case is to append them at the end (hence preserving
the property that entries[0..sorted] is always sorted).
If you reword the comment "How many of the entries..." to something like
"entries at 0 up to this index in the array are sorted", you could express
that idea without changing the log message that much, I guess.
> Signed-off-by: Michael Haggerty <mhagger@xxxxxxxxxxxx>
> ---
> refs.c | 29 ++++++++++++++++++++++++-----
> 1 files changed, 24 insertions(+), 5 deletions(-)
>
> diff --git a/refs.c b/refs.c
> index ccd2806..ce141ea 100644
> --- a/refs.c
> +++ b/refs.c
> @@ -108,6 +108,10 @@ struct ref_value {
>
> struct ref_dir {
> int nr, alloc;
> +
> + /* How many of the entries in this directory are sorted? */
> + int sorted;
> +
> struct ref_entry **entries;
> };
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html