Add a UniqueVector class to GN

This is an ordered set tailored to GN's (simple) needs.

This vector is now used to store all config lists. Previously the code did a bunch of work to uniquify configs at certain points (in target.cc) but direct_dependent_configs still ended up with lots of duplicates.

Before this patch the chrome/browser target has 41098 direct_dependent_configs, and after this patch it has 7. Apparently we were also spending a lot of time on these. Before this patch Windows wall clock time was 1031ms, and after this patch it's 831ms. Linux was 834ms before and 593ms after.

Also fix minor build issues in base I noticed while working on this.

R=viettrungluu@chromium.org

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

[viettrungluu, 2013-10-08 23:39:41]

lgtm

https://codereview.chromium.org/26537002/diff/3001/tools/gn/uniquify.h
File tools/gn/uniquify.h (right):

https://codereview.chromium.org/26537002/diff/3001/tools/gn/uniquify.h#newcode77
tools/gn/uniquify.h:77: std::swap(cur, (*container)[dest_i]);
Having to do a swap is a little unfortunate (since you really want to move cur
to the dest_i position), though I don't see a good way to avoid it. :/

https://codereview.chromium.org/26537002/diff/3001/tools/gn/uniquify_unittest.cc
File tools/gn/uniquify_unittest.cc (right):

https://codereview.chromium.org/26537002/diff/3001/tools/gn/uniquify_unittest...
tools/gn/uniquify_unittest.cc:80: /* Performance test for measuring relative
performance of brute-force and
I wish it were easier to add perf tests (and monitoring of perf tests) to the
bots and such.

Arguably, this should be in a separate perf test target, and kept compiling at
least. <shrug>

[brettw, 2014-08-01 23:08:50]

PTAL.

This removes the Uniquify algorithm and replaces it with a UniqueVector
container that works similarly. This vector is append-only and should be pretty
straightforward.

This uses UniqueVector for storing configs. Previously these were getting
duplicated as dependents were getting pushed around the tree. I thought about
adding a unit test that dependent configs don't get duplicated, but the test
reduced to verifying that there aren't duplicates in a UniqueVector which seemed
like something that the Target level shouldn't need to be testing. Let me know
if you violently disagree and I can add something.

[viettrungluu, 2014-08-06 19:43:52]

https://codereview.chromium.org/26537002/diff/235001/tools/gn/unique_vector.h
File tools/gn/unique_vector.h (right):

https://codereview.chromium.org/26537002/diff/235001/tools/gn/unique_vector.h...
tools/gn/unique_vector.h:14: // This struct allows us to insert things by
reference into a hash table. This
Which struct are you talking about?

(Actually, this comment makes no sense to me.)

https://codereview.chromium.org/26537002/diff/235001/tools/gn/unique_vector.h...
tools/gn/unique_vector.h:39: UniquifyRef(const std::vector<T>* v, size_t i)
Why would you use this instead of passing &v[i] to the previous ctor?

https://codereview.chromium.org/26537002/diff/235001/tools/gn/unique_vector.h...
tools/gn/unique_vector.h:46: // Initialize with an array + index and a know hash
value to prevent
s/know/known/ I assume.

https://codereview.chromium.org/26537002/diff/235001/tools/gn/unique_vector.h...
tools/gn/unique_vector.h:111: // of configs and libraries, and are appended to
but not
appended to but not ... what?

https://codereview.chromium.org/26537002/diff/235001/tools/gn/unique_vector.h...
tools/gn/unique_vector.h:162: for (iter i = begin; i < end; i++)
Generally preferred:
!= end
++i

https://codereview.chromium.org/26537002/diff/235001/tools/gn/unique_vector.h...
tools/gn/unique_vector.h:163: push_back(*i);
Maybe you should have a (debug-only) assertion about uniqueness?

[brettw, 2014-08-06 20:13:03]

https://codereview.chromium.org/26537002/diff/235001/tools/gn/unique_vector.h
File tools/gn/unique_vector.h (right):

https://codereview.chromium.org/26537002/diff/235001/tools/gn/unique_vector.h...
tools/gn/unique_vector.h:39: UniquifyRef(const std::vector<T>* v, size_t i)
On 2014/08/06 19:43:52, viettrungluu wrote:
> Why would you use this instead of passing &v[i] to the previous ctor?

I clarified the class-level comment. The vector*+index is so that the references
don't go out-of-date when the vector is reallocated.

https://codereview.chromium.org/26537002/diff/235001/tools/gn/unique_vector.h...
tools/gn/unique_vector.h:163: push_back(*i);
On 2014/08/06 19:43:52, viettrungluu wrote:
> Maybe you should have a (debug-only) assertion about uniqueness?

This calls push_back which handles duplicate elements. It's not clear where such
an assertion would go in here that isn't obviously duplicative with the code
around it.

[viettrungluu, 2014-08-06 20:26:16]

Do you use UniquifyRef outside of the implementation of UniqueVector?

If not, maybe you should put it inside an internal:: namespace, since its API is
a little dubious.

On 2014/08/06 20:13:03, brettw wrote:
> https://codereview.chromium.org/26537002/diff/235001/tools/gn/unique_vector.h
> File tools/gn/unique_vector.h (right):
> 
>
https://codereview.chromium.org/26537002/diff/235001/tools/gn/unique_vector.h...
> tools/gn/unique_vector.h:39: UniquifyRef(const std::vector<T>* v, size_t i)
> On 2014/08/06 19:43:52, viettrungluu wrote:
> > Why would you use this instead of passing &v[i] to the previous ctor?
> 
> I clarified the class-level comment. The vector*+index is so that the
references
> don't go out-of-date when the vector is reallocated.
> 
>
https://codereview.chromium.org/26537002/diff/235001/tools/gn/unique_vector.h...
> tools/gn/unique_vector.h:163: push_back(*i);
> On 2014/08/06 19:43:52, viettrungluu wrote:
> > Maybe you should have a (debug-only) assertion about uniqueness?
> 
> This calls push_back which handles duplicate elements. It's not clear where
such
> an assertion would go in here that isn't obviously duplicative with the code
> around it.

Oh, right. It's calling your push_back, not the vector's.

[brettw, 2014-08-06 20:35:08]

On 2014/08/06 20:26:16, viettrungluu wrote:
> Do you use UniquifyRef outside of the implementation of UniqueVector?
> 
> If not, maybe you should put it inside an internal:: namespace, since its API
is
> a little dubious.

It already is.

[viettrungluu, 2014-08-06 21:42:49]

lgtm

[brettw, 2014-08-06 21:44:39]

Committed patchset #16 manually as 287865 (presubmit successful).