5 ms·

The stack monoid revisited

216 points by harperlee 5y ago

uyt 5y ago
If you test on random parens, won't the nesting depth be fairly shallow? I'm still reading and I am trying to understand what this will do if you have long streaks of pushes with rare pops (but maybe still occasional enough to cause large shuffles in the in-place reduction). What do you do after the stack size is larger than the number of parallel thread?
- raphlinus 5y ago
  Just testing on random parens gives you an expected stack depth of O(sqrt(N)). I've also (just now) tried biasing the sequence generation with more pushes than pops, and it doesn't substantially affect running time. The case where the stack depth is greater than the partition size is tricky for sure, and this is what I call the "backlink" mechanism. The tl;dr is that it follows the deepest link (furthest from top of stack) that it can, and continues the look-back process, until the slice is complete. You can search for "backlink" in the code - it's actually not a huge amount of logic, though it certainly was subtle to get right.
  - dan-robertson 5y ago
    Any guess as to what the distribution will look like in practice? I suppose you started with a list of iid equally likely parens, but I would guess that in practice the distribution D might look more like: () moderately likely (X) where X ~ (roughly) D quite likely X Y where X,Y ~ (roughly) D slightly likely. My prior is that in user interfaces one will typically see a somewhat deep nesting of clips (ie components) with a few primitives to draw at each level. But maybe this is just wrong or most of these clips are axis-aligned rectangles and can be dealt with as the command list is built. Or maybe you do see nesting in practice but not super deep nesting (say window > panel > panel > set of buttons > button > text with each corresponding to several layers of nested clips)
  - 082349872349872 5y ago
    Is the distribution normal around that expected stack depth, or does it skew to many shallow stacks but the rare deep stacks are really deep?
StandardFuture 5y ago
Would someone like to ELI5/summate what this is and what it is for?
- anchpop 5y ago
  The author is working on piet-gpu, a library for efficiently rendering 2D graphics on the GPU, for UIs and font editors and things like that. This is very nontrivial (and in fact most 2D graphics you see today are in large part rendered on the CPU). The goal of piet-gpu is that you just specify the scene graph (blue circle here, red line there, etc) and send it over to the GPU, and the GPU takes care of all the rendering. GPUs are very good at processing data in the shape of arrays. For example, a pixel shader (or "fragment shader") processes a 2D array of pixels on the screen. piet-gpu needs to sometimes process data that has a tree structure, rather than an array structure, to support clipping (for example to show a shape that represents the intersection between a circle and a square). The stack monoid the article talks about is a way of doing tree-like operations in parallel on the GPU, and the author thinks it will end up being useful for being able to process clipping operations entirely on the GPU.
  - marai2 5y ago
    You could start a business doing ELI5s of complex topics! Thank you for a wonderful summary!
  - StandardFuture 5y ago
    Thanks for the summary! Quick question: wouldn't executing partially-ordered sets of operations in a semi-parallel or fully-parallel way already be an existing research topic in Computer Science? Obviously this project is attempting to find a solution for a singular application and not attempting to find a general algorithm, but still there must be some historical precedent. I would imagine that companies like NVIDIA would have even already contributed to this space? Are there any existing resources on the topic that perhaps you or the OP knows of?
    - mijoharas 5y ago
joe_the_user 5y ago
The ability to compute the stack monoid on slices of the input, then stitch them together later, is essential for processing this in parallel. So what isn't possible is having two threads push/pop to the same conventional stack. So I assume the author is doing something different. So what I guess they're doing is descending down the tree, and splitting off all the operations that can be done in parallel so that you get a bunch of kernels feeding their results into each other with the structure of the tree. It seems like some synchronization is need so one thread waits for the results of another. A monoid, as I vaguely understand them, acts as a kind stored operation so this seems logical. And if you ran out of threads, the monoid would just act as a conventional stack on some of the remaining threads. Of course, none of this says the mechanism to implement this.
- lmm 5y ago
  > So what isn't possible is having two threads push/pop to the same conventional stack. So I assume the author is doing something different. Indeed; what they're doing is building up a command object that represents a sequence of modifications to a stack. And that's something that you can parallelise, map-reduce style: they've come up with a representation for that command that makes it easy to combine two commands into a bigger command, and a technique for doing that combine in-place without needing extra scratch space. This doesn't need any synchronization between parallel threads - of course the final result is only formed when all the threads finish. (To materialize the final value of the stack you'd have to "run" the final command, but it turns out that's trivial for this command representation - just confirm that the number of pops is zero, and then the push sequence is the final value of the stack).
  - joe_the_user 5y ago
    * This doesn't need any synchronization between parallel threads - of course the final result is only formed when all the threads finish* I'm still confused. If one calculates (x+y)*(z+w). You can divide the addition between threads but the multiplication has to happen once these two threads end. If you're talking a "map-reduce" approach, as far as I understand it, the reduce has to happen once the mapping is done. Which would seem to require synchronization also.
gugagore 5y ago
From Wikipedia: > In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. So M = (S, op, id) My go-to example of a monoid is (the set of strings, string concatenation, the empty string). It's my go-to because there's e.g. no `x` such that `concat("blah", x) == ""`. Another example is (integers, +, 0), but it is not my go-to example because it also more than a monoid. I did not find a clear explanation of what the stack monoid is here. Can someone state it, please?
- tomstuart 5y ago
  An earlier post (https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html) explains it. The elements of the monoid are stack operations represented by pairs `(n, vs)`, where `n` is a number of values to pop off the stack and `vs` is a list of values to push on afterwards. So e.g. `(3, [])` is “pop 3 values”, `(1, ['foo', 'bar'])` is “pop 1 value then push 'foo' and 'bar'”, etc. Two elements are composed by combining their pop counts and push lists to reflect what happens to the stack if you apply the operations sequentially, e.g. the previous two examples compose to `(4, ['foo', 'bar'])`. The identity is `(0, [])`.
  - lmm 5y ago
    So this isn't really the stack monoid, this is mutations as a monoid (which is a construction that exists for anything mutable), or the command monoid. The insight is that these mutations have a nice representation as first-class values and you can combine two "stack mutation commands" efficiently.
    - Twisol 5y ago
      > So this isn't really the stack monoid, this is mutations as a monoid (which is a construction that exists for anything mutable) I can see why you'd balk at the name "stack monoid", but the specific commands / actions being modeled (push/pop) are exactly the ones modeling a stack. It's not a purely syntactic construction because a push followed by a pop is evaluated away. The representation as `(pops, pushes)` is the natural conclusion of this line of semantic analysis. > this is mutations as a monoid In general though, yeah, this is the secret sauce. The history of commands on a mutable cell is sufficient to recover the value of the cell at any point in time, and the history of values held by the cell is sufficient to derive a (not necessarily unique) history of commands going between each snapshot. Typically, though, we only remember the "latest" value of the cell, so we lose a lot of information. In a parallel algorithm, multiple "points in time" need to be accessible simultaneously, so you get a lot by moving to a representation where you're not already missing information.
liuliu 5y ago
Interesting in-depth discussion with the parallel parentheses matching solution. Back to the clipping problem though, in each intermediate step (when we still incorporating prefixed results), do we compute clipping for each elements progressively (the result array in 1st pseudo-code snippet), or do we just compute the clipping boxes (the stack array snapshot in 1st pseudo-code snippet) and then compute the final clipping for each elements in parallel when the clipping boxes (position of each push & their bounding boxes) are ready? Sorry about my inaccurate terminology in advance as I didn't work closely with 2D graphics before.
mlang23 5y ago
Monoids are cool. It took me a long time to actually discover monoids during coding. It finally clicked when I realized the QuadBitboard I wrote for a chess move generator is actually a monoid. Empty board is the neutral element, and xor of all 4 bitboards is the operation. https://github.com/mlang/chessIO/blob/master/src/Game/Chess/Internal/QuadBitboard.hs https://github.com/mlang/chessIO/blob/master/src/Game/Chess/...
- bweitzman 5y ago
  What does xoring mean for combining two boards that have pieces in the same position? Is there a use for such an operation?

216 points by harperlee 5y ago

uyt 5y ago

If you test on random parens, won't the nesting depth be fairly shallow? I'm still reading and I am trying to understand what this will do if you have long streaks of pushes with rare pops (but maybe still occasional enough to cause large shuffles in the in-place reduction). What do you do after the stack size is larger than the number of parallel thread?

raphlinus 5y ago
Just testing on random parens gives you an expected stack depth of O(sqrt(N)). I've also (just now) tried biasing the sequence generation with more pushes than pops, and it doesn't substantially affect running time. The case where the stack depth is greater than the partition size is tricky for sure, and this is what I call the "backlink" mechanism. The tl;dr is that it follows the deepest link (furthest from top of stack) that it can, and continues the look-back process, until the slice is complete. You can search for "backlink" in the code - it's actually not a huge amount of logic, though it certainly was subtle to get right.
- dan-robertson 5y ago
  Any guess as to what the distribution will look like in practice? I suppose you started with a list of iid equally likely parens, but I would guess that in practice the distribution D might look more like: () moderately likely (X) where X ~ (roughly) D quite likely X Y where X,Y ~ (roughly) D slightly likely. My prior is that in user interfaces one will typically see a somewhat deep nesting of clips (ie components) with a few primitives to draw at each level. But maybe this is just wrong or most of these clips are axis-aligned rectangles and can be dealt with as the command list is built. Or maybe you do see nesting in practice but not super deep nesting (say window > panel > panel > set of buttons > button > text with each corresponding to several layers of nested clips)
- 082349872349872 5y ago
  Is the distribution normal around that expected stack depth, or does it skew to many shallow stacks but the rare deep stacks are really deep?

StandardFuture 5y ago

Would someone like to ELI5/summate what this is and what it is for?

anchpop 5y ago
The author is working on piet-gpu, a library for efficiently rendering 2D graphics on the GPU, for UIs and font editors and things like that. This is very nontrivial (and in fact most 2D graphics you see today are in large part rendered on the CPU). The goal of piet-gpu is that you just specify the scene graph (blue circle here, red line there, etc) and send it over to the GPU, and the GPU takes care of all the rendering. GPUs are very good at processing data in the shape of arrays. For example, a pixel shader (or "fragment shader") processes a 2D array of pixels on the screen. piet-gpu needs to sometimes process data that has a tree structure, rather than an array structure, to support clipping (for example to show a shape that represents the intersection between a circle and a square). The stack monoid the article talks about is a way of doing tree-like operations in parallel on the GPU, and the author thinks it will end up being useful for being able to process clipping operations entirely on the GPU.
- marai2 5y ago
  You could start a business doing ELI5s of complex topics! Thank you for a wonderful summary!
- StandardFuture 5y ago
  Thanks for the summary! Quick question: wouldn't executing partially-ordered sets of operations in a semi-parallel or fully-parallel way already be an existing research topic in Computer Science? Obviously this project is attempting to find a solution for a singular application and not attempting to find a general algorithm, but still there must be some historical precedent. I would imagine that companies like NVIDIA would have even already contributed to this space? Are there any existing resources on the topic that perhaps you or the OP knows of?
  - mijoharas 5y ago

joe_the_user 5y ago

The ability to compute the stack monoid on slices of the input, then stitch them together later, is essential for processing this in parallel. So what isn't possible is having two threads push/pop to the same conventional stack. So I assume the author is doing something different. So what I guess they're doing is descending down the tree, and splitting off all the operations that can be done in parallel so that you get a bunch of kernels feeding their results into each other with the structure of the tree. It seems like some synchronization is need so one thread waits for the results of another. A monoid, as I vaguely understand them, acts as a kind stored operation so this seems logical. And if you ran out of threads, the monoid would just act as a conventional stack on some of the remaining threads. Of course, none of this says the mechanism to implement this.

lmm 5y ago
> So what isn't possible is having two threads push/pop to the same conventional stack. So I assume the author is doing something different. Indeed; what they're doing is building up a command object that represents a sequence of modifications to a stack. And that's something that you can parallelise, map-reduce style: they've come up with a representation for that command that makes it easy to combine two commands into a bigger command, and a technique for doing that combine in-place without needing extra scratch space. This doesn't need any synchronization between parallel threads - of course the final result is only formed when all the threads finish. (To materialize the final value of the stack you'd have to "run" the final command, but it turns out that's trivial for this command representation - just confirm that the number of pops is zero, and then the push sequence is the final value of the stack).
- joe_the_user 5y ago
  * This doesn't need any synchronization between parallel threads - of course the final result is only formed when all the threads finish* I'm still confused. If one calculates (x+y)*(z+w). You can divide the addition between threads but the multiplication has to happen once these two threads end. If you're talking a "map-reduce" approach, as far as I understand it, the reduce has to happen once the mapping is done. Which would seem to require synchronization also.

gugagore 5y ago

From Wikipedia: > In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. So M = (S, op, id) My go-to example of a monoid is (the set of strings, string concatenation, the empty string). It's my go-to because there's e.g. no `x` such that `concat("blah", x) == ""`. Another example is (integers, +, 0), but it is not my go-to example because it also more than a monoid. I did not find a clear explanation of what the stack monoid is here. Can someone state it, please?

tomstuart 5y ago
An earlier post (https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html) explains it. The elements of the monoid are stack operations represented by pairs `(n, vs)`, where `n` is a number of values to pop off the stack and `vs` is a list of values to push on afterwards. So e.g. `(3, [])` is “pop 3 values”, `(1, ['foo', 'bar'])` is “pop 1 value then push 'foo' and 'bar'”, etc. Two elements are composed by combining their pop counts and push lists to reflect what happens to the stack if you apply the operations sequentially, e.g. the previous two examples compose to `(4, ['foo', 'bar'])`. The identity is `(0, [])`.
- lmm 5y ago
  So this isn't really the stack monoid, this is mutations as a monoid (which is a construction that exists for anything mutable), or the command monoid. The insight is that these mutations have a nice representation as first-class values and you can combine two "stack mutation commands" efficiently.
  - Twisol 5y ago
    > So this isn't really the stack monoid, this is mutations as a monoid (which is a construction that exists for anything mutable) I can see why you'd balk at the name "stack monoid", but the specific commands / actions being modeled (push/pop) are exactly the ones modeling a stack. It's not a purely syntactic construction because a push followed by a pop is evaluated away. The representation as `(pops, pushes)` is the natural conclusion of this line of semantic analysis. > this is mutations as a monoid In general though, yeah, this is the secret sauce. The history of commands on a mutable cell is sufficient to recover the value of the cell at any point in time, and the history of values held by the cell is sufficient to derive a (not necessarily unique) history of commands going between each snapshot. Typically, though, we only remember the "latest" value of the cell, so we lose a lot of information. In a parallel algorithm, multiple "points in time" need to be accessible simultaneously, so you get a lot by moving to a representation where you're not already missing information.

liuliu 5y ago

Interesting in-depth discussion with the parallel parentheses matching solution. Back to the clipping problem though, in each intermediate step (when we still incorporating prefixed results), do we compute clipping for each elements progressively (the result array in 1st pseudo-code snippet), or do we just compute the clipping boxes (the stack array snapshot in 1st pseudo-code snippet) and then compute the final clipping for each elements in parallel when the clipping boxes (position of each push & their bounding boxes) are ready? Sorry about my inaccurate terminology in advance as I didn't work closely with 2D graphics before.

mlang23 5y ago

Monoids are cool. It took me a long time to actually discover monoids during coding. It finally clicked when I realized the QuadBitboard I wrote for a chess move generator is actually a monoid. Empty board is the neutral element, and xor of all 4 bitboards is the operation. https://github.com/mlang/chessIO/blob/master/src/Game/Chess/Internal/QuadBitboard.hs https://github.com/mlang/chessIO/blob/master/src/Game/Chess/...

bweitzman 5y ago
What does xoring mean for combining two boards that have pieces in the same position? Is there a use for such an operation?