4 ms·

I was able to make a variant of the higher-base version that runs in a single pass, by stopping when one partition fills up and using a different method for the

I was able to make a variant of the higher-base version that runs in a single pass, by stopping when one partition fills up and using a different method for the remaining (asymptotically few) elements. I described the idea, which is based on another effort called MergeShuffle, here: https://mlochbaum.github.io/BQN/implementation/primitive/random.html#shuffling https://mlochbaum.github.io/BQN/implementation/primitive/ran... And it is better when N gets large. My implementation set the cutoff at 2^19 elements, although the effect isn't too big for a few more powers of two. Here's the main radix loop: https://github.com/dzaima/CBQN/blob/v0.7.0/src/builtins/sysfn.c#L476-L486 https://github.com/dzaima/CBQN/blob/v0.7.0/src/builtins/sysf...

orlp 2y ago
I found another in-place approach which also does a higher-base version described here: https://arxiv.org/pdf/2302.03317 https://arxiv.org/pdf/2302.03317, with an open source implementation: https://crates.io/crates/rip_shuffle https://crates.io/crates/rip_shuffle. Might want to compare it with your version.
- mlochbaum 2y ago
  Performance-oriented library with no benchmarking instructions, fun. I get 850ms to shuffle 32-bit integers up to 1e8 with this library versus 400ms in BQN (•rand.Deal•_timed 1e8). However, BQN also has a large advantage at smaller sizes, such as 425us versus 120us for 1e5 elements, so a lot of this may be the random number generator. I haven't figured out how to get PCG working yet. BQN uses wyrand which is faster but I now know has quality issues (can't even generate every possible output; I need to update the page I linked...). It's substantially the same algorithm so any differences would just be down to implementation details. Other than multi-threading which BQN doesn't do. The usage is also a little different as BQN generates shuffled integers directly; generating the integers is 100ms of the 850ms for rip_shuffle but I'm not sure whether it makes sense to subtract that or not.
  - mlochbaum 2y ago
    Not quite the same, rip_shuffle does have some contortions to be able to run in-place (I'm still scratching my head about who's running these sorts of high-performance algorithms with no auxiliary memory available), so if those cost anything they could contribute to the difference.

orlp 2y ago

I found another in-place approach which also does a higher-base version described here: https://arxiv.org/pdf/2302.03317 https://arxiv.org/pdf/2302.03317, with an open source implementation: https://crates.io/crates/rip_shuffle https://crates.io/crates/rip_shuffle. Might want to compare it with your version.

mlochbaum 2y ago
Performance-oriented library with no benchmarking instructions, fun. I get 850ms to shuffle 32-bit integers up to 1e8 with this library versus 400ms in BQN (•rand.Deal•_timed 1e8). However, BQN also has a large advantage at smaller sizes, such as 425us versus 120us for 1e5 elements, so a lot of this may be the random number generator. I haven't figured out how to get PCG working yet. BQN uses wyrand which is faster but I now know has quality issues (can't even generate every possible output; I need to update the page I linked...). It's substantially the same algorithm so any differences would just be down to implementation details. Other than multi-threading which BQN doesn't do. The usage is also a little different as BQN generates shuffled integers directly; generating the integers is 100ms of the 850ms for rip_shuffle but I'm not sure whether it makes sense to subtract that or not.
- mlochbaum 2y ago
  Not quite the same, rip_shuffle does have some contortions to be able to run in-place (I'm still scratching my head about who's running these sorts of high-performance algorithms with no auxiliary memory available), so if those cost anything they could contribute to the difference.