Closed Bug 672728 Opened 13 years ago Closed 13 years ago

js::HashMap should support "move" semantics for its elements

Categories

(Core :: JavaScript Engine, defect)

x86_64
Linux
defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla8

People

(Reporter: jimb, Assigned: jimb)

References

Details

(Whiteboard: [inbound])

Attachments

(3 files, 1 obsolete file)

Some types can be moved more efficiently than they can be copied, but at present, js::HashMap's underlying implementation, js::HashTable, can only copy its element types. SpiderMonkey should have some way for types to indicate that they can be moved efficiently, and some way for containers to use those more efficient operations.
Attachment #546992 - Flags: feedback?(luke)
Comment on attachment 546992 [details] [diff] [review]
Define Rval, an rvalue reference type; provide a move constructor for js::Vector; and annotate moves in js::HashTable.

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

Great job, looking mostly right.

Two general comments:
1. Rval<T> is a word-sized value, so, even though inlining should boil all these types away, it would be preferable to write pass Rval<T> by value everywhere instead of by const Rval<T> &.
2. (Blaming myself) I just realized that "Rval" might not be best name for this thing.  True, C++1x has a feature called "rvalue references", so s/T&&/Rval<T>/ follows, but that only helps C++ wonks.  The best I can think of atm is MoveRef<T>, but feel free to propose your own or start an irc discussion.

::: js/src/jshashtable.h
@@ +554,4 @@
>          for (Entry *src = oldTable, *end = src + oldCap; src != end; ++src) {
>              if (src->isLive()) {
>                  src->unsetCollision();
> +                new(&findFreeEntry(src->getKeyHash())) Entry(Move(*src));

I know I wrote placement-new in irc, but, looking at the code, it seems that the Entry& returned by findFreeEntry is an already-live object (even if only default-constructed).  For lifetime-purity (i.e., giving every object exactly one ctor/dtor call), could you also define move-assignment on Vector (Vector::operator=(Rval<Vector>)) and use that here?

::: js/src/jsutil.h
@@ +687,5 @@
>   */
>  enum MaybeReportError { REPORT_ERROR = true, DONT_REPORT_ERROR = false };
>  
> +/*
> + * Rvalue references

Fantastic comment!

@@ +765,5 @@
> + *     new(&x) T(Move(y));
> + *
> + *   The 'placement new' expression has the same effect as an assignment, but
> + *   rephrases it as the application of a constructor to an Rval<T>. (Indeed,
> + *   'x = y' and 'new(&x) T(y)' generate the same machine code in GNU C++.)

For the reasons mentioned earlier, can you rewrite this paragraph to instead describe move-assignment?

@@ +768,5 @@
> + *   rephrases it as the application of a constructor to an Rval<T>. (Indeed,
> + *   'x = y' and 'new(&x) T(y)' generate the same machine code in GNU C++.)
> + *
> + * - If you're writing a move constructor where the type has members that should
> + *   be moved themselves, it's much nicer to write this:

I imagine you wrote this before you wrote the code b/c you do the right thing in the code which is:

  C(Rval<C> c) : x(Move(c->x)), y(Move(c->y)) {}

Can you update the comment?

::: js/src/jsvector.h
@@ +469,5 @@
> +template <class T, size_t N, class AllocPolicy>
> +JS_ALWAYS_INLINE
> +Vector<T, N, AllocPolicy>::Vector(const Rval<Vector> &srcRval)
> +{
> +    clearAndFree();

A constructor necessarily happens on a new object (as long as we obey lifetime-purity as mentioned above) so this clearAndFree() isn't necessary.

@@ +480,5 @@
> +#endif
> +
> +    if (src.usingInlineStorage()) {
> +        /* We can't move the buffer over in this case, so copy elements. */
> +        Impl::copyConstruct(mBegin, src.beginNoCheck(), src.endNoCheck());

For bonus points: Impl::moveConstruct :)  Perhaps leave a TODO...

@@ +491,5 @@
> +    }
> +
> +    src.mLength = 0;
> +#ifdef DEBUG
> +    /* In general, applying Move to a vector undoes prior reservations. */

Perhaps you can generalize this comment (placed before the first mutation of 'src'): "By the Rval contract, 'src' need only be left valid for calling ~Vector()."
Attachment #546992 - Flags: feedback?(luke) → feedback+
(In reply to comment #1)
> Two general comments:
> 1. Rval<T> is a word-sized value, so, even though inlining should boil all
> these types away, it would be preferable to write pass Rval<T> by value
> everywhere instead of by const Rval<T> &.

Right. I think I've fixed these.

> 2. (Blaming myself) I just realized that "Rval" might not be best name for
> this thing.  True, C++1x has a feature called "rvalue references", so
> s/T&&/Rval<T>/ follows, but that only helps C++ wonks.  The best I can think
> of atm is MoveRef<T>, but feel free to propose your own or start an irc
> discussion.

MoveRef seems fine to me. Done.
 
> ::: js/src/jshashtable.h
> @@ +554,4 @@
> >          for (Entry *src = oldTable, *end = src + oldCap; src != end; ++src) {
> >              if (src->isLive()) {
> >                  src->unsetCollision();
> > +                new(&findFreeEntry(src->getKeyHash())) Entry(Move(*src));
> 
> I know I wrote placement-new in irc, but, looking at the code, it seems that
> the Entry& returned by findFreeEntry is an already-live object (even if only
> default-constructed).  For lifetime-purity (i.e., giving every object
> exactly one ctor/dtor call), could you also define move-assignment on Vector
> (Vector::operator=(Rval<Vector>)) and use that here?

You're being generous phrasing it as some sort of purity issue --- constructing new objects atop existing objects is a flat-out bug. Fixed. "Move assignment" seems really icky, but I think it made some other stuff cleaner, so we'll go with it.

> Fantastic comment!

"Our motto is 'Caveat Emptor', which means 'We hope you like it!'" :)

> For the reasons mentioned earlier, can you rewrite this paragraph to instead
> describe move-assignment?

Done.

> I imagine you wrote this before you wrote the code b/c you do the right
> thing in the code which is:
> 
>   C(Rval<C> c) : x(Move(c->x)), y(Move(c->y)) {}
> 
> Can you update the comment?

Done.

> ::: js/src/jsvector.h
> @@ +469,5 @@
> > +template <class T, size_t N, class AllocPolicy>
> > +JS_ALWAYS_INLINE
> > +Vector<T, N, AllocPolicy>::Vector(const Rval<Vector> &srcRval)
> > +{
> > +    clearAndFree();
> 
> A constructor necessarily happens on a new object (as long as we obey
> lifetime-purity as mentioned above) so this clearAndFree() isn't necessary.

Duh. Fixed.

> @@ +480,5 @@
> > +#endif
> > +
> > +    if (src.usingInlineStorage()) {
> > +        /* We can't move the buffer over in this case, so copy elements. */
> > +        Impl::copyConstruct(mBegin, src.beginNoCheck(), src.endNoCheck());
> 
> For bonus points: Impl::moveConstruct :)  Perhaps leave a TODO...

So that vector elements can provide move constructors and assignment? Done.

It seemed like there were *lots* of opportunities to expand the support for Move semantics --- the append member functions, for example --- but I didn't want to work through them all right yet. We can add them as we go.

> @@ +491,5 @@
> > +    }
> > +
> > +    src.mLength = 0;
> > +#ifdef DEBUG
> > +    /* In general, applying Move to a vector undoes prior reservations. */
> 
> Perhaps you can generalize this comment (placed before the first mutation of
> 'src'): "By the Rval contract, 'src' need only be left valid for calling
> ~Vector()."

Right --- done.
Revised, per Luke's comments.
Assignee: general → jimb
Attachment #546992 - Attachment is obsolete: true
Attachment #547287 - Flags: review?(luke)
Comment on attachment 547287 [details] [diff] [review]
Define MoveRef, an rvalue reference type; provide a move constructor for js::Vector; and annotate moves in js::HashTable.

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

Great, thanks!

::: js/src/jsutil.h
@@ +784,5 @@
> + *
> + *   C(MoveRef<C> c) { new(&x) X(c->x); new(&y) Y(c->y); }
> + *
> + * especially since GNU C++ fails to notice that this does indeed initialize x
> + * and y, which may matter if they're const.

I would just leave out everything after "than the equivalent..."
Attachment #547287 - Flags: review?(luke) → review+
I think I've identified a problem in the vector move constructor, here:

https://bugzilla.mozilla.org/attachment.cgi?id=547287&action=diff#a/js/src/jsvector.h_sec5

At the end of the constructor, it says:

+    /* By the contract of a move constructor, src need only be valid for destruction. */
+    rhs->mLength = 0;
+#ifdef DEBUG
+    rhs->mReserved = 0;
+#endif

If I'm correct, a move constructor may leave its RHS in any state, as long as it's destructible. But there are destructible states which *must* be destructed. In the in-line storage case, if there were n elements in the RHS's in-line storage, before they were moved to the LHS, then those n elements still require destruction. But setting the length to zero causes the destructor to ignore them.
Here's a revision of the patch that addresses those issues and expands the operations that support move semantics a bit, as needed for bug 672736.

It's changed enough, and I've fixed a bug, that I thought I should get a re-review.
Attachment #549279 - Flags: review?(luke)
Comment on attachment 549279 [details] [diff] [review]
Define MoveRef, an rvalue reference type; provide some support for move construction and assignment in js::Vector and js::HashTable.

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

Good observation!

::: js/src/jsvector.h
@@ +761,5 @@
>  }
>  
>  template <class T, size_t N, class AP>
> +JS_ALWAYS_INLINE bool
> +Vector<T,N,AP>::append(MoveRef<T> t)

IIRC, these new move-append/internalAppend members are identical to the current copying versions except for the type of the arg.  Can we just not add the new ones and templatize the existing ones to take some type U?  Then the MoveRef will flow through and things should work.

It does push type errors deeper into the implementation, but I think it should be manageable.
Attachment #549279 - Flags: review?(luke) → review+
>+    MoveRef(T &t) : pointer(&t) { }

Needs `explicit`.
(In reply to comment #8)
> >+    MoveRef(T &t) : pointer(&t) { }
> 
> Needs `explicit`.

Fixed, thanks.
Whiteboard: [inbound]
http://hg.mozilla.org/mozilla-central/rev/bcf8b4086274
Status: NEW → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla8
Depends on: 686280
Depends on: 687039
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: