It is important to note that in all the test cases the data fits comfortably in L1 cache. The author mentions this
> Eventually, the bitset would get so large that doing a single pass would make more sense as it makes better use of cache, but in a BitmapContainer the length is fixed to 1024 elements, so this is immaterial.
but I think it needs to be called out more explicitly.
As soon as the data doesn't fit in L1, the benefits from better pipelining or vectorization will be negligible compared to the cost of loading the data twice.
In a general case, it is safer to split the data into blocks, large enough to amortize the outer loop but small enough to fit in L1 cache, and perform fission within each block.
I suspect that analysis is wrong. You don’t roll up the loop when it hits cache limits, you unroll it again. An outer loop that runs k/n times, and two inner loops running over the same k elements.
If your data gets larger than L1 you can still use loop fission if you are able to do batching, which is exactly the base idea of roaring bitmaps (It works on blocks containing up to 2^16 integers)
8 comments
[ 2.4 ms ] story [ 29.6 ms ] thread> Eventually, the bitset would get so large that doing a single pass would make more sense as it makes better use of cache, but in a BitmapContainer the length is fixed to 1024 elements, so this is immaterial.
but I think it needs to be called out more explicitly.
As soon as the data doesn't fit in L1, the benefits from better pipelining or vectorization will be negligible compared to the cost of loading the data twice.
In a general case, it is safer to split the data into blocks, large enough to amortize the outer loop but small enough to fit in L1 cache, and perform fission within each block.
They can basically rearrange loops (including splitting) to have optimal locality/communication/parallelism/etc.
https://polyhedral.info/ has more.
What is polyhedral compilation? [about six minutes]: https://www.youtube.com/watch?v=iAF-orse4hE
Polyhedral Compilation as a Design Pattern for Compilers - Albert Cohen - PLISS 2019 [about an hour and a half]: https://www.youtube.com/watch?v=mt6pIpt5Wk0