Bug 130772 - [WTF] Add the move constructor, move assignment operator for HashTable
Summary: [WTF] Add the move constructor, move assignment operator for HashTable
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: New Bugs (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Zan Dobersek
URL:
Keywords:
Depends on: 134831 134869
Blocks:
  Show dependency treegraph
 
Reported: 2014-03-26 05:25 PDT by Zan Dobersek
Modified: 2014-07-19 03:11 PDT (History)
3 users (show)

See Also:


Attachments
Patch (3.30 KB, patch)
2014-03-26 08:51 PDT, Zan Dobersek
no flags Details | Formatted Diff | Diff
Patch (3.19 KB, patch)
2014-03-26 10:21 PDT, Zan Dobersek
no flags Details | Formatted Diff | Diff
Patch (3.22 KB, patch)
2014-03-26 10:36 PDT, Zan Dobersek
no flags Details | Formatted Diff | Diff
Patch (3.55 KB, patch)
2014-07-08 11:31 PDT, Zan Dobersek
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Zan Dobersek 2014-03-26 05:25:24 PDT
[WTF] Add the move constructor, move assignment operator for HashTable
Comment 1 Zan Dobersek 2014-03-26 08:51:50 PDT
Created attachment 227851 [details]
Patch
Comment 2 Darin Adler 2014-03-26 09:31:07 PDT
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.
Comment 3 Zan Dobersek 2014-03-26 10:13:51 PDT
Ah, makes sense. Thanks for the review, I'll upload a new iteration shortly.
Comment 4 Zan Dobersek 2014-03-26 10:21:41 PDT
Created attachment 227858 [details]
Patch
Comment 5 Zan Dobersek 2014-03-26 10:36:02 PDT
Created attachment 227862 [details]
Patch
Comment 6 Anders Carlsson 2014-03-26 17:45:26 PDT
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.
Comment 7 Zan Dobersek 2014-03-27 10:25:31 PDT
(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.
Comment 8 Darin Adler 2014-06-30 08:21:12 PDT
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.
Comment 9 Zan Dobersek 2014-07-08 11:21:53 PDT
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.
Comment 10 Zan Dobersek 2014-07-08 11:31:29 PDT
Created attachment 234576 [details]
Patch
Comment 11 Darin Adler 2014-07-08 17:38:14 PDT
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.
Comment 12 Zan Dobersek 2014-07-09 12:06:38 PDT
(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.
Comment 13 Zan Dobersek 2014-07-11 01:17:08 PDT
Committed r170995: <http://trac.webkit.org/changeset/170995>
Comment 14 WebKit Commit Bot 2014-07-11 05:23:50 PDT
Re-opened since this is blocked by bug 134831
Comment 15 Zan Dobersek 2014-07-19 03:11:24 PDT
Comment on attachment 234576 [details]
Patch

Clearing flags on attachment: 234576

Committed r171262: <http://trac.webkit.org/changeset/171262>
Comment 16 Zan Dobersek 2014-07-19 03:11:34 PDT
All reviewed patches have been landed.  Closing bug.