Clean up Simple Index handling of removed entries.

Clean up Simple Index handling of removed entries.

The loop to remove entries seemed a bit silly going through both lists;
it's a bit more clear to do it on the merged set.

R=rdsmith,pliard
BUG=None

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=220618

[gavinp, 2013-08-10 18:16:30]

rdsmith, pliard: PTAL.

This is downstream of https://codereview.chromium.org/22406005/ , I'd have
included it there, but we are considering a merge of that issue, so I wanted to
minimize churn.

[Philippe, 2013-08-11 07:56:49]

lgtm, thanks Gavin!

[Randy Smith (Not in Mondays), 2013-08-11 23:50:11]

So I have no objection to landing this (so LGTM), but: a) IIUC, there shouldn't
be anything in the active index that's in removed_entries_, so you shouldn't
need to remove them from that list, and b) you'll have very slightly better
performance if you do the removal before the merge rather than after it because
you'll keep the size of index you're working on smaller at each step.  Is there
something I'm missing?

[gavinp, 2013-08-12 13:06:55]

On 2013/08/11 23:50:11, rdsmith wrote:
> So I have no objection to landing this (so LGTM), but: a) IIUC, there
shouldn't
> be anything in the active index that's in removed_entries_, so you shouldn't
> need to remove them from that list, and b) you'll have very slightly better
> performance if you do the removal before the merge rather than after it
because
> you'll keep the size of index you're working on smaller at each step.  Is
there
> something I'm missing?

Nope, nothing. Thanks for catching that. I've also gone ahead and moved the
clear() operation earlier, which further reduces fragmentation. Take another
peek if you like, I'll CQ this shortly as its upstream issue has landed.

[gavinp, 2013-08-12 13:08:28]

(also: note that the try jobs are relative to master, since LKGR hasn't advanced
past the upstream CL)

[Randy Smith (Not in Mondays), 2013-08-12 15:34:24]

Still LGTM.  

One other thought, though: I think the current algorithm is best for memory
allocation.  However, I'm not sure, and it's not best for CPU usage, so I wanted
to at least raise the (hypothetically :-}) best CPU algorithm.

I believe set inserts are O(log n), so the merge is O(n log n).  I believe that
sets are stored in an internal memory format s.t. iterating over all elements in
the set in order is O(n).  So I think a better computation algorithm would be
scanning the two sets in order (keeping the iteration point "the same" in both
sets), adding entries into a third set (presumably of good reserved size) as you
went, and then deleting the first two sets.  This does, of course, result in a
peak memory allocation noticeably higher than the current method.  A compromise
might be to do the in-order iteration, but do the insert in the current larger
set using the iterator (presumed O(1)?  Not sure), to get the benefits of both
the O(n) algorithm and not increasing peak memory allocation.

My gut says that the peak memory allocation is the dominant issue, so I'm not
pushing for this.  But having had the thought, I wanted to raise it.

[gavinp, 2013-08-28 20:19:49]

On 2013/08/12 15:34:24, rdsmith wrote:
> Still LGTM.  
> 
> One other thought, though: I think the current algorithm is best for memory
> allocation.  However, I'm not sure, and it's not best for CPU usage, so I
wanted
> to at least raise the (hypothetically :-}) best CPU algorithm.
> 
> I believe set inserts are O(log n), so the merge is O(n log n).  I believe
that
> sets are stored in an internal memory format s.t. iterating over all elements
in
> the set in order is O(n).  So I think a better computation algorithm would be
> scanning the two sets in order (keeping the iteration point "the same" in both
> sets), adding entries into a third set (presumably of good reserved size) as
you
> went, and then deleting the first two sets.  This does, of course, result in a
> peak memory allocation noticeably higher than the current method.  A
compromise
> might be to do the in-order iteration, but do the insert in the current larger
> set using the iterator (presumed O(1)?  Not sure), to get the benefits of both
> the O(n) algorithm and not increasing peak memory allocation.
> 
> My gut says that the peak memory allocation is the dominant issue, so I'm not
> pushing for this.  But having had the thought, I wanted to raise it.

We are using hash maps, not std::map, and so inserts are O(n), lookups are O(n)
and the merge is O(n). Further, if we're good about iterating over the smaller
list, we're probably optimal.

If we wanted to be super generic and stay linear if using the (typically binary
balanced tree) std::map, then I guess we could use std::set_difference or
std::set_symmetric_difference etc... to do this. I think it's overkill.

Incidentally, this is why I hate typedefs hiding STL types.

[commit-bot: I haz the power, 2013-08-30 15:16:19]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/gavinp@chromium.org/22430014/78001

[commit-bot: I haz the power, 2013-08-30 19:03:03]

Change committed as 220618