4 ms·

Good call, that rings a bell and I'll look into it. A bounded k-stack with overflow seems like a really good fit for the capabilities provided by GPU.

boulos 6y ago
Hmm. In the end, maybe transparency is a bad example, because people immediately jumped to approximating it instead. Wyman's review paper though is a good read regardless: http://cwyman.org/papers/hpg16_oitContinuum.pdf http://cwyman.org/papers/hpg16_oitContinuum.pdf The GPU / accelerator BVH traversals are perhaps more applicable (e.g., https://www.embree.org/papers/2019-HPG-ShortStack.pdf https://www.embree.org/papers/2019-HPG-ShortStack.pdf) but they also have a different "I can restart my computation" property that say JSON parsing wouldn't have (though maybe if you're willing to do a lot of restarts once you parse the inner portions and push them onto a heap...). Anyway, cool problem!
- raphlinus 6y ago
  The bell it rang for me was [1], which has come up in discussions with Patrick Walton about maintaining a sort order for coarse rasterization in 2D vector rendering. Taking another look at that, it seems like they propose both bounded k-stacks and linked lists as solutions for recording all the fragments to be combined for transparency blending, but not the hybrid of the two. I wouldn't be surprised if that's been considered. The problem is slightly different, though, because the major focus for transparency is concurrent writing from potentially many different shaders, while in the stack case each thread can build its data structure without any concurrency or need for atomics; once an aggregate is built, it is "published" (see my prefix sum blog for details on that) and treated as immutable. These kinds of concurrent approaches do become important for later stages in the JSON parsing process, like building hashmaps for keys in a dictionary. I'm pretty sure the whole problem is tractable and have thoughts how to solve it, but deliberately kept the scope of this blog post limited, as I figured it was challenging enough. But it's very cool to reach people who appreciate the ideas, and if you find anything else that's relevant, I'd love to hear from you. [1]: https://on-demand.gputechconf.com/gtc/2014/presentations/S4385-order-independent-transparency-opengl.pdf https://on-demand.gputechconf.com/gtc/2014/presentations/S43...

boulos 6y ago

Hmm. In the end, maybe transparency is a bad example, because people immediately jumped to approximating it instead. Wyman's review paper though is a good read regardless: http://cwyman.org/papers/hpg16_oitContinuum.pdf http://cwyman.org/papers/hpg16_oitContinuum.pdf The GPU / accelerator BVH traversals are perhaps more applicable (e.g., https://www.embree.org/papers/2019-HPG-ShortStack.pdf https://www.embree.org/papers/2019-HPG-ShortStack.pdf) but they also have a different "I can restart my computation" property that say JSON parsing wouldn't have (though maybe if you're willing to do a lot of restarts once you parse the inner portions and push them onto a heap...). Anyway, cool problem!

raphlinus 6y ago
The bell it rang for me was [1], which has come up in discussions with Patrick Walton about maintaining a sort order for coarse rasterization in 2D vector rendering. Taking another look at that, it seems like they propose both bounded k-stacks and linked lists as solutions for recording all the fragments to be combined for transparency blending, but not the hybrid of the two. I wouldn't be surprised if that's been considered. The problem is slightly different, though, because the major focus for transparency is concurrent writing from potentially many different shaders, while in the stack case each thread can build its data structure without any concurrency or need for atomics; once an aggregate is built, it is "published" (see my prefix sum blog for details on that) and treated as immutable. These kinds of concurrent approaches do become important for later stages in the JSON parsing process, like building hashmaps for keys in a dictionary. I'm pretty sure the whole problem is tractable and have thoughts how to solve it, but deliberately kept the scope of this blog post limited, as I figured it was challenging enough. But it's very cool to reach people who appreciate the ideas, and if you find anything else that's relevant, I'd love to hear from you. [1]: https://on-demand.gputechconf.com/gtc/2014/presentations/S4385-order-independent-transparency-opengl.pdf https://on-demand.gputechconf.com/gtc/2014/presentations/S43...