1300379 - stylo: Implement concurrent rule tree in Servo

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect, P2)

Description

[Emilio Cobos Álvarez (:emilio)]

Just had this conversation about all the optimizations that the rule tree allows and, even though it's unlikely that we can create a data-structure like that from multiple threads, it's probably worth to investigate if we can do something smart about it.

Comment 1

[Bobby Holley (:bholley)]

One insight that Simon had was that children in the rule tree don't need to have an ordering, so it's possible that we might be able to use some kind of lockless map to implement a mult-threaded rule tree. There are still lots of issues to be sorted out though, so it's not clear if this is something we want to pursue. We should investigate it at some point though.

Comment 2

[Bobby Holley (:bholley)]

We spent a lot of time today discussing this, and decided this is probably something we want to do. Having a mechanism to express the result of selector matching has a lot of advantages, especially for incremental restyle and animations. And we feel pretty confident that we can implement it in in a threadsafe way without sacrificing in performance and memory from what we have now.

The core primitive is a prefix tree that is threadsafe with respect to get_or_insert, shared among the worker threads. This will look quite similar to Gecko's rule tree, probably including the union between linked list and hashmap to store children. We can implement atomic get_or_insert for either, and we can periodically traverse the tree in exclusive mode (when the parallel workers are idle) to collect unused nodes and (optionally) convert long linked lists into hashmaps. This traversal can either be whole-tree, or based on something more targeted linked a free list.

Creation of the tree shouldn't be much additional overhead to our current process of building the list of ApplicableDeclarations, since we can just replace the insertions into the smallvec with a get_or_insert-based walk down the prefix tree.

The rule tree gives us a precise version of ApplicableDeclarations cache, which we should be able to remove once we have it. The first DOM node to be cascaded for a given rule node will store its ComputedValues on the rule node. Each node will hold a pointer to its rule node in addition to its ComputedValues, and we can use the existing cascade_with_cached_declarations logic if we're cascading a node whose rule node already has a cached ComputedValues.

The gecko rule tree also does various caching of individual non-inherited style structs at various levels of the rule tree, which reduces the work required to cascade nodes whose rule nodes have a cached struct in one of their ancestors. This doesn't really work all that well with servo's cascade algorithm, and so we can probably skip this part.

Comment 3

[Boris Zbarsky [:bzbarsky]]

> The first DOM node to be cascaded for a given rule node will store its ComputedValues on the rule node.

Computed values depend on node _and_ parent, no?  Or are ComputedValues actually specified values?

Comment 4

[Emilio Cobos Álvarez (:emilio)]

(In reply to Boris Zbarsky [:bz] from comment #3)
> Computed values depend on node _and_ parent, no?  Or are ComputedValues
> actually specified values?

Right, you can only cache the computed reset structs in the rule node (and only the ones that don't have any explicitly inherited reset property).

Comment 5

[Cameron McCormack (:heycam)]

And we'll only do this in cases similar to what Gecko does for faulting out of rule tree caching, i.e. if we encounter font-size relative units, explicit inherit on reset properties, etc.

Note also that we will store a pointer to the ComputedValues that was produced for the first element that matched that rule node (assuming it's allowed to be cached).  We'll then just ignore the inherited values on it, and clone out the reset structs from it when we want to re-use them.

(Storing the whole ComputedValues is easier since we won't have to copy out the reset structs from it.  Alternatively we could make a ComputedValues have two members, one for inherited and one for reset structs, and make the reset structs one an Arc.  Then we could just store that in the rule tree.  Not sure if it's worth doing that.)

Comment 6

[Bobby Holley (:bholley)]

(In reply to Cameron McCormack (:heycam) from comment #5)
> Alternatively we could make a ComputedValues
> have two members, one for inherited and one for reset structs, and make the
> reset structs one an Arc.  Then we could just store that in the rule tree. 
> Not sure if it's worth doing that.)

I filed bug 1304244 to discuss this.

Comment 7

[Emilio Cobos Álvarez (:emilio)]

This landed in https://github.com/servo/servo/pull/13202.