▲ 123 points
back
81 comments
The most impressive example I've ever seen of this kind of compiler cleverness is the following function from the "convoluted isEven" competition:
bool isEven(int n) {
return n == 0 || !isEven(n + 1);
}
Isn't the unsigned version the correct one? Presumably the int version will hit the same problem as in the original article, in that the C spec says that ints are not treated as overflowing? (i.e. the compiler cannot assume that adding one will eventually turn negative and then later on reach 0)
Well the int version returns the correct answer for "empty()" unlike unsigned. The size of a list of 2^32-1 elements should not be reported as zero, nor as "empty".
In this case, the compiler has to enforce wrap semantics for unsigned, which is an applicaton-level level bug if it occurs, and doesn't need to enforce it for int, which happens to lead to the right answer for empty (i.e., it checks if it has at least one element, which continues to return the correct "not empty" answer for 2^32-1 or 2^31-1 elements).
Both get the wrong answer for size() (over different domains), if you allow lists that large: they can't even represent very large lists.
Yes that's right - unsigned is defined to wrap, but ints have undefined behavior if you add to the max value (or do other silly things with them). Thus the int version given could be optimized to do whatever when a positive integer is passed, since it only doesn't have UB when negatives or zero are passed.
> the compiler cannot assume that adding one will eventually turn negative and then later on reach 0
Signed overflow is undefined behavior, so it is allowed to assume that. It's also allowed to assume anything else that it wants to.
Once you cause a signed overflow, all guarantees are out the window and the compiler can do anything it wants to.
Is the LLVM optimisation pass that does this hyper-specialised for this one particular trick, and, if so, is it valuable in practice?
Here's an example where (I think) the two functions are equivalent, so I'm a little disappointed it couldn't make the same optimisation on the second one. (At least it still optimised the tail call to a jump.)
No, it is very generic. See https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geo..., https://blog.matthieud.me/2020/exploring-clang-llvm-optimiza... (discussed at https://news.ycombinator.com/item?id=28207207)
(I remember reading a page with more examples, but cannot find it)
Is this code not relying on UB? Seems like it could/should be optimized to `return true`
It's UB for positive integers, so the compiler can assume it never happens. It's correct for negative integers, so the compiler just optimizes it for negative integers and ignores the positive ones - in this case with the end result that it works for positive integers as well.
If the argument is changed to unsigned int then it seems to be correct and portable because the C standard[1] requires UINT_MAX to be of the form 2^n - 1 (which makes it wrap from odd to even when overflowing).
So the one with signed argument is UB for positive integers but happens to work by accident (but the nasal demons may still lurk just around the corner, e.g. the compiler may also assume that it's never called with a positive argument which may affect the compilation of callers). The one with unsigned argument is correct because unsigned overflow is well-defined to wrap around to zero, combined with the restrictions on max unsigned int.
[1]: From C17 6.2.6.2:
For unsigned integer types other than unsigned char, the bits of the object representation shall be divided into two groups: value bits and padding bits (there need not be any of the latter). If there are N value bits, each bit shall represent a different power of 2 between 1 and 2*(N-1), so that objects of that type shall be capable of representing values from 0 to 2*(N-1) using a pure binary representation; this shall be known as the value representation.
It's only UB for positive n. For negative n, it is an is-even test, so it can't be optimized to return true.
What’s the UB?
> Amazingly, we find that the GCC compilers is able to compile Travis’ is_empty C++ function to constant-time code.
It's actually an interesting example where undefined behavior allowed compiler optimization:
(1) dereferencing an invalid pointer is UD
(2) signed integer overflow is UD.
This allows the compiler to assume that the program never crashes and the counter never overflows. The loop is then optimized out knowing that it is read-only thus has no side-effects.
> It's actually an interesting example where undefined behavior allowed compiler optimization
That is literally reason why any behavior is considered undefined. So that the compiler can skip checks to produce better optimized code.
Actually, many instances of undefined behavior are born out of a desire for portability. Some processors will fault on both of those and the standard wants to be inclusive of those behaviors. Compilers happen to be able to use the definition of undefined behavior to also optimize code, but the concept is born out of practicality.
And so you get an optimal, but broken, program. This helps nobody.
Maybe I'm splitting hairs, but it's not specifically the presence of 'undefined behavior' that allows the compiler optimization. Instead, it's the language specification. The C spec says that integers cannot be relied upon to overflow. The result of this is that compilers are then free to assume that the program they are compiling has NO undefined behavior in it, and so the optimization is possible.
EDIT: To make it clearer, you could imagine an alternate version of C that aborted the program if an integer overflowed. Then there would be no undefined behavior at all - but the optimization is still possible. It's not the UB that helps us here, it's the language spec telling us what behavior is reliable and what is not.
> To make it clearer, you could imagine an alternate version of C that aborted the program if an integer overflowed. Then there would be no undefined behavior at all - but the optimization is still possible.
The optimisation wouldn't be possible in that case because then the program wouldn't abort when the integer overflowed. It would break the defined behaviour that overflow=abort.
> Then there would be no undefined behavior at all - but the optimization is still possible.
But then an optimization could change the defined behavior of aborting to not aborting, which is essentially what undefined behavior means and really bad if you don’t treat it exactly like undefined behavior.
You need not imagine an alternate version of C, such a version of C is provided by any decent C compiler.
For example, with gcc you can use either the option "-ftrapv" or the better option "-fsanitize=undefined -fsanitize-undefined-trap-on-error" and the program will abort on integer overflows (with the second option it will also abort for many other error conditions, e.g. access out of bounds).
I suppose it is a safe assumption that the counter will never overlow if memory space is not large enough to possibly hold the maximum positive integer number of data structs. Though if say was using a smaller int for size than what the hypothetical size that virtual memory could handle, such as a short int in a 32-bit memory system, then that assumption may not be true. But on a 64-bit linux system which only allows up to 128 TiB of virtual address space for individual processes, a 64-bit signed int could be as large as 2^63, which would be larger than the hypothetical maximum size that a 128 TiB virtual memory could reference, so the assumption that the size counter could never overflow would be safe.
It's interesting that size() has to be constant-time. From what I understand of the standard linked from the blog post, it looks like size() being constant-time is a property of Container and not each individual method (§ 23.2.1, page 747).
What does this mean for implementations that want to have these properties but have internal structures that make this inherently difficult? Do they have to recompute a cached size value during other operations, and amortize the cost of size() on insert, for example?
I can see it being tricky in some situations: imagine a collection with expiring data, for example. You might want to prune the expired items in the background, but still have size() return the number of elements currently not expired. How would someone do this while maintaining an exact size() value when the background clean-up will inherently take some time?
The standard's requirements for the standard library types don't imply any corresponding requirement for types you define yourself. If you want to write a container which can't reasonably do O(1) size() then you just don't do O(1) size(). If such a container was added to the standard library, the standard library's Container requirements will be adjusted to permit that.
Exactly, most STL algorithms, for example, can be applied using iterators as well. But anyway if GP has specific requirements iterator invalidation might be a problem too, they wouldn't probably want to constrain their interface to that of STL containers.
Once upon a time, size() wasn't required to be constant-time. This showed up in some standard library implementations of std::list::size which actually did count all the things.
The painful ABI break at C++11 is a big part of why implementors were so opposed to allowing another ABI break in C++20.
It's also why other people in the C++ community are opposed to ABIs themselves.
> What does this mean for implementations that want to have these properties but have internal structures that make this inherently difficult?
Such implementations are de facto forbidden in the STL.
Although its containers have vague names like "forward_list" today the C++ STL's containers are in practice very specific data structures that have the specified properties because other data structures would miss one or more of the requirements.
This suits "stability at all costs" C++ programmers fine. Better that every C++ program is 10% slower than that their buggy library from 1995 has to be fixed to actually do what the standard says rather than whatever worked in 1995.
If you care about this but you like C++ you just don't use the STL. Third parties are free to make containers that use data structures that aren't old enough to stand for President of the United States of America, some of them aren't even old enough to legally drive in the United States of America.
> What does this mean for implementations that want to have these properties but have internal structures that make this inherently difficult
I'm not sure I can think of an example of such a data structure?
my understanding is that whatever your data structure is, you can keep a "size_t current_size;" private counter which you atomically increment/decrement on every insertion/deletion. size() is simply:
size_t size() { return current_size; }
Some
std::list::splice(const_iterator pos, list& other, const_iterator first, const_iterator last)
> I'm not sure I can think of an example of such a data structure?
C style strings are the classical example. Computing the size (strlen) takes linear time. Not saying that this is a good idea or anything, but it's extremely common.
One could imagine a binary tree implemented in a similar manner. It costs a little time and memory to keep track of the current size, but it almosy always pays off.
My point was that the background thread would remove elements periodically, by checking something like:
if (it->expiry_time < now) erase(it);
This is what I meant by "have size() return the number of elements currently not expired". What you're describing is "size returns the number of elements currently not expired OR expired but not yet cleaned up", which is different.
If you work in real time embedded systems you become aware of code constructs that will deliver better performance. I always study the instruction set to see what tools it might reveal.
For example, most people might write something like this (pseudocode, "MAX" being a constant):
for i=0; i < MAX; i++
<some code>
for i=MAX; i != 0; i--
<some code>
As far as I know, these are not optimizations a compiler is capable of.
That's absolutely something a compiler can do, and it's easily verifiable:
https://godbolt.org/z/3Tze5q594
Compilers can and do perform these optimizations; they maintain internal tables of instruction costs that guide what code is emitted. It’s just that modern processors don’t really have these kinds of differences, and the ones that do are generally not amenable to high-level compilers for other reasons (extreme register pressure, etc.)
That depends if the loop has side effects such that the optimization would be unsound.
The actual transformation is dead simple albeit possibly not that profitable on a modern processor that will be macro and micro fusing to hell and back
> As far as I know, these are not optimizations a compiler is capable of.
If <some code> has side effects I don’t want the compiler to make that optimization as the order might be important and there is no way to tell.
(If there are no side effects the compiler can optimize — by removing the loop!).
You can tell the compiler you don’t care about order by replacing the for loop with an algorithm like for_each which is allowed to do this kind of thing, and can take a parallel policy too.
(Though is there an implementation that uses execution policies?)
I work in embedded systems and generally I think the priorities still are:
1. Correctness 2. Readability 3. Performance
A lot of people worry too much about time constraints and performance, at the end of the day, correctness is the most important, readability second _specially_ if you are consulting and leaving that codebase behind for someone else to maintain. Performance is important but only to the extent that it is specified.
So many times people write performance enhacements for functionality that has no hard real-time deadlines.
If the performance objective is not in a specification then the optimization is not adding value (other than personal satisfaction).
> If the performance objective is not in a specification then the optimization is not adding value
Very true. I agree 100%.
I only resort to "sculpting" the code for performance when standard code will not meet timing requirements. Sometimes you just don't have the option to increase clock rates or change processors and have to make things work if at all possible.
In general terms, if things are too tight it, it means you are using the wrong processor or should consider going up to a higher speed grade.
That said, I can't tell you how many times I have faced apparent limits that absolutely evaporated by taking detailed control of the low level implementation. The easiest example I can provide was a custom dynamic RAM controller I designed for a Xilinx FPGA. It had a microcoded control architecture necessary for the specific application it targeted.
This particular device (I think it was an XC2-V1000) could not get much past 160 MHz no matter what we did. Compiler optimizations didn't help much past this point.
I decided to hand-wire and hand-place the design. This means locating each logic element by hand and wiring them by hand within the FPGA fabric. If I remember correctly, the hand-placed design could reliably reach 250 MHz. We didn't need to go that fast, I think we backed it down to 200 MHz with the comfort of knowing that we had good margin. It was tested for reliability in a thermal chamber, where it easily exceeded design requirements.
Not doing this would have meant moving up to a more expensive speed grade or an even more expensive member of the Xilinx family. Taking intimate control of the implementation likely saved well over a million dollars over the life of the product.
I have also been at the opposite end of the scale, where you are trying to squeeze the last bit of performance out of a $0.57 microcontroller because the design can't support a $0.75 chip. Sometimes life forces your hand that way.
If you’re actually at the point where you care about that kind of performance, you may want to shy away from the STL, and use (or write) something simpler instead.
I've always hated this bit of conventional wisdom, which has become less and less applicable over the past couple decades. STL implementations are now quite highly optimized within their spec. With the one little caveat that they're generally optimized for CPU cycles rather than per object memory usage.
But you should understand the performance characteristics of the STL. A std::vector is super fast for basically everything except for dynamic resizing. If performance is a concern, your first approach should be to see if you can avoid reallocation. Often it's very simple to just preallocate a reasonable maximum, or calculate an exact maximum based on your input.
Finally, if you truly need to do weird stuff with resizing, you can look at other containers or write your own.
> std::vector is super fast for basically everything except for dynamic resizing.
Resizing it is just fine, there's not really anything unexpectedly slow there. Rather, the big downside to std::vector is the lack of small size optimization (something std::string has, so too does std::function for that matter).
That's the big win for things like absl's inlined_vector https://github.com/abseil/abseil-cpp/blob/master/absl/contai...
It's an ABI break to add small-size optimizations to std::vector at this point so unfortunately while there's not really anything in the API requirements that would prevent it, compatibility concerns pose a formidable barrier
I thought the conventional wisdom was to avoid the STL if you need consistent performance across platforms, because they all have different pitfalls. Things might be different with libc++, now, though, since you can use it in most cases.
On the other hand, if you’re not at the point where you care about maximum performance, you may want to shy away from C++ altogether.
This implies that there are very few situations in which C++ with STL is the right choice - which seems contrary to how widely it’s actually used.
This seems like a pretty silly way to look at performance - If I'm working in C++, I 'care' about performance, but performance always exists on a continuum.
If I "truly cared" I could write it in assembler; but I don't, because chasing down the diminishing returns isn't worth it.
C++ w/STD is a perfectly valid (and extremely powerful!) point in the continuum that runs from Python to Assembly :)
Hmm, I’m not sure I agree there. There’s a difference between using C++ because I just want to avoid obvious waste (interpreter, GC pauses…), and actually optimizing my code.
I would put v.empty() vs v.size()==0 in the latter category. Day to day, I mostly trust that std::vector is not wasting cycles except on resizes.
> I can forcefully bound the return value of count_nodes() to be no more than 1000.
If I change the code to return a standard size_t type, like so…
size_t count_nodes(const node* p) {
size_t size = 0;
while (p) {
p = p->next;
size++;
if(size == 1000)
return 1000;
}
return size;
}
Interestingly, this version is optimized by GCC and Clang:
size_t count_nodes(const node* p) {
size_t size = 0;
while (p && (size < 1000)) {
p = p->next;
size++;
}
return size;
}
This was just discussed yesterday also: https://news.ycombinator.com/item?id=29007821
Not all O(1) functions have the same cost. Suppose we have a container that stores its data on the heap, and has a null pointer and no heap object when it is empty. Then Container::empty() const just needs to check that pointer, where Container::size() const has to read the size out of the heap object, so c.size() == 0 has to cost more, as the compiler is unlikely to be able to optimize away the extra accesses.
In a Wooooorld, where newer generation of developers does not grasp the concept of database indexes, and network latency is assumed to be zero, one man.....