7 ms·
C is not suited to SIMD (2019)
- PaulHoule 2y agoSo are those functional languages. The really cool SIMD code I see people writing now is by people like Lemire using the latest extensions who do clever things like decoding UTF-8 which I think will always take assembly language to express unless you are getting an SMT solver to write it for you.
- dagelf 2y agoLink?
- mananaysiempre 2y agohttps://simdjson.org/publications/ https://simdjson.org/publications/ https://simdutf.github.io/simdutf/ https://simdutf.github.io/simdutf/ https://lemire.me/blog/ https://lemire.me/blog/ https://branchfree.org/ https://branchfree.org/ http://0x80.pl/ http://0x80.pl/
- throwawaymaths 2y agonot even an SMT solver, that's not what they are for.
- 1propionyl 2y agoNo? SMT solvers underpin the majority of program synthesis research tools. When you get down to it, you're optimizing (searching) for some program that maximizes/minimizes some objective function with terms for error relative to specification/examples and size of synthesized program, while applying some form of cleverness to pruning the search space. This is absolutely within the wheelhouse of SMT solvers, and something that they are used for. SMT doesn't have to be used, but for implementation it enables iterating on the concept more quickly (see also, more broadly: prototyping in Prolog), and in other cases it's simply the most effective tool for the job. So, it tends to get a lot of play.
- throwawaymaths 2y agoIf SMT solvers were all you needed, then for example, LLVM wouldn't need a polyhedral optimizer. And a polyhedral optimizer is a subset of the sorts of things you will need for doing the sort of things you're asking to do automatically.
- dzaima 2y agoSMT solvers might not be feasible for large-scale things, but they can certainly be used to find a sequence of a couple instructions doing a specific thing if you give enough computational resources, and that's what OP was talking about. (whether it'll complete in a reasonable time (i.e. less than like an hour) for something with more than like 4 instructions is a separate question; but 4 instructions is enough for some fancy stuff). Like, just playing around not particularly seriously, I've gotten SMT to spit out [1] for narrowing & packing four int32x8 vectors into one int8x32 vector, assuming no wrapping necessary (4 minutes via Bitwuzla), among other things; nothing one couldn't figure out by doing a bit of thinking, but it does work! And could conceivably get more feasible for larger tasks over time. [1]: https://dzaima.github.io/paste/#0KytITM4uLi5PUqjMzTXRAZEGYNKYqwxZyhQsaAgmjVClzHQQek2BUqlFuSl6mUUgrrmOgkGFAQSYQ2ljKG0KpQ2htIkBKjCD0kYKNkY6ZjoGOiY6hjqmOsY65nZgq8wA#asm https://dzaima.github.io/paste/#0KytITM4uLi5PUqjMzTXRAZEGYNK...
- kibwen 2y ago> So are those functional languages. The author is suggesting array languages as the solution, which are a separate category from functional languages.
- janwas 2y agoLemire and collaborators often write in C++ intrinsics, or thin platform-specific wrappers on top of them. I count ~8 different implementations [1], which demonstrates considerable commitment :) Personally, I prefer to write once with portable intrinsics. https://github.com/simdutf/simdutf/tree/1d5b5cd2b60850954df59caa8691ce10ebf04cfe/src https://github.com/simdutf/simdutf/tree/1d5b5cd2b60850954df5...
- mananaysiempre 2y agoI don’t think that really works beyond 128 bits. AVX/AVX2 with its weird tiered 2×128-bit structure occasionally forces you down some really awkward paths. AVX-512 with its masks is powerful and quite elegant, but the idioms it enables don’t really translate to other ISAs. And even in 128-bit land, the difference between good code for SSE and NEON can be quite significant, all because of a single instruction (PMOVMSKB) the latter lacks[1]. Portable instructions and “scalable” length-agnostic vectors are usually fine for straightforward mathy (type-1[2]) SIMD code. But real SIMD trickery, the one that starts as soon as you take your variable byte shuffle out of the stable, is rarely so kind. [1] https://branchfree.org/2019/04/01/fitting-my-head-through-the-arm-holes-or-two-sequences-to-substitute-for-the-missing-pmovmskb-instruction-on-arm-neon/ https://branchfree.org/2019/04/01/fitting-my-head-through-th... [2] https://branchfree.org/2024/06/09/a-draft-taxonomy-of-simd-usage/ https://branchfree.org/2024/06/09/a-draft-taxonomy-of-simd-u...
- janwas 2y agoValid points, but I am doing exactly that full-time for the past years :) Including compression and quicksort, which are nontrivial uses of SIMD. The 2x128 is handled by adopting AVX2 semantics for our InterleaveLower/Upper op, and when we want the extra fixup, there is also InterleaveWholeLower. I agree AVX-512 is awesome, it's my favorite target. Some of its useful ops (compress[store]) are fine to emulate. What idioms did you have in mind that don't translate? Spot on about PMOVMSKB, that's a pain point. We provide several ops to replace it with more relaxed semantics that are easier to emulate on other platforms, for example AllTrue, CountTrue, AllFalse. (I think DanilaK's NEON VSHRN trick is faster than the one from your first link?)
- AnimalMuppet 2y agoThe argument seems to be that C isn't suited to SIMD because some functions (exp, for instance) are not. But it then talks about how exp is implemented in hardware, in a way that forces it to be a non-SIMD calculation. That's not a C issue, that's a CPU issue. No language can save you there (unless it uses a software-only function for exp). Is this article really confused, or did I misunderstand it? The thing that makes C/C++ a good language for SIMD is how easily it lets you control memory alignment.
- high_na_euv 2y agoEven high level languages like c# allow you to express such a thing https://stackoverflow.com/questions/73269625/create-memory-aligned-array-in-c-sharp https://stackoverflow.com/questions/73269625/create-memory-a... Also structlayout and fieldoffset
- leecarraher 2y agoi think the article is confused. i write quite a bit of SIMD code for HPC and c is my goto for low level computing because of the low level memory allocation in c. In fact that tends to be the lion share of work to implement simd operations where memory isn't the bottleneck. if only it were as simple as calling vfmadd132ps on two datatypes.
- woooooo 2y agoNot in the article, but I've read that the way C does pointers, a single address with length implicit, makes it hard for compilers to assert that 2 arrays don't overlap/alias and this is an obstacle for generating SIMD instructions.
- 1718627440 2y agoNot really. Pointers from different allocations are guaranteed to never alias. If they do, it is UB.
- AnimalMuppet 2y agoRight, but the compiler in general has no way to know that pointers are from different allocations - especially several function calls away from the allocations, with some pointer arithmetic in between.
- notorandit 2y agoC has been invented when CPUs, those few available, were just single cored and single threaded. Wanna SMP? Use multi-thread libreries. Wanna SIMD/MIMD? Use (inline) assembler functions. Or design your own language.
- LiamPowell 2y agoThat's missing the point of the article, but it's also not true, at least not at the time of C89. This can be easily verified by a Google search. As an aside, Ada also had multi-threading support before C89 was released, but this article is about SIMD, not multi-threading.
- johnnyjeans 2y agoc89 is 19 years into c's life
- LiamPowell 2y agoYes, but before standardisation there were many implementations all doing different things based on a book with no particularly formal specifications, so picking 1989 makes more sense than 1970 in my opinion. Multi-threading also existed in 1970 but wasn't as widespread.
- pjmlp 2y agoYou had plenty of places outside Bell Labs doing concurrency stuff, Concurrent Pascal and Solo OS is one example among many.
- dragontamer 2y agoFortran is older but it's array manipulation maps naturally to SIMD.
- TinkersW 2y agoThis reads like jibberish. C functions can't be vectorized? WTF are you talking about? You can certainly pass vector registers to functions. Exp can also be vectorized, AVX512 even includes specific instructions to make it easier.( there is no direct exp instruction on most hardware,it is generally a sequence of instructions)
- deleted 2y ago[deleted]
- mlochbaum 2y agoSeveral comments seem confused about this point: the article is not about manual SIMD, which of course C is perfectly capable of with intrinsics. It's discussing problems in compiling architecture-independent code to SIMD instructions, which in practice C compilers very often fail to do (so, exp having scalar hardware support may force other arithmetic not to be vectorized). An alternative mentioned is array programming, where operations are run one at a time on all the data; these languages serve as a proof of concept that useful programs can be run in a way that uses SIMD nearly all the time it's applicable, but at the cost of having to write every intermediate result to memory. So the hope is that "more fluent methods for compilation" can generate SIMD code without losing the advantages of scalar compilation. As an array implementer I've thought about the issue a lot and have been meaning to write a full page on it. For now I have some comments at https://mlochbaum.github.io/BQN/implementation/versusc.html#fusion-versus-fission https://mlochbaum.github.io/BQN/implementation/versusc.html#... and the last paragraph of https://mlochbaum.github.io/BQN/implementation/compile/intro.html#and-which-is-better https://mlochbaum.github.io/BQN/implementation/compile/intro....
- deleted 2y ago[deleted]
- mlochbaum 2y agoGot the introduction written at https://mlochbaum.github.io/BQN/implementation/compile/fusion.html https://mlochbaum.github.io/BQN/implementation/compile/fusio....
- brundolf 2y agoThank you. The title is confusing
- mlochbaum 2y agoFinding it increasingly funny how many people have come out of the woodworks to "defend" C by offering this or that method of explicit vectorization. What an indictment! C programmers can no longer even conceive of a language that works from a description of what should be done and not which instructions should be used!
- 2y ago
- jiehong 2y agoIt seems that Zig is well suited for writing SIMD [0]. If only GPU makers could standardise an extended ISA like AVX on CPU, and we could all run SIMD or SIMT code without needing any librairies, but our compilers. [0]: https://zig.guide/language-basics/vectors/ https://zig.guide/language-basics/vectors/
- dundarious 2y agoI like zig, but no, what it provides pales in comparison to what intrinsics offer.
- deleted 2y ago[deleted]
- camel-cdr 2y agoThis depends entirely on compiler support. Intels ICX compiler can easily vectorize a sigmoid loop, by calling SVMLs vectorized expf function: https://godbolt.org/z/no6zhYGK6 https://godbolt.org/z/no6zhYGK6 If you implement a scalar expf in a vectorizer friendly way, and it's visible to the compiler, then it could also be vectorized: https://godbolt.org/z/zxTn8hbEe https://godbolt.org/z/zxTn8hbEe
- dzaima 2y agogcc and clang are also capable of it, given certain compiler flags: https://godbolt.org/z/z766hc64n https://godbolt.org/z/z766hc64n
- camel-cdr 2y agoThanks, I didn't know about this. Interesting that it seems to require fast-math.
- ComputerGuru 2y agoThat means it’ll never be used. ffast-math is verboten in most serious codebases.
- dzaima 2y agoSeems "-fno-math-errno" is enough for clang. gcc needs a whole "-fno-math-errno -funsafe-math-optimizations -ffinite-math-only".
- Vosporos 2y agoWoo, very happy to see more posts by McHale these days!
- Const-me 2y agoI would rather conclude that automatic vectorizers are still less than ideal, despite SIMD instructions have been widely available in commodity processors for 25 years now. The language is actually great with SIMD, you just have to do it yourself with intrinsics, or use libraries. BTW, here’s a library which implements 4-wide vectorized exponent functions for FP32 precision on top of SSE, AVX and NEON SIMD intrinsics (MIT license): https://github.com/microsoft/DirectXMath/blob/oct2024/Inc/DirectXMathVector.inl#L3252 https://github.com/microsoft/DirectXMath/blob/oct2024/Inc/Di...
- nine_k 2y agoWhy does FORTRAN, which is older than C, has no trouble with auto-vectorization? Mostly because of a very different memory model, of course. Arrays are first-class things, not hacks on top of pointers, and can't alias each other.
- MisterTea 2y ago> Arrays are first-class things, not hacks on top of pointers, and can't alias each other. "Hacks" feels like the wrong term to use here. Comparing managed objects surrounded by runtime to memory isn't a fair comparison.
- nine_k 2y agoThere's no language-level difference between int[] and int* in C. Indexing is just pointer arithmetics. No support for (non-jagged) multidimensional arrays either. A proper array would at least know its length. It does not require a lot of runtime to do, and most C code require libc anyway for basic stuff like malloc().
- jjmarr 2y agoThis isn't true. int[] decays into an int* but is a different type. An array member of a struct will have its data allocated contiguously with other struct members (subject to compiler padding). An int* would point outside the struct. This is possible even with variable length arrays. Specifically, you can declare the final member of a struct as an int[] which makes it a "flexible array member". Then you have to malloc the struct to be the sizeof the struct + whatever size you want the array to be. https://en.wikipedia.org/wiki/Flexible_array_member https://en.wikipedia.org/wiki/Flexible_array_member This is used in struct sockaddr for generic APIs where the actual struct can be of different sizes. https://lwn.net/Articles/997094/ https://lwn.net/Articles/997094/ This is rather pedantic but the memory model for arrays is important here. If you're iterating over multiple struct members that are arrays, the fact the arrays are stored contiguously in memory is going to matter to SIMD.
- svilen_dobrev 2y agoreminds me of this old article.. ~2009, Sun/MIT - "The Future is Parallel" .. and "sequential decomposition and usual math are wrong horse.." https://ocw.mit.edu/courses/6-945-adventures-in-advanced-symbolic-programming-spring-2009/resources/mit6_945s09_read02_parallel/ https://ocw.mit.edu/courses/6-945-adventures-in-advanced-sym...
- npalli 2y agoC++ does OK. Google's highway [1] Microsoft DirectXMath [2] [1] https://github.com/google/highway https://github.com/google/highway [2] https://github.com/microsoft/DirectXMath https://github.com/microsoft/DirectXMath
- vmchale 2y agoFrom highway: > Does what you expect: Highway is a C++ library with carefully-chosen functions that map well to CPU instructions without extensive compiler transformations. The resulting code is more predictable and robust to code changes/compiler updates than autovectorization. So C compilers are not a good place to start if one wants to write a compiler for an array language (which naturally expresses SIMD calculations). Which is what I point out in the last paragraph of the blog post: > To some extent this percolates compilers textbooks. Array languages naturally express SIMD calculations; perhaps there are more fluent methods for compilation (and better data structures for export à la object files).
- pjmlp 2y agoIt is more like, ISO C++ with compiler extensions does ok.
- dvorack101 2y agoNot my code, but illustrates how SIMD works. https://github.com/dezashibi-c/a-simd_in_c https://github.com/dezashibi-c/a-simd_in_c Copy rights go to Navid Dezashibi.
- commandlinefan 2y agoThis seems more of a generalization of Richard Steven's observation: "Modularity is the enemy of performance" If you want optimal performance, you have to collapse the layers. Look at Deepseek, for example.
- vkaku 2y agoI also think that vectorizers and compilers can detect parallel memory adds/moves/subs and without that, many do not take time to provide adequate hints to the compiler about it. Some people have vectorized successfully with C, even with all the hacks/pointers/union/opaque business. It requires careful programming, for sure. The ffmpeg cases are super good examples of how compiler misses happen, and how to optimize for full throughput in those cases. Worth a look for all compiler engineers.
- exitcode0000 2y agoOf course C easily allows you to directly write SIMD routines via intrinsic instructions or inline assembly: ``` generic type T is private; Aligned : Bool := True; function Inverse_Sqrt_T (V : T) return T; function Inverse_Sqrt_T (V : T) return T is Result : aliased T; THREE : constant Real := 3.0; NEGATIVE_HALF : constant Real := -0.5; VMOVPS : constant String := (if Aligned then "vmovaps" else "vmovups"); begin Asm (Clobber => "xmm0, xmm1, xmm2, xmm3, memory", Inputs => (Ptr'Asm_Input ("r", Result'Address), Ptr'Asm_Input ("r", V'Address), Ptr'Asm_Input ("r", THREE'Address), Ptr'Asm_Input ("r", NEGATIVE_HALF'Address)), Template => VMOVPS & " (%1), %%xmm0 " & E & -- xmm0 ← V " vrsqrtps %%xmm0, %%xmm1 " & E & -- xmm1 ← Reciprocal sqrt of xmm0 " vmulps %%xmm1, %%xmm1, %%xmm2 " & E & -- xmm2 ← xmm1 \* xmm1 " vbroadcastss (%2), %%xmm3 " & E & -- xmm3 ← NEGATIVE_HALF " vfmsub231ps %%xmm2, %%xmm0, %%xmm3 " & E & -- xmm3 ← (V - xmm2) \* NEGATIVE_HALF " vbroadcastss (%3), %%xmm0 " & E & -- xmm0 ← THREE " vmulps %%xmm0, %%xmm1, %%xmm0 " & E & -- xmm0 ← THREE \* xmm1 " vmulps %%xmm3, %%xmm0, %%xmm0 " & E & -- xmm0 ← xmm3 \* xmm0 VMOVPS & " %%xmm0, (%0) "); -- Result ← xmm0 return Result; end; function Inverse_Sqrt is new Inverse_Sqrt_T (Vector_2D, Aligned => False); function Inverse_Sqrt is new Inverse_Sqrt_T (Vector_3D, Aligned => False); function Inverse_Sqrt is new Inverse_Sqrt_T (Vector_4D); ``` ```C vector_3d vector_inverse_sqrt(const vector_3d\* v) { ... vector_4d vector_inverse_sqrt(const vector_4d\* v) { vector_4d out; static const float THREE = 3.0f; // 0x40400000 static const float NEGATIVE_HALF = -0.5f; // 0xbf000000 __asm__ ( // Load the input vector into xmm0 "vmovaps (%1), %%xmm0\n\t" "vrsqrtps %%xmm0, %%xmm1\n\t" "vmulps %%xmm1, %%xmm1, %%xmm2\n\t" "vbroadcastss (%2), %%xmm3\n\t" "vfmsub231ps %%xmm2, %%xmm0, %%xmm3\n\t" "vbroadcastss (%3), %%xmm0\n\t" "vmulps %%xmm0, %%xmm1, %%xmm0\n\t" "vmulps %%xmm3, %%xmm0, %%xmm0\n\t" "vmovups %%xmm0, (%0)\n\t" // Output operand : : "r" (&out), "r" (v), "r" (&THREE), "r" (&NEGATIVE_HALF) // Input operands : "xmm0", "xmm1", "xmm2", "memory" // Clobbered registers ); return out; } ```
- musicale 2y agoThat's why CUDA never went anywhere. /s ;-) (Oh, that's SIMT. Carry on then.)
- musicale 2y agohttps://docs.nvidia.com/cuda/cuda-math-api/cuda_math_api/group__CUDA__MATH__INTRINSIC__SIMD.html https://docs.nvidia.com/cuda/cuda-math-api/cuda_math_api/gro...