Hacker News Reader

Comment by samsquire | Hacker News Reader

Is compositing different bitmaps an embarrassingly parallel problem?

I started writing a simple layout engine based on the ORCSolver white paper but I wonder how layout can be parallelized.

https://GitHub.com/samsquire/browser

I always thought servers could prelayout the HTML to determine X and Ys and widths for different browser viewport sizes and this metadata would speed up layout because you have a good candidate for layout immediately.

When it comes to changing the DOM and reflow, I wonder if you can reflow against the row only into chunks of the screen and recomposite bitmaps to move elements down the screen.

Some web pages are really pathological with relayout costs

View on HN

I’ve been out of the browser rendering engine game for a long time.

But even back in the day, the various ways that a DOM element’s physical layout could escape its parent’s bounding box, the multiple stages of coordinate evaluation, the zillion edge cases: it’s hard.

And that’s assuming that all inputs are perfectly formed. By the time you’ve cranked in enough Poe’s Law to be more than a tech demo, and enough performance to interest anyone?

It’s one of the nastiest practical problems you’ll encounter in a long career and the cross product of the kooky standard and the bugs you have to honor on the real web, a back compat story worse than Win32 mean that there’s no One Elegant Answer.

It’s a fucking mess and my hat is tipped to the hard-ass veterans who can even make a credible attempt.

I’d rather be on the hook for a modern RDBMS than a modern browser.

> I’d rather be on the hook for a modern RDBMS than a modern browser.

I've worked on both a RDBMS and a browser, and yes, I'm inclined to agree. In particular, it is largely acceptable for an RDBMS to pick a niche where you perform well, and do worse in others—and you're (silently) allowed to support only a given subset and have your own incompatibilities. Nobody would ever use a browser that performs well on NYT but could hardly run YouTube (or the other way around).

Interestingly, there are very small teams who have written usable instances of both.

It’s quite a career that includes both! Congratulations on an interesting professional life!

Are you at liberty to share any inside baseball about the small teams you mentioned?

I haven't been part of a small team building either, but the obvious small team doing RDBMSes is SQLite. Three people building the world's most popular software, and possibly the world's most robust database. They found a niche and implemented it perfectly.

For browsers, the most prominent example is probably LibWeb/Ladybird, part of SerenityOS (but with a Qt port, allowing it to run on other operating systems). I've never tried it myself, but supposedly it's complete enough to run large web applications fairly acceptably, which is amazing for something developed largely by basically two people AIUI.

I've been watching the SerenityOS videos and especially the Ladybird videos show a decent chunk of spec. One man (okay, one man with a history in WebKit development) and a bunch of volunteers gave built up a browser that could almost be competitive if it existed back in the day. Of course the people working on the project are incredibly talented, but I'd argue that if one full time employee developing both an operating system and a browser can get this much done with a community, the problem isn't as hard as many people deem it to be.

There's a lot that can go wrong, but the spec describes much more than I remember reading back in the day. Layout algorithms and such are all spelled out. There's no arcane knowledge in finding out what the right size of an <img> is, there are rules that will tell you exactly what you want to know if you follow the spec.

Not everything has been documented as well as it should be, but the vagueness and complexity of the web stack devs often like to lament about really isn't that difficult. It's a lot of reading, and boring reading at that, but the problems all seem relatively straightforward to me.

Even quirks mode has been largely documented. A spec for things that don't follow the spec!

I know things were very hard back when Internet Explorer was still a major browser because there were no rules. These days, you can either find your answer in the spec, or the publicly available source code for your competition.

With the amount of features being crammed into database systems these days, I'm not sure what I would prefer to maintain. A modern RDBMS sure seems less complex than a browser, particularly because there's no user facing UI, but the problems with an RDBMS are a lot more about (inventing) complex algorithms than many of the modern browser challenges.

>By the time you’ve cranked in enough Poe’s Law to be more than a tech demo

>Poe’s Law

What? What is this trying to say here? Is it a typo?

Perhaps referring to supporting web pages that are so poorly implemented that you suspect the developer did it as a joke? :)

See the previous paragraph, describing things that "could go wrong."

> Is compositing different bitmaps an embarrassingly parallel problem?

If you can make an initial approximate guess of the area for each section, you can split regions with lower and upper size constraints that can be laid out in parallel. A global branch and bound algorithm can coordinate those processes, tightening the upper constraints of one region when another connected region exceededs its minimum bounds.

Indeed there still may be degenerate cases where multiple regions need to be recalculated several times, but overall the default case should be able to finish without much conflict.

> Some web pages are really pathological with relayout costs

I'm always wondering how much do these awesome pathological sites contribute to CO2 emissions. Along with ADs, autoplay videos, huge and slow JS libraries, animations, and other needless and outright unwanted content. Even more on mobile. I'd say it's a lot and could be cut off immediately with very positive impact and no real loss.

CSS Containment <https://developer.mozilla.org/en-US/docs/Web/CSS/CSS_Contain...> defines ways of optimising a lot of calculation and recalculation, roughly by forbidding various of the harder or slower cases. (It’s approximately just an optimisation hint, though it does change behaviour if you try to break out of the containment you declare. It’s conceivable that in the future browsers could determine whether these optimisations can safely be done without the need for the hint, though that could only help relayout, never initial layout.) Some forms of containment that you can declared definitely allow for parallel layout to work without it being speculative.

> I always thought servers could prelayout the HTML to determine X and Ys and widths for different browser viewport sizes and this metadata would speed up layout because you have a good candidate for layout immediately.

They tried this with <img srcset>, where it can have a lot more value since you can fetch a lower-quality version of the image if you don’t need more pixels. In practice, effective use is somewhere between uncommon and extremely rare, depending on how you want to classify things. Some reconceptualisation of that that integrated with container queries <https://developer.mozilla.org/en-US/docs/Web/CSS/CSS_contain...> might have more potential. But all up, things like media queries, viewport units and calc() make any kind of “serialise the layout” concept extraordinarily difficult to do to any useful degree, and for almost no benefit.

> Is compositing different bitmaps an embarrassingly parallel problem?

> I started writing a simple layout engine based on the ORCSolver white paper but I wonder how layout can be parallelized.

Well Servo has webrender and stylo (now adopted in Firefox) which is aimed at harnessing the available parallelism to do those tasks

Reply on news.ycombinator.com