On 02/10, René Scharfe wrote:
> prune_cache() first identifies those entries at the start of the sorted
> array that can be discarded. Then it moves the rest of the entries up.
> Last it identifies the unwanted trailing entries among the moved ones
> and cuts them off.
>
> Change the order: Identify both start *and* end of the range to keep
> first and then move only those entries to the top. The resulting code
> is slightly shorter and a bit more efficient.
>
> Signed-off-by: Rene Scharfe <l.s.r@xxxxxx>
> ---
> The performance impact is probably only measurable with a *really* big
> index.
Well there's been a lot of talk recently about *really* big indexes, so
I'm sure someone out there will be happy :)
>
> builtin/ls-files.c | 9 ++++-----
> 1 file changed, 4 insertions(+), 5 deletions(-)
>
> diff --git a/builtin/ls-files.c b/builtin/ls-files.c
> index 18105ec7ea..1c0f057d02 100644
> --- a/builtin/ls-files.c
> +++ b/builtin/ls-files.c
> @@ -379,10 +379,7 @@ static void prune_cache(const char *prefix, size_t prefixlen)
> pos = cache_name_pos(prefix, prefixlen);
> if (pos < 0)
> pos = -pos-1;
> - memmove(active_cache, active_cache + pos,
> - (active_nr - pos) * sizeof(struct cache_entry *));
> - active_nr -= pos;
> - first = 0;
> + first = pos;
> last = active_nr;
> while (last > first) {
> int next = (last + first) >> 1;
> @@ -393,7 +390,9 @@ static void prune_cache(const char *prefix, size_t prefixlen)
> }
> last = next;
> }
> - active_nr = last;
> + memmove(active_cache, active_cache + pos,
> + (last - pos) * sizeof(struct cache_entry *));
> + active_nr = last - pos;
> }
>
> /*
> --
> 2.11.1
>
Both these patches look good to me.
--
Brandon Williams