carlosmn/libgit2 — comment on commit 6f38bf6e78f21ace75998ea6ae5903ad541d86a6
File:  line 0
By peff:

On Fri, Oct 28, 2011 at 11:59:59AM -0700, Carlos Martín Nieto wrote:

> I remembered there was actually a sensible reason why I chose to do a
> tree search. The idea was to make it faster when we there were a lot
> of additions by figuring out how many there were and signalling all of
> them instead of comparing each addition in the list. It probably
> doesn't make it that much faster, though.

I don't see how your way makes that faster, though. You only signal a
chunk of additions if they are at the end, which is the same as in my
proposed code. If you have an addition (or deletion) in the middle, you
will end up just signaling one at a time anyway.

Your algorithm is O(n*lg(n)) in the worst case[1]. A straight list merge
is always O(n). Probably not a huge difference, but I actually think
the merge is simpler to read, too (it also has better cache locality,
but that is the sort of thing that you really have to benchmark to
analyze, anyway).

-Peff

[1] Your worst case is that everything in "A" gets moved to a new
filename in "B", but the new "B" names all sort after the new "A" names.
You hit each "A" entry individually, binary searching in "B" to find
that it isn't there.