https://lemire.me/blog/2021/10/26/in-c-is-empty-faster-than-comparing-the-size-with-zero/ Skip to content Daniel Lemire's blog Daniel Lemire is a computer science professor at the University of Quebec (TELUQ) in Montreal. His research is focused on software performance and data engineering. He is a techno-optimist and a free-speech advocate. Menu and widgets * My home page * My papers * My software Subscribe Email Address [ ] [ ] [Subscribe by email] You can also follow this blog on telegram. Where to find me? I am on Twitter and GitHub: Follow @lemire You can also find Daniel Lemire on * on Google Scholar with 4k citations and over 75 peer-reviewed publications, * on Facebook, * and on LinkedIn. Before the pandemic of 2020, you could meet Daniel in person, as he was organizing regular talks open to the public in Montreal: tribalab and technolab . Search for: [ ] [Search] Support my work! I do not accept any advertisement. However, you can support the blog with donations through paypal. Please consider getting in touch if you are a supporter so that I can thank you. Recent Posts * In C, how do you know if the dynamic allocation succeeded? * In C++, is empty() faster than comparing the size with zero? * Science and Technology links (October 23rd 2021) * Converting binary floating-point numbers to integers * Science and Technology links (October 16th 2021) Recent Comments * Walt N on In C++, is empty() faster than comparing the size with zero? * Jakub on In C, how do you know if the dynamic allocation succeeded? * Alexander Adler on In C, how do you know if the dynamic allocation succeeded? * Raivokas Ripuli on In C, how do you know if the dynamic allocation succeeded? * Samuel on In C++, is empty() faster than comparing the size with zero? Pages * A short history of technology * About me * Book recommendations * Cognitive biases * Interviews and talks * My bets * My favorite articles * My favorite quotes * My readers * My sayings * Predictions * Recommended video games * Terms of use * Write good papers Archives Archives [Select Month ] Boring stuff * Log in * Entries feed * Comments feed * WordPress.org In C++, is empty() faster than comparing the size with zero? 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. Obviously, 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 compilers 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 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. Published by [2ca999] Daniel Lemire A computer science professor at the University of Quebec (TELUQ). View all posts by Daniel Lemire Posted on October 26, 2021October 27, 2021Author Daniel Lemire Categories 14 thoughts on "In C++, is empty() faster than comparing the size with zero?" 1. [cf72c9] nyanpasu64 says: October 26, 2021 at 10:49 pm Still disappointed C++ and Rust containers don't have a non_empty () method, and the Rust discussion fizzled out. Reply 1. [64c8d0] Dmitry says: October 27, 2021 at 5:27 am Have you considered writing `not array.empty()`? Reply 2. [711667] Alex says: October 27, 2021 at 8:54 am The is_empty function in this blog post has an obvious mistake Reply 3. [f24a34] Thomas Muller Graf says: October 27, 2021 at 9:28 am > 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. [f24a34] Thomas Muller Graf says: October 27, 2021 at 9:58 am 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 2. [659497] Ilya says: October 27, 2021 at 1:18 pm In C++, an infinite loop without side effects is Undefined Behavior, so the compiler is allowed to optimize it away. Reply 4. [2b3a5c] pjhades says: October 27, 2021 at 1:09 pm 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 1. [2ca999] Daniel Lemire says: October 27, 2021 at 1:23 pm Yes. Thanks. Reply 5. [608b3a] Dennis says: October 27, 2021 at 1:17 pm Better? bool is_empty(const node* p) { return p ; } Reply 1. [608b3a] Dennis says: October 27, 2021 at 1:17 pm Er. return !p Reply 6. [ccafdd] Mark says: October 27, 2021 at 4:29 pm 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. [2ca999] Daniel Lemire says: October 27, 2021 at 4:38 pm 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 7. [a94527] Samuel says: October 27, 2021 at 6:35 pm thanks for bringing the awareness to us Reply 8. [1bf5de] Walt N says: October 28, 2021 at 8:16 pm 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 Leave a Reply Cancel reply Your email address will not be published. The comment form expects plain text. If you need to format your text, you can use HTML elements such strong, blockquote, cite, code and em. For formatting code as HTML automatically, I recommend tohtml.com. [ ] [ ] [ ] [ ] [ ] [ ] [ ] Comment [ ] Name * [ ] Email * [ ] Website [ ] [ ] Save my name, email, and website in this browser for the next time I comment. Receive Email Notifications? [no, do not subscribe ] [instantly ] Or, you can subscribe without commenting. [Post Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] Post navigation Previous Previous post: Science and Technology links (October 23rd 2021) Next Next post: In C, how do you know if the dynamic allocation succeeded? Proudly powered by WordPress