4 ms·

Is compositing different bitmaps an embarrassingly parallel problem? I started writing a simple layout engine based on the ORCSolver white paper but I wonder h

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

TuringTest 3y ago
> 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.
benreesman 3y ago
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.
- Sesse__ 3y ago
  > 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.
  - benreesman 3y ago
    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?
    - Sesse__ 3y ago
      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.
- knome 3y ago
  >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?
  - ptx 3y ago
    Perhaps referring to supporting web pages that are so poorly implemented that you suspect the developer did it as a joke? :)
hexo 3y ago
> 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.
nextaccountic 3y ago
> 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
chrismorgan 3y ago
CSS Containment <https://developer.mozilla.org/en-US/docs/Web/CSS/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_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.

TuringTest 3y ago

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

benreesman 3y ago

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.

Sesse__ 3y ago
> 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.
- benreesman 3y ago
  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?
  - Sesse__ 3y ago
    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.
knome 3y ago
>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?
- ptx 3y ago
  Perhaps referring to supporting web pages that are so poorly implemented that you suspect the developer did it as a joke? :)

hexo 3y ago

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

nextaccountic 3y ago

> 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

chrismorgan 3y ago

CSS Containment <https://developer.mozilla.org/en-US/docs/Web/CSS/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_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.