[webkit-dev] parallel layout research

[lmeyerov]

>  It reminds me a lot of the work Badros did circa 2000 [1].
> 

That work added linear constraints to CSS and a variety of other languages.
It did not show how to do flow-based layout with linear constraints:
ultimately, the utility and applicability of their techniques to actual
layout systems was never really understood (e.g., can we cleanly implement
and specify CSS with linear constraints? quadratic ones?). I don't recall
the end-to-end solving time, but, in my experience, it's not the constraint
solving of stuff like finding what point of font (which is essentially what
they support). The way I think about that work is that there is awkwardness
with strictly flow-based layout and Badros showed a useful primitive --
linearly constrained variables -- to help with some of it.



> they've implemented an abstract language for describing the CSS
> spec for parameterizing layout.
> 

Most of my implementation work has actually been on tweaking out selectors
as a way to get used to multicore performance concerns in this space :) I'm
working on language subsets, not full ones, in order to experiment with
actual implementations and iterate over many algorithm ideas.

For layout, I started with formalizing a subset of CSS 2.1 -- essentially
inlines, inline blocks, blocks, and left-floats with no
margins/padding/explicit positioning. Given that subset, I found places for
parallelism at the node-level (with speculation that floats don't have an
impact at the local level, which seems founded). Next I'll be bouncing
between expanding it and implementing and then tweaking it for various
memory systems.



>  They suggest that this model does layout of the CSS 2.1 spec in time
> similar to the hand-tuned sequential engine in Gecko [2]
> using Cilk++ to handle low-level paralleism, they've seen
> significant speedups beyond that for multi-core [2] 
> 

That work is now moving into the implementation phase: the slides were for a
model showing a minimum of what we'd expect if solving constraints was the
bottleneck (so parallelizing a tree of slow constraints). Interesting,
they're not -- it's stuff like dealing with text and images that come into
play -- so I actually expect a much better speedup. Because of this, my
first implementation step was to actually reexamine how to call into a font
library like freetype2 for better caching and multicore behavior.



> I think parallel layout is an interesting topic to explore, in light of
> where CPUs are going... We have had a lot of success with improving layout
> performance given test cases that demonstrate slowness.
> 

Worth mentioning our interest is half in traditional browser settings
(faster slashdot) and half in the mobile space. For the former, you may or
may not care if opening a page is as fast as hitting the back button (though
there are studies to show this has a big impact on usability in practice),
but, for the latter, we want to do at least a magnitude better *everywhere*.
Moh has had luck with firefox in terms of better memory usage, but I think
that's telling: you need to take advantage of the hardware with the
algorithms, whether it be CPU or L1.



> We probably can't use code in Cilk++ directly,
> 

TBB might be a more viable route in terms of licensing (and more amenable to
performance tools). Currently, I benefit from Cilk most in the early
prototyping phases -- I then rewrite in TBB because the compiler seems to do
better and I can do better profiling.


I'll be back in the bay area starting mid-September and would love to meet
anybody interested in this stuff. There are approaches that might work
(e.g., STM or rewriting in a pure language), but at least we're starting to
get proof that multicore helps for at least one approach :) Finally, it's
worth noting that I also get significant speedups by being careful about
l1/l2 usage -- I doubt that style of optimization works well in a huge
codebase with many contributors, so parallelization (with a sane framework
like cilk/tbb) might better scale with the code over time.
-- 
View this message in context: http://www.nabble.com/parallel-layout-research-tp24761520p24765531.html
Sent from the Webkit mailing list archive at Nabble.com.