6 ms·

Firefox: Retained Display Lists

145 points by agnivade 9y ago

mrec 9y ago
Interesting post. It feels quite closely analogous to the virtual-DOM diffing approaches that have dominated client-side JS frameworks lately. Is there any history of this technique being used in game engine design? Or is that more concerned about optimizing for the worst case (thou shalt not drop frames) than for the average case?
- speps 9y ago
  It's very common, even OpenGL had a way to do that way back in OpenGL 1.3[1][2]... I said it before with they "Off Main Thread" feature, it's been in game engines for decades now... Meh, what's not known is bound to be reinvented. [1] https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glNewList.xml https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml... [2] http://www.songho.ca/opengl/gl_displaylist.html http://www.songho.ca/opengl/gl_displaylist.html
  - mrec 9y ago
    Not quite the same - I remember using GL display lists, but once you'd compiled one it was set in stone. There was no way to mostly reuse it but with a few changes here and there.
    - speps 9y ago
      It all depends on how your organize them really. If you follow the DOM hierarchy then you would only need to change one if the element has changed color for example, not position, scale, rotation as that would be done with the transform.
      - mrec 9y ago
        Aren't you assuming one display list per leaf element, which kind of negates the whole benefit of batching? If DOM node X hasn't rotated but one of its grandchildren has, a display list representing the whole of X will definitely need updating!
- royjacobs 9y ago
  Game engines have never had the approach of recalculating everything every frame. Instead, aggressively reusing data and only changing what you need is the default approach (as it should be if you want to squeeze the most out of a CPU/GPU). Things like command lists, vertex and index buffers and textures are retained from frame to frame as much as possible. Anything dynamic is usually handled on the GPU-side by taking a static input and applying simple (animated) parameters on top or, more commonly now, feeding back into the original buffer thereby updating it from the GPU calculations themselves. The fact that web development has finally caught up to this approach is certainly welcome, but this is nothing new at all.
  - mrec 9y ago
    I think vbuffers/ibuffers/textures are a red herring here - the browser equivalent there would be re-requesting CSS files or images every frame, which nobody has ever suggested. And yes, reusing unmodified GPU command buffers is a very old technique. The interesting thing here seems to be the equivalent of selectively patching a command buffer without rebuilding the whole thing, and I wasn't aware of any game-engine precedent there. (Though I haven't really followed graphics closely for years.) > Anything dynamic is usually handled on the GPU-side That mostly only applies to cosmetic stuff, e.g. particle systems or bone-weighted skinning. For anything where the output has to feed back into CPU-based logic like collision physics or AI or even coarse frustum culling, it gets messier. I believe there are async readback APIs these days so that you don't have to stall the whole pipeline to get anything out, but it's still tricksy.
  - pcwalton 9y ago
    This is something different from what game engines do. A game engine can typically just walk the scene graph, emitting draw calls as it encounters potentially visible objects. The equivalent approach on the Web would be walking the render tree/frame tree, issuing draw calls as it goes. This is indeed the traditional method that Gecko and WebKit used to use, but it has a lot of problems, which are why Blink and Gecko use display lists: 1. The CSS 2.1 Appendix E painting order is complex: it's not enough to traverse the tree in breadth-first or depth-first order. You could get around that by traversing the tree multiple times, as Blink and WebKit do, but that gets complex. It's a lot more straightforward, not to mention cache friendlier, to build display items into a list and then later sort them into the proper CSS stacking order. This is actually similar to what game engines do for transparent objects (assuming they actually care about rendering them properly and aren't using any fancy OIT techniques). 2. For security reasons, these days you don't want direct GPU access in the same process as JavaScript. Display lists enable an elegant solution to this, as they can be transmitted over IPC to a trusted process. 3. Display lists can be rendered in a separate thread from the layout and/or JavaScript execution, enabling better use of concurrency. 4. Unlike a typical game, which has the luxury of being able to build up vertex and index buffers beforehand and can cache them on the individual nodes in the scene graph, on the Web each individual display item only has a tiny amount of GPU data. Slow rendering on the Web is often the result of "death by a thousand cuts", where the GPU is swamped in draw calls from lots of unrelated items. The only scalable solution to this problem is to batch across display items, using knowledge of the entire scene to construct VBOs and IBOs. This is only possible if the renderer has a global view of the entire scene, and the display list is a natural way to achieve that. I certainly think that Web browsers can learn a lot from game engines (and WebRender is designed to do just that). But display lists are one of those cases in which the problem space is just different: trying to do exactly what a game engine does doesn't work well.
- westmeal 9y ago
  It sounds kind of like culling in game engines. Is it truly similar though? I'm not familiar how you can quickly test for an object being in view without doing an O(n) operation first and then retaining the list visible if the scene didn't change. Is there any way to do so?
  - royjacobs 9y ago
    Look at spatial partitioning schemes like BSP, octrees, etc. In fact, look at another trending story[1] about the Unreal editor because it discusses this exact concept (except this was being done in the early to mid 90s). [1] https://www.gamasutra.com/blogs/DavidLightbown/20180109/309414/Classic_Tools_Retrospective_Tim_Sweeney_on_the_first_version_of_the_Unreal_Editor.php https://www.gamasutra.com/blogs/DavidLightbown/20180109/3094...
  - sp332 9y ago
    Firefox has been changing the rendering system pretty dramatically lately. https://hacks.mozilla.org/2017/10/the-whole-web-at-maximum-fps-how-webrender-gets-rid-of-jank/ https://hacks.mozilla.org/2017/10/the-whole-web-at-maximum-f... They describe the direction they're going as: "make it more like a 3D game engine."
- muizelaar 9y ago
  The current approach without retained display lists is actually closer to the virtual-DOM diffing approach. i.e. Without retained display lists: - build up a display list of the entire scene. - diff this display list with the previous one to see what areas have changed. - paint the areas that have changed With retained display lists: - keep a list of elements that have changed - build a display list for part of the screen that have changed elements in them - merge the new partial display list into the old one - diff this display list with the previous to see what areas have changed - paint the areas that have changed
DiabloD3 9y ago
Previously on HN: https://news.ycombinator.com/item?id=16112283 https://news.ycombinator.com/item?id=16112283
- jwilk 9y ago
  There were no comments, so there's no point linking to it.
- dang 9y ago
  No, agnivade's post was earlier, as you can see from its ID as well as from https://news.ycombinator.com/from?site=mozillagfx.wordpress.com https://news.ycombinator.com/from?site=mozillagfx.wordpress..... We put it in the second-chance queue, described at https://news.ycombinator.com/item?id=11662380 https://news.ycombinator.com/item?id=11662380 and links back from there. When we see a good article that fell through the cracks and put it in the second-chance queue, we try to pick the first submission of the article. When we do this, the submission timestamp on the front page becomes the time it was put in the queue, approximately. That's why it looked like a later post than yours. I don't like doing this, but not doing it invariably triggers a barrage of questions and complaints ("what is this 2-day old story with 3 upvotes doing on the front page"). You can always see the original timestamp by looking at the submission in the user history (https://news.ycombinator.com/submitted?id=agnivade https://news.ycombinator.com/submitted?id=agnivade) or the site history (https://news.ycombinator.com/from?site=mozillagfx.wordpress.com https://news.ycombinator.com/from?site=mozillagfx.wordpress....). More here if anyone cares: https://hn.algolia.com/?sort=byDate&dateRange=all&type=comment&storyText=false&prefix&page=0&query=by:dang%20timestamp%20front https://hn.algolia.com/?sort=byDate&dateRange=all&type=comme...
  - DiabloD3 9y ago
    Huh. That's fine, but it should have caught my submission as a duplicate of his then, or at least, tell me someone else has.
    - dang 9y ago
      That's not so easy, because in cases where we don't notice the story and re-up it, reposts are key to giving good articles multiple chances at attention.
Misdicorl 9y ago
That second graph and discussion is really frustrating. The claim is that latencies from 38-50 get shifted down into other buckets, and the the 51+ bucket increases is an artifact of the lower aggregate numbers. Maybe the data supports this, but there's no way to know looking at the graph. The histogram should be scaled against total counts rather than the subcounts (just zoomed in appropriately for the dataset). As shown, its bad statistics at best, and disingenuous lies at worst
Vinnl 9y ago
So I'll be that person: if it can be enabled in the 58 beta, does that mean it's on track for being included in that or another specific release? Or is it not planned yet?
- Manishearth 9y ago
  If it can be enabled in 58 beta, you'll likely be able to enable it in 58 release. But there may not be any stability guarantees on it working correctly. I believe the target is 59, though it might stretch to 60.
  - Vinnl 9y ago
    Thanks, that's the info I was looking for!
cryptonector 9y ago
Will this improve remote X11 display performance for Firefox?
- moosingin3space 9y ago
  Unlikely -- remote X11 display performance for anything GPU-accelerated isn't great due to X11's design, not Firefox's.
  - cryptonector 9y ago
    Firefox repaints too often.

145 points by agnivade 9y ago

mrec 9y ago

Interesting post. It feels quite closely analogous to the virtual-DOM diffing approaches that have dominated client-side JS frameworks lately. Is there any history of this technique being used in game engine design? Or is that more concerned about optimizing for the worst case (thou shalt not drop frames) than for the average case?

speps 9y ago
It's very common, even OpenGL had a way to do that way back in OpenGL 1.3[1][2]... I said it before with they "Off Main Thread" feature, it's been in game engines for decades now... Meh, what's not known is bound to be reinvented. [1] https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/glNewList.xml https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml... [2] http://www.songho.ca/opengl/gl_displaylist.html http://www.songho.ca/opengl/gl_displaylist.html
- mrec 9y ago
  Not quite the same - I remember using GL display lists, but once you'd compiled one it was set in stone. There was no way to mostly reuse it but with a few changes here and there.
  - speps 9y ago
    It all depends on how your organize them really. If you follow the DOM hierarchy then you would only need to change one if the element has changed color for example, not position, scale, rotation as that would be done with the transform.
    - mrec 9y ago
      Aren't you assuming one display list per leaf element, which kind of negates the whole benefit of batching? If DOM node X hasn't rotated but one of its grandchildren has, a display list representing the whole of X will definitely need updating!
royjacobs 9y ago
Game engines have never had the approach of recalculating everything every frame. Instead, aggressively reusing data and only changing what you need is the default approach (as it should be if you want to squeeze the most out of a CPU/GPU). Things like command lists, vertex and index buffers and textures are retained from frame to frame as much as possible. Anything dynamic is usually handled on the GPU-side by taking a static input and applying simple (animated) parameters on top or, more commonly now, feeding back into the original buffer thereby updating it from the GPU calculations themselves. The fact that web development has finally caught up to this approach is certainly welcome, but this is nothing new at all.
- mrec 9y ago
  I think vbuffers/ibuffers/textures are a red herring here - the browser equivalent there would be re-requesting CSS files or images every frame, which nobody has ever suggested. And yes, reusing unmodified GPU command buffers is a very old technique. The interesting thing here seems to be the equivalent of selectively patching a command buffer without rebuilding the whole thing, and I wasn't aware of any game-engine precedent there. (Though I haven't really followed graphics closely for years.) > Anything dynamic is usually handled on the GPU-side That mostly only applies to cosmetic stuff, e.g. particle systems or bone-weighted skinning. For anything where the output has to feed back into CPU-based logic like collision physics or AI or even coarse frustum culling, it gets messier. I believe there are async readback APIs these days so that you don't have to stall the whole pipeline to get anything out, but it's still tricksy.
- pcwalton 9y ago
  This is something different from what game engines do. A game engine can typically just walk the scene graph, emitting draw calls as it encounters potentially visible objects. The equivalent approach on the Web would be walking the render tree/frame tree, issuing draw calls as it goes. This is indeed the traditional method that Gecko and WebKit used to use, but it has a lot of problems, which are why Blink and Gecko use display lists: 1. The CSS 2.1 Appendix E painting order is complex: it's not enough to traverse the tree in breadth-first or depth-first order. You could get around that by traversing the tree multiple times, as Blink and WebKit do, but that gets complex. It's a lot more straightforward, not to mention cache friendlier, to build display items into a list and then later sort them into the proper CSS stacking order. This is actually similar to what game engines do for transparent objects (assuming they actually care about rendering them properly and aren't using any fancy OIT techniques). 2. For security reasons, these days you don't want direct GPU access in the same process as JavaScript. Display lists enable an elegant solution to this, as they can be transmitted over IPC to a trusted process. 3. Display lists can be rendered in a separate thread from the layout and/or JavaScript execution, enabling better use of concurrency. 4. Unlike a typical game, which has the luxury of being able to build up vertex and index buffers beforehand and can cache them on the individual nodes in the scene graph, on the Web each individual display item only has a tiny amount of GPU data. Slow rendering on the Web is often the result of "death by a thousand cuts", where the GPU is swamped in draw calls from lots of unrelated items. The only scalable solution to this problem is to batch across display items, using knowledge of the entire scene to construct VBOs and IBOs. This is only possible if the renderer has a global view of the entire scene, and the display list is a natural way to achieve that. I certainly think that Web browsers can learn a lot from game engines (and WebRender is designed to do just that). But display lists are one of those cases in which the problem space is just different: trying to do exactly what a game engine does doesn't work well.
westmeal 9y ago
It sounds kind of like culling in game engines. Is it truly similar though? I'm not familiar how you can quickly test for an object being in view without doing an O(n) operation first and then retaining the list visible if the scene didn't change. Is there any way to do so?
- royjacobs 9y ago
  Look at spatial partitioning schemes like BSP, octrees, etc. In fact, look at another trending story[1] about the Unreal editor because it discusses this exact concept (except this was being done in the early to mid 90s). [1] https://www.gamasutra.com/blogs/DavidLightbown/20180109/309414/Classic_Tools_Retrospective_Tim_Sweeney_on_the_first_version_of_the_Unreal_Editor.php https://www.gamasutra.com/blogs/DavidLightbown/20180109/3094...
- sp332 9y ago
  Firefox has been changing the rendering system pretty dramatically lately. https://hacks.mozilla.org/2017/10/the-whole-web-at-maximum-fps-how-webrender-gets-rid-of-jank/ https://hacks.mozilla.org/2017/10/the-whole-web-at-maximum-f... They describe the direction they're going as: "make it more like a 3D game engine."
muizelaar 9y ago
The current approach without retained display lists is actually closer to the virtual-DOM diffing approach. i.e. Without retained display lists: - build up a display list of the entire scene. - diff this display list with the previous one to see what areas have changed. - paint the areas that have changed With retained display lists: - keep a list of elements that have changed - build a display list for part of the screen that have changed elements in them - merge the new partial display list into the old one - diff this display list with the previous to see what areas have changed - paint the areas that have changed

DiabloD3 9y ago

Previously on HN: https://news.ycombinator.com/item?id=16112283 https://news.ycombinator.com/item?id=16112283

jwilk 9y ago
There were no comments, so there's no point linking to it.
dang 9y ago
No, agnivade's post was earlier, as you can see from its ID as well as from https://news.ycombinator.com/from?site=mozillagfx.wordpress.com https://news.ycombinator.com/from?site=mozillagfx.wordpress..... We put it in the second-chance queue, described at https://news.ycombinator.com/item?id=11662380 https://news.ycombinator.com/item?id=11662380 and links back from there. When we see a good article that fell through the cracks and put it in the second-chance queue, we try to pick the first submission of the article. When we do this, the submission timestamp on the front page becomes the time it was put in the queue, approximately. That's why it looked like a later post than yours. I don't like doing this, but not doing it invariably triggers a barrage of questions and complaints ("what is this 2-day old story with 3 upvotes doing on the front page"). You can always see the original timestamp by looking at the submission in the user history (https://news.ycombinator.com/submitted?id=agnivade https://news.ycombinator.com/submitted?id=agnivade) or the site history (https://news.ycombinator.com/from?site=mozillagfx.wordpress.com https://news.ycombinator.com/from?site=mozillagfx.wordpress....). More here if anyone cares: https://hn.algolia.com/?sort=byDate&dateRange=all&type=comment&storyText=false&prefix&page=0&query=by:dang%20timestamp%20front https://hn.algolia.com/?sort=byDate&dateRange=all&type=comme...
- DiabloD3 9y ago
  Huh. That's fine, but it should have caught my submission as a duplicate of his then, or at least, tell me someone else has.
  - dang 9y ago
    That's not so easy, because in cases where we don't notice the story and re-up it, reposts are key to giving good articles multiple chances at attention.

Misdicorl 9y ago

That second graph and discussion is really frustrating. The claim is that latencies from 38-50 get shifted down into other buckets, and the the 51+ bucket increases is an artifact of the lower aggregate numbers. Maybe the data supports this, but there's no way to know looking at the graph. The histogram should be scaled against total counts rather than the subcounts (just zoomed in appropriately for the dataset). As shown, its bad statistics at best, and disingenuous lies at worst

Vinnl 9y ago

So I'll be that person: if it can be enabled in the 58 beta, does that mean it's on track for being included in that or another specific release? Or is it not planned yet?

Manishearth 9y ago
If it can be enabled in 58 beta, you'll likely be able to enable it in 58 release. But there may not be any stability guarantees on it working correctly. I believe the target is 59, though it might stretch to 60.
- Vinnl 9y ago
  Thanks, that's the info I was looking for!

cryptonector 9y ago

Will this improve remote X11 display performance for Firefox?

moosingin3space 9y ago
Unlikely -- remote X11 display performance for anything GPU-accelerated isn't great due to X11's design, not Firefox's.
- cryptonector 9y ago
  Firefox repaints too often.