1300372 - stylo: The style bloom filter is recreated a lot of times during parallel traversal.

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect)

Description

[Emilio Cobos Álvarez (:emilio)]

We basically store the parent of the last item removed from the bloom filter, which works great during sequential mode, and check if it matches to see if we need to recreate the bloom filter.

Code: https://github.com/servo/servo/blob/master/components/style/traversal.rs#L82

Basically, the code is not bogus, but the way Servo does selector matching in parallel (breadth-first instead of depth-first) makes it miss a lot.

I'm kind of concerned with the amount of misses because the order of this is exponential as the depth of the DOM increases.

Comment 1

[Bobby Holley (:bholley)]

In Taipei, we came up with a solution for this. From the etherpad:

It seems that the plan is something like the following:
    Every work unit nodes are at the same depth, so we can send that depth along with the work unit, and also keep track of the depth of thel last node stored in the bloom filter.
    With that, then we can either recreate the bloom filter or find a common ancestor.
    The algorithm would look something like this:
        Store the bloom filter and the depth of the last node inserted with it.
        When we're styling:
            Find the common ancestor between both nodes. This is O(N), since we know both depths.
            We could do two things during that search:
                One is popping ancestors and pushing ancestor while we go to find the common ancestor.
                Other, is first find the common ancestor, then see which strategy we want.
            As an heuristic, we can say that if the depth difference is more than one, two things might have happened:
                Someone has stolen job from us, or...
                We've stolen job to another.
            It seems reasonable to say that in any of these cases, we might be arbitrarily far away in the DOM, and we might as well just re-create the bloom filter.
    Once this is done, we should measure it, and then consider if the bloom filter is that useful.

Comment 2

[Emilio Cobos Álvarez (:emilio)]

Fixed in https://github.com/servo/servo/pull/14461