> > > 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

