Re: [PATCH v2 30/51] sort_ref_dir(): do not sort if already sorted

mhagger@alum.mit.edu writes:

From: Michael Haggerty <redacted>

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.