2 ms·

What do you consider hard parts? The actual magic is that there is no hard parts.

taeric 9y ago
I haven't read it. That snippet just seemed odd to me. The hard parts, in this case, would be in Rust, most likely. I'm assuming that flipping CSS to parallel is not a trivial process. I'm further assuming that there is still some sort of locking mechanism so that you don't fire off two parallel traversals at the same time. Or allow updates during a scan. (Or abort running scans if an update happens?)
- sanxiyn 9y ago
  Ah yes, parallelism (locking etc) part is entirely handled in generic Rust library (Rayon in this case), and not specific to Stylo at all. Here is where Stylo meets Rayon, https://github.com/servo/servo/blob/master/components/style/parallel.rs https://github.com/servo/servo/blob/master/components/style/... //! Implements parallel traversal over the DOM tree. //! //! This traversal is based on Rayon, and therefore its safety is largely //! verified by the type system. /// A parallel top-down DOM traversal. /// /// This algorithm traverses the DOM in a breadth-first, top-down manner. The /// goals are: /// * Never process a child before its parent (since child style depends on /// parent style). If this were to happen, the styling algorithm would panic. /// * Prioritize discovering nodes as quickly as possible to maximize /// opportunities for parallelism. But this needs to be weighed against /// styling cousins on a single thread to improve sharing. /// * Style all the children of a given node (i.e. all sibling nodes) on /// a single thread (with an upper bound to handle nodes with an /// abnormally large number of children). This is important because we use /// a thread-local cache to share styles between siblings.
  - peoplewindow 9y ago
    It looks like Rayon is the same thing as Java's ForkJoinPool and parallel streams but with the neat trick (really, Rust's neat trick) that it can statically check that the code is safe to parallelise through the borrow checker.
    - sanxiyn 9y ago
      Yes, that's a good summary.
  - taeric 9y ago
    I'm curious how well this plays with some of the fancier selectors. Adjacent sibling, in particular. I'm also curious if this pretty much prohibits ever having a parent selector. I guess you could do a first pass through the styles to remove any DAG nature from them?
    - sanxiyn 9y ago
      DOM element has parent and sibling pointer, so there is nothing particularly difficult about adjacent sibling, later sibling, or even parent selector as far as selector matching goes. Avoiding restyling becomes more tricky, but nothing serious. "Parent before child" is for CSS inheritance, not for selector matching. For not-very-difficult details, read https://github.com/servo/servo/blob/master/components/selectors/matching.rs https://github.com/servo/servo/blob/master/components/select... searching for NotMatchedAndRestartFromClosestLaterSibling and HAS_SLOW_SELECTOR_LATER_SIBLINGS.
      - taeric 9y ago
        As soon as there are parent selectors, the pointers don't help. Specifically, if I restyle a parent, all children of parent need to be adjusted, right? Siblings... I'm assuming there is nothing hard there. Positions, maybe?
        sanxiyn 9y ago
        I still don't see what problem parent selectors cause. Restyling parent happens anyway without parent selectors (say, by JavaScript), so it is handled. In https://github.com/servo/servo/blob/master/components/style/matching.rs https://github.com/servo/servo/blob/master/components/style/..., MustCascadeChildren is returned when you... must.
        taeric 9y ago
        I was basically restating the restriction for the parallel scan. It goes from parent down so that during the scan you don't do something that causes the scan to have to restart. I was also shooting from the hip for things I'm interested in, here. I'm not sure it matters. But, if on scanning, you pick relevant rules to apply based on the path to a node, then I could see some trickiness on having to consider both the top down and the bottom up paths to a node. Siblings.., I don't think has this problem. Not sure why I thought it might. And javascript is ultimately a different topic. So I wasn't worried about that here.

I haven't read it. That snippet just seemed odd to me. The hard parts, in this case, would be in Rust, most likely. I'm assuming that flipping CSS to parallel is not a trivial process. I'm further assuming that there is still some sort of locking mechanism so that you don't fire off two parallel traversals at the same time. Or allow updates during a scan. (Or abort running scans if an update happens?)

sanxiyn 9y ago
Ah yes, parallelism (locking etc) part is entirely handled in generic Rust library (Rayon in this case), and not specific to Stylo at all. Here is where Stylo meets Rayon, https://github.com/servo/servo/blob/master/components/style/parallel.rs https://github.com/servo/servo/blob/master/components/style/... //! Implements parallel traversal over the DOM tree. //! //! This traversal is based on Rayon, and therefore its safety is largely //! verified by the type system. /// A parallel top-down DOM traversal. /// /// This algorithm traverses the DOM in a breadth-first, top-down manner. The /// goals are: /// * Never process a child before its parent (since child style depends on /// parent style). If this were to happen, the styling algorithm would panic. /// * Prioritize discovering nodes as quickly as possible to maximize /// opportunities for parallelism. But this needs to be weighed against /// styling cousins on a single thread to improve sharing. /// * Style all the children of a given node (i.e. all sibling nodes) on /// a single thread (with an upper bound to handle nodes with an /// abnormally large number of children). This is important because we use /// a thread-local cache to share styles between siblings.
- peoplewindow 9y ago
  It looks like Rayon is the same thing as Java's ForkJoinPool and parallel streams but with the neat trick (really, Rust's neat trick) that it can statically check that the code is safe to parallelise through the borrow checker.
  - sanxiyn 9y ago
    Yes, that's a good summary.
- taeric 9y ago
  I'm curious how well this plays with some of the fancier selectors. Adjacent sibling, in particular. I'm also curious if this pretty much prohibits ever having a parent selector. I guess you could do a first pass through the styles to remove any DAG nature from them?
  - sanxiyn 9y ago
    DOM element has parent and sibling pointer, so there is nothing particularly difficult about adjacent sibling, later sibling, or even parent selector as far as selector matching goes. Avoiding restyling becomes more tricky, but nothing serious. "Parent before child" is for CSS inheritance, not for selector matching. For not-very-difficult details, read https://github.com/servo/servo/blob/master/components/selectors/matching.rs https://github.com/servo/servo/blob/master/components/select... searching for NotMatchedAndRestartFromClosestLaterSibling and HAS_SLOW_SELECTOR_LATER_SIBLINGS.
    - taeric 9y ago
      As soon as there are parent selectors, the pointers don't help. Specifically, if I restyle a parent, all children of parent need to be adjusted, right? Siblings... I'm assuming there is nothing hard there. Positions, maybe?
      - sanxiyn 9y ago
        I still don't see what problem parent selectors cause. Restyling parent happens anyway without parent selectors (say, by JavaScript), so it is handled. In https://github.com/servo/servo/blob/master/components/style/matching.rs https://github.com/servo/servo/blob/master/components/style/..., MustCascadeChildren is returned when you... must.
        taeric 9y ago
        I was basically restating the restriction for the parallel scan. It goes from parent down so that during the scan you don't do something that causes the scan to have to restart. I was also shooting from the hip for things I'm interested in, here. I'm not sure it matters. But, if on scanning, you pick relevant rules to apply based on the path to a node, then I could see some trickiness on having to consider both the top down and the bottom up paths to a node. Siblings.., I don't think has this problem. Not sure why I thought it might. And javascript is ultimately a different topic. So I wasn't worried about that here.