Why BQN Wins
3 points by veqq
3 points by veqq
All BQN solutions outperformed everything else in this perf wars video, this file explains the optimizations BQN has which led it there.
The report opens with saying that because CBQN represents arrays of booleans as bit-packed arrays, whereas in C++ they use std::string, but why don't they use std::vector<bool> which can be implemented as a bit-packed array?
This post reeks of AI writing and can't even seem to get the basics right, which is disappointing because this kind of analysis could be really interesting otherwise.
I had a similar feeling reading through it. It’s really not a comprehensive deep dive as it proclaims, it’s doesn’t go beyond what’s written in the BQN website on performance.
You can implement the bit-vector solution in C with barely any changes to the C count + construct byte-vector solution. Instead of replicating k initial 1-bytes, you replicate k/8 -1-bytes. Similarly for the (n-k)/8 final 0-bytes. You also need a transition byte derived from k%8. The byte replication via memset is already hand-vectorized by libc and the count loop is auto-vectorized by the compiler.