Daniel Lemire's blog

, 11 min read

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

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

  1. nyanpasu64 says:

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

    1. Dmitry says:

      Have you considered writing `not array.empty()`?

  2. Alex says:

    The is_empty function in this blog post has an obvious mistake 🙂

  3. Thomas Müller Graf says:

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

    1. Thomas Müller Graf says:

      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)

      1. DimeCadmium says:

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

    2. Ilya says:

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

  4. pjhades says:

    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

    1. Yes. Thanks.

  5. Dennis says:

    Better?

    bool is_empty(const node* p) {
    return p ;
    }

    1. Dennis says:

      Er. return !p

  6. Mark says:

    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.

    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?

  7. Samuel says:

    thanks for bringing the awareness to us

  8. Walt N says:

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

  9. Josué Andrade Gomes says:

    I still prefer clarity and readability. I use empty() to show the intent to, well, check emptiness.

  10. John says:

    FYI: https://godbolt.org/z/bh3PMe8nG

    Seems like “<=" allows more optimizations than a simple "!="

    1. Maarten Bosmans says:

      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.