Bug 239876 – Speed-up querySelectorAll() with single by-class selector

• Component: DOM
• Status: NEW

[Alexey Shvayka]

Speed-up querySelectorAll() with single by-class selector

[Alexey Shvayka]

Created attachment 458552 [details]
Patch

[Alexey Shvayka]

Created attachment 458553 [details]
Microbenchmark

[Alexey Shvayka]

Created attachment 458555 [details]
Patch

Add RefCountedVector.h to CMakeLists.txt

[Chris Dumez]

Comment on attachment 458555 [details]
Patch

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

Antti should probably look at this but I made comments since there are a few non-WebKit idioms in here.

> Source/WTF/wtf/RefCountedVector.h:41
> +    static Ref<RefCountedVector> create(size_t size)

Maybe the parameter could be optional with = 0;, given how it is used.

> Source/WebCore/dom/ClassCollection.cpp:41
> +RefPtr<ClassCollection> ClassCollection::create(ContainerNode& rootNode, const AtomString& classNames)

This cannot return null so this change seems like a regression, we should return a Ref<>, not a RefPtr<>.

> Source/WebCore/dom/ClassCollection.h:73
> +inline void ClassCollection::invalidateCacheIfNeeded(const ClassChangeVector* classChanges)

This function assumes classChanges pointer is non null so we should pass a reference instead of a pointer.

> Source/WebCore/dom/CollectionIndexCache.h:47
> +    Ref<CachedListType> ensureValidCache(const Collection& collection)

Given that this isn't a one liner, we should move it out of the class (put it below in this file) and mark it as inline.

> Source/WebCore/dom/NodeRareData.h:128
> +    ALWAYS_INLINE RefPtr<ClassCollection> addCachedClassCollection(ContainerNode& node, const AtomString& classNames)

Why does this return a RefPtr<> and not a Ref<>. It does not look like it can return null?

> Source/WebCore/dom/NodeRareData.h:191
> +    void removeCachedClassCollection(RefPtr<ClassCollection> collection, const AtomString& classNames)

It seems this is unnecessarily doing ref counting churn for the collection, this should likely take a `ClassCollection&` in argument. The call site should just pass `*this`.

Note that RefPtr<> was not only inefficient but also confusing since this function cannot be called with null.

> Source/WebCore/dom/SelectorQuery.cpp:171
> +        const CSSSelector& selector = *m_selectors.first().selector;

auto&

> Source/WebCore/dom/SelectorQuery.cpp:174
> +        const AtomString& className = selector.value();

auto&

> Source/WebCore/dom/StaticNodeList.h:84
> +    unsigned length() const override;

could be marked as final

> Source/WebCore/dom/StaticNodeList.h:85
> +    Element* item(unsigned index) const override;

ditto.

> Source/WebCore/style/ClassChangeInvalidation.cpp:84
> +void ClassChangeInvalidation::computeInvalidation(const ClassChangeVector* classChanges)

Looks like classChanges is assumed to be non null so we should pass a reference, not a raw pointer:
const ClassChangeVector&

> Source/WebCore/style/ClassChangeInvalidation.cpp:90
> +        for (const auto& classChange : *classChanges) {

We don't normally use `const auto`, the previous code was correct and more WebKit-like.

It was already const and the previous code was more concise.

> Source/WebCore/style/ClassChangeInvalidation.cpp:114
> +    for (const auto& classChange : *classChanges) {

Ditto.

> Source/WebCore/style/ClassChangeInvalidation.h:60
> +    ASSERT(classChanges);

No, please pass classChanges by reference and drop this assertion.

[Antti Koivisto]

Comment on attachment 458555 [details]
Patch

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

> Source/WebCore/dom/Element.cpp:2007
> +    std::unique_ptr<ClassChangeVector> classChanges;

This needs a pointless heap allocation. It should be std::optional.

> Source/WebCore/dom/Element.cpp:2009
> +        classChanges = makeUnique<ClassChangeVector>(Style::ClassChangeInvalidation::computeClassChanges(oldClassNames, newClassNames));

It would be better to factor computeClassChanges out from style code (like ClassChangeVector already was) if it is going to be used outside it.

> Source/WebCore/dom/Element.cpp:-2005
> +    if (needsStyleInvalidation) {
> +        Style::ClassChangeInvalidation styleInvalidation(*this, classChanges.get());
> +        elementData()->setClassNames(WTFMove(newClassNames));
> +    } else
>          elementData()->setClassNames(WTFMove(newClassNames));
> -    }

You could avoid two paths for setClassName by having ClassChangeInvalidation do nothing when uninitialized classChanges is passed in (keeping the existing ClassChangeInvalidation::m_isEnabled bit).

[Antti Koivisto]

> > +    std::unique_ptr<ClassChangeVector> classChanges;
> 
> This needs a pointless heap allocation. It should be std::optional.

Or just plain ClassChangeVector. An empty vector signifies nothing needs to be done.

[Alexey Shvayka]

Created attachment 458609 [details]
Patch

Adjust test and apply all suggestions except passing ClassChangeVector by reference and keeping m_isEnabled.

[Alexey Shvayka]

Thank you both for the very thorough review. Really appreciate all the comments!

(In reply to Chris Dumez from comment #4)
> > Source/WebCore/dom/NodeRareData.h:128
> > +    ALWAYS_INLINE RefPtr<ClassCollection> addCachedClassCollection(ContainerNode& node, const AtomString& classNames)
> 
> Why does this return a RefPtr<> and not a Ref<>. It does not look like it
> can return null?

It indeed doesn't make sense and was used just for the `fastAdd(classNames, nullptr)` thing, which doesn't justify it at all and was replaced with ensure().

> > Source/WebCore/style/ClassChangeInvalidation.h:60
> > +    ASSERT(classChanges);
> 
> No, please pass classChanges by reference and drop this assertion.

Given the way ClassChangeVector is used (in a loop), I don't see how we can std::move it, so passing it by reference means copying the content, right? I'm a bit hesitant to do that given it's on a very hot path, hence the pointer.

Is there a way to drop ASSERT(classChanges) while avoiding copying the vector?

(In reply to Antti Koivisto from comment #5)
> > Source/WebCore/dom/Element.cpp:-2005
> > +    if (needsStyleInvalidation) {
> > +        Style::ClassChangeInvalidation styleInvalidation(*this, classChanges.get());
> > +        elementData()->setClassNames(WTFMove(newClassNames));
> > +    } else
> >          elementData()->setClassNames(WTFMove(newClassNames));
> > -    }
> 
> You could avoid two paths for setClassName by having ClassChangeInvalidation
> do nothing when uninitialized classChanges is passed in (keeping the
> existing ClassChangeInvalidation::m_isEnabled bit).

Yeah that's possible, but I try to avoid computeClassChanges() if it won't be used (which I presume most of the times), and for that I require needsStyleInvalidation(), which is non-trivial and I'm attempting to avoid adding an calling it twice on the hot path.

[Chris Dumez]

Comment on attachment 458609 [details]
Patch

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

I do not understand what copies you are talking about. A reference is like a pointer that cannot be null, it doesn't involve copying.

> Source/WebCore/style/ClassChangeInvalidation.cpp:38
> +void ClassChangeInvalidation::computeInvalidation(const ClassChangeVector* classChanges)

Please pass a `const ClassChangeVector&`

> Source/WebCore/style/ClassChangeInvalidation.cpp:44
> +        for (auto& classChange : *classChanges) {

classChanges

> Source/WebCore/style/ClassChangeInvalidation.cpp:68
> +    for (auto& classChange : *classChanges) {

classChanges

> Source/WebCore/style/ClassChangeInvalidation.h:44
> +    void computeInvalidation(const ClassChangeVector*);

const ClassChangeVector&

> Source/WebCore/style/ClassChangeInvalidation.h:54
> +inline ClassChangeInvalidation::ClassChangeInvalidation(Element& element, const ClassChangeVector* classChanges)

const ClassChangeVector&

> Source/WebCore/style/ClassChangeInvalidation.h:58
> +    ASSERT(classChanges);

No longer needed.

[Alexey Shvayka]

Created attachment 458619 [details]
Patch

Pass ClassChangeVector by reference and fix --debug build.

[Alexey Shvayka]

Comment on attachment 458619 [details]
Patch

(In reply to Chris Dumez from comment #9)
> Comment on attachment 458609 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=458609&action=review
> 
> I do not understand what copies you are talking about. A reference is like a pointer that cannot be null, it doesn't involve copying.

Oh wow, I've got basics all wrong, that's embarrassing.

Thanks Chris!

> LayoutTests/ChangeLog:8
> +        * intersection-observer/root-element-deleted.html:

This makes me think index cache change to keep Ref<Element> instead of Element* should probably be reverted, it's unsafe and not actually necessary.

[Ryosuke Niwa]

(In reply to Alexey Shvayka from comment #11)
> Comment on attachment 458619 [details]
> Patch
> 
> > LayoutTests/ChangeLog:8
> > +        * intersection-observer/root-element-deleted.html:
> 
> This makes me think index cache change to keep Ref<Element> instead of
> Element* should probably be reverted, it's unsafe and not actually necessary.

?? Ref will keep Element alive whereas Element* won't so can end up doing use-after-free. It's definitely safer to use Ref.

[Antti Koivisto]

> Yeah that's possible, but I try to avoid computeClassChanges() if it won't
> be used (which I presume most of the times), and for that I require
> needsStyleInvalidation(), which is non-trivial and I'm attempting to avoid
> adding an calling it twice on the hot path.

I understand that. I meant 

ChangeChangeVector classChanges;
if (needsComputeClassChange)
   classChanges = computeClassChanges(...);

ClassChangeInvalidation invalidation(classChanges);
setClassName(...);

where ClassChangeInvalidation simply doesn't do anything with empty vector.

[Sam Weinig]

Comment on attachment 458619 [details]
Patch

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

> Source/WTF/ChangeLog:10
> +        * wtf/RefCountedVector.h: Added.

Can you provide a description of what this new data structure is and when / why one would use it?

[Ryosuke Niwa]

Comment on attachment 458619 [details]
Patch

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

> Source/WTF/wtf/RefCountedVector.h:35
> +class RefCountedVector final : public RefCounted<RefCountedVector<T>>, public Vector<T> {

What's the point of this class??

> Source/WebCore/dom/CollectionIndexCache.h:40
> +    using CachedListType = RefCountedVector<Ref<NodeType>>;

We can't use Ref here. This will result in a leak since we don't automatically clear collection cache when a subtree is detached.
r- because of this.

[Ryosuke Niwa]

Comment on attachment 458619 [details]
Patch

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

> Source/WebCore/dom/ClassCollection.h:83
> +        if (hasOneRef())
> +            removeFromCache();

Deleting self like this is a dangerous pattern.
Let's make this function return a boolean indicating that this object needs to be removed instead.

> Source/WebCore/dom/Node.cpp:1003
> +    for (auto* node = this; node; node = node->parentNode()) {

Please use RefPtr instead.

> Source/WebCore/dom/Node.cpp:1977
> +void NodeListsNodeData::invalidateCachesForClassAttribute(const ClassChangeVector& classChanges)

We should probably rename the other one to invalidateCachesForNonClassAttribute

> Source/WebCore/dom/Node.cpp:1983
> +    Vector<ClassCollection*> cachedClassCollections;
> +    cachedClassCollections.reserveInitialCapacity(m_cachedClassCollections.size());
> +    for (auto& classCollection : m_cachedClassCollections.values())
> +        cachedClassCollections.uncheckedAppend(classCollection.ptr());
> +

Instead of always allocating a vector of collection, why not just call invalidateCacheIfNeeded
and store the collection to a vector only if the function returns boolean indicating that the deletion is necessary.

> Source/WebCore/dom/Node.h:81
> +    AtomStringImpl* className { };

Can we just store AtomString instead?
Storing a raw pointer like this seems rather dangerous.
This seems to be an over-optimization to me.

[Radar WebKit Bug Importer]

<rdar://problem/92827069>

[Alexey Shvayka]

(In reply to Ryosuke Niwa from comment #15)

Hey Ryosuke, sorry for the delay (I took some time off), and thank you for thorough review. Always appreciated.

> > Source/WebCore/dom/CollectionIndexCache.h:40
> > +    using CachedListType = RefCountedVector<Ref<NodeType>>;
> 
> We can't use Ref here. This will result in a leak since we don't
> automatically clear collection cache when a subtree is detached.
> r- because of this.

Could you please give me a hint on how to repro this leak?
I've tried a bunch of cases with detaching ancestor / parent before / after acquiring a valid cache for ClassCollection, while trying to invalidate it via changing attributes / children.
The cache always seems to be invalidated (yet again, I've tried only ClassCollection): when a node is detached, Node::invalidateNodeListAndCollectionCachesInAncestors() is called on its parent and goes all the way up.

> > LayoutTests/ChangeLog:8
> > +        * intersection-observer/root-element-deleted.html:
> 
> This makes me think index cache change to keep Ref<Element> instead of
> Element* should probably be reverted, it's unsafe and not actually necessary.

Expanding on this comment: I've used Ref<NodeType> so the vector could be shared (to avoid copying, since it's quite large in Speedo2) between a static querySelectorAll() NodeList and the cache of live getElementsByClassName() collection, even though the latter could get around with raw C++ pointer or WeakPtr.