Also see Fast GPU bounding boxes on tree-structured scenes[1] (unpublished paper) and notes toward a blog post[2]. This is a highly tuned GPU implementation of parentheses matching. It's actually used in Vello (the classic version in which we offload basically all the work to the GPU, not the newer CPU-GPU hybrid version in which tracking the blend stack is done on the CPU).
Earlier versions of the work were featured on HN [3][4], but this is much more sophisticated. (plus a few more zero-comment submissions)
The basic idea (bicyclic semigroup and binary search) is the same as the submission. I think earliest attribution is to Bar-On and Vishkin[5] from 1985. Another implementation of this idea is in pareas[6], an experimental GPU-accelerated compiler.
I believe this work is publishable and would love to work with a student to resubmit it. Especially if you're a student or prof in Sydney, please reach out.
Getting to discover Oleg Kiselyov's work for the first time is such a treat. His web archive is incredible! I'm envious of the author and anyone else discovering it today.
The rendering appears to be done specifically by the js hosted on jsdelivr so if you've blocked that as a script source you'll just get the raw LaTeX (which I assume we're all fluent in anyways, of course!)
Also see Fast GPU bounding boxes on tree-structured scenes[1] (unpublished paper) and notes toward a blog post[2]. This is a highly tuned GPU implementation of parentheses matching. It's actually used in Vello (the classic version in which we offload basically all the work to the GPU, not the newer CPU-GPU hybrid version in which tracking the blend stack is done on the CPU).
Earlier versions of the work were featured on HN [3][4], but this is much more sophisticated. (plus a few more zero-comment submissions)
The basic idea (bicyclic semigroup and binary search) is the same as the submission. I think earliest attribution is to Bar-On and Vishkin[5] from 1985. Another implementation of this idea is in pareas[6], an experimental GPU-accelerated compiler.
I believe this work is publishable and would love to work with a student to resubmit it. Especially if you're a student or prof in Sydney, please reach out.
[1]: https://arxiv.org/abs/2205.11659
[2]: https://github.com/raphlinus/raphlinus.github.io/issues/66
[3]: https://news.ycombinator.com/item?id=24385095
[4]: https://news.ycombinator.com/item?id=27164009
[5]: https://dl.acm.org/doi/10.1145/3318.3478
[6]: https://github.com/Snektron/pareas
Getting to discover Oleg Kiselyov's work for the first time is such a treat. His web archive is incredible! I'm envious of the author and anyone else discovering it today.
https://okmij.org/ftp/
Fun article and worth the read, but sadly none of the LaTeX was rendered for me (assuming it was supposed to).
The rendering appears to be done specifically by the js hosted on jsdelivr so if you've blocked that as a script source you'll just get the raw LaTeX (which I assume we're all fluent in anyways, of course!)