OrderedHashTable implementation with Set and Map interfaces

OrderedHashTable implementation with Set and Map interfaces

OrderedHashTable is an insertion-ordered HashTable based on
Jason Orendorff's writeup of a data structure attributed to Tyler Close:
https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables

It is intended as the new backing store for JSSet/JSMap, as ES6 requires
insertion-order-based iteration. Note, however, that in the interest of
keeping the initial check-in small this patch does not yet include any
iteration support.

This change also doesn't yet touch any existing behavior, but in
a branch I've verified that these structures pass the existing
JSSet/JSMap mjsunit tests.

BUG=v8:1793
LOG=N
R=mstarzinger@chromium.org

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

[adamk, 2014-04-01 00:13:17]

This could definitely use some more polish before landing (for example, the
initial capacity of 4 is probably silly), but I wanted to get some review
comments before I worked much more on this.

(Note that I spent some time working on this patch over at
https://codereview.chromium.org/202293004, but it seemed too confusing to
continue this work there, given all the work-in-progress patches I uploaded; let
me know if you disagree and I can port this CL description over there.)

[arv (Not doing code reviews), 2014-04-01 15:22:44]

https://codereview.chromium.org/220293002/diff/1/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode15898
src/objects.cc:15898: MaybeObject* OrderedHashTable<entrysize>::Allocate(Heap*
heap, int capacity) {
We should probably have a pretenure flag here too. If the old table was in the
old space we should probably create the new table in the old space as well.

[Michael Starzinger, 2014-04-02 12:09:36]

Looking good, I like this. The bulk of the comments is about handles vs. raw
pointers.

https://codereview.chromium.org/220293002/diff/1/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode15924
src/objects.cc:15924: MaybeObject* OrderedHashTable<entrysize>::EnsureGrowable()
{
Is there a particular reason why this implementation is unhandlified and the
sub-classes contain handle-wrappers? If not, I would vote for making this
implementation be handle-based. IIUC, this would alleviate the need to even
declare them explicitly.

Admittedly, doing that straight-forward would make the return type be
Handle<OrderedHashTable> instead of the concrete sub-class. But one idea
(courtesy of Andreas) would be to add a second template parameter (in addition
to "entrysize") to declare to concrete type.

https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode15942
src/objects.cc:15942: MaybeObject* OrderedHashTable<entrysize>::Shrink() {
Likewise.

https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode15956
src/objects.cc:15956: MaybeObject*
OrderedHashTable<entrysize>::Rehash(OrderedHashTable* new_table) {
AFAICT, addressing the above two comments would also allow us to implement this
one handle-based.

https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode16031
src/objects.cc:16031: Handle<OrderedHashSet> OrderedHashSet::EnsureGrowable(
Obsolete if above comments are addressed, I think.

https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode16040
src/objects.cc:16040: Handle<OrderedHashSet>
OrderedHashSet::Shrink(Handle<OrderedHashSet> table) {
Likewise.

https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode16078
src/objects.cc:16078: Handle<OrderedHashMap> OrderedHashMap::EnsureGrowable(
Likewise.

https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode16087
src/objects.cc:16087: Handle<OrderedHashMap>
OrderedHashMap::Shrink(Handle<OrderedHashMap> table) {
Likewise.

https://codereview.chromium.org/220293002/diff/1/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/220293002/diff/1/src/objects.h#newcode94
src/objects.h:94: //             - MapCache
nit: Can we add the three new classes into the hierarchy here?

https://codereview.chromium.org/220293002/diff/1/src/objects.h#newcode4267
src/objects.h:4267: //   [3]: "hash table", an array of length NumberOfBuckets()
entry numbers
nit: Can we somehow visually note that the "hash table" is actually at [3..n],
because currently it looks like there is an indirection at [3] that points to
the "hash table".

https://codereview.chromium.org/220293002/diff/1/test/cctest/test-ordered-has...
File test/cctest/test-ordered-hash-table.cc (right):

https://codereview.chromium.org/220293002/diff/1/test/cctest/test-ordered-has...
test/cctest/test-ordered-hash-table.cc:158: // BELOW THIS LINE TESTS WERE
CONVERTED FROM test-dictionary.cc
It would be nice if we could avoid duplicating the tests from test-dictionary.cc
here. Would it be possible to templatize the tests in test-dictionary.cc and
instantiate them there for both, ObjectHashTable and OrderedHashMap. At a first
glance this looks doable for all tests right after the call to
Factory::NewFoo().

[Michael Starzinger, 2014-04-02 12:12:17]

One clarification.

https://codereview.chromium.org/220293002/diff/1/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode15924
src/objects.cc:15924: MaybeObject* OrderedHashTable<entrysize>::EnsureGrowable()
{
On 2014/04/02 12:09:37, Michael Starzinger wrote:
> Is there a particular reason why this implementation is unhandlified and the
> sub-classes contain handle-wrappers? If not, I would vote for making this
> implementation be handle-based. IIUC, this would alleviate the need to even
> declare them explicitly.

... [to declare them explicitly] in the concrete subclasses again.
 
> Admittedly, doing that straight-forward would make the return type be
> Handle<OrderedHashTable> instead of the concrete sub-class. But one idea
> (courtesy of Andreas) would be to add a second template parameter (in addition
> to "entrysize") to declare to concrete type.

[rossberg, 2014-04-02 13:09:12]

https://codereview.chromium.org/220293002/diff/1/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode15924
src/objects.cc:15924: MaybeObject* OrderedHashTable<entrysize>::EnsureGrowable()
{
On 2014/04/02 12:09:37, Michael Starzinger wrote:
> Is there a particular reason why this implementation is unhandlified and the
> sub-classes contain handle-wrappers? If not, I would vote for making this
> implementation be handle-based. IIUC, this would alleviate the need to even
> declare them explicitly.
> 
> Admittedly, doing that straight-forward would make the return type be
> Handle<OrderedHashTable> instead of the concrete sub-class. But one idea
> (courtesy of Andreas) would be to add a second template parameter (in addition
> to "entrysize") to declare to concrete type.

More concretely, something like

template<class Derived, int entrysize> class OrderHashTable {
  // ..., e.g.:
  Handle<Derived> Rehash(Handle<Derived>);
};

class OrderedHashSet: OrderedHashTable<OrderedHashSet, 1> { ... };

should work (perhaps with some extra tweaks).

[adamk, 2014-04-02 22:01:10]

https://codereview.chromium.org/220293002/diff/1/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode15924
src/objects.cc:15924: MaybeObject* OrderedHashTable<entrysize>::EnsureGrowable()
{
On 2014/04/02 13:09:12, rossberg wrote:
> On 2014/04/02 12:09:37, Michael Starzinger wrote:
> > Is there a particular reason why this implementation is unhandlified and the
> > sub-classes contain handle-wrappers? If not, I would vote for making this
> > implementation be handle-based. IIUC, this would alleviate the need to even
> > declare them explicitly.
> > 
> > Admittedly, doing that straight-forward would make the return type be
> > Handle<OrderedHashTable> instead of the concrete sub-class. But one idea
> > (courtesy of Andreas) would be to add a second template parameter (in
addition
> > to "entrysize") to declare to concrete type.
> 
> More concretely, something like
> 
> template<class Derived, int entrysize> class OrderHashTable {
>   // ..., e.g.:
>   Handle<Derived> Rehash(Handle<Derived>);
> };
> 
> class OrderedHashSet: OrderedHashTable<OrderedHashSet, 1> { ... };
> 
> should work (perhaps with some extra tweaks).

Done and done. This code was so-structured because it was based on
ObjectHashTable.

Note that in the current patch Allocate() is also handlified, but this seems to
go against the norms of objects.cc...let me know what's preferred here.

https://codereview.chromium.org/220293002/diff/1/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/220293002/diff/1/src/objects.h#newcode94
src/objects.h:94: //             - MapCache
On 2014/04/02 12:09:37, Michael Starzinger wrote:
> nit: Can we add the three new classes into the hierarchy here?

Done.

https://codereview.chromium.org/220293002/diff/1/src/objects.h#newcode4267
src/objects.h:4267: //   [3]: "hash table", an array of length NumberOfBuckets()
entry numbers
On 2014/04/02 12:09:37, Michael Starzinger wrote:
> nit: Can we somehow visually note that the "hash table" is actually at [3..n],
> because currently it looks like there is an indirection at [3] that points to
> the "hash table".

Explained more. This could probably use some more explanation, though, I'll see
if I can figure a better way to lay it out.

https://codereview.chromium.org/220293002/diff/1/test/cctest/test-ordered-has...
File test/cctest/test-ordered-hash-table.cc (right):

https://codereview.chromium.org/220293002/diff/1/test/cctest/test-ordered-has...
test/cctest/test-ordered-hash-table.cc:158: // BELOW THIS LINE TESTS WERE
CONVERTED FROM test-dictionary.cc
On 2014/04/02 12:09:37, Michael Starzinger wrote:
> It would be nice if we could avoid duplicating the tests from
test-dictionary.cc
> here. Would it be possible to templatize the tests in test-dictionary.cc and
> instantiate them there for both, ObjectHashTable and OrderedHashMap. At a
first
> glance this looks doable for all tests right after the call to
> Factory::NewFoo().

Yeah, should be able to take care of this, will look into it next.

[adamk, 2014-04-03 22:38:48]

Updated tests to avoid duplication

[adamk, 2014-04-03 22:53:38]

https://codereview.chromium.org/220293002/diff/1/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode15898
src/objects.cc:15898: MaybeObject* OrderedHashTable<entrysize>::Allocate(Heap*
heap, int capacity) {
On 2014/04/01 15:22:45, arv wrote:
> We should probably have a pretenure flag here too. If the old table was in the
> old space we should probably create the new table in the old space as well.

Added a PretenureFlag, though I wonder if I need to do something like what
HashTable does and have a minimum size I'll allocate in the old space.

[Michael Starzinger, 2014-04-04 09:38:12]

LGTM, just two nits left.

https://codereview.chromium.org/220293002/diff/1/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode15924
src/objects.cc:15924: MaybeObject* OrderedHashTable<entrysize>::EnsureGrowable()
{
On 2014/04/02 22:01:10, adamk wrote:
> On 2014/04/02 13:09:12, rossberg wrote:
> > On 2014/04/02 12:09:37, Michael Starzinger wrote:
> > > Is there a particular reason why this implementation is unhandlified and
the
> > > sub-classes contain handle-wrappers? If not, I would vote for making this
> > > implementation be handle-based. IIUC, this would alleviate the need to
even
> > > declare them explicitly.
> > > 
> > > Admittedly, doing that straight-forward would make the return type be
> > > Handle<OrderedHashTable> instead of the concrete sub-class. But one idea
> > > (courtesy of Andreas) would be to add a second template parameter (in
> addition
> > > to "entrysize") to declare to concrete type.
> > 
> > More concretely, something like
> > 
> > template<class Derived, int entrysize> class OrderHashTable {
> >   // ..., e.g.:
> >   Handle<Derived> Rehash(Handle<Derived>);
> > };
> > 
> > class OrderedHashSet: OrderedHashTable<OrderedHashSet, 1> { ... };
> > 
> > should work (perhaps with some extra tweaks).
> 
> Done and done. This code was so-structured because it was based on
> ObjectHashTable.
> 
> Note that in the current patch Allocate() is also handlified, but this seems
to
> go against the norms of objects.cc...let me know what's preferred here.

I definitely prefer handlified as you did in your recent patch set.

https://codereview.chromium.org/220293002/diff/80001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/220293002/diff/80001/src/objects.cc#newcode15900
src/objects.cc:15900: // capacity must be a factor of two
nit: Comment says "factor", code says "power". Also please capitalize and
punctuate comment.

https://codereview.chromium.org/220293002/diff/80001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/220293002/diff/80001/src/objects.h#newcode4294
src/objects.h:4294: static OrderedHashTable* cast(Object* obj) {
nit: Since this can be considered an abstract class and the two concrete
sub-classes both have their own casting method, should we even have this casting
method? If it is actually used/needed anywhere I am fine with it of course.

[adamk, 2014-04-04 20:18:35]

https://codereview.chromium.org/220293002/diff/80001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/220293002/diff/80001/src/objects.cc#newcode15900
src/objects.cc:15900: // capacity must be a factor of two
On 2014/04/04 09:38:13, Michael Starzinger wrote:
> nit: Comment says "factor", code says "power". Also please capitalize and
> punctuate comment.

Done and explained why. In a follow-up I'll probably just add a "capacity"
field.

https://codereview.chromium.org/220293002/diff/80001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/220293002/diff/80001/src/objects.h#newcode4294
src/objects.h:4294: static OrderedHashTable* cast(Object* obj) {
On 2014/04/04 09:38:13, Michael Starzinger wrote:
> nit: Since this can be considered an abstract class and the two concrete
> sub-classes both have their own casting method, should we even have this
casting
> method? If it is actually used/needed anywhere I am fine with it of course.

Removed, this was previously used but no longer.

[adamk, 2014-04-04 20:42:04]

Committed patchset #6 manually as r20522 (presubmit successful).

[arv (Not doing code reviews), 2014-04-07 00:01:20]

LGTM

https://codereview.chromium.org/220293002/diff/100001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/220293002/diff/100001/src/objects.h#newcode4259
src/objects.h:4259: // Only Object* keys are supported, with Object::SameValue()
used as the
ES6 Map/Set uses SameValueZero (which treats -0 and +0 as equal). We currently
have a hack to handle this on the js side. Since this is only used for
JSMap/JSSet we might want to change this on the C++ side.