5 ms·
Loop Fission
- kingcharles 5y agoHuh. Programming for 40 years and I'm still learning shit.
- ot 5y agoIt 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.
- hinkley 5y agoI 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.
- legulere 5y agoIf 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)
- DannyBee 5y agoIf you go down this rabbit hole of what to do to loops, you will end up at polyhedral models, which are very neat. They can basically rearrange loops (including splitting) to have optimal locality/communication/parallelism/etc. https://polyhedral.info/ https://polyhedral.info/ has more.
- code_biologist 5y agoI hadn't heard of them before. They are neat. If papers aren't your style here's some videos I've found: What is polyhedral compilation? [about six minutes]: https://www.youtube.com/watch?v=iAF-orse4hE 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 https://www.youtube.com/watch?v=mt6pIpt5Wk0