Bug 125827 – Implement an ordered multimap in WTF

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

[Myles C. Maxfield]

Implement an ordered multimap in WTF

[Myles C. Maxfield]

Created attachment 219387 [details]
Patch

[Myles C. Maxfield]

Created attachment 219393 [details]
Patch

[Geoffrey Garen]

Comment on attachment 219393 [details]
Patch

Our typical strategy for keyed collections in WebKit is to use a hash table. The reason is that it is faster.

Did you test the performance of this data structure? Did you compare it to the performance of a simple hash table, in which the values are vectors or linked lists? I'm hoping you did, but your ChangeLog doesn't contain any performance information, so I think you didn't.

Our typical strategy for memory management is to use smart pointers. The reason is that raw pointers leak and crash. Did you consider unique_ptr with move semantics or some other smart pointer solution instead of manual new and delete?

[Myles C. Maxfield]

Clearly a hash table is faster than a binary tree for the operations it supports; however, I am working on a patch (https://bugs.webkit.org/show_bug.cgi?id=125477) that needs to iterate over the items in a map in increasing key order, which a hashmap doesn't support. I would have used a RedBlackTree directly, but I need to store multiple key-value pairs with the same key in this data structure. That led me to use a RedBlackTree of DoublyLinkedLists. Another reason I cannot use a HashTable is that I need to keep multiple iterators into this data structure, even while other keys value pairs are being added and removed, which  HashTable doesn't support (it's add() function calls invalidateIterators()).

I originally was using std::multimap for my work, but was told to use WTF types instead, so I had to create this class.

I did not measure the performance, because I do not have anything to compare performance numbers against (because there is no other class in WTF with similar semantics).

I used new and delete because they are the best fit for the existing base classes for RedBlackTree<>::Node and DoublyLinkedListNode<>. RedBlackTree<>::Node declares it's own left and right pointers as raw pointers; I could declare my own overriding left and right OwnPtr<>s, but that would end up with essentially an entirely new Node type and no code reuse with the existing Node class. I think making this new Node type is fine, but I think it belongs in RedBlackTee.h, which probably should be in another patch. Should I do this, or keep it as it is?

For the DoublyLinkedListNode case, my subclass keeps the pointer members, however operations on the list itself (like append() and tail()) deal with raw pointers. Because DoublyLinkedList itself calls the  assignment operator on the previous and next pointers, without using adoptRef, I would end up having to re-implement an entirely new LinkedList implementation.

[Anders Carlsson]

I think a sorted vector would be fine here because the IOSurface management code is going to dwarf the cache management code here anyway.

[Geoffrey Garen]

(In reply to comment #4)
> Clearly a hash table is faster than a binary tree for the operations it supports; however, I am working on a patch (https://bugs.webkit.org/show_bug.cgi?id=125477) that needs to iterate over the items in a map in increasing key order, which a hashmap doesn't support.

I see. This sounds like a red flag.

If we're willing to pay the cost of iterating the data structure, we can probably use a much simpler data structure. If we're not willing to pay the cost of iterating the data structure, we need a different design.