First implementation of HUnique<T> and HUniqueSet<T>, which is supposed to replace UniqueValueId.

First implementation of HUnique<T> and HUniqueSet<T>, which is supposed to replace UniqueValueId.

BUG=
R=rossberg@chromium.org, verwaest@chromium.org

Committed: https://code.google.com/p/v8/source/detail?r=16683

[rossberg, 2013-09-11 10:34:07]

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h
File src/hydrogen.h (right):

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2309
src/hydrogen.h:2309: class HUnique V8_FINAL {
I think this should live somewhere else (e.g. handles.h or perhaps its own
file), and be named Unique, since it isn't really specific to Hydrogen.

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2384
src/hydrogen.h:2384: for (int j = size_ - 1; j >= i; j--) {
Could it be worth using memmove here?

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2412
src/hydrogen.h:2412: bool found = false;
The rest of this for-loop could be simplified to:

while (j < that->size_ && sought != that->array_[j]) j++;
if (j == that->size_) return false;

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2429
src/hydrogen.h:2429: out->Grow(this->size_ > that->size_ ? this->size_ :
that->size_, zone);
Nit: Min(...)

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2434
src/hydrogen.h:2434: if (j >= that->size_) break;  // Right has been exhausted.
Why not simply

while (i < this->size && j < that->size_)

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2462
src/hydrogen.h:2462: for (;;) {
Same here:

while (i < this->size && j < that->size_)

and then simply process the rests after the loop:

while (j < that->size_) out->array_[k++] = that->array_[j++];
while (i < this->size_) out->array_[k++] = this->array_[i++];

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2518
src/hydrogen.h:2518: int new_capacity = capacity_ + capacity_ + size;  //
2*current + needed
That seems like a lot, and can cause up to a 200% space overhead. What's the
rationale?

[Toon Verwaest, 2013-09-11 11:17:57]

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h
File src/hydrogen.h (right):

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2309
src/hydrogen.h:2309: class HUnique V8_FINAL {
A separate file would be nice.

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2316
src/hydrogen.h:2316: raw_address_ = reinterpret_cast<Address>(*handle);
Can we ensure that this is only called in a DisallowHeapAllocation? This is
pretty scary stuff.

The UniqueValueIds are in exactly such a scope, so they are already protected.
If you cannot do this because you plan on using this in parallel compilation;
could we just use the unique value ids that are stored up front rather than the
handles?

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2383
src/hydrogen.h:2383: Grow(size_ + 1, zone);
You can merge this code with the code after the for-loop by declaring "int i"
outside of the for-loop; then always growing by 1, moving elements past i to the
top (won't be any if i == size), and assigning array_[i] = uniq;

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2419
src/hydrogen.h:2419: if (!found) return false;
For minimal checking

if (that->size_ < this->size_) return false;
int j = 0;
for (int i = 0; i < this->size_; i++) {
  HUnique<T> sought = this->array_[i];
  do {
    if (sought == that->array[j++]) break;
    // Fail whenever we have less elements left in [that] than
    // we still need to find from [this].
    if (that->size_ - j < this->size_ - i) return false;
  } while (true);
}
return true;

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2429
src/hydrogen.h:2429: out->Grow(this->size_ > that->size_ ? this->size_ :
that->size_, zone);
I guess you meant to flip the sizes?
What about just using out->Grow(Min(this->size_, that->size_), zone) to avoid
problems :)

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2518
src/hydrogen.h:2518: int new_capacity = capacity_ + capacity_ + size;  //
2*current + needed
I guess this is 0, 1 or 4? Otherwise it seems like a lot of extra space...

[titzer, 2013-09-11 13:53:45]

On 2013/09/11 10:34:07, rossberg wrote:
> https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h
> File src/hydrogen.h (right):
> 
> https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2309
> src/hydrogen.h:2309: class HUnique V8_FINAL {
> I think this should live somewhere else (e.g. handles.h or perhaps its own
> file), and be named Unique, since it isn't really specific to Hydrogen.
> 

Yeah I agree that we might want it to live in a more general place later, but I
don't want to go too far down the path of generalizing it just yet. So, I want
to introduce it and start using in hydrogen, and when we find other uses for it,
we can move it out.

> https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2384
> src/hydrogen.h:2384: for (int j = size_ - 1; j >= i; j--) {
> Could it be worth using memmove here?

I thought about that, but that call would look like:
OS::MemMove(array_ + j + 1, array_ + j, (size_ - j - 1) * sizeof(HUnique<T>));

> 
> https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2412
> src/hydrogen.h:2412: bool found = false;
> The rest of this for-loop could be simplified to:
> 
> while (j < that->size_ && sought != that->array_[j]) j++;
> if (j == that->size_) return false;

Nice.

> 
> https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2429
> src/hydrogen.h:2429: out->Grow(this->size_ > that->size_ ? this->size_ :
> that->size_, zone);
> Nit: Min(...)
> 

Done.

> https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2434
> src/hydrogen.h:2434: if (j >= that->size_) break;  // Right has been
exhausted.
> Why not simply
> 
> while (i < this->size && j < that->size_)

Nice.

> 
> https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2462
> src/hydrogen.h:2462: for (;;) {
> Same here:
> 
> while (i < this->size && j < that->size_)
> 
> and then simply process the rests after the loop:
> 
> while (j < that->size_) out->array_[k++] = that->array_[j++];
> while (i < this->size_) out->array_[k++] = this->array_[i++];
> 

Oh alright. You fancy kids and your && constructs.

> https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2518
> src/hydrogen.h:2518: int new_capacity = capacity_ + capacity_ + size;  //
> 2*current + needed
> That seems like a lot, and can cause up to a 200% space overhead. What's the
> rationale?

I've used this growth heuristic before and it works pretty nicely. The rationale
is that most sets will be 1 element, probably 99.9% after that will be <= 4
elements (in fact, SmallMapList is limited to 4 elements, IIRC). Other sets
might be big, so you want to grow aggressively to avoid copying.

[rossberg, 2013-09-11 14:11:31]

On 2013/09/11 13:53:45, titzer wrote:
> On 2013/09/11 10:34:07, rossberg wrote:
> > https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h
> > File src/hydrogen.h (right):
> > 
> > https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2309
> > src/hydrogen.h:2309: class HUnique V8_FINAL {
> > I think this should live somewhere else (e.g. handles.h or perhaps its own
> > file), and be named Unique, since it isn't really specific to Hydrogen.
> 
> Yeah I agree that we might want it to live in a more general place later, but
I
> don't want to go too far down the path of generalizing it just yet. So, I want
> to introduce it and start using in hydrogen, and when we find other uses for
it,
> we can move it out.

It's already perfectly general. That's why this is the wrong place to put it. ;)
 And hydrogen.h is far too long already anyway.


> Oh alright. You fancy kids and your && constructs.

I'd like to propose a 5€ kitty tax for unjustified uses of goto (a.k.a. break).
:)


> > https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2518
> > src/hydrogen.h:2518: int new_capacity = capacity_ + capacity_ + size;  //
> > 2*current + needed
> > That seems like a lot, and can cause up to a 200% space overhead. What's the
> > rationale?
> 
> I've used this growth heuristic before and it works pretty nicely. The
rationale
> is that most sets will be 1 element, probably 99.9% after that will be <= 4
> elements (in fact, SmallMapList is limited to 4 elements, IIRC). Other sets
> might be big, so you want to grow aggressively to avoid copying.

Note that on average, you copy half of the array anyway.  If minimizing copying
was a concern, it might be worth avoiding the duplicate copying. But I agree
that for the sizes we are dealing with here, it probably doesn't matter either
way.

[Toon Verwaest, 2013-09-11 14:24:10]

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h
File src/hydrogen.h (right):

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2412
src/hydrogen.h:2412: bool found = false;
This version double-checks every entry though; since you don't increment to the
next value if sought == that->array[j].

On 2013/09/11 10:34:07, rossberg wrote:
> The rest of this for-loop could be simplified to:
> 
> while (j < that->size_ && sought != that->array_[j]) j++;
> if (j == that->size_) return false;

[rossberg, 2013-09-11 15:01:49]

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h
File src/hydrogen.h (right):

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2412
src/hydrogen.h:2412: bool found = false;
On 2013/09/11 14:24:11, Toon Verwaest wrote:
> This version double-checks every entry though; since you don't increment to
the
> next value if sought == that->array[j].
> 
> On 2013/09/11 10:34:07, rossberg wrote:
> > The rest of this for-loop could be simplified to:
> > 
> > while (j < that->size_ && sought != that->array_[j]) j++;
> > if (j == that->size_) return false;

Good catch. Tweaking that is left as an exercise. :)

[Toon Verwaest, 2013-09-11 15:27:52]

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h
File src/hydrogen.h (right):

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2412
src/hydrogen.h:2412: bool found = false;
Hence the version I attached in my previous comment ;)

On 2013/09/11 15:01:49, rossberg wrote:
> On 2013/09/11 14:24:11, Toon Verwaest wrote:
> > This version double-checks every entry though; since you don't increment to
> the
> > next value if sought == that->array[j].
> > 
> > On 2013/09/11 10:34:07, rossberg wrote:
> > > The rest of this for-loop could be simplified to:
> > > 
> > > while (j < that->size_ && sought != that->array_[j]) j++;
> > > if (j == that->size_) return false;
> 
> Good catch. Tweaking that is left as an exercise. :)

[titzer, 2013-09-11 16:52:03]

On 2013/09/11 15:27:52, Toon Verwaest wrote:
> https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h
> File src/hydrogen.h (right):
> 
> https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2412
> src/hydrogen.h:2412: bool found = false;
> Hence the version I attached in my previous comment ;)
> 

In the end I went with the Toon special.

> On 2013/09/11 15:01:49, rossberg wrote:
> > On 2013/09/11 14:24:11, Toon Verwaest wrote:
> > > This version double-checks every entry though; since you don't increment
to
> > the
> > > next value if sought == that->array[j].
> > > 
> > > On 2013/09/11 10:34:07, rossberg wrote:
> > > > The rest of this for-loop could be simplified to:
> > > > 
> > > > while (j < that->size_ && sought != that->array_[j]) j++;
> > > > if (j == that->size_) return false;
> > 
> > Good catch. Tweaking that is left as an exercise. :)

[titzer, 2013-09-11 16:52:40]

On 2013/09/11 10:34:07, rossberg wrote:
> https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h
> File src/hydrogen.h (right):
> 
> https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2309
> src/hydrogen.h:2309: class HUnique V8_FINAL {
> I think this should live somewhere else (e.g. handles.h or perhaps its own
> file), and be named Unique, since it isn't really specific to Hydrogen.
> 

Btw, as per discussion with Toon, I've moved this to hydrogen-unique.h.

[Toon Verwaest, 2013-09-11 19:28:40]

lgtm

[rossberg, 2013-09-12 09:34:36]

On 2013/09/11 16:52:40, titzer wrote:
> On 2013/09/11 10:34:07, rossberg wrote:
> > https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h
> > File src/hydrogen.h (right):
> > 
> > https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2309
> > src/hydrogen.h:2309: class HUnique V8_FINAL {
> > I think this should live somewhere else (e.g. handles.h or perhaps its own
> > file), and be named Unique, since it isn't really specific to Hydrogen.
> 
> Btw, as per discussion with Toon, I've moved this to hydrogen-unique.h.

Thanks. But please also remove the hydrogen and H from the names. This
abstraction is in no way specific to Hydrogen, and we gonna use it in other
places soon (e.g. zonified types).

[rossberg, 2013-09-12 09:34:45]

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h
File src/hydrogen.h (right):

https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2412
src/hydrogen.h:2412: bool found = false;
On 2013/09/11 15:27:53, Toon Verwaest wrote:
> Hence the version I attached in my previous comment ;)

That's still one for the kitty. :)

[titzer, 2013-09-12 10:46:33]

On 2013/09/12 09:34:45, rossberg wrote:
> https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h
> File src/hydrogen.h (right):
> 
> https://codereview.chromium.org/23609020/diff/1/src/hydrogen.h#newcode2412
> src/hydrogen.h:2412: bool found = false;
> On 2013/09/11 15:27:53, Toon Verwaest wrote:
> > Hence the version I attached in my previous comment ;)
> 
> That's still one for the kitty. :)

Renamed HUnique to Unique.

[rossberg, 2013-09-12 10:51:10]

lgtm

[titzer, 2013-09-12 12:09:05]

Committed patchset #4 manually as r16683 (presubmit successful).