In C++, is empty() faster than comparing the size with zero?
lemire.me
lemire.me
bool isEven(int n) {
return n == 0 || !isEven(n + 1);
}
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.
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.
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.)
(I remember reading a page with more examples, but cannot find it)
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 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.
That is literally reason why any behavior is considered undefined. So that the compiler can skip checks to produce better optimized code.
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.
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.
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.
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).
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.
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.
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.
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?
Defining the behaviour of a particular compiler under specific circumstances does not equate to defining the behaviour of the C language.
I don't think there's an obvious 'good' and 'bad' choice here.
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?
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.
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.
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.
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; }
std::list::splice(const_iterator pos, list& other, const_iterator first, const_iterator last)
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 );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.
(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).
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).
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.
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.
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.
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.
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
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?)
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).
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.
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.
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 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.
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.
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 :)
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.
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;
}