Bug 672728: Define MoveRef, an rvalue reference type; provide some support for move construction and assignment in js::Vector and js::HashTable. r=luke
authorJim Blandy <jimb@mozilla.com>
Mon, 01 Aug 2011 17:52:53 -0700
changeset 73647 bcf8b4086274041c3c58357c8bd09c9555e5c2e7
parent 73646 f29ddae820bfdcf3df8fb4ce393e3c29d42c7dfc
child 73648 8f72d67f42a5df6d750e75ec6c2760e3090e8e25
push id20900
push usermak77@bonardo.net
push dateTue, 02 Aug 2011 09:54:14 +0000
treeherdermozilla-central@10927265c555 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersluke
bugs672728
milestone8.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 672728: Define MoveRef, an rvalue reference type; provide some support for move construction and assignment in js::Vector and js::HashTable. r=luke
js/src/jshashtable.h
js/src/jsutil.h
js/src/jsvector.h
--- a/js/src/jshashtable.h
+++ b/js/src/jshashtable.h
@@ -40,16 +40,17 @@
  *
  * ***** END LICENSE BLOCK ***** */
 
 #ifndef jshashtable_h_
 #define jshashtable_h_
 
 #include "jsalloc.h"
 #include "jstl.h"
+#include "jsutil.h"
 
 namespace js {
 
 /* Integral types for all hash functions. */
 typedef uint32 HashNumber;
 
 /*****************************************************************************/
 
@@ -72,17 +73,19 @@ class HashTableEntry {
 
     static bool isLiveHash(HashNumber hash)
     {
         return hash > sRemovedKey;
     }
 
   public:
     HashTableEntry() : keyHash(0), t() {}
+    HashTableEntry(MoveRef<HashTableEntry> rhs) : keyHash(rhs->keyHash), t(Move(rhs->t)) { }
     void operator=(const HashTableEntry &rhs) { keyHash = rhs.keyHash; t = rhs.t; }
+    void operator=(MoveRef<HashTableEntry> rhs) { keyHash = rhs->keyHash; t = Move(rhs->t); }
 
     NonConstT t;
 
     bool isFree() const           { return keyHash == sFreeKey; }
     void setFree()                { keyHash = sFreeKey; t = T(); }
     bool isRemoved() const        { return keyHash == sRemovedKey; }
     void setRemoved()             { keyHash = sRemovedKey; t = T(); }
     bool isLive() const           { return isLiveHash(keyHash); }
@@ -547,17 +550,17 @@ class HashTable : private AllocPolicy
         removedCount = 0;
         gen++;
         table = newTable;
 
         /* Copy only live entries, leaving removed ones behind. */
         for (Entry *src = oldTable, *end = src + oldCap; src != end; ++src) {
             if (src->isLive()) {
                 src->unsetCollision();
-                findFreeEntry(src->getKeyHash()) = *src;
+                findFreeEntry(src->getKeyHash()) = Move(*src);
             }
         }
 
         destroyTable(*this, oldTable, oldCap);
         return true;
     }
 
     void remove(Entry &e)
@@ -876,16 +879,22 @@ class HashMapEntry
     void operator=(const HashMapEntry &rhs) {
         const_cast<Key &>(key) = rhs.key;
         value = rhs.value;
     }
 
   public:
     HashMapEntry() : key(), value() {}
     HashMapEntry(const Key &k, const Value &v) : key(k), value(v) {}
+    HashMapEntry(MoveRef<HashMapEntry> rhs) 
+      : key(Move(rhs->key)), value(Move(rhs->value)) { }
+    void operator=(MoveRef<HashMapEntry> rhs) {
+        const_cast<Key &>(key) = Move(rhs->key);
+        value = Move(rhs->value);
+    }
 
     const Key key;
     Value value;
 };
 
 namespace tl {
 
 template <class T>
@@ -1014,16 +1023,25 @@ class HashMap
         Entry *pentry;
         if (!impl.add(p, &pentry))
             return false;
         const_cast<Key &>(pentry->key) = k;
         pentry->value = v;
         return true;
     }
 
+    bool add(AddPtr &p, const Key &k, MoveRef<Value> v) {
+        Entry *pentry;
+        if (!impl.add(p, &pentry))
+            return false;
+        const_cast<Key &>(pentry->key) = k;
+        pentry->value = v;
+        return true;
+    }
+
     bool add(AddPtr &p, const Key &k) {
         Entry *pentry;
         if (!impl.add(p, &pentry))
             return false;
         const_cast<Key &>(pentry->key) = k;
         return true;
     }
 
--- a/js/src/jsutil.h
+++ b/js/src/jsutil.h
@@ -688,13 +688,128 @@ PodEqual(T *one, T *two, size_t len)
  * Ordinarily, a function taking a JSContext* 'cx' paremter reports errors on
  * the context. In some cases, functions optionally report and indicate this by
  * taking a nullable 'maybecx' parameter. In some cases, though, a function
  * always needs a 'cx', but optionally reports. This option is presented by the
  * MaybeReportError.
  */
 enum MaybeReportError { REPORT_ERROR = true, DONT_REPORT_ERROR = false };
 
+/*
+ * "Move" References
+ *
+ * Some types can be copied much more efficiently if we know the original's
+ * value need not be preserved --- that is, if we are doing a "move", not a
+ * "copy". For example, if we have:
+ *
+ *   Vector<T> u;
+ *   Vector<T> v(u);
+ * 
+ * the constructor for v must apply a copy constructor to each element of u ---
+ * taking time linear in the length of u. However, if we know we will not need u
+ * any more once v has been initialized, then we could initialize v very
+ * efficiently simply by stealing u's dynamically allocated buffer and giving it
+ * to v --- a constant-time operation, regardless of the size of u.
+ *
+ * Moves often appear in container implementations. For example, when we append
+ * to a vector, we may need to resize its buffer. This entails moving each of
+ * its extant elements from the old, smaller buffer to the new, larger buffer.
+ * But once the elements have been migrated, we're just going to throw away the
+ * old buffer; we don't care if they still have their values. So if the vector's
+ * element type can implement "move" more efficiently than "copy", the vector
+ * resizing should by all means use a "move" operation. Hash tables also need to
+ * be resized.
+ *
+ * The details of the optimization, and whether it's worth applying, vary from
+ * one type to the next. And while some constructor calls are moves, many really
+ * are copies, and can't be optimized this way. So we need:
+ *
+ * 1) a way for a particular invocation of a copy constructor to say that it's
+ *    really a move, and that the value of the original isn't important
+ *    afterwards (althought it must still be safe to destroy); and
+ *
+ * 2) a way for a type (like Vector) to announce that it can be moved more
+ *    efficiently than it can be copied, and provide an implementation of that
+ *    move operation.
+ *
+ * The Move(T &) function takes a reference to a T, and returns an MoveRef<T>
+ * referring to the same value; that's 1). An MoveRef<T> is simply a reference
+ * to a T, annotated to say that a copy constructor applied to it may move that
+ * T, instead of copying it. Finally, a constructor that accepts an MoveRef<T>
+ * should perform a more efficient move, instead of a copy, providing 2).
+ *
+ * So, where we might define a copy constructor for a class C like this:
+ *
+ *   C(const C &rhs) { ... copy rhs to this ... }
+ *
+ * we would declare a move constructor like this:
+ *
+ *   C(MoveRef<C> rhs) { ... move rhs to this ... }
+ *
+ * And where we might perform a copy like this:
+ *
+ *   C c2(c1);
+ *
+ * we would perform a move like this:
+ *
+ *   C c2(Move(c1))
+ * 
+ * Note that MoveRef<T> implicitly converts to T &, so you can pass an
+ * MoveRef<T> to an ordinary copy constructor for a type that doesn't support a
+ * special move constructor, and you'll just get a copy. This means that
+ * templates can use Move whenever they know they won't use the original value
+ * any more, even if they're not sure whether the type at hand has a specialized
+ * move constructor. If it doesn't, the MoveRef<T> will just convert to a T &,
+ * and the ordinary copy constructor will apply.
+ *
+ * A class with a move constructor can also provide a move assignment operator,
+ * which runs this's destructor, and then applies the move constructor to
+ * *this's memory. A typical definition:
+ *
+ *   C &operator=(MoveRef<C> rhs) {
+ *     this->~C();
+ *     new(this) C(rhs);
+ *     return *this;
+ *   }
+ *
+ * With that in place, one can write move assignments like this:
+ *
+ *   c2 = Move(c1);
+ *
+ * This destroys c1, moves c1's value to c2, and leaves c1 in an undefined but
+ * destructible state.
+ *
+ * This header file defines MoveRef and Move in the js namespace. It's up to
+ * individual containers to annotate moves as such, by calling Move; and it's up
+ * to individual types to define move constructors.
+ *
+ * One hint: if you're writing a move constructor where the type has members
+ * that should be moved themselves, it's much nicer to write this:
+ *
+ *   C(MoveRef<C> c) : x(c->x), y(c->y) { }
+ *
+ * than the equivalent:
+ *
+ *   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.
+ */
+template<typename T>
+class MoveRef {
+  public:
+    typedef T Referent;
+    explicit MoveRef(T &t) : pointer(&t) { }
+    T &operator*()  const { return *pointer; }
+    T *operator->() const { return  pointer; }
+    operator T &()  const { return *pointer; }
+  private:
+    T *pointer;
+};
+
+template<typename T>
+MoveRef<T> Move(T &t) { return MoveRef<T>(t); }
+
 } /* namespace js */
 
 #endif /* defined(__cplusplus) */
 
 #endif /* jsutil_h___ */
--- a/js/src/jsvector.h
+++ b/js/src/jsvector.h
@@ -39,16 +39,17 @@
  * ***** END LICENSE BLOCK ***** */
 
 #ifndef jsvector_h_
 #define jsvector_h_
 
 #include "jsalloc.h"
 #include "jstl.h"
 #include "jsprvtd.h"
+#include "jsutil.h"
 
 /* Silence dire "bugs in previous versions of MSVC have been fixed" warnings */
 #ifdef _MSC_VER
 #pragma warning(push)
 #pragma warning(disable:4345)
 #endif
 
 namespace js {
@@ -78,16 +79,26 @@ struct VectorImpl
      */
     template <class U>
     static inline void copyConstruct(T *dst, const U *srcbeg, const U *srcend) {
         for (const U *p = srcbeg; p != srcend; ++p, ++dst)
             new(dst) T(*p);
     }
 
     /*
+     * Move-constructs objects in the uninitialized range
+     * [dst, dst+(srcend-srcbeg)) from the range [srcbeg, srcend).
+     */
+    template <class U>
+    static inline void moveConstruct(T *dst, const U *srcbeg, const U *srcend) {
+        for (const U *p = srcbeg; p != srcend; ++p, ++dst)
+            new(dst) T(Move(*p));
+    }
+
+    /*
      * Copy-constructs objects in the uninitialized range [dst, dst+n) from the
      * same object u.
      */
     template <class U>
     static inline void copyConstructN(T *dst, size_t n, const U &u) {
         for (T *end = dst + n; dst != end; ++dst)
             new(dst) T(u);
     }
@@ -99,17 +110,17 @@ struct VectorImpl
      * not overflow.
      */
     static inline bool growTo(Vector<T,N,AP> &v, size_t newcap) {
         JS_ASSERT(!v.usingInlineStorage());
         T *newbuf = reinterpret_cast<T *>(v.malloc_(newcap * sizeof(T)));
         if (!newbuf)
             return false;
         for (T *dst = newbuf, *src = v.beginNoCheck(); src != v.endNoCheck(); ++dst, ++src)
-            new(dst) T(*src);
+            new(dst) T(Move(*src));
         VectorImpl::destroy(v.beginNoCheck(), v.endNoCheck());
         v.free_(v.mBegin);
         v.mBegin = newbuf;
         /* v.mLength is unchanged. */
         v.mCapacity = newcap;
         return true;
     }
 };
@@ -145,16 +156,21 @@ struct VectorImpl<T, N, AP, true>
          * requiring T == U.
          *
          * memcpy(dst, srcbeg, sizeof(T) * (srcend - srcbeg));
          */
         for (const U *p = srcbeg; p != srcend; ++p, ++dst)
             *dst = *p;
     }
 
+    template <class U>
+    static inline void moveConstruct(T *dst, const U *srcbeg, const U *srcend) {
+        copyConstruct(dst, srcbeg, srcend);
+    }
+
     static inline void copyConstructN(T *dst, size_t n, const T &t) {
         for (T *p = dst, *end = dst + n; p != end; ++p)
             *p = t;
     }
 
     static inline bool growTo(Vector<T,N,AP> &v, size_t newcap) {
         JS_ASSERT(!v.usingInlineStorage());
         size_t bytes = sizeof(T) * newcap;
@@ -282,27 +298,29 @@ class Vector : private AllocPolicy
     size_t reserved() const {
         JS_ASSERT(mReserved <= mCapacity);
         JS_ASSERT(mLength <= mReserved);
         return mReserved;
     }
 #endif
 
     /* Append operations guaranteed to succeed due to pre-reserved space. */
-    void internalAppend(const T &t);
+    template <class U> void internalAppend(U t);
     void internalAppendN(const T &t, size_t n);
     template <class U> void internalAppend(const U *begin, size_t length);
     template <class U, size_t O, class BP> void internalAppend(const Vector<U,O,BP> &other);
 
   public:
     static const size_t sMaxInlineStorage = N;
 
     typedef T ElementType;
 
     Vector(AllocPolicy = AllocPolicy());
+    Vector(MoveRef<Vector>); /* Move constructor. */
+    Vector &operator=(MoveRef<Vector>); /* Move assignment. */
     ~Vector();
 
     /* accessors */
 
     const AllocPolicy &allocPolicy() const {
         return *this;
     }
 
@@ -381,18 +399,25 @@ class Vector : private AllocPolicy
     bool resizeUninitialized(size_t newLength);
 
     /* Shorthand for shrinkBy(length()). */
     void clear();
 
     /* Clears and releases any heap-allocated storage. */
     void clearAndFree();
 
-    /* Potentially fallible append operations. */
-    bool append(const T &t);
+    /*
+     * Potentially fallible append operations.
+     *
+     * The function templates that take an unspecified type U require a
+     * const T & or a MoveRef<T>. The MoveRef<T> variants move their
+     * operands into the vector, instead of copying them. If they fail, the
+     * operand is left unmoved.
+     */
+    template <class U> bool append(U t);
     bool appendN(const T &t, size_t n);
     template <class U> bool append(const U *begin, const U *end);
     template <class U> bool append(const U *begin, size_t length);
     template <class U, size_t O, class BP> bool append(const Vector<U,O,BP> &other);
 
     /*
      * Guaranteed-infallible append operations for use upon vectors whose
      * memory has been pre-reserved.
@@ -462,16 +487,61 @@ JS_ALWAYS_INLINE
 Vector<T,N,AllocPolicy>::Vector(AllocPolicy ap)
   : AllocPolicy(ap), mBegin((T *)storage.addr()), mLength(0),
     mCapacity(sInlineCapacity)
 #ifdef DEBUG
   , mReserved(0), entered(false)
 #endif
 {}
 
+/* Move constructor. */
+template <class T, size_t N, class AllocPolicy>
+JS_ALWAYS_INLINE
+Vector<T, N, AllocPolicy>::Vector(MoveRef<Vector> rhs)
+    : AllocPolicy(rhs)
+{
+    mLength = rhs->mLength;
+    mCapacity = rhs->mCapacity;
+#ifdef DEBUG
+    mReserved = rhs->mReserved;
+#endif
+
+    if (rhs->usingInlineStorage()) {
+        /* We can't move the buffer over in this case, so copy elements. */
+        Impl::moveConstruct(mBegin, rhs->beginNoCheck(), rhs->endNoCheck());
+        /*
+         * Leave rhs's mLength, mBegin, mCapacity, and mReserved as they are.
+         * The elements in its in-line storage still need to be destroyed.
+         */
+    } else {
+        /*
+         * Take src's buffer, and turn src into an empty vector using
+         * in-line storage.
+         */
+        mBegin = rhs->mBegin;
+        rhs->mBegin = (T *) rhs->storage.addr();
+        rhs->mCapacity = sInlineCapacity;
+        rhs->mLength = 0;
+#ifdef DEBUG
+        rhs->mReserved = 0;
+#endif
+    }
+}
+
+/* Move assignment. */
+template <class T, size_t N, class AP>
+JS_ALWAYS_INLINE
+Vector<T, N, AP> &
+Vector<T, N, AP>::operator=(MoveRef<Vector> rhs)
+{
+    this->~Vector();
+    new(this) Vector(rhs);
+    return *this;
+}
+
 template <class T, size_t N, class AP>
 JS_ALWAYS_INLINE
 Vector<T,N,AP>::~Vector()
 {
     REENTRANCY_GUARD_ET_AL;
     Impl::destroy(beginNoCheck(), endNoCheck());
     if (!usingInlineStorage())
         this->free_(beginNoCheck());
@@ -542,17 +612,17 @@ Vector<T,N,AP>::convertToHeapStorage(siz
         return false;
 
     /* Allocate buffer. */
     T *newBuf = reinterpret_cast<T *>(this->malloc_(newCap * sizeof(T)));
     if (!newBuf)
         return false;
 
     /* Copy inline elements into heap buffer. */
-    Impl::copyConstruct(newBuf, beginNoCheck(), endNoCheck());
+    Impl::moveConstruct(newBuf, beginNoCheck(), endNoCheck());
     Impl::destroy(beginNoCheck(), endNoCheck());
 
     /* Switch in heap buffer. */
     mBegin = newBuf;
     /* mLength is unchanged. */
     mCapacity = newCap;
     return true;
 }
@@ -567,26 +637,26 @@ Vector<T,N,AP>::growStorageBy(size_t inc
          : growHeapStorageBy(incr);
 }
 
 template <class T, size_t N, class AP>
 inline bool
 Vector<T,N,AP>::reserve(size_t request)
 {
     REENTRANCY_GUARD_ET_AL;
-    if (request <= mCapacity || growStorageBy(request - mLength)) {
+    if (request > mCapacity && !growStorageBy(request - mLength))
+        return false;
+
 #ifdef DEBUG
-        if (request > mReserved)
-            mReserved = request;
-        JS_ASSERT(mLength <= mReserved);
-        JS_ASSERT(mReserved <= mCapacity);
+    if (request > mReserved)
+        mReserved = request;
+    JS_ASSERT(mLength <= mReserved);
+    JS_ASSERT(mReserved <= mCapacity);
 #endif
-        return true;
-    }
-    return false;
+    return true;
 }
 
 template <class T, size_t N, class AP>
 inline void
 Vector<T,N,AP>::shrinkBy(size_t incr)
 {
     REENTRANCY_GUARD_ET_AL;
     JS_ASSERT(incr <= mLength);
@@ -674,34 +744,36 @@ Vector<T,N,AP>::clearAndFree()
     mBegin = (T *)storage.addr();
     mCapacity = sInlineCapacity;
 #ifdef DEBUG
     mReserved = 0;
 #endif
 }
 
 template <class T, size_t N, class AP>
+template <class U>
 JS_ALWAYS_INLINE bool
-Vector<T,N,AP>::append(const T &t)
+Vector<T,N,AP>::append(U t)
 {
     REENTRANCY_GUARD_ET_AL;
     if (mLength == mCapacity && !growStorageBy(1))
         return false;
 
 #ifdef DEBUG
     if (mLength + 1 > mReserved)
         mReserved = mLength + 1;
 #endif
     internalAppend(t);
     return true;
 }
 
 template <class T, size_t N, class AP>
+template <class U>
 JS_ALWAYS_INLINE void
-Vector<T,N,AP>::internalAppend(const T &t)
+Vector<T,N,AP>::internalAppend(U t)
 {
     JS_ASSERT(mLength + 1 <= mReserved);
     JS_ASSERT(mReserved <= mCapacity);
     new(endNoCheck()) T(t);
     ++mLength;
 }
 
 template <class T, size_t N, class AP>
@@ -876,17 +948,17 @@ Vector<T,N,AP>::replaceRawBuffer(T *p, s
         /*
          * We convert to inline storage if possible, even though p might
          * otherwise be acceptable.  Maybe this behaviour should be
          * specifiable with an argument to this function.
          */
         mBegin = (T *)storage.addr();
         mLength = length;
         mCapacity = sInlineCapacity;
-        Impl::copyConstruct(mBegin, p, p + length);
+        Impl::moveConstruct(mBegin, p, p + length);
         Impl::destroy(p, p + length);
         this->free_(p);
     } else {
         mBegin = p;
         mLength = length;
         mCapacity = length;
     }
 #ifdef DEBUG