Bug 130772 – [WTF] Add the move constructor, move assignment operator for HashTable

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Zan Dobersek]

[WTF] Add the move constructor, move assignment operator for HashTable

[Zan Dobersek]

Created attachment 227851 [details]
Patch

[Darin Adler]

Comment on attachment 227851 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=227851&action=review

> Source/WTF/wtf/HashTable.h:1190
> +        , m_iterators(std::move(other.m_iterators))

We need to invalidate other.m_iterators, not move them. The iterators point back to the table, and it’s not safe to just point the new table at them but leave them pointing to the old table.

Should initialize m_iterators to nullptr and call other.invalidateIterators() in the body of the constructor.

> Source/WTF/wtf/HashTable.h:1201
> +        std::swap(m_table, other.m_table);
> +        std::swap(m_tableSize, other.m_tableSize);
> +        std::swap(m_tableSizeMask, other.m_tableSizeMask);
> +        std::swap(m_keyCount, other.m_keyCount);
> +        std::swap(m_deletedCount, other.m_deletedCount);

I don’t think we need to write it like this. We should just copy the data members in the initialization section, and then zero them out here:

    other.m_table = nullptr;

Writing it with std::swap is unnecessarily oblique and doesn’t have any significant benefits that I can see.

> Source/WTF/wtf/HashTable.h:1221
> +    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
> +    inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(HashTable&& other) -> HashTable&
> +    {
> +        std::swap(m_table, other.m_table);
> +        std::swap(m_tableSize, other.m_tableSize);
> +        std::swap(m_tableSizeMask, other.m_tableSizeMask);
> +        std::swap(m_keyCount, other.m_keyCount);
> +        std::swap(m_deletedCount, other.m_deletedCount);
> +
> +#if CHECK_HASHTABLE_ITERATORS
> +        std::swap(m_iterators, other.m_iterators);
> +#endif
> +#if DUMP_HASHTABLE_STATS_PER_TABLE
> +        std::swap(m_stats, other.m_stats);
> +#endif
> +
> +        return *this;
> +    }

This is incorrect. It swaps, and doesn't move.

If we wanted to build move out of swap we’d need to clear out “this” first. But I see no reason to build move out of swap.

Also, it swaps incorrectly. If we wanted to swap correctly we could use the existing swap function above that does it correctly.

[Zan Dobersek]

Ah, makes sense. Thanks for the review, I'll upload a new iteration shortly.

[Zan Dobersek]

Created attachment 227858 [details]
Patch

[Zan Dobersek]

Created attachment 227862 [details]
Patch

[Anders Carlsson]

Comment on attachment 227862 [details]
Patch

I don't think this is needed since we have move ctors and move assignment operators for both HashSet and HashMap.

[Zan Dobersek]

(In reply to comment #6)
> (From update of attachment 227862 [details])
> I don't think this is needed since we have move ctors and move assignment operators for both HashSet and HashMap.

Only a few of those are generated, and they all end up using the HashTable copy ctor, which kind of defeats the purpose.

Making HashTable move-constructible and move-assignable fixes that. In addition, more of HashSet and HashMap move ctors and move assignment operators are generated in place of analogous copy operations.

[Darin Adler]

Comment on attachment 227862 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=227862&action=review

> Source/WTF/wtf/HashTable.h:1198
> +    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
> +    inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(HashTable&& other)
> +        : m_table(nullptr)
> +        , m_tableSize(0)
> +        , m_tableSizeMask(0)
> +        , m_keyCount(0)
> +        , m_deletedCount(0)
> +#if CHECK_HASHTABLE_ITERATORS
> +        , m_iterators(nullptr)
> +        , m_mutex(std::make_unique<std::mutex>())
> +#endif
> +#if DUMP_HASHTABLE_STATS_PER_TABLE
> +        , m_stats(nullptr)
> +#endif
> +    {
> +        *this = std::move(other);
> +    }

I don’t think it’s good to first make everything null and 0 and only then overwrite by moving. I suggest we instead just repeat the code from operator= below here.

> Source/WTF/wtf/HashTable.h:1210
> +        m_table = std::move(other.m_table);
> +        m_tableSize = std::move(other.m_tableSize);
> +        m_tableSizeMask = std::move(other.m_tableSizeMask);
> +        m_keyCount = std::move(other.m_keyCount);
> +        m_deletedCount = std::move(other.m_deletedCount);

These uses of std::move don’t accomplish anything. I wish that std::move worked with scalars in this fashion, but it doesn’t, and it’s not helpful to write code as if it did. Please omit the calls to std::move and just use normal assignment.

> Source/WTF/wtf/HashTable.h:1219
> +        m_stats = std::move(other.m_stats);

Ditto.

[Zan Dobersek]

Comment on attachment 227862 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=227862&action=review

I'll upload a new patch for re-review.

>> Source/WTF/wtf/HashTable.h:1198
>> +    }
> 
> I don’t think it’s good to first make everything null and 0 and only then overwrite by moving. I suggest we instead just repeat the code from operator= below here.

OK.

>> Source/WTF/wtf/HashTable.h:1210
>> +        m_deletedCount = std::move(other.m_deletedCount);
> 
> These uses of std::move don’t accomplish anything. I wish that std::move worked with scalars in this fashion, but it doesn’t, and it’s not helpful to write code as if it did. Please omit the calls to std::move and just use normal assignment.

OK.

> Source/WTF/wtf/HashTable.h:1216
> +        other.m_table = nullptr;
> +        other.m_tableSize = 0;
> +        other.m_tableSizeMask = 0;
> +        other.m_keyCount = 0;
> +        m_deletedCount = 0;

Oops!

>> Source/WTF/wtf/HashTable.h:1219
>> +        m_stats = std::move(other.m_stats);
> 
> Ditto.

m_stats is a std::unique_ptr<>, so the move is required.

[Zan Dobersek]

Created attachment 234576 [details]
Patch

[Darin Adler]

Comment on attachment 234576 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=234576&action=review

I must admit I still don’t understand where this code will be used. Can you give an example of a source line that will end up calling this? Anders pointer out that we already have HashMap and HashSet move constructors and assignment operators.

> Source/WTF/wtf/HashTable.h:1205
> +        other.m_stats = nullptr;

This line of code isn’t needed. Moving out of the unique_ptr will null it out.

> Source/WTF/wtf/HashTable.h:1229
> +        other.m_stats = nullptr;

This line of code isn’t needed. Moving out of the unique_ptr will null it out.

[Zan Dobersek]

(In reply to comment #11)
> (From update of attachment 234576 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=234576&action=review
> 
> I must admit I still don’t understand where this code will be used. Can you give an example of a source line that will end up calling this? Anders pointer out that we already have HashMap and HashSet move constructors and assignment operators.
> 

Move constructors and assignment operators for HashMap and HashSet are indeed implicitly defined, but those currently end up copying the HashTable instead of moving it, simply because HashTable is not movable.

This patch fixes that, so for every move of HashMap and HashSet the underlying HashTable is moved as well.

[Zan Dobersek]

Committed r170995: <http://trac.webkit.org/changeset/170995>

[WebKit Commit Bot]

Re-opened since this is blocked by bug 134831

[Zan Dobersek]

Comment on attachment 234576 [details]
Patch

Clearing flags on attachment: 234576

Committed r171262: <http://trac.webkit.org/changeset/171262>

[Zan Dobersek]

All reviewed patches have been landed.  Closing bug.