[webkit-reviews] review denied: [Bug 179788] Make RenderSVGResource::markForLayoutAndParentResourceInvalidation() more robust : [Attachment 327087] Patch

[bugzilla-daemon at webkit.org]

Darin Adler <darin at apple.com> has denied Said Abou-Hallawa
<sabouhallawa at apple.com>'s request for review:
Bug 179788: Make
RenderSVGResource::markForLayoutAndParentResourceInvalidation() more robust
https://bugs.webkit.org/show_bug.cgi?id=179788

Attachment 327087: Patch

https://bugs.webkit.org/attachment.cgi?id=327087&action=review




--- Comment #3 from Darin Adler <darin at apple.com> ---
Comment on attachment 327087
  --> https://bugs.webkit.org/attachment.cgi?id=327087
Patch

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

This algorithm uses more hash table lookups than the old one did. The old
algorithm was careful to make both add and contains share a single hash table
lookup.

I think the best alternative for a new algorithm would be to replace both the
Vector and HashSet with a single ListHashSet. We can add new elements to the
set as we discover them, and use an iterator to walk through them in the order
they were added. The ListHashSet supports iterating through the set as we add
items to it. This makes both discoveredObjects and markedObjects into a single
hash table and means we will only hash each item once. It will take a little
bit of careful restructuring, but should work fine.

> Source/WebCore/ChangeLog:8
> +	   Use the BFS algorithm to make the function clearer and easier to
read.

Does BFS mean breadth-first search?

> Source/WebCore/rendering/svg/RenderSVGResource.cpp:161
> +    if (RenderSVGResourceFilter* filter = resources->filter())

I suggest auto* here.

> Source/WebCore/rendering/svg/RenderSVGResource.cpp:164
> +    if (RenderSVGResourceMasker* masker = resources->masker())

I suggest auto* here.

> Source/WebCore/rendering/svg/RenderSVGResource.cpp:167
> +    if (RenderSVGResourceClipper* clipper = resources->clipper())

I suggest auto* here.

> Source/WebCore/rendering/svg/RenderSVGResource.cpp:190
> +	   if (parent && !markedObjects.contains(parent) &&
!discoveredObjects.contains(parent)) {

Vector::contains is a potentially expensive operation that can make the
algorithm O(n^2). Since we need to do contains, we should be using a
ListHashSet instead of a Vector.

> Source/WebCore/rendering/svg/RenderSVGResource.cpp:193
> +		  
downcast<RenderSVGResourceContainer>(object)->removeAllClientsFromCache();

To avoid a null check that the compiler might or might not otherwise be able to
remove, we should write:

    downcast<SVGResourceContainer>(*object).removeAllClientsFromCache();

> Source/WebCore/rendering/svg/RenderSVGResource.cpp:195
> +		   discoveredObjects.insert(0, parent);

Vector::insert is a potentially expensive operation that can make the algorithm
O(n^2). That’s why we would normally use Deque/append/takeFirst instead of
Vector/insert(0)/takeLast. But since we want to do the contains operation as
well, we should use ListHashSet/add/takeFirst.

Except that I think we should probably use ListHashSet/add and an iterator and
not remove things from the set at all, iterate instead. That will visit nodes
in a different order, but I think that’s OK.

> Source/WebCore/rendering/svg/RenderSVGResource.cpp:199
> +	   if (!element || !element->isSVGElement())

This should be:

    if (!is<SVGElement>(element))

> Source/WebCore/rendering/svg/RenderSVGResource.cpp:205
> +	   HashSet<SVGElement*>* dependencies =
element->document().accessSVGExtensions().setOfElementsReferencingTarget(downca
st<SVGElement>(element));

I suggest auto* here.