Re: [PATCH] Avoid sorting if references are added to ref_cache in order

> >Technically we would still be sorted if strcmp(...) == 0. But I guess it
> >probably doesn't matter, as we shouldn't ever be adding duplicates here.
> 
> Yes, duplicate refs should be an exceptional case and needn't be
> handled efficiently.  sort_ref_dir() explicitly accepts the
> possibility of duplicate references, de-dups them if they are
> consistent with each other, or dies if they are inconsistent.  We
> shouldn't add a way to bypass that logic.  We could implement the
> duplicate-detection-and-checking code again in add_entry_to_dir(),
> but my choice was to leave it to sort_ref_dir() to deal with
> duplicates.

> More general approaches:
> [...]
> Something that would help read_packed_refs() would be to keep track
> of the directory that it is currently working in.  This would
> effectively remove the need to access a directory while working in
> one of its subdirectories, thereby avoiding any need to repeatedly
> sort intermediate directories.  It would also avoid having to
> traverse the directories starting at the root for each new entry,
> which itself would save time independent of the time for sorting.  I
> have some patches that implement this change but they are stale.  I
> want to do some benchmarking first though to see whether the extra
> complication brings measurable benefits.

> Finally, I did some work on the idea of keeping the refs within a
> directory *mostly* sorted.  (Probably this technique is already
> known, but I have never run into it.)  One would keep the first part
> of the array sorted, and append new references to the tail of the
> array unsorted.  Searching would be via a binary search over the
> sorted part of the array, and a linear search over the unsorted tail.
> The trick is that every so often the tail should be sorted and merged
> into the head.  How often?  It is a tradeoff between the work of
> sorting and merging versus the work saved by avoiding linear searches
> through the tail.  I worked out the theory, and I think the optimum
> was to re-sort the array when the size of the unsorted tail reached
> the squareroot of the total size or something like that.  This method
> could reduce the cost of (lookup, add, lookup, add, ...) sequences,
> albeit not to the extent of a more optimal data structure.