Hash tables templates, wrapping Array.

Hash tables templates, wrapping Array.

Highly customizable to support various internal uses as well as the basis for user-level classes.

Use in Library's resolved names cache.

Next step is to add new instance classes for the user-level maps/sets (akin to GrowableObjectArray).

R=asiva@google.com

Committed: https://code.google.com/p/dart/source/detail?r=37716

[koda, 2014-06-06 17:42:00]

The code is quite template-heavy, mostly because I wanted to share code, and
also to some extent to avoid the overhead of virtuals.

There are still some aspects of the implementation I'd like to polish more, like
the growth/shrinkage policy and probing sequence, but I especially wanted to get
some feedback on the handle-wrapping interface.

This low-level handle-wrapping interface is meant to be useful for internal uses
of tables where none of the user-level maps/sets work out-of-the-box, for
instance when looking up a Field by its String name, or by a char*.

[siva, 2014-06-13 19:51:19]

Sorry for the delay, just a few nits.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h
File runtime/vm/hash_table.h (right):

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:96: // TODO(koda): Adjust after moving to quadratic
probing.
Is there an assertion to ensure that there is at least one unoccupied entry.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:146: bool FindKeyOrDeletedOrUnused(const Key& key,
intptr_t* entry) const {
ASSERT(entry != NULL);

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:157: deleted = (deleted != -1) ? deleted : probe;
why not :
if (deleted == -1) {
  deleted = probe;
}
would be more explicit in stating that we want to set deleted only if it has not
been already set.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:262: return smi.Value();
You could write this as:
ASSERT(Object::Handle(data_.At(index)).IsSmi());
return Smi::Value(Smi::RawCast(data_.At(index)));
That would avoid a handle creation in what appears to be a critical path.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:267: smi = Smi::New(value);
const Smi& smi = Smi::Handle(Smi::New(value));

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:275: data_.SetAt(index, smi);
Assuming GetSmiValueAt is changed above to a non handle version
can this function be written as:

SetSmiValueAt(index, (GetSmiValueAt(index) + delta));

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:299: } while (entry_ < table_->NumEntries() &&
!table_->IsOccupied(entry_));
One could call MoveNext() repeatedly cause an integer overflow and a subsequent
crash when table->isOccupied(entry) is called. Not sure if
that is an issue.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:319: }
Why is it necessary to have these methods which just call the base methods isn't
that implicit when Initialize, InsertKey, DeleteEntry is called?

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:353: ++index_;
Ditto comment, I feel MoveNext should not allow the index to grow past the max
size to avoid overflow issues. This could be written as

if (index < (static_cast<intptr_t>(entries_.size() - 1)) {
  index++;
  return true;
}
return false;

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:378: }
Ditto comment about DeleteEntry, is it needed?

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table_t...
File runtime/vm/hash_table_test.cc (right):

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table_t...
runtime/vm/hash_table_test.cc:29: static bool IsMatch(const std::string& key,
const Object& obj) {
why do you want the C++ string API here, we try to avoid uses of the C++ string
as much as possible,

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table_t...
runtime/vm/hash_table_test.cc:32: static uword Hash(const std::string& key) {
Ditto comment about C++ string.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table_t...
runtime/vm/hash_table_test.cc:36: return b.IsString() &&
String::Cast(a).Equals(String::Cast(b));
a.IsString() needs to be checked too?

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table_t...
runtime/vm/hash_table_test.cc:66: EXPECT_LE(5, table.NumEntries());
why EXPECT_LE(5, ...) instead of EXPECT_EQ(0, ...);

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/object.cc#ne...
runtime/vm/object.cc:8517: ASSERT(cache.Release() == resolved_names());
Strange that you are calling Release which has a side effect in the
ASSERT that would mean no side effect in the 'release' build.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/object.cc#ne...
runtime/vm/object.cc:9056: Array& cache =
Array::Handle(HashTables::New<ResolvedNamesMap>(size));
const Array& cache = ...;

[koda, 2014-06-23 19:44:56]

Addressed all comments and updated issue14236_test; PTAL.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h
File runtime/vm/hash_table.h (right):

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:96: // TODO(koda): Adjust after moving to quadratic
probing.
On 2014/06/13 19:51:18, siva wrote:
> Is there an assertion to ensure that there is at least one unoccupied entry.

Yes; see InsertKey.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:146: bool FindKeyOrDeletedOrUnused(const Key& key,
intptr_t* entry) const {
On 2014/06/13 19:51:18, siva wrote:
> ASSERT(entry != NULL);

Done.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:157: deleted = (deleted != -1) ? deleted : probe;
On 2014/06/13 19:51:18, siva wrote:
> why not :
> if (deleted == -1) {
>   deleted = probe;
> }
> would be more explicit in stating that we want to set deleted only if it has
not
> been already set.

Done.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:262: return smi.Value();
On 2014/06/13 19:51:18, siva wrote:
> You could write this as:
> ASSERT(Object::Handle(data_.At(index)).IsSmi());
> return Smi::Value(Smi::RawCast(data_.At(index)));
> That would avoid a handle creation in what appears to be a critical path.

Done.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:267: smi = Smi::New(value);
On 2014/06/13 19:51:18, siva wrote:
> const Smi& smi = Smi::Handle(Smi::New(value));

Done.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:275: data_.SetAt(index, smi);
On 2014/06/13 19:51:18, siva wrote:
> Assuming GetSmiValueAt is changed above to a non handle version
> can this function be written as:
> 
> SetSmiValueAt(index, (GetSmiValueAt(index) + delta));

Done.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:299: } while (entry_ < table_->NumEntries() &&
!table_->IsOccupied(entry_));
On 2014/06/13 19:51:18, siva wrote:
> One could call MoveNext() repeatedly cause an integer overflow and a
subsequent
> crash when table->isOccupied(entry) is called. Not sure if
> that is an issue.

True. Rewrote the loop to avoid this.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:319: }
On 2014/06/13 19:51:18, siva wrote:
> Why is it necessary to have these methods which just call the base methods
isn't
> that implicit when Initialize, InsertKey, DeleteEntry is called?

They are not necessary.

I just wanted to be explicit that these methods do not need any extra
book-keeping in this case (unlike enum index below).

Replaced them with a comment instead.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:353: ++index_;
On 2014/06/13 19:51:18, siva wrote:
> Ditto comment, I feel MoveNext should not allow the index to grow past the max
> size to avoid overflow issues. This could be written as
> 
> if (index < (static_cast<intptr_t>(entries_.size() - 1)) {
>   index++;
>   return true;
> }
> return false;

Done.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
runtime/vm/hash_table.h:378: }
On 2014/06/13 19:51:18, siva wrote:
> Ditto comment about DeleteEntry, is it needed?

Done.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table_t...
File runtime/vm/hash_table_test.cc (right):

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table_t...
runtime/vm/hash_table_test.cc:29: static bool IsMatch(const std::string& key,
const Object& obj) {
On 2014/06/13 19:51:18, siva wrote:
> why do you want the C++ string API here, we try to avoid uses of the C++
string
> as much as possible,

Removed.

Mainly, it was to show that an arbitrary number of lookup types can be defined.

I used std::string in this test because it conveniently constructs sample
strings. It can be rewritten to use C strings if needed.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table_t...
runtime/vm/hash_table_test.cc:32: static uword Hash(const std::string& key) {
On 2014/06/13 19:51:18, siva wrote:
> Ditto comment about C++ string.

Done.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table_t...
runtime/vm/hash_table_test.cc:36: return b.IsString() &&
String::Cast(a).Equals(String::Cast(b));
On 2014/06/13 19:51:19, siva wrote:
> a.IsString() needs to be checked too?

Done.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table_t...
runtime/vm/hash_table_test.cc:66: EXPECT_LE(5, table.NumEntries());
On 2014/06/13 19:51:19, siva wrote:
> why EXPECT_LE(5, ...) instead of EXPECT_EQ(0, ...);

NumEntries is the *total* number of entries (contrast with NumOccupied below).
Depending on the probe strategy, it may be more than 5, to guarantee that we can
actually perform 5 insertions.

Extended test to actually reach 5 occupied entries and added comment.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/object.cc#ne...
runtime/vm/object.cc:8517: ASSERT(cache.Release() == resolved_names());
On 2014/06/13 19:51:19, siva wrote:
> Strange that you are calling Release which has a side effect in the
> ASSERT that would mean no side effect in the 'release' build.

Done.

https://codereview.chromium.org/304253002/diff/100001/runtime/vm/object.cc#ne...
runtime/vm/object.cc:9056: Array& cache =
Array::Handle(HashTables::New<ResolvedNamesMap>(size));
On 2014/06/13 19:51:19, siva wrote:
> const Array& cache = ...;

Done.

[koda, 2014-06-25 23:37:21]

On 2014/06/23 19:44:56, koda wrote:
> Addressed all comments and updated issue14236_test; PTAL.
> 
> https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h
> File runtime/vm/hash_table.h (right):
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
> runtime/vm/hash_table.h:96: // TODO(koda): Adjust after moving to quadratic
> probing.
> On 2014/06/13 19:51:18, siva wrote:
> > Is there an assertion to ensure that there is at least one unoccupied entry.
> 
> Yes; see InsertKey.
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
> runtime/vm/hash_table.h:146: bool FindKeyOrDeletedOrUnused(const Key& key,
> intptr_t* entry) const {
> On 2014/06/13 19:51:18, siva wrote:
> > ASSERT(entry != NULL);
> 
> Done.
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
> runtime/vm/hash_table.h:157: deleted = (deleted != -1) ? deleted : probe;
> On 2014/06/13 19:51:18, siva wrote:
> > why not :
> > if (deleted == -1) {
> >   deleted = probe;
> > }
> > would be more explicit in stating that we want to set deleted only if it has
> not
> > been already set.
> 
> Done.
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
> runtime/vm/hash_table.h:262: return smi.Value();
> On 2014/06/13 19:51:18, siva wrote:
> > You could write this as:
> > ASSERT(Object::Handle(data_.At(index)).IsSmi());
> > return Smi::Value(Smi::RawCast(data_.At(index)));
> > That would avoid a handle creation in what appears to be a critical path.
> 
> Done.
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
> runtime/vm/hash_table.h:267: smi = Smi::New(value);
> On 2014/06/13 19:51:18, siva wrote:
> > const Smi& smi = Smi::Handle(Smi::New(value));
> 
> Done.
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
> runtime/vm/hash_table.h:275: data_.SetAt(index, smi);
> On 2014/06/13 19:51:18, siva wrote:
> > Assuming GetSmiValueAt is changed above to a non handle version
> > can this function be written as:
> > 
> > SetSmiValueAt(index, (GetSmiValueAt(index) + delta));
> 
> Done.
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
> runtime/vm/hash_table.h:299: } while (entry_ < table_->NumEntries() &&
> !table_->IsOccupied(entry_));
> On 2014/06/13 19:51:18, siva wrote:
> > One could call MoveNext() repeatedly cause an integer overflow and a
> subsequent
> > crash when table->isOccupied(entry) is called. Not sure if
> > that is an issue.
> 
> True. Rewrote the loop to avoid this.
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
> runtime/vm/hash_table.h:319: }
> On 2014/06/13 19:51:18, siva wrote:
> > Why is it necessary to have these methods which just call the base methods
> isn't
> > that implicit when Initialize, InsertKey, DeleteEntry is called?
> 
> They are not necessary.
> 
> I just wanted to be explicit that these methods do not need any extra
> book-keeping in this case (unlike enum index below).
> 
> Replaced them with a comment instead.
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
> runtime/vm/hash_table.h:353: ++index_;
> On 2014/06/13 19:51:18, siva wrote:
> > Ditto comment, I feel MoveNext should not allow the index to grow past the
max
> > size to avoid overflow issues. This could be written as
> > 
> > if (index < (static_cast<intptr_t>(entries_.size() - 1)) {
> >   index++;
> >   return true;
> > }
> > return false;
> 
> Done.
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table.h...
> runtime/vm/hash_table.h:378: }
> On 2014/06/13 19:51:18, siva wrote:
> > Ditto comment about DeleteEntry, is it needed?
> 
> Done.
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table_t...
> File runtime/vm/hash_table_test.cc (right):
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table_t...
> runtime/vm/hash_table_test.cc:29: static bool IsMatch(const std::string& key,
> const Object& obj) {
> On 2014/06/13 19:51:18, siva wrote:
> > why do you want the C++ string API here, we try to avoid uses of the C++
> string
> > as much as possible,
> 
> Removed.
> 
> Mainly, it was to show that an arbitrary number of lookup types can be
defined.
> 
> I used std::string in this test because it conveniently constructs sample
> strings. It can be rewritten to use C strings if needed.
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table_t...
> runtime/vm/hash_table_test.cc:32: static uword Hash(const std::string& key) {
> On 2014/06/13 19:51:18, siva wrote:
> > Ditto comment about C++ string.
> 
> Done.
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table_t...
> runtime/vm/hash_table_test.cc:36: return b.IsString() &&
> String::Cast(a).Equals(String::Cast(b));
> On 2014/06/13 19:51:19, siva wrote:
> > a.IsString() needs to be checked too?
> 
> Done.
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/hash_table_t...
> runtime/vm/hash_table_test.cc:66: EXPECT_LE(5, table.NumEntries());
> On 2014/06/13 19:51:19, siva wrote:
> > why EXPECT_LE(5, ...) instead of EXPECT_EQ(0, ...);
> 
> NumEntries is the *total* number of entries (contrast with NumOccupied below).
> Depending on the probe strategy, it may be more than 5, to guarantee that we
can
> actually perform 5 insertions.
> 
> Extended test to actually reach 5 occupied entries and added comment.
> 
> https://codereview.chromium.org/304253002/diff/100001/runtime/vm/object.cc
> File runtime/vm/object.cc (right):
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/object.cc#ne...
> runtime/vm/object.cc:8517: ASSERT(cache.Release() == resolved_names());
> On 2014/06/13 19:51:19, siva wrote:
> > Strange that you are calling Release which has a side effect in the
> > ASSERT that would mean no side effect in the 'release' build.
> 
> Done.
> 
>
https://codereview.chromium.org/304253002/diff/100001/runtime/vm/object.cc#ne...
> runtime/vm/object.cc:9056: Array& cache =
> Array::Handle(HashTables::New<ResolvedNamesMap>(size));
> On 2014/06/13 19:51:19, siva wrote:
> > const Array& cache = ...;
> 
> Done.

Ping.

I'd like to know asap if you feel any major changes are needed, since I'm
already working on the next step: adding a DefaultHashMap subclass of Instance
and, protected behind a flag, use it for default-constructed maps.

Thanks,
 Daniel

[siva, 2014-06-26 00:27:21]

LGTM.

Can you add a comment in hash_table.h that the use of
stl map and vector is a temporary step and would go away
once we have true dart heap objects for these.

[koda, 2014-06-26 00:50:46]

On 2014/06/26 00:27:21, siva wrote:
> LGTM.
> 
> Can you add a comment in hash_table.h that the use of
> stl map and vector is a temporary step and would go away
> once we have true dart heap objects for these.

Done.

[koda, 2014-06-26 00:51:09]

Committed patchset #8 manually as r37716 (presubmit successful).