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);
    }

Clang somehow optimizes it to a constant-time implementation, even if we use "unsigned"! https://gcc.godbolt.org/z/nGbn1T

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.)

https://godbolt.org/z/K9rMajsjK

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.

Oh yeah - negative numbers exist, doh!

What’s the UB?

Calling it on any positive int causes signed integer overflow, which is UB.

signed integer overflow for positive N

> 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.

It helps everyone whose input does not cause undefined behavior.

in most cases a program that invokes undefined behavior is already broken; it's just a question of how catastrophic the failure will be.

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.

This is correct. In the motivating example, it would have to scan the entire list of pointers to see whether it finds a NULL link before it overflows the size counter or not.

Ah, you're completely right, the compiler couldn't hid or assume away the aborts as they would now be part of the spec.

> 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).

> You need not imagine an alternate version of C, such a version of C is provided by any decent C compiler.

Classic misunderstanding of undefined behaviour. In this case it's still undefined behaviour, but the vendor has said "this is what my compiler will do with this particular undefined behaviour under these circumstances". Vendors are allowed to do anything they want when code containing undefined behaviour is submitted to their compiler, including doing something you might consider sane.

I agree that leaving such important behavior as undefined is a failure for a programming language standard, because the standard fails to guarantee that a program will do the right things independently of what compiler has been used and with what compiler options.

Nevertheless, in such cases it is the responsibility of the programmer to either write programs in which it is guaranteed that events for which the program behavior is undefined will never happen or to choose compiler options to handle such events.

If the programmers do their job right, then the compiler is free to optimize like when the undefined cases do not exist.

Unlike the case with integer overflow, there are cases where the programming language standards correctly leave some behavior as undefined, e.g. the order of evaluation for function arguments. For that kind of undefined behavior the programmer must take care to write only programs whose effects do not depend on it.

Data dependent events like integer overflow cannot always be avoided, so compilers must have options to generate exceptions when they happen.

> Data dependent events like integer overflow cannot always be avoided, so compilers must have options to generate exceptions when they happen.

This is a language choice. A better language can ensure that "data dependent events like integer overflow" are in fact avoided entirely. C and C++ chose not to do this.

I'm certain you'll disregard evidence from any languages that don't have similar performance characteristics to C or C++, so let's focus on two that do.

In Rust, the arithmetic operations that can result in overflow are supplied in typically four varieties. Checked operations, which produce an Option that is either Some(answer) or None if they would overflow, Overflow operations which produce a pair (answer,overflow?) where the boolean overflow? tells us whether an overflow occurred, Saturating operations, which produce an answer that's either correct or, if it overflows, saturated at the boundary crossed and finally Wrapping operations, which produce the answer with a wrapping number line.

In WUFFS the programmer is responsible for ensuring that their arithmetic operations cannot overflow. If you try to add two arbitrary 16-bit integers together in WUFFS the compiler will complain that it can't see why this is safe as they might overflow. Only once the programmer has excluded this case (e.g. if either integer is larger than 999 or smaller than -999 the function reports this as an error and doesn't add them together) can they add the integers together, since now there can't be an overflow.

The behavior is defined, but by the compiler documentation, not the language standard. Different documents can define different things.

Saying 'this is what I will do when an int can't hold the assigned value' is defining the behavior, ergo it is no longer undefined!

Vendors are allowed to do anything they want when code containing undefined behaviour is submitted to their compiler

Yes, and his compiler is saying that it will trap these events. Are you suggesting that the compiler will secretly ignore this setting and then go on to do all kinds of insane things?

> Saying 'this is what I will do when an int can't hold the assigned value' is defining the behavior, ergo it is no longer undefined!

Defining the behaviour of a particular compiler under specific circumstances does not equate to defining the behaviour of the C language.

You are reading words that nobody wrote. No-one claimed that they were redefining the ‘C spec’ by passing flags to their compiler - the standards board’s job is still safe!

Sure, but I understand why the C spec does not define this - because not all processors can trap these events, at all times and in all situations, without added costs. And C is very much of the opinion that it doesn't want added costs - but it lets you pick and choose what you want, hence the compiler options.

I don't think there's an obvious 'good' and 'bad' choice here.

I think the "good" choice is to remove undefined behaviour and accept that C will be slighlty slower on esoteric hardware.

This will make C much slower on your hardware, too.

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.

Wait, isn't the point of the STL algorithms that they use iterators?

For sure the iterator over a vector may be very cheap to use, but it is still an iterator, even if you tacitly know it's just pointer arithmetic under the hood.

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.

The live-at-head model really only works well in a cloud computing or JIT environments. It really shouldn't have been a surprise to find that this model is unpopular outside of those narrow use-cases.

in my personal experience it also works great for desktop software

That depends. It’s awful for the libraries that your OS provides to support your desktop app, for example.

> 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; }

In your background clean-up example structure, if the background thread is removing N elements, it must decrease current_size by N. Atomically! (i.e. remove the element and decrease the current_size using a mutex::lock/unlock)

Some

  std::list::splice(const_iterator pos, list& other, const_iterator first, const_iterator last)

implementations used to be constant-time, since they could just change some pointers in the spliced nodes. Nowadays they take linear time, since they need to count how many nodes are transferred so they can update the sizes correctly.

Wouldn't this still be constant-time today? It doesn't need to count the nodes because the other list already has a count of its nodes.

No, because you'd still need book keeping around the length of [first, last), even if the implementation does under-the-hood O(1) movement of nodes in [first, last) from other to *this. Computing the length of [first, last) is still an O(n) operation for forward iterators.

Maybe you're assuming [first, last) is the entirety of other? For that case, there are overloads for splicing an entire list in O(1) time:

    void splice( const_iterator pos, list& other );
    void splice( const_iterator pos, list&& other );

This seems like an extremely niche use-case, compared to the prevalence of use-cases needing to check the size of a list.

This niche is exactly why I've used std::list in several cases. It allows fairly easy preallocation of list nodes.

Fortunately, the single-node splice is still fast. But batch allocations, say related to some scatter/gather operations, would still be hit by this change.

No, because you can splice in the middle. Given just the iterators you simply have no other way than counting.

(The reason why it used to be constant time is that it didn't have to count because it didn't have to compute the new size).

Interesting, a good case for another std::list<> like std::non_counting_list<>

Reminds me of Michael Bolton from Office Space, "Why should I change, he's the one who sucks!"

std::list WAS noncounting. introducing std::counting_list was an option. I didn't follow this decision so I don't know why they opted to break the behavior (performance expectations).

> 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.

Which is long since fixed with std:string & co. The data structure concept of a string has no need for linear length calculation. Rather, C just did strings badly.

My point was that the background thread would remove elements periodically, by checking something like:

    if (it->expiry_time < now) erase(it);

Where erase() could certainly remove the item and update the size, but it would remove elements after they have expired. So if size() must return the actual number of unexpired elements present right now, the cached counter you mention would not be up to date.

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.

When you have multiple threads running concurrently, you're going to have to deal with coherency and synchronization one way or another.

What does `now` even mean? It's presumably a sampled count from a running clock. With concurrent execution, there's no guarantee about the relationship between two thread's samples of the clock unless you synchronize them. One thread may read the clock, then get preempted for a while before doing any actual work. According to the preempted thread's point of view it's still in the present and running calculations without a care in the world, but from the preempting thread's point of view it's frozen in the past to be thawed out in the future.

Do you really need to be that picky about coherency of this hypothetical multi-threaded expiring data structure? So what if the size reads slightly larger on average? It seems like the reasonable direction to err on, since elements are getting deleted out from under you anyway, and so there's an inherent race condition between when a thread would call size() and then call another function dependent on the result of calling size().

If you need it to truly be cycle-by-cycle coherent with the hardware clock, then you'll need to add synchronization. The size() function will no longer take a predictably constant time, as it will either block on a mutex, spin some number of times on a lock-free atomic, or remove expired elements itself.

As other folk have also pointed out, though, the time complexity of the STL member functions are only a self-imposed rule. A function like size can do whatever you want if you're writing the implementation.

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>
    

On most processors this runs faster:

    for i=MAX; i != 0; i--
        <some code>
    

This is because most processors have the equivalent of a "CJNZ" or "CJZ" (Compare and Jump if Not Zero; Compare and Jump if Zero) instruction. It is much faster (generally one clock cycle) to determine if the value in a register or accumulator is zero than to load multiple registers and determine "less than" or "less than or equal to".

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

> 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

It's also a tradeoff as you would either need additional branching on access (this is what most std::string implementations do) and/or bloat the size of all vector objects, even those that will never fit into the static size.

It's a tradeoff the user can make, not something the STL needs to generically know like std::string does. If you look at inlined_vector (or similar implementations), the static size is specified in a type parameter, not something automatic. So just have it be 0 if you want it to behave like std::vector does currently. As such, no downsides to adding this to the type other than the ABI breakage. Default the size to 0 and you preserve API compatibility, even.

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.

My point exactly: I can trust the STL’s standardised interface, but performance is often dependent on implementation details, which are bound to vary from platform to platform, or even from computer to computer (assuming a dynamically linked libc++).

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;
  }

> Sadly, GCC is now unable to optimize away the call. Maybe compilers are not yet all powerful beings?

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;
  }

https://godbolt.org/z/YKWbWb5zr

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.....