In C++, is empty() faster than comparing the size with zero?

26 October 2021 · 4 min

Most C++ programmers rely on “STL” for their data structures. The most popular data structure is probably vector, which is just a dynamic array. The set and the map are other useful ones.

The STL data structures are a minimalist design. You have relatively few methods. All of them allow you to compute the size of the data structure, that is, how many elements it contains, via the size() method. In recent C++ (C++11), the size() method must have constant-time complexity for all containers. To put it in clearer terms, the people implementing the containers can never scan the content to find out the number of elements.

These containers also have another method called empty() which simply returns true of the container is… well… empty. Obviously, an equivalent strategy would be to compare the size with zero:  mystruct.size() == 0.

Determining whether a data structure is empty is conceptually easier than determining its size. Thus, at least in theory, calling empty() could be faster.

Inspecting the assembly output, I find that recent versions of GCC produce nearly identical code for the comparison of the size and the empty call. The exception being the list data structure where the assembly is slightly different, but not in a manner that should affect performance.

Of course, there are different implementations of C++ and it is possible that other implementations could provide more efficient code when calling empty(). An interesting question is whether effort is needed from the compiler.

Travis Downs wrote a list data structure by hand, but with a size() function that is linear time. He then implemented the empty function naively:

struct node {
    struct node *next;
    int payload;
};

int count_nodes(const node* p) {
    int size = 0;
    while (p) {
        p = p->next;
        size++;
    }
    return size;
}

bool is_not_empty(const node* p) {
    return count_nodes(p) > 0;
}

Amazingly, we find that the GCC compiler is able to compile Travis’ is_not_empty C++ function to constant-time code. The compiler inlines the count_nodes function into is_empty. Then the compiler figures out that as soon as you enter the loop once with count_nodes, then size is going to be greater than zero, so there is no need to keep looping.

However, the optimisation is not robust. Suppose that I wish instead to return an unsigned type instead of Travis’ int value. The problem with an unsigned type is that I might overflow if the list is very long. With a signed integer, the compiler is allowed to assume that overflows do not happen. It could be difficult for the compiler to tell whether count_nodes() return 0 or not, if the compiler must handle overflows. To handle this potential issue, 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…

#include <cstddef>

struct node {
    struct node *next;
    int payload;
};

size_t count_nodes(const node* p) {
    size_t size = 0;
    while (p) {
        p = p->next;
        size++;
        if(size == 1000) { 
            return 1000; 
        }
    }
    return size;
}

bool is_not_empty(const node* p) {
    return count_nodes(p) > 0;
}

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

The lesson is that it is probably wise to get in the habit of calling directly empty() if you care about performance. Though it may not help much with modern STL data structures, in other code it could be different.

Of course, another argument is that the call to empty()  is shorter and cleaner.

Credit: This blog post was motivated by a tweet by Richard Startin.

Daniel Lemire, "In C++, is empty() faster than comparing the size with zero?," in Daniel Lemire's blog, October 26, 2021, https://lemire.me/blog/2021/10/26/in-c-is-empty-faster-than-comparing-the-size-with-zero/.
[BibTeX]

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

20 thoughts on “In C++, is empty() faster than comparing the size with zero?”

  1. Still disappointed C++ and Rust containers don’t have a non_empty() method, and the Rust discussion fizzled out.

    Reply

  3. > the compiler figures out that as soon as you enter the loop once with count_nodes, then size is going to be greater than zero, so there is no need to keep looping.

    It could result in an endless loop, is it allowed to optimize that away? Also, it could wrap (to 0 for unsigned, or negative for signed). With 32 bit integers, it would be quite easy; with 64 bit, not sure how long it would take / memory size needed. Anyway, to me it looks like an incorrect optimization.

    The other case, with a limit on 1000, on the other hand, can be optimized away.

    Reply

    1. Ah I see, integer overflow causes undefined behaviour. And for endless loops: GCC assumes that a loop with an exit will eventually exit (option -ffinite-loops)

      Reply

      1. -ffinite-loops (or conversely -O2 -fno-finite-loops) does not affect the assembly output of the optimizable example in this article.

        Reply

    2. In C++, an infinite loop without side effects is Undefined Behavior, so the compiler is allowed to optimize it away.

      Reply

    3. Amazingly, yes! But only because the function has a signed return type. is_not_empty() specifically compares the return value of count_nodes() to 0, returning true if it’s greater or otherwise false. And inlining count_nodes() allows the compiler to observe that size can only increase and never decrease. Because signed values cannot overflow™, any situation which would cause an overflow is undefined behaviour, and can be handled however the compiler desires. Thus, if the number of nodes can be stored in an int, it can be compared to 0. And if it’s sufficiently large that it _can’t_ be stored in an int, then it invokes UB, allowing the compiler to just say that “if N > 0, then N+X > 0 because X is always positive”; it would overflow, but since it **can’t** overflow, the compiler must assume that the value is incomprehensibly positive. Thus, as size can never be smaller than 0, all UB cases are automatically > 0, and all cases where size is in the range of 1 to INTMAX (inclusive) are > 0, the only situation where is_not_empty() could possibly return false is when size is never increased. And that, in turn, allows the compiler to recognise that as size will always increase if the loop body is entered, any situation where the loop body enters will implicitly fail the check.

      This allows it to replace the loop body with while (p) { size = 1; break; }, which in turn allows the inlined count_nodes() to be flattened to something like int size = 0; if (p) size = 1; return size;, and then transformed into something like (p ? 1 : 0) for inlining purposes. (Because inlining allows the compiler to understand that we only care whether count_nodes() does or does not return 0 specifically, and thus allows it to treat all non-zero "return values" as 1.) Which means that is_not_empty() can be treated as having an effective body of return (p ? 1 : 0) > 0, and thus that the entire function is essentially a null pointer check with more work.

      In essence, the facts that 1) size can only increase and never decrease, 2) the function only cares whether size is greater than zero (and its actual value doesn't matter), and 3) signed variables are not allowed to overflow (thus any situation which causes signed overflow is UB), allow it to optimise infinite loops away. Because size can never decrease, any infinite loop will simply result in an infinitely positive value, and because there's no signed overflow, this infinitely positive value will never loop around, and will always be greater than zero. Thus, any situation which would cause signed overflow, such as an infinite loop, simply means that is_not_empty() will return true; importantly, it doesn't need to actually _enter_ the infinite loop to know this, because it knows that it's impossible™ for the loop to ever decrease size's value. Basically, if you ask someone that can only count to ten whether infinity is bigger than zero, they can answer "infinity is bigger than ten, so yes"; they don't need to actually count to infinity to figure it out, they just need to realise that infinity is bigger than they can count and stop there.

      ----

      Notably, this is also why changing count_nodes() to use an unsigned type removes is_not_empty()'s constant-time complexity. Unsigned values are allowed to overflow, and have defined wraparound behaviour when they do so. This means that sufficiently high sizes can, in fact, be exactly equal to zero, and thus it cannot make assumptions anymore. The signed version is constant-time because the compiler is allowed to use UB to make logical assumptions such as "numbers that can never decrease will never decrease", and ignore the hardware limitations in favour of the code's actual intent. The unsigned version has no UB for the compiler to work with, and also has known breakpoints where the signed assumption will be provably incorrect, forcing it to calculate an exact value instead of making assumptions about values too large to calculate. It's the same situation that allows compilers to realise that if x is signed, (x + 1) > x and x * 2 / 2 == x are always true if x is signed, even if the expression would cause signed overflow, as explained in LLVM's What Every C Programmer Should Know About Undefined Behavior article.

      Significantly, while infinite loops would also be UB, and could result in the compiler just discarding the entire true branch and forcing is_not_empty() to always return false, the compiler cannot actually _determine_ whether a loop would be infinite at compile time, off of the given information. For a loop to be infinite, a node would need to be linked to a node that's earlier in the list, which would only happen at runtime. Thus, for the compiler to do infinite loop optimisations, it would need to be able to prove that all node-based linked lists are infinite, which it cannot do with the given code. The best it could do would be to throw in a few runtime traps just in case, but it's unlikely that the optimiser would keep the traps in place. So, the compiler won't really care whether the loop is infinite or not, since it has no way to know.

      ----

      tl;dr: Basically, the compiler can't tell whether the loop is infinite or not, so the only UB it can see is signed overflow. Thus, any loop that _would_ be infinite is just a case of (x + 1) > x, and the compiler can determine that the answer is "true" regardless of whether the loop is infinite or not. Which then goes on to let the optimiser see that the _real_ question is whether (0 + x) > 0, and that entering the loop always results in x > 0, thus allowing it to determine that the entire function is just a "would we enter the loop?" check with more steps. (The unsigned version doesn't have that, though, forcing it to actually iterate over the list in case there are exactly enough nodes to overflow to 0. And even if we cap it to _n_, it still needs to run through the loop a maximum of _n_ times. Hence the unsigned version never seeing this optimisation.)

      Reply

  4. Maybe a typo? In the end of paragraph 2:
    > to find out the number of containers
    should probably be
    > to find out the number of elements

    Reply

  6. I’m not sure what the point of this article is. The author explicitly states “the people implementing the containers can never scan the content to find out the number of elements.”

    Then continues on to test against exactly what he described as against the rules. Its not hard to keep track of the size of a container via a class member variable. There is literally no need to scan the items. The empty() probably just returns the size as a bool. This entire discussion and article is pointless.

    Reply

    1. The author explicitly states “the people implementing the containers can never scan the content to find out the number of elements.”

      For STL containers.

      Here is the conclusion:

      The lesson is that it is probably wise to get in the habit of calling directly empty() if you care about performance. Though it may not help much with modern STL data structures, in other code it could be different.

      The assumption is that you will not just use STL containers in all of the code you are relying upon. Of course, if you are quite sure to only use recent STL containers, then you may consider the blog post pointless, but what makes you so sure?

      Reply

    2. The point of it is that empty() can sometimes be optimised more aggressively than size(), so we should assume that empty() is always at least as efficient as size() == 0, and sometimes more efficient. Thus, it’s better to get in the habit of doing the former and not the latter.

      Reply

  8. I have spent a bit too much time in Python, but I wish the STL containers had an implicit conversion to bool. That would be even less code than calling empty().

    Reply

    1. With that implementation, the count_nodes function returns 0 for an empty list and 1000 for a non-empty list. That is not what was meant for the overflow-preventing case.

      Reply

Leave a Reply

Your email address will not be published.

You can also subscribe by email to this blog (non-commercial, no ads, weekly email).

How to post code (C, C++, Java, Python, etc.):

Wrap your code in backticks, like this:

`int main() {
    return 0;
}`