You can also achieve the fix using the arguably more natural
template<typename T>
T const& clamp(T const& v, T const& lo, T const& hi) {
T const& a = v < lo ? lo : v;
T const& b = a > hi ? hi : a;
return b;
}
Either way, the commitee's idea of returning references for the C++ max/min/clamp functions was terrible, and it's a constant source of problems with temporaries and such. Like this: https://godbolt.org/z/j593Mebd6
But it's not unreasonable for a programmer to expect no temporaries in code that just uses references.
The rules are too complex, some of this is down to the language itself and some is the fault of compiler writers.
I find myself using Compiler Explorer more and more for short code snippets to (obviously) see what the compiler is doing because I don't really trust my intuition that much any more. And the annoying thing is that clang and gcc can differ wildly in their codegen.
I don't think anyone can call themselves a C++, or possibly Rust, programmer unless they can also understand assembly code. Just getting code to compile isn't enough. It seems like a step backwards to me.
> I don't think anyone can call themselves a C++, or possibly Rust, programmer unless they can also understand assembly code.
Slow down on the gate keeping there. It really depends what you’re trying to achieve. I’ve spent the last few days optimising a btree implementation in rust. The code runs fast, but the performance varies +/- 15% or so seemingly arbitrarily based on how I structure my code.
I could hop into compiler explorer and figure out what the compiler is actually doing. But the code is long and complex, and my mostly-allocation free approach is already about 80x faster than the javascript implementation this code is trying to replace. Optimising it further is not worth my time. The fact that I don’t have the skills or the time to squeeze a few more % out of my algorithm doesn’t make me a bad rust programmer. It makes me good at planning - I’m optimising my time.
There will always be a line in the sand where further optimizations based on even deeper understanding will stop being worth your effort. Where that point is depends on the project. Is it worth running benchmarks? Doing profile based hotspot optimization? Is it worth looking at the compiler’s assembly output? Are you going to hardcode asm routines? How about per-cpu variants of core algorithms for popular CPUs?
No. We all stop somewhere, depending on the needs of the project at hand, depending on how our time is best spent. That is the only reasonable answer if you want to ever finish projects. You don’t get to tell me I’m not a real rust programmer because I’m not microoptimizing this project as much as you would. That’s silly.
Actually, I don't think it's silly at all. Beating JS isn't hard to achieve, it doesn't tell you much about the quality of your code. Me beating a toddler in a 100m sprint doesn't make me an athlete.
Benchmark against a C or C++ implementation. You'll be examining things on Compiler Explorer soon enough.
Beating JS by 5x is easy. Beating a good JS implementation by 80x is much harder.
> Benchmark against a C or C++ implementation
Alas no; I'm not going to do that. First because there aren't any implementations in C/C++ for what I'm doing. But also, because as much fun as it is to wring every last cycle out of my CPU, I've met myself. Spending every moment trying to make my code go faster is a trap. If I spend too much time optimizing for performance, I'll never finish what I'm writing. I've done it before.
Performance is fun because its measurable. You get a score, and that feels great. But beyond some point, documentation, testing and features all become much more important. I could write the fastest library in the world but if its buggy, missing features or has no documentation, nobody will use it. Worse, I won't be able to build things on top of it because I'll be too distracted trying to make my benchmark numbers go up.
Performance is fun, but its far from the only measure of software quality.
I spent a decade or so of my life writing assembly, and a few years as a performance specialist for a programming team. What you're describing is a specialist skill. There's nothing wrong with it - it's a good skill to have - but there is no need to have everybody in the team have it, and you can expect better results by having some people develop that skill and other people develop other skills.
What would you have them use instead of constant references? If you take values and T is bigint, then clamp becomes unusable. Even if it’s 128 bit ints... that’s worse.
I think const ref makes perfect sense. It has the logic you want but no copying etc. When clamp is inlined, the compiler should be able to deal with const refs as easily as values for small Ts. (And if it’s not, let’s fix the compilers... not stdlib)
Having everything be const references is in a sense optimal, but is so prone to misuse that I wouldn't want it in the standard library.
One option is to pass everything by value. Move semantics does the rest. Like:
template<typename T>
T clamp(T v, T lo, T hi) {
if(v < lo) v = std::move(lo);
if(v > hi) v = std::move(hi);
return std::move(v);
}
For fundamental types, this is the same or better than before (including __int128_t and such). For bigint types with heap allocation, i.e., GMP wrappers and such, moving is fairly inexpensive (but for constant lo, hi, they need to be created/copied each time...). For fixed-width bigint types, moving is no different from copying and the cost is higher. In any case, the 99-percentile usage of these functions is with fundamental types, where pass-by-value is clearly the better choice.
Alternatively, you could have
template<typename T>
T& clamp(T& v, T const& lo, T const& hi) {
if(v < lo) v = lo;
if(v > hi) v = hi;
return v;
}
This forces the returned reference to be an l-value, and so returning dangling temporaries becomes more difficult. There's the added cost for the assignments, though.
- clamp(a, b, c), where a, b, c are all l-values would copy everything. Not destructive by default (but wasteful on "big" types).
- clamp(a, std::move(b), c) would potentially destroy b, but that's something the caller explicitly opted into.
- clamp(a, T{ something }, T{ something else }) would be an implicit move, but nobody is going to accidentally use those r-values anywhere else.
The non-const ref version returning is not something I quite like either; it would make more sense to me to have `void clamp(T& x, T const& l, T const& h)`, where the semantics would be more like `x.clamp(l, h);`. But to retain the same API I returned the reference.
julia> clamp(x, lo, hi) = x < lo ? lo : x > hi ? hi : x
clamp (generic function with 1 method)
julia> @code_native clamp(2.0f0, -1.0f0, 1.0f0)
.text
vminss %xmm0, %xmm2, %xmm2
vcmpnltss %xmm1, %xmm0, %xmm0
vblendvps %xmm0, %xmm2, %xmm1, %xmm0
retq
Looks like it might even be better? I'm not quite sure but the mnemonics are longer so they must be better ;)
Does Julia have a JIT? If so, maybe LLVM's x86 backend could do better if given the codegen flags corresponding to what Julia detects is available natively.
How is _LIBCPP_ASSERT implemented? I know that GCC can make more intelligent optimizations when you explicitly rule out user-level undefined behavior as in:
if (will_not_happen()) {
__builtin_unreachable();
}
In the specific case highlighted in this article will_not_happen() can be replaced with “hi < lo”.
Rust's RFC for clamp has specifically tuned the definition and handling of NaN to be able to generate good assembly. I'm glad people have noticed and appreciate this.
The "good" assembly output that this article refers to isn't clearly good...
Long chains of instructions (ie. Where the output of one instruction is required as the input to another) are slow on modern hardware. It might well be faster to calculate the high side clamp and the low side clamp independently, and then to decide which result to return.
Also, I'd hope that clamp() is always inlined, so inspecting it as a separate function doesn't make much sense...
> Long chains of instructions (ie. Where the output of one instruction is required as the input to another) are slow on modern hardware. It might well be faster to calculate the high side clamp and the low side clamp independently, and then to decide which result to return.
Probably not, at least not on Intel: the CPU could conceivably schedule both sides simultaneously on different execution ports, but they'd still be serialized internally on the floating point unit. That port is better used by other in-flight (u)ops. You're right that data dependencies are important to be aware of, but the generated code here is probably pretty close to optimal for recent Intel and AMU CPUs.
25 comments
[ 0.27 ms ] story [ 74.2 ms ] threadThe rules are too complex, some of this is down to the language itself and some is the fault of compiler writers.
I find myself using Compiler Explorer more and more for short code snippets to (obviously) see what the compiler is doing because I don't really trust my intuition that much any more. And the annoying thing is that clang and gcc can differ wildly in their codegen.
I don't think anyone can call themselves a C++, or possibly Rust, programmer unless they can also understand assembly code. Just getting code to compile isn't enough. It seems like a step backwards to me.
Slow down on the gate keeping there. It really depends what you’re trying to achieve. I’ve spent the last few days optimising a btree implementation in rust. The code runs fast, but the performance varies +/- 15% or so seemingly arbitrarily based on how I structure my code.
I could hop into compiler explorer and figure out what the compiler is actually doing. But the code is long and complex, and my mostly-allocation free approach is already about 80x faster than the javascript implementation this code is trying to replace. Optimising it further is not worth my time. The fact that I don’t have the skills or the time to squeeze a few more % out of my algorithm doesn’t make me a bad rust programmer. It makes me good at planning - I’m optimising my time.
There will always be a line in the sand where further optimizations based on even deeper understanding will stop being worth your effort. Where that point is depends on the project. Is it worth running benchmarks? Doing profile based hotspot optimization? Is it worth looking at the compiler’s assembly output? Are you going to hardcode asm routines? How about per-cpu variants of core algorithms for popular CPUs?
No. We all stop somewhere, depending on the needs of the project at hand, depending on how our time is best spent. That is the only reasonable answer if you want to ever finish projects. You don’t get to tell me I’m not a real rust programmer because I’m not microoptimizing this project as much as you would. That’s silly.
Benchmark against a C or C++ implementation. You'll be examining things on Compiler Explorer soon enough.
> Benchmark against a C or C++ implementation
Alas no; I'm not going to do that. First because there aren't any implementations in C/C++ for what I'm doing. But also, because as much fun as it is to wring every last cycle out of my CPU, I've met myself. Spending every moment trying to make my code go faster is a trap. If I spend too much time optimizing for performance, I'll never finish what I'm writing. I've done it before.
Performance is fun because its measurable. You get a score, and that feels great. But beyond some point, documentation, testing and features all become much more important. I could write the fastest library in the world but if its buggy, missing features or has no documentation, nobody will use it. Worse, I won't be able to build things on top of it because I'll be too distracted trying to make my benchmark numbers go up.
Performance is fun, but its far from the only measure of software quality.
I think const ref makes perfect sense. It has the logic you want but no copying etc. When clamp is inlined, the compiler should be able to deal with const refs as easily as values for small Ts. (And if it’s not, let’s fix the compilers... not stdlib)
One option is to pass everything by value. Move semantics does the rest. Like:
For fundamental types, this is the same or better than before (including __int128_t and such). For bigint types with heap allocation, i.e., GMP wrappers and such, moving is fairly inexpensive (but for constant lo, hi, they need to be created/copied each time...). For fixed-width bigint types, moving is no different from copying and the cost is higher. In any case, the 99-percentile usage of these functions is with fundamental types, where pass-by-value is clearly the better choice.Alternatively, you could have
This forces the returned reference to be an l-value, and so returning dangling temporaries becomes more difficult. There's the added cost for the assignments, though.Non const refs seems like a weird idea (what if I got a const ref from my callee? Why can’t I clamp?).
- clamp(a, b, c), where a, b, c are all l-values would copy everything. Not destructive by default (but wasteful on "big" types).
- clamp(a, std::move(b), c) would potentially destroy b, but that's something the caller explicitly opted into.
- clamp(a, T{ something }, T{ something else }) would be an implicit move, but nobody is going to accidentally use those r-values anywhere else.
The non-const ref version returning is not something I quite like either; it would make more sense to me to have `void clamp(T& x, T const& l, T const& h)`, where the semantics would be more like `x.clamp(l, h);`. But to retain the same API I returned the reference.
Does Julia have a JIT? If so, maybe LLVM's x86 backend could do better if given the codegen flags corresponding to what Julia detects is available natively.
https://github.com/rust-lang/rfcs/pull/1961
I suspect it will be fixed and that will also have an effect on other methods that are similar in nature.
https://bugs.llvm.org/show_bug.cgi?id=47271
The fix in OPs article landed in master today.
Long chains of instructions (ie. Where the output of one instruction is required as the input to another) are slow on modern hardware. It might well be faster to calculate the high side clamp and the low side clamp independently, and then to decide which result to return.
Also, I'd hope that clamp() is always inlined, so inspecting it as a separate function doesn't make much sense...
Probably not, at least not on Intel: the CPU could conceivably schedule both sides simultaneously on different execution ports, but they'd still be serialized internally on the floating point unit. That port is better used by other in-flight (u)ops. You're right that data dependencies are important to be aware of, but the generated code here is probably pretty close to optimal for recent Intel and AMU CPUs.