Environment bookkeping has linear time complexity now, not a quadratic one.

Environment bookkeping has linear time complexity now, not a quadratic one.

This reduces the time take for mjsunit/limit-locals from 56.8s to 15.1s in debug
mode and from 12.0s to 1.6s in release mode.

Note that GrowableBitVector and BitVector should really be merged, and probably
have their allocation strategy parmeterized. The current state of affairs
involving tons of checks and delegation is extremely ugly, and it is far from
clear if all that special casing is a clear win. STL FTW! :-P

Committed: http://code.google.com/p/v8/source/detail?r=13327

[Toon Verwaest, 2013-01-07 15:10:34]

lgtm with nits

https://codereview.chromium.org/11775016/diff/1/src/data-flow.h
File src/data-flow.h (right):

https://codereview.chromium.org/11775016/diff/1/src/data-flow.h#newcode229
src/data-flow.h:229: void Union(const GrowableBitVector& other, Zone* zone) {
I'd prefer keeping the original AddAll name (in the client of this method).
Union sounds like it would return a new vector as the union of both arguments.

Could possibly EnsureCapacity(other->Length());

[Sven Panne, 2013-01-07 15:27:37]

https://codereview.chromium.org/11775016/diff/1/src/data-flow.h
File src/data-flow.h (right):

https://codereview.chromium.org/11775016/diff/1/src/data-flow.h#newcode229
src/data-flow.h:229: void Union(const GrowableBitVector& other, Zone* zone) {
On 2013/01/07 15:10:34, Toon Verwaest wrote:
> I'd prefer keeping the original AddAll name (in the client of this method).
> Union sounds like it would return a new vector as the union of both arguments.

I intentionally chose Union, because it is semantically the same as
BitVector::Union, so it is much more important to keep it consistent with that
than with any other collections data structure. All (Growable)BitVector
functions destructively change "this", and as much as I would like it, I don't
remember seeing any persistent/immutable data structure in v8. :-P

> Could possibly EnsureCapacity(other->Length());

Again, I considered this, but this is not necessarily an improvement: other
could have been overallocated, so this would be wasteful. In any case: Don't
optimize unless you have hard numbers, and the gprof profile tells me that this
is definitely not hot.

In any case I agree that there should be some naming/semantic cleanup of the
current collection chaos, but this is intended to be a small localized CL. :-)

[Toon Verwaest, 2013-01-07 15:31:16]

I presumed so. Yes, we should clean up naming... Still LGTM though.