7 ms·
Own Constant Folder in C/C++
- fwsgonzo 2y agoVery interesting, and that constant folding trick is handy!
- smitty1e 2y agoI was going to label this a fine example of yak shaving. Usually when I'm working this hard against the tool, I've missed something, though the author here sounds expert.
- DrBazza 2y agoThis is the sort of thing we do in HFT to get single instruction calls and save nanos in places that get called many many thousands of times a second.
- smitty1e 2y agoI mean, at some point, why not just write a custom compiler?
- trelane 2y agoIf you care that much, you use intrinsics, asm in the C file, or asm to create an object you call into. Most of the code doesn't need nearly that level of optimization, so you write it in a higher level language. Making your own compiler is a lot of work compared to just doing what I've outlined above. So you don't. I's not worth it, and you'd still end up back where you are.
- TillE 2y agoWriting assembly really isn't that scary, especially in small doses for performance-critical code. That was a very common practice in the 80s/90s, though it's faded as compiler optimizations have improved.
- feverzsj 2y agoclang has __builtin_elementwise_sqrt, which meets all your requirements.
- josephg 2y agoI just tried it on godbolt. __builtin_elementwise_sqrt emits the same terrible asm as _mm_sqrt_ps when -ffast-math is enabled: https://godbolt.org/z/34z81GEsG https://godbolt.org/z/34z81GEsG
- btdmaster 2y agoFortunately gcc does not miscompile like this: https://godbolt.org/z/PaeaohqGz https://godbolt.org/z/PaeaohqGz
- noitpmeder 2y agoThis seems like a great example of why people don't like C/C++, and probably a good example of why some people _do_ like it. How is a non-expert in the language supposed to learn tricks/... things like this? I'm asking as a C++ developer of 6+ years in high performance settings, most of this article is esoteric to me.
- joosters 2y agoIs this really C++ specific though? It seems like the optimisations are happening on a lower level, and so would 'infect' other languages too. Whatever the language, at some point in performance tweaking you will end up having to look at the assembly produced by your compiler, and discovering all kinds of surprises.
- tialaramex 2y agoLLVM isn't perfect, but the problem here is that there's a C++ compiler flag (-ffast-math) which says OK, disregard how arithmetic actually works, we're going to promise across the entire codebase that we don't actually care and that's fine. This is nonsense, but it's really common, distressingly common, for C and C++ programmers to use this sort of inappropriate global modelling. It's something which cannot scale, it works OK for one man projects, "Oh, I use the Special Goose Mode to make routine A better, so even though normal Elephants can't Teleport I need to remember that in Special Goose Mode the Elephants in routine B might Teleport". In practice you'll screw this up, but it feels like you'll get it right often enough to be valuable. In a large project where we're doing software engineering this is complete nonsense, now Jenny, the newest member of the team working on routine A, will see that obviously Special Goose Mode is a great idea, and turn it on, whereupon the entirely different team handling routine B find that their fucking Elephants can now Teleport. WTF. The need to never do this is why I was glad to see Rust stabilize (e.g) u32::unchecked_add fairly recently. This (unsafe obviously) method says no, I don't want checked arithmetic, or wrapping, or saturating, I want you to assume this cannot overflow. I am formally promising that this addition is never going to overflow, in order to squeeze out the last drops of performance. Notice that's not a global flag. I can write let a = unsafe { b.unchecked_add(c) }; in just one place in a 50MLOC system, and for just that one place the compiler can go absolutely wild optimising for the promise that overflows never happen - and yet right next door, even on the next line, I can write let x = y + z; and that still gets the kid gloves, if it overflows nothing catches on fire. That's how granular this needs to be to be useful, unlike C++ -ffast-math.
- pxmpxm 2y agoHuh, why would reciprocal sqrt and fpmul be faster than regular sqrt?
- pkhuong 2y agoIt's less accurate.
- GrantMoyer 2y agoIntel's explanation (at section 15.12): https://cdrdv2.intel.com/v1/dl/getContent/814198?fileName=248966-Optimization-Reference-Manual-V1-050.pdf#G16.92586 https://cdrdv2.intel.com/v1/dl/getContent/814198?fileName=24... > In Intel microarchitectures prior to Skylake, the SSE divide and square root instructions DIVPS and SQRTPS have a latency of 14 cycles (or the neighborhood) and they are not pipelined. This means that the throughput of these instructions is one in every fourteen cycles. The 256-bit Intel AVX instructions VDIVPS and VSQRTPS execute with 128-bit data path and have a latency of twenty-eight cycles and they are not pipelined as well. > In microarchitectures that provide DIVPS/SQRTPS with high latency and low throughput, it is possible to speed up single-precision divide and square root calculations using the (V)RSQRTPS and (V)RCPPS instructions. For example, with 128-bit RCPPS/RSQRTPS at five-cycle latency and one-cycle throughput or with 256-bit implementation of these instructions at seven-cycle latency and two-cycle throughput, a single Newton-Raphson iteration or Taylor approximation can achieve almost the same precision as the (V)DIVPS and (V)SQRTPS instructions (emphasis mine)
- dooglius 2y agoThat's a different case where one is trying to calculate rsqrt(x) from 1/sqrt(x) whereas the article involves computing sqrt(x) from x*rsqrt(x) and in this case you don't need the divps instruction for sqrt but do need an additional mul instruction for the rsqrt case.
- GrantMoyer 2y agoI think you've misread the section: > it is possible to speed up single-precision divide and square root calculations using the (V)RSQRTPS and (V)RCPPS instructions
- eqvinox 2y agoPet peeve: this isn't "your own constant folder in C/C++"… it's "your own enabling constant folding in C/C++"… With "own constant folder" I expected a GCC/clang plugin that does tree/control flow analysis and some fancy logic in order to determine when, where and how to constant fold…
- GrantMoyer 2y agoI think the real problem is "really really wanted the sqrtps to be used in some code they were writing" is at odds with -ffast-math. Clang transforms sqrtps(x) to x * rsqrtps(x) when -ffast-math is set because it's often faster (See [1] section 15.12). It isn't faster for some architectures, but if you tell clang what architecture you're targeting (with -mtune), it appears to make the right choice for the architecture[2]. [1]: https://cdrdv2.intel.com/v1/dl/getContent/814198?fileName=248966-Optimization-Reference-Manual-V1-050.pdf#G16.92586 https://cdrdv2.intel.com/v1/dl/getContent/814198?fileName=24... [2]: https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:(endColumn:26,endLineNumber:3,positionColumn:26,positionLineNumber:3,selectionStartColumn:26,selectionStartLineNumber:3,startColumn:26,startLineNumber:3),source:'%23include+%3Cxmmintrin.h%3E%0A%0A__attribute__((noinline))%0A__m128+test(const+__m128+vec)%0A%7B%0A++++return+_mm_sqrt_ps(vec)%3B%0A%7D%0A%0A__m128+call_test()%0A%7B%0A++++return+test(_mm_setr_ps(1.f,+2.f,+3.f,+4.f))%3B%0A%7D'),l:'5',n:'1',o:'C%2B%2B+source+%231',t:'0')),k:38.69451697127938,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((g:!((h:compiler,i:(compiler:clang1810,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1',verboseDemangling:'0'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!(),options:'-O3+-ffast-math+-mtune%3Dskylake',overrides:!(),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+clang+18.1.0+(Editor+%231)',t:'0')),k:35.34004163775156,l:'4',m:50,n:'0',o:'',s:0,t:'0'),(g:!((h:output,i:(editorid:1,fontScale:14,fontUsePx:'0',j:1,wrap:'1'),l:'5',n:'0',o:'Output+of+x86-64+clang+18.1.0+(Compiler+%231)',t:'0')),header:(),l:'4',m:50,n:'0',o:'',s:0,t:'0')),k:61.30548302872063,l:'3',n:'0',o:'',t:'0')),l:'2',n:'0',o:'',t:'0')),version:4 https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename...
- white_beach 2y agosomewhat related to this: https://godbolt.org/z/1543TYszP https://godbolt.org/z/1543TYszP (intel c++ compiler)
- deleted 2y ago[deleted]
- kookamamie 2y agoIt's just so fiddly - can't trust the compiler, not a good sign for a language or its implementation.
- g15jv2dp 2y agoDo you think other compilers for other languages don't perform optimizations like this?
- adgjlsfhk1 2y agoJulia does all of this correctly (although there are a few 0 cost redundant move instructions presumably for ABI reasons). julia> f(x) = @fastmath sqrt.(x) julia > @code_native debuginfo=:none f.(Tuple(rand(Float32, 8))) vsqrtps ymm0, ymmword ptr [rsi] mov rbp, rsp mov rax, rdi vmovups ymmword ptr [rdi], ymm0 pop rbp vzeroupper ret julia> g() = f((1f0, 2f0, 3f0, 4f0)) julia> @code_native debuginfo=:none g() .LCPI0_0: .long 0x3f800000 # float 1 .long 0x3fb504f3 # float 1.41421354 .long 0x3fddb3d7 # float 1.73205078 .long 0x40000000 # float 2 .text .globl julia_g_600 .p2align 4, 0x90 .type julia_g_600,@function julia_g_600: # @julia_g_600 # %bb.0: # %top push rbp movabs rcx, offset .LCPI0_0 mov rbp, rsp mov rax, rdi vmovaps xmm0, xmmword ptr [rcx] vmovups xmmword ptr [rdi], xmm0 pop rbp ret
- g15jv2dp 2y ago...so does LLVM, unless you specifically instruct it to do otherwise with -ffast-math. Don't be fooled by the name of this flag, if it were possible to just do math faster without compromising anything, it wouldn't be a flag, it would be the default. It seems that Julia has a flag with the same name but a different behavior. Okay? What's your point exactly?
- chongli 2y agoBut in this case, -ffast-math actually results in slower math, so the flag is badly named. Naming things is important (and hard). The naive expectation of a flag named -ffast-math is that the math should never be slower, sometimes be faster, and potentially less accurate and/or error prone. The fact that it can also be sometimes slower means the flag really should be named -fdifferent-math or (uncharitably) -funreliable-math.
- edelsohn 2y ago__builtin_constant_p(vec) is not inquiring if the contents of vec is constant. The compilers are not being fickle. The statement is not performing the question that the developer intended.
- dooglius 2y agoI have not found __builtin_constant_p to be very reliable when I want to fold multiple times. Is there any way to do this trick better using c++ constexpr I wonder?
- ComputerGuru 2y ago> but I think the LLVM folks have purposefully tried to match what GCC would do. I never got that impression in my perusal of LLVM bug reports and patches. I wonder if there is an open issue for this specific case.
- pclmulqdq 2y agoAnother option is to use "-march" to set your target architecture to something post-skylake/Zen 2. That should emit the right instruction. The square root and div instructions used to be a lot slower than they are now.
- ComputerGuru 2y agoThis reminds me of an issue that I ran into with rust [0] when I was trying to optimize some machine learning code. Rust's über-strict type-safe math operations have you use matching types to get the euclidean non-negative remainder of x mod y. When you have a float-point x value but an integral y value, the operation can be performed much more cheaply than when y is also a floating point value. The problem is that you end up promoting y from an integer to an f64 and get a much slower operation. I ended up writing my own `rem_i64(self: &f64, divisor: i64) -> f64` routine that was some ~35x faster (a huge win when crunching massive arrays), but as there are range limitations (since f64::MAX > i64::MAX) you can't naively replace all call sites based on the type signatures. However, with some support from the compiler it would be completely doable anytime the compiler is able to infer an upper/lower bound on the f64 dividend, when the result of the operation is coerced to an integer afterwards, or when the dividend is a constant value that doesn't exceed that range. So now I copy that function around from ML project to ML project, because what else can I do? (A “workaround” was to use a slower-but-still-faster `rem_i128(self: &f64, divisor: i128) -> f64` to raise the functional limits of the operation, but you're never going to match the range of a 64-bit floating point value until you use 512-bit integral math!) [0]: https://github.com/rust-lang/rust/issues/83973 https://github.com/rust-lang/rust/issues/83973 Godbolt link: https://godbolt.org/z/EqrEqExnc https://godbolt.org/z/EqrEqExnc
- toast0 2y ago> So now I copy that function around from ML project to ML project, because what else can I do? Aren't you supposed to make a crate? Which is copying with more steps, but might make your life easier (or harder).
- ComputerGuru 2y agoI knew someone would pipe in with that suggestion as I was writing that comment! Yes, I suppose that would be the canonical way to go. But it's just one function; four lines! I'm getting isEven() vibes!
- pryelluw 2y ago
- SAI_Peregrinus 2y ago> if you happened to use -ffast-math That option is terribly named. It should be -fincorrect_math_that_might_sometimes_be_faster.
- omoikane 2y agoOfftopic, but the original title is "Your Own Constant Folder in C/C++". I am guessing Hacker News cut out the "your" for some reason, but at first glance I thought it was some kind of read-only directory implemented in C/C++. It's like a truncated garden path sentence. https://en.wikipedia.org/wiki/Garden-path_sentence https://en.wikipedia.org/wiki/Garden-path_sentence
- mgaunard 2y agoThe real fix is to not use -ffast-math. It breaks all sorts of things by design. If you really want to relax the correctness of your code to get some potential speedup, either do the optimizations yourself instead of letting the compiler do them, or locally enable fast-math equivalents. As for the is constant expression GCC extensions, that stuff is natively available in standard C++ nowadays.
- Lockal 2y agoFor C++ this goes to the question https://stackoverflow.com/questions/8936549/constexpr-overloading/22062918 https://stackoverflow.com/questions/8936549/constexpr-overlo... Back in the days the answer was `__builtin_constant_p`. But with C++20 it is possible to use std::is_constant_evaluated, or `if consteval` with C++23. But this is for scenario when you still want to keep high quality of code (maybe when you write multiprecision math library; not when you hack around compiler flag), which inline assembly violates for many reasons: 1) major issue: instead of dealing with `-ffast-math` with inline asm, just remove `-ffast-math` 2) randomly slapped inline asm inside normal fp32 computations breaks autovectorization 3) randomly slapped inline asm in example uses non-vex encoding, you will likely to forget to call vzeroupper on transition. Or in general, this limits code to x86 (forget about x86-64/arm) 4) provided example (best_always_inline) does not work in GCC as expected
- hansvm 2y agoForced constant folding is something I use on occasion in Zig. To declare that a computation needs to happen at compile-time, just prefix it with `comptime`. Compile-time execution emulates the target architecture, which has pros and cons. The most notable con is that inline assembly isn't supported (yet?). The complete solution to this particular problem then additionally requires `return if (isComptime()) normal_code() else assembly_magic();` (which has no runtime cost because that branch is constant-folded). Given that inline assembly usually also branches on target architecture, that winds up not adding much complexity -- especially given that you probably had exactly that same code as a fallback for architectures you didn't explicitly handle.
- metadat 2y agoIs `_mm_sqrt_ps(..)' an Intel-only thing? Why is the naming so jacked? https://www.intel.com/content/www/us/en/docs/cpp-compiler/developer-guide-reference/2021-8/mm-sqrt-ps-mm256-sqrt-ps.html https://www.intel.com/content/www/us/en/docs/cpp-compiler/de...
- ack_complete 2y agoIt is a compiler intrinsic named after the SQRTPS instruction it's intended to generate. The "PS" refers to the vectorization type and stands for packed single. That being said, the naming of Intel's vector intrinsics _is_ pretty bad, such as the pi64 vs. epi64 difference. ARM's vector intrinsic naming, despite looking like having come from a cat sitting on the home row keys, is more consistent and has less gotchas.
- bibouthegreat 2y agoI wonder what it would be with a constexpr. If it works, it would be good to add this to intrinsic functions