Still disappointed C++ and Rust containers don’t have a non_empty() method, and the Rust discussion fizzled out.
Dmitrysays:
Have you considered writing `not array.empty()`?
Alexsays:
The is_empty function in this blog post has an obvious mistake 🙂
Thomas Müller Grafsays:
> 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.
Thomas Müller Grafsays:
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)
DimeCadmiumsays:
-ffinite-loops (or conversely -O2 -fno-finite-loops) does not affect the assembly output of the optimizable example in this article.
Ilyasays:
In C++, an infinite loop without side effects is Undefined Behavior, so the compiler is allowed to optimize it away.
pjhadessays:
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
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.
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?
Samuelsays:
thanks for bringing the awareness to us
Walt Nsays:
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().
Josué Andrade Gomessays:
I still prefer clarity and readability. I use empty() to show the intent to, well, check emptiness.
Seems like “<=" allows more optimizations than a simple "!="
Maarten Bosmanssays:
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.
Still disappointed C++ and Rust containers don’t have a non_empty() method, and the Rust discussion fizzled out.
Have you considered writing `not array.empty()`?
The is_empty function in this blog post has an obvious mistake 🙂
> 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.
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)
-ffinite-loops (or conversely -O2 -fno-finite-loops) does not affect the assembly output of the optimizable example in this article.
In C++, an infinite loop without side effects is Undefined Behavior, so the compiler is allowed to optimize it away.
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
Yes. Thanks.
Better?
bool is_empty(const node* p) {
return p ;
}
Er. return !p
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.
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 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?
thanks for bringing the awareness to us
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().
I still prefer clarity and readability. I use empty() to show the intent to, well, check emptiness.
FYI: https://godbolt.org/z/bh3PMe8nG
Seems like “<=" allows more optimizations than a simple "!="
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.