Closed Bug 810192 Opened 9 years ago Closed 9 years ago

don't require a default constructor for Hash{Map,Set}; only construct objects for live elements

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla19

People

(Reporter: luke, Assigned: luke)

References

Details

Attachments

(1 file, 2 obsolete files)

Attached patch patch (obsolete) — Splinter Review
Currently, we immediately default-construct Hash{Map,Set} entries when we first allocate the buffer.  I just ran into a use case where I have a type that has no good option for a default constructor, so I'd like to remove this restriction.  With this patch, we only in-place construct a key/value when an element is added and we destroy it when the element is removed.

This patch required some pretty broad changes but, fortunately, they were mostly trivial and guided by the type system.  These changes ended up revealing a lot of simplifications making this patch net -50 lines.

Incidentally this change (and the assert I added that we only access live elements that somehow was missing on the Ptr::operator* path) exposed two "bugs" where we were unconditionally dereferencing a Ptr.  Fortunately, both cases were saved (and are well-defined) due to the current guaranteed-default-constructed status of "dead" elements.

I also tidied up a bit: putting HashMap/Set before the alloc policies before the impl (which is the order you'd like to read), changing to the new // comment style, and removing some cruft that got into the public interface.  Unfortunately, I accidentally mixed in the tidying with the changes above; sorry about that.  Since the underlying change wants a simple audit of most of HashTable.h anyway, I didn't try to separate the two patches back out.
Attachment #679966 - Flags: review?(terrence)
Summary: don't require a default constructor for Hash{Map,Set}; only construct for live elements → don't require a default constructor for Hash{Map,Set}; only construct objects for live elements
Attached patch patch v.2 (obsolete) — Splinter Review
Windows and Linux take privacy a bit more seriously than gcc.
Attachment #679966 - Attachment is obsolete: true
Attachment #679966 - Flags: review?(terrence)
Attachment #679969 - Flags: review?(terrence)
Attached patch patch v.4Splinter Review
The third patch also burned down, fell over, then sank into the swamp.  (Template subtleties with clang.)  But this fourth one looks green.
Attachment #679969 - Attachment is obsolete: true
Attachment #679969 - Flags: review?(terrence)
Attachment #680105 - Flags: review?(terrence)
Comment on attachment 680105 [details] [diff] [review]
patch v.4

Review of attachment 680105 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/public/HashTable.h
@@ +28,5 @@
> +// values. In particular, HashMap calls constructors and destructors of all
> +// objects added so non-PODs may be used safely.
> +//
> +// Key/Value requirements:
> +//  - default constructible, movable, destructible, assignable

Seems like this first is out-of-date now.
Hah, indeed :)
Comment on attachment 680105 [details] [diff] [review]
patch v.4

Review of attachment 680105 [details] [diff] [review]:
-----------------------------------------------------------------

I gave it a careful read and all I was able to find were style and documentation nits.  And a few gaps in my understanding of C++, but that was pre-existing.

::: js/public/HashTable.h
@@ +28,5 @@
> +// values. In particular, HashMap calls constructors and destructors of all
> +// objects added so non-PODs may be used safely.
> +//
> +// Key/Value requirements:
> +//  - default constructible, movable, destructible, assignable

You'll probably want to at least remove "default constructible" (sp) from this list.

@@ +46,5 @@
> +class HashMap
> +{
> +    typedef HashMapEntry<Key, Value> TableEntry;
> +
> +    struct MapHashPolicy : HashPolicy {

{ on new line.

@@ +170,5 @@
> +    // be initialized again before any use.
> +    void finish()                                     { impl.finish(); }
> +
> +    // Does the table contain any entries?
> +    bool empty() const                                { return impl.empty(); }

It would be nice if this could be |isEmpty()|, but that's not for this patch.

@@ +215,5 @@
> +        Entry e(k, v);
> +        return impl.putNew(k, Move(e));
> +    }
> +
> +    // Add (k,defaultValue) if k no found. Return false-y Ptr on oom.

s/no/is not/
s/Return false-y/Return a false-y/
And add || to |k|.

@@ +248,5 @@
> +// particular, HashSet calls constructors and destructors of all objects added
> +// so non-PODs may be used safely.
> +//
> +// T requirements:
> +//  - default constructible, movable, destructible, assignable

Same fix as above.

@@ +263,5 @@
> +          class HashPolicy = DefaultHasher<T>,
> +          class AllocPolicy = TempAllocPolicy>
> +class HashSet
> +{
> +    struct SetOps : HashPolicy {

{ on newline.

@@ +328,5 @@
> +    //    }
> +    //    assert(*p == 3);
> +    //
> +    // Note that relookupOrAdd(p,l,t) performs Lookup using l and adds the
> +    // entry t, where the caller ensures match(l,t).

|| around the relevant parts, particularly |l| and |t|.

@@ +332,5 @@
> +    // entry t, where the caller ensures match(l,t).
> +    typedef typename Impl::AddPtr AddPtr;
> +    AddPtr lookupForAdd(const Lookup &l) const        { return impl.lookupForAdd(l); }
> +
> +    bool add(AddPtr &p, const T &t)                   { return impl.add(p, t); }

I'm guessing we don't templatize on ValueInput for Set because it just has less demanding users?

@@ +780,3 @@
>  
> +    void setTableSizeLog2(unsigned sizeLog2)
> +    {

Hmm.  Since you moved a bunch of { to the newline below here, could we also do all the ones above here as well?

@@ +845,5 @@
>  
>      static Entry *createTable(AllocPolicy &alloc, uint32_t capacity)
>      {
> +        // See JS_STATIC_ASSERT(sFreeKey == 0) in HashTableEntry.
> +        return (Entry *)alloc.calloc_(capacity * sizeof(Entry));

Not for this patch, but I doubt it would take too much work to convert AllocPolicy to use pod_.alloc.

@@ +1287,5 @@
>              METER(stats.addOverRemoved++);
>              removedCount--;
>              p.keyHash |= sCollisionBit;
>          } else {
> +            // Preserve the validity of p.entry.

Why remove the |...|?

::: js/public/Vector.h
@@ +513,5 @@
>  Vector<T, N, AllocPolicy>::Vector(MoveRef<Vector> rhs)
>      : AllocPolicy(rhs)
> +#ifdef DEBUG
> +    , entered(false)
> +#endif

Good catch.
Attachment #680105 - Flags: review?(terrence) → review+
https://hg.mozilla.org/mozilla-central/rev/7c4212c1e583
Status: ASSIGNED → RESOLVED
Closed: 9 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla19
Depends on: 928914
You need to log in before you can comment on or make changes to this bug.