8 ms·
Prefix Sum with SIMD
- udbhavs 5y agoThe whole book looks very full of interesting low level techniques. Do high level JIT compilers like the V8 or JVM apply vectorisation or any of the other optimisations mentioned there, or is that level of fine-tuned performance only possible if you code them manually in C++?
- sereja 5y agoAuthor here. I wrote a separate section trying to answer this question: https://en.algorithmica.org/hpc/complexity/languages/ https://en.algorithmica.org/hpc/complexity/languages/ tl;dr: to some extent, but mostly no
- marcos100 5y agoHey author. This looks like a very approachable book given the subject. Still on chapter 2, but really enjoying it. Instant buy for me. Thanks for your effort.
- khoobid_shoma 5y agoI think topics are nicely explained in C and assembly but not C++.
- saagarjha 5y agoMost JITs have basic autovectorization support, but it's generally not that good.
- tralarpa 5y agoPeople claim that the JVM is able to auto-vectorize simple loops: https://stackoverflow.com/questions/59725341/java-auto-vectorization-example https://stackoverflow.com/questions/59725341/java-auto-vecto... That said, I tried the matrix-multiplication example from section 1.2 on different computers and with different jdk version, but I didn't manage to convince the JVM JIT to emit SIMD instructions. No idea whether the loop is too complex for the JIT or whether there is some secret JVM option that I'm not aware of.
- sereja 5y agoIt is not technically legal to use SIMD on most floating-point loops, including the inner product in matrix multiplication, because rounding errors are not commutative. C compilers don't vectorize such loops either unless you pass the -ffast-math flag. I'm sure the JIT compiler of JVM has a similar option. (read the article I linked below, it's all explained there)
- gfd 5y agoI've seen the author advertise his book on codeforces.com blogs before if you want somewhere to reach him: https://codeforces.com/blog/entry/99790 https://codeforces.com/blog/entry/99790 That might be a better intro than a random chapter of the book and contextualizes why you might want to learn SIMD programming (i.e., up to an order of magnitude speed-up vs STL implementations).
- jonstewart 5y agoYes, but his work here on prefix sum is very recent, he just started telling people about it on Twitter this past week (specifically, the improvement due to interleaving).
- deleted 5y ago[deleted]
- fulafel 5y agoIt's interesting that SIMD came to the mainstream 25 years ago and compilers, our apps and PL tech are still quite far from effectively utilizing it outside nonportable manually coded SIMD aware compute kernels in glorified assembler. There are some exceptions like ispc and GPU languages like OpenCL and Futhark (GPU people say "cores" when they mean SIMD lanes!)...
- zozbot234 5y agoLLVM does a pretty good job of vectorizing code these days, and pretty much everything is using it. And making vectorization more effective is one of the most workable avenues for improving compiler tech.
- fulafel 5y agoGiven the constraints llvm frequently does a relatively ok job with the pieces it has to work with, but the results are usually poor in absolute terms vs what manual optimizations would allow. The language semantics of c/c++ don't support the required leeway of optimization transformations (eg optimizing data layout hand in hand with it's access patterns, parallel semantics).
- mandarax8 5y agoAre there any languages you know that do support these kinds of transformations?
- fulafel 5y agoBesides the ones mentioned in the other comment, Halide I think is a good model of the kind of approach needed, but that is somewhat domain-specific. So expressing the problem in a sufficiently abstract form that the compiler has many freedoms in organizing how the computation in concrete terms takes place. The IPSC approach seems solid as well even though it's much less ambitious and doesn't do data layout optimizations. An important nontechnical problem with these is that there is such a long way to travel for a language to reach widespread adoption, needing credible long term sponsorship and commitment from a broad shouldered user community or private organisation, etc.
- JimBlackwood 5y agoThis book is fantastic - it comes at a perfect time too, where I’m getting more work related projects about ‘make slow code fast’. Going to be reading this - and looking forward to any future parts!
- mhkool 5y agoSince the performance for array sizes <L1-size and <L2-size is similar , I would like to see an attempt to improve B. B = L2-size / 2 / sizeof(int) - 16 might produce better results. Note also that _mm_broadcast_ss() is faster on newer processors.
- NohatCoder 5y agoI don't get why the baseline is so slow, a read, a write and an add per clock should all be within the capabilities of a modern processor.
- dragontamer 5y agoBecause a 64-bit read to L1 or L2 cache takes the same amount of time as a 256-bit (or even 512-bit) SIMD read on a modern Intel or AMD processor. On L3 cache or DDR4, coalesced reads/writes are still more beneficial and 256-bit reads SIMD still has benefits over 64-bit reads, though its less dramatic.
- NohatCoder 5y agoIt takes 1 read port for 1 clock. Any AVX2-capable processor has at least 1 read and 1 separate write port, therefore we should get 1 processing cycle per clock, the reported number is only around a third of that.
- deleted 5y ago[deleted]
- dahart 5y agoThe author assumes an average of (slightly over) 2 instructions per iteration, which means the theoretical limit is a half iteration per clock, assuming no cache misses ever. How can you reduce that to 1 processing cycle per clock in a single thread, is there a load-add-store instruction, or a way to get multiple instructions per clock through a single thread?
- NohatCoder 5y agoAll modern high-performance processors do multiple instructions per clock.
- dahart 5y ago