Add removeOne(value) / removeAll(value) convenience methods to WTF::Vector to reduce complexity a bit at call sites. The naming is inspired by QVector: http://doc.qt.io/qt-5/qvector.html#removeOne http://doc.qt.io/qt-5/qvector.html#removeAll I am planning to add overloads for these taking a lambda function for matching in a follow-up patch as well. I have seen quite a few Vector::remove(index) call sites that would benefit from it.
Created attachment 245954 [details] Patch
Created attachment 245959 [details] Patch
Created attachment 245963 [details] Patch
I compared the performance of Vector::removeAll() compared to the old way of index-based traversal + Vector::remove(index). I used the following input: Vector<int> speedV = {3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3, 3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3, 3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3, 3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3, 3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3, 3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3, 3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3}; I did 10000000 iterations to removed all the 1's. The results look really good: Manual: 2478.31 ms RemoveAll: 2129.9 ms (~17% faster)
(In reply to comment #4) > I compared the performance of Vector::removeAll() compared to the old way of > index-based traversal + Vector::remove(index). > > I used the following input: > Vector<int> speedV = {3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3, 3, 1, 2, 1, 2, 1, > 2, 2, 1, 1, 1, 3, 3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3, 3, 1, 2, 1, 2, 1, 2, > 2, 1, 1, 1, 3, 3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3, 3, 1, 2, 1, 2, 1, 2, 2, > 1, 1, 1, 3, 3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3}; > > I did 10000000 iterations to removed all the 1's. > > The results look really good: > Manual: 2478.31 ms > RemoveAll: 2129.9 ms (~17% faster) I also tried a Vector of CString because we currently don't use memcpy/memmove for those: Vector<CString> speedV = {"3", "1", "2", "1", "2", "1", "2", "2", "1", "1", "1", "3", "3", "1", "2", "1", "2", "1", "2", "2", "1", "1", "1", "3", "3", "1", "2", "1", "2", "1", "2", "2", "1", "1", "1", "3", "3", "1", "2", "1", "2", "1", "2", "2", "1", "1", "1", "3", "3", "1", "2", "1", "2", "1", "2", "2", "1", "1", "1", "3", "3", "1", "2", "1", "2", "1", "2", "2", "1", "1", "1", "3"}; I did 1000000 iterations to removed all the 1's. The results were even better: Manual: 1716.21 ms RemoveAll: 581.744 ms Micro-benchmark: http://pastebin.com/C4q4a2gb
Comment on attachment 245963 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=245963&action=review That looks great to me. > Source/WTF/ChangeLog:10 > + QVector. hehehe, back to the roots of WTF :) > Source/WTF/ChangeLog:18 > + (WTF::OverflowHandler>::removeOne): > + (WTF::OverflowHandler>::removeAll): Not a big fan of the name. The name removeAll() seems to be a better name for Vector::clear(). The name removeOne() seems like a removeAny(). It should be some kind of removeFirstOf(). Maybe the name should hint that the operation is not O(1)? findAndRemove() findAndRemoveAll() You should ask Darin for ideas, he always have good feedback on naming. > Source/WTF/wtf/Vector.h:739 > + template<typename U> bool removeOne(const U&); > + template<typename U> unsigned removeAll(const U&); Two spaces between the template<> and the return type. > Source/WTF/wtf/Vector.h:1348 > + m_size -= matchCount; Orthogonal to your patch but: it may be worth considering shrinking the vector if "matchCount" >= m_size / 2. > Source/WebCore/html/HTMLFormElement.cpp:-615 > - unsigned index; > - for (index = 0; index < m_associatedElements.size(); ++index) { > - if (m_associatedElements[index] == e) > - break; > - } Weird > Source/WebCore/page/SecurityPolicy.cpp:158 > + if (!list.removeOne(OriginAccessEntry(destinationProtocol, destinationDomain, allowDestinationSubdomains ? OriginAccessEntry::AllowSubdomains : OriginAccessEntry::DisallowSubdomains))) Maybe split this? OriginAccessEntry someVeryGoodNameForSecurityStuff(destinationProtocol, destinationDomain, allowDestinationSubdomains ? OriginAccessEntry::AllowSubdomains : OriginAccessEntry::DisallowSubdomains); > Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:348 > + EXPECT_EQ(9U, v.size()); > + EXPECT_TRUE(v == Vector<int>({1, 1, 1, 1, 1, 1, 1, 1, 1})); I would test the loop doing removeOne() eleven times, brute forcing that all branches are used. > Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:377 > + v = {1, 2, 1, 2, 1, 2, 2, 1, 1, 1}; Large match at the end. > Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:386 > + v = {3, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3}; Large match in the middle. > Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:394 > + Where is large match at the front?
Comment on attachment 245963 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=245963&action=review >> Source/WTF/ChangeLog:18 >> + (WTF::OverflowHandler>::removeAll): > > Not a big fan of the name. > > The name removeAll() seems to be a better name for Vector::clear(). > The name removeOne() seems like a removeAny(). It should be some kind of removeFirstOf(). > > Maybe the name should hint that the operation is not O(1)? > findAndRemove() > findAndRemoveAll() > > You should ask Darin for ideas, he always have good feedback on naming. For what it's worth, glib seems to be using g_list_remove() / g_list_remove_all() for those: https://developer.gnome.org/glib/stable/glib-Doubly-Linked-Lists.html#g-list-remove-all In our case we cannot really call the first one remove(value) because it could be ambiguous with existing remove(index). findAndRemove*() is clearer in terms of complexity but I am not a fan because it is long (and I have never seen this naming anywhere :).
Comment on attachment 245963 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=245963&action=review >>> Source/WTF/ChangeLog:18 >>> + (WTF::OverflowHandler>::removeAll): >> >> Not a big fan of the name. >> >> The name removeAll() seems to be a better name for Vector::clear(). >> The name removeOne() seems like a removeAny(). It should be some kind of removeFirstOf(). >> >> Maybe the name should hint that the operation is not O(1)? >> findAndRemove() >> findAndRemoveAll() >> >> You should ask Darin for ideas, he always have good feedback on naming. > > For what it's worth, glib seems to be using g_list_remove() / g_list_remove_all() for those: > https://developer.gnome.org/glib/stable/glib-Doubly-Linked-Lists.html#g-list-remove-all > > In our case we cannot really call the first one remove(value) because it could be ambiguous with existing remove(index). > > findAndRemove*() is clearer in terms of complexity but I am not a fan because it is long (and I have never seen this naming anywhere :). I do think removeFirst(value) would be a bit more explicit than removeOne(value) though. It would be clearer that we delete the *first* occurrence, not just any. And it leaves room for a removeLast(value) if ever useful.
Created attachment 246012 [details] Patch
Did you mean to cq+?
Comment on attachment 246012 [details] Patch Clearing flags on attachment: 246012 Committed r179599: <http://trac.webkit.org/changeset/179599>
All reviewed patches have been landed. Closing bug.