4 ms·

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 str

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

by uyt 5y ago

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?