8 ms·
Std: Clamp generates less efficient assembly than std:min(max,std:max(min,v))
- fooker 3y agoIf you benchmark these, you'll likely find the version with the jump edges out the one with the conditional instruction in practice.
- svantana 3y agoThat must depend on the platform and the surrounding code, no?
- fooker 3y agoYes. On platform - most modern cpus are happier with predictable branches than exotic instructions. On surrounding code - for sure.
- pclmulqdq 3y agoCompilers often under-generate conditional instructions. They implicitly assume (correctly) that most branches you write are 90/10 (ie very predictable), not 50/50. The branches that actually are 50/50 suffer from being treated as being 90/10.
- fooker 3y agoThe branches in this example are not 50/50. Given a few million calls of clamp, most would be no-ops in practice. Modern CPUs are very good at dynamically observing this.
- pclmulqdq 3y agoDo you know that for a fact? For all calls of clamp? I have definitely used min and max when they are true 50/50s and I assume clamp also gets some similar use.
- fooker 3y agoModern compilers generate code assuming all branches are highly predictable. If your use case does not follow that pattern and you really care about performance, you have to pull out something like inline assembly. Consider software like ffmpeg which have to do this for the sake of performance.
- IainIreland 3y agoIt's hard to predict statically which branches will be dynamically unpredictable. A seasoned hardware architect once told me that Intel went all-in on predication for Itanium, under the assumption that a Sufficiently Smart Compiler could figure it out, and then discovered to their horror that their compiler team's best efforts were not Sufficiently Smart. He implied that this was why Intel pushed to get a profile-guided optimization step added to the SPEC CPU benchmark, since profiling was the only way to get sufficiently accurate data. I've never gone back to see whether the timeline checks out, but it's a good story.
- fooker 3y agoThe compiler doesn't do much of the predicting, it's done by the CPU in runtime.
- kyboren 3y agoNot prediction, predication: https://en.wikipedia.org/wiki/Predication_(computer_architecture) https://en.wikipedia.org/wiki/Predication_(computer_architec... By avoiding conditional branches and essentially masking out some instructions, you can avoid stalls and mis-predictions and keep the pipeline full. Actually I think @IainIreland mis-remembers what the seasoned architect told him about Itanium. While Itanium did support predicated instructions, the problematic static scheduling was actually because Itanium was a VLIW machine: https://en.wikipedia.org/wiki/VLIW https://en.wikipedia.org/wiki/VLIW . TL;DR: dynamic scheduling on superscalar out-of-order processors with vector units works great and the transistor overhead got increasingly cheap, but static scheduling stayed really hard.
- jeffbee 3y agoFYI. https://quick-bench.com/q/sK9t9GoFDRkx9XxloUUbB8Q3ht4 https://quick-bench.com/q/sK9t9GoFDRkx9XxloUUbB8Q3ht4' Using this microbenchmark on an Intel Sapphire Rapids CPU, compiled with march=k8 to get the older form, takes ~980ns, while compiling with march=native gives ~570ns. It's not at all clear that the imperfection the article describes is really relevant in context, because the compiler transforms this function into something quite different.
- fooker 3y agoWith random test cases, branch prediction can't help.
- tambre 3y agoBoth recent GCC and Clang are able to generate the most optimal version for std::clamp() if you add something like -march=znver1, even at -O1 [0]. Interesting! [0] https://godbolt.org/z/YsMMo7Kjz https://godbolt.org/z/YsMMo7Kjz
- GrumpySloth 3y agoBut then it uses AVX instructions. (You can replace -march=znver1 with just -mavx.) When AVX isn’t enabled, the std::min + std::max example still uses fewer instructions. Looks like a random register allocation failure.
- gpderetta 3y agoThe additional "movapd xmm0, xmm2" is mostly free as it is handled by renaming, but yes, it seems a quirk of the register allocator. It wouldn't be the first time I see GCC trying to move stuff around without obvious reasons.
- x1f604 3y agoI don't think it's a register allocation failure but is in fact necessitated by the ABI requirement (calling convention) for the first parameter to be in xmm0 and the return value to also be placed into xmm0. So when you have an algorithm like clamp which requires v to be "preserved" throughout the computation you can't overwrite xmm0 with the first instruction, basically you need to "save" and "restore" it which means an extra instruction. I'm not sure why this causes the extra assembly to be generated in the "realistic" code example though. See https://godbolt.org/z/hd44KjMMn https://godbolt.org/z/hd44KjMMn
- x1f604 3y agoEven with -march=znver1 at -O3 the compiler still generates fewer lines of assembly for the incorrect clamp compared to the correct clamp for this "realistic" code: https://godbolt.org/z/WMKbeq5TY https://godbolt.org/z/WMKbeq5TY
- jeffbee 3y agoClang generates the shortest of these if you target sandybridge, or x86-64-v3, or later. The real article that's buried in this article is that compilers target k8-generic unless you tell them otherwise, and the features and cost model of opteron are obsolete. Always specify your target.
- josephg 3y agoYep. Adding "-C target-cpu=native" to rustc on my desktop computer consistently gets a ~10-15% performance boost compared to the default target. The default target is extremely conservative. As far as I can tell, it doesn't take advantage of any CPU features added in the last 20 years. (The k8 came out in 2003.)
- jeffbee 3y agoThose Gentoo people were onto something.
- alexey-salmin 3y agoFunny that it stopped being the case for a while around 2006. AMD64 became widespread while also being very new, closing the gap between "default" and "native".
- skykooler 3y agoOf course, gentoo just started using prebuilt packages a few months ago…
- wongarsu 3y agoRed Hat Enterprise Linux has upgraded their default target to x86-64-v2 and is considering switching to x86-64-v3 for RHEL 10 (which should release around 2026?). I'd take that as a sign that those might be reasonable choices for newly released software. Some linux distros also give you the option to either get a version compatible with ancient hardware or the optimized x86-64-v3 version, which seems like a good compromise.
- 3y ago
- svantana 3y agoI'm a heavy std::clamp user, but I'm considering replacing it with min+max because of the uncertainty about what will happen when lo > hi. On windows it triggers an assertion, while other platforms just do a min+max in one or the other order. Of course, this should never happen but can be difficult to guarantee when the limits are derived from user inputs.
- lifthrasiir 3y agoPretty sure that their behaviors on NaN arguments will also differ.
- wegfawefgawefg 3y agoI hope they fix it. Thats quite a basic functional unit for it to be a footgun all on its own.
- camblomquist 3y agoDon't get your hopes up, the behavior when lo > hi is explicitly undefined.
- lpapez 3y ago> Of course, this should never happen but can be difficult to guarantee when the limits are derived from user inputs. Sounds to me like you are missing a validation step before calling your logic. When it comes to parsing, trusting user input is a recipe for disaster in the form of buffer overruns and potential exploits. As they used to say in the Soviet Union: "trust, but verify".
- PaulDavisThe1st 3y agoThat was what Reagan said about the Soviet Union, not what was said in the Soviet Union. Correct me if I'm wrong.
- deleted 3y ago[deleted]
- celegans25 3y agoOn gcc 13, the difference in assembly between the min(max()) version and std::clamp is eliminated when I add the -ffast-math flag. I suspect that the two implementations handle one of the arguments being NaN a bit differently. https://gcc.godbolt.org/z/fGaP6roe9 https://gcc.godbolt.org/z/fGaP6roe9 I see the same behavior on clang 17 as well https://gcc.godbolt.org/z/6jvnoxWhb https://gcc.godbolt.org/z/6jvnoxWhb
- gumby 3y agoYou (celegans25) probably know this but here is a PSA that -ffast-math is really -finaccurate-math. The knowledgeable developer will know when to use it (almost never) while the naive user will have bugs.
- cogman10 3y agoEhh, not so much inaccurate, more of a "floating point numbers are tricky, let's act like they aren't". Compilers are pretty skittish about changing the order of floating point operations (for good reason) and ffast-math is the thing that lets them transform equations to try and generate faster code. IE, instead of doing "n / 10" doing "n * 0.1". The issue, of course, being that things like 0.1 can't be perfectly represented with floats but 100 / 10 can be. So now you've introduced a tiny bit of error where it might not have existed.
- phkahler 3y agoI've never understood why generating exceptions is preferable to just using higher precision.
- gumby 3y agoHigher precision isn’t always available. IEEE 754 is an unusually well-thought-through standard (thanks to some smart people with a lot of painful experience) and is pretty good at justifying its decisions, some of which are surprising (far from obvious) to anyone not steeped in it.
- planede 3y agoOn a somewhat similar note, don't use std::lerp if you don't need its strong guarantees around rounding (monotonicity among other things). https://godbolt.org/z/hzrG3s6T4 https://godbolt.org/z/hzrG3s6T4
- camblomquist 3y agoI did a double take on this because I wrote a blog post about this topic a few months ago and came to a very different conclusion, that the results are effectively identical on clang and gcc is just weird. Then I realized that I was writing about compiling for ARM and this post is about x86. Which is extra weird! Why is the compiler better tuned for ARM than x86 in this case? Never did figure out what gcc's problem was. https://godbolt.org/z/Y75qnTGdr https://godbolt.org/z/Y75qnTGdr
- frozenport 3y agoTry switching to -Ofast it produces different ASM
- klodolph 3y ago-Ofast is one of those dangerous flags that you should probably be careful with. It is “contagious” and it can mess up code elsewhere in the program, because it changes processor flags. I would try a more specific flag like -ffinite-math-only.
- Sharlin 3y agofinite-math-only is a footgun as well as it allows the compiler assume that NaNs do not exist. Which means all `isnan()` calls are just reduced to `false` so it’s difficult to program defensively. And if a NaN in fact occurs it’s naturally a one-way ticket to UB land.
- klodolph 3y agoIf that’s a foot gun, then -Ofast is an autocannon. I like to think that the flag should be renamed “-Ofuck-my-shit-up”.
- MaulingMonkey 3y agoAs 1 of ∞ examples of UB land, I once had to debug JS objects being misinterpreted as numbers when https://duktape.org/ https://duktape.org/ was miscompiled with a fast-math equivalent (references to objects were encoded as NaNs.)
- nickysielicki 3y agohttps://bugs.llvm.org/show_bug.cgi?id=47271 https://bugs.llvm.org/show_bug.cgi?id=47271 This specific test (click the godbolt links) does not reproduce the issue.
- cmovq 3y agoDepending on the order of the arguments to min max you'll get an extra move instruction [1]: std::min(max, std::max(min, v)); maxsd xmm0, xmm1 minsd xmm0, xmm2 std::min(std::max(v, min), max); maxsd xmm1, xmm0 minsd xmm2, xmm1 movapd xmm0, xmm2 For min/max on x86 if any operand is NaN the instruction copies the second operand into the first. So the compiler can't reorder the second case to look like the first (to leave the result in xmm0 for the return value). The reason for this NaN behavior is that minsd is implemented to look like `(a < b) ? a : b`, where if any of a or b is NaN the condition is false, and the expression evaluates to b. Possibly std::clamp has the comparisons ordered like the second case? [1]: https://godbolt.org/z/coes8Gdhz https://godbolt.org/z/coes8Gdhz
- x1f604 3y agoI think the libstdc++ implementation does indeed have the comparisons ordered in the way that you describe. I stepped into the std::clamp() call in gdb and got this: ┌─/usr/include/c++/12/bits/stl_algo.h────────────────────────────────────────────────────────────────────────────────────── │ 3617 \* @pre `_Tp` is LessThanComparable and `(__hi < __lo)` is false. │ 3618 \*/ │ 3619 template<typename _Tp> │ 3620 constexpr const _Tp& │ 3621 clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi) │ 3622 { │ 3623 __glibcxx_assert(!(__hi < __lo)); │ > 3624 return std::min(std::max(__val, __lo), __hi); │ 3625 } │ 3626
- cmovq 3y agoThanks for sharing. I don't know if the C++ standard mandates one behavior or another, it really depends on how you want clamp to behave if the value is NaN. std::clamp returns NaN, while the reverse order returns the min value.
- cornstalks 3y agoFrom §25.8.9 Bounded value [alg.clamp]: > 2 Preconditions: `bool(comp(proj(hi), proj(lo)))` is false. For the first form, type `T` meets the Cpp17LessThanComparable requirements (Table 26). > 3 Returns: `lo` if `bool(comp(proj(v), proj(lo)))` is true, `hi` if `bool(comp(proj(hi), proj(v)))` is true, otherwise `v`. > 4 [Note: If NaN is avoided, `T` can be a floating-point type. — end note] From Table 26: > `<` is a strict weak ordering relation (25.8)
- CountHackulus 3y agoI see that the assembly instructions are different, but what's the performance difference? Personally, I don't care about the number of instructions used, as long as it's faster. With things like store forwarding and register files, a lot of those movs might be treated as noops.
- deleted 3y ago[deleted]
- superjan 3y agoThe only times I worry about min/max/clamp performance is when I need to do thousands or millions of them. And in that case, I’d suggest intrinsics. You get to choose how NaN is handled, it’s branchless, and you can do multiple in parallel. It feels backwards that you need to order your comparisons so as to generate optimal assembly.