Last Comment Bug 672728 - js::HashMap should support "move" semantics for its elements
: js::HashMap should support "move" semantics for its elements
Status: RESOLVED FIXED
[inbound]
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: x86_64 Linux
: -- normal (vote)
: mozilla8
Assigned To: Jim Blandy :jimb
:
Mentors:
Depends on: 686280 687039
Blocks: findReferences
  Show dependency treegraph
 
Reported: 2011-07-19 22:38 PDT by Jim Blandy :jimb
Modified: 2011-09-16 01:51 PDT (History)
4 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Define Rval, an rvalue reference type; provide a move constructor for js::Vector; and annotate moves in js::HashTable. (8.28 KB, patch)
2011-07-19 22:38 PDT, Jim Blandy :jimb
luke: feedback+
Details | Diff | Review
Define MoveRef, an rvalue reference type; provide a move constructor for js::Vector; and annotate moves in js::HashTable. (9.84 KB, patch)
2011-07-20 16:24 PDT, Jim Blandy :jimb
luke: review+
Details | Diff | Review
Define MoveRef, an rvalue reference type; provide some support for move construction and assignment in js::Vector and js::HashTable. (13.39 KB, patch)
2011-07-28 17:07 PDT, Jim Blandy :jimb
luke: review+
Details | Diff | Review
[Revised per coment 7.] Define MoveRef, an rvalue reference type; provide some support for move construction and assignment in js::Vector and js::HashTable. (13.20 KB, patch)
2011-08-01 13:57 PDT, Jim Blandy :jimb
no flags Details | Diff | Review

Description Jim Blandy :jimb 2011-07-19 22:38:52 PDT
Created attachment 546992 [details] [diff] [review]
Define Rval, an rvalue reference type; provide a move constructor for js::Vector; and annotate moves in js::HashTable.

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.
Comment 1 Luke Wagner [:luke] 2011-07-20 10:34:04 PDT
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()."
Comment 2 Jim Blandy :jimb 2011-07-20 16:23:35 PDT
(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.
Comment 3 Jim Blandy :jimb 2011-07-20 16:24:20 PDT
Created attachment 547287 [details] [diff] [review]
Define MoveRef, an rvalue reference type; provide a move constructor for js::Vector; and annotate moves in js::HashTable.

Revised, per Luke's comments.
Comment 4 Luke Wagner [:luke] 2011-07-20 16:55:46 PDT
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..."
Comment 5 Jim Blandy :jimb 2011-07-28 16:01:01 PDT
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.
Comment 6 Jim Blandy :jimb 2011-07-28 17:07:31 PDT
Created 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.

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.
Comment 7 Luke Wagner [:luke] 2011-07-28 17:47:54 PDT
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.
Comment 8 Jason Orendorff [:jorendorff] 2011-07-29 14:47:19 PDT
>+    MoveRef(T &t) : pointer(&t) { }

Needs `explicit`.
Comment 9 Jim Blandy :jimb 2011-08-01 12:37:06 PDT
(In reply to comment #8)
> >+    MoveRef(T &t) : pointer(&t) { }
> 
> Needs `explicit`.

Fixed, thanks.
Comment 10 Jim Blandy :jimb 2011-08-01 13:57:39 PDT
Created attachment 549909 [details] [diff] [review]
[Revised per coment 7.] Define MoveRef, an rvalue reference type; provide some support for move construction and assignment in js::Vector and js::HashTable.
Comment 12 Marco Bonardo [::mak] 2011-08-02 03:38:20 PDT
http://hg.mozilla.org/mozilla-central/rev/bcf8b4086274

Note You need to log in before you can comment on or make changes to this bug.