> 
> 
> Eric Atkinson and I whiteboarded some ideas for ensuring data race 
> freedom and memory safety while performing parallel constraint solving 
> in layout. Here are some random notes from that discussion as well as 
> previous discussions we've had:


Sounds cool :)  In Flex, the (sequential) layout passes were extensible so 
users could script their own layout node types such as an accordion menu. As a 
guy brought in to help with bug fixes, I can attest that fixing ordering bugs 
stunk!

> 
> 
> * Floats constrain some subtrees to be in-order traversals, and 
> therefore those subtrees are not parallelizable during the assign-widths 
> traversal. We didn't discuss any general strategy for making sure that 
> memory safety/data race freedom are not violated in the presence of 
> floats; that will come later. (I don't foresee any fundamental problems 
> with ensuring this though.)


Individual (or even multiple) sequential float passes might also be 
parallelized via value speculation. The idea is to assume no floats anywhere, 
flag where the assumption was wrong, and recompute only as needed.

Stage 1. Speculative passes: assume no floats are used anywhere and do layout 
in parallel. At the end, flag violations where the computed result of one task 
does not match the speculated value for the next. Basically, follow the current 
layout strategy, so no races.

Stage 2. Sequential repair passes: in order, recompute subtrees that speculated 
incorrectly. To optimize for time, skip subtrees that speculated correctly. 
Note that not all 'flagged' mispeculations are valid -- one repair may change 
the speculation status of the subsequent task. To optimize for data, move the 
'repair' thread from core to core based on the subtree it is examining (to 
match which core did the speculative layout task). This process is sequential 
and thus also race-free.

More speculatively ( ;-) ), repair features some latent parallelism as well. 
I'd let benchmarks dictate where to focus on parallelization there, however. 
There's probably a paper in here somewhere that reveals the next level of 
optimization beyond Daan's "Two for the Price of One" paper at OOPSLA.

Regards,

- Leo
_______________________________________________
dev-servo mailing list
[email protected]
https://lists.mozilla.org/listinfo/dev-servo

Reply via email to