9 ms·
In C++, is empty() faster than comparing the size with zero?
- sillycross 5y ago> Amazingly, we find that the GCC compilers is able to compile Travis’ is_empty C++ function to constant-time code. 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.
- joosters 5y agoMaybe I'm splitting hairs, but it's not specifically the presence of 'undefined behavior' that allows the compiler optimization. Instead, it's the language specification. The C spec says that integers cannot be relied upon to overflow. The result of this is that compilers are then free to assume that the program they are compiling has NO undefined behavior in it, and so the optimization is possible. 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.
- adrian_b 5y agoYou need not imagine an alternate version of C, such a version of C is provided by any decent C compiler. 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).
- bregma 5y ago> You need not imagine an alternate version of C, such a version of C is provided by any decent C compiler. 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.
- joosters 5y agoSaying 'this is what I will do when an int can't hold the assigned value' is defining the behavior, ergo it is no longer undefined! 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?
- bregma 5y ago> Saying 'this is what I will do when an int can't hold the assigned value' is defining the behavior, ergo it is no longer undefined! Defining the behaviour of a particular compiler under specific circumstances does not equate to defining the behaviour of the C language.
- joosters 5y agoYou are reading words that nobody wrote. No-one claimed that they were redefining the ‘C spec’ by passing flags to their compiler - the standards board’s job is still safe!
- adrian_b 5y agoI agree that leaving such important behavior as undefined is a failure for a programming language standard, because the standard fails to guarantee that a program will do the right things independently of what compiler has been used and with what compiler options. 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.
- minitech 5y ago> Then there would be no undefined behavior at all - but the optimization is still possible. 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.
- IshKebab 5y ago> 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. 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.
- caf 5y agoThis is correct. In the motivating example, it would have to scan the entire list of pointers to see whether it finds a NULL link before it overflows the size counter or not.
- joosters 5y agoAh, you're completely right, the compiler couldn't hid or assume away the aborts as they would now be part of the spec.
- em3rgent0rdr 5y agoI suppose it is a safe assumption that the counter will never overlow if memory space is not large enough to possibly hold the maximum positive integer number of data structs. Though if say was using a smaller int for size than what the hypothetical size that virtual memory could handle, such as a short int in a 32-bit memory system, then that assumption may not be true. But on a 64-bit linux system which only allows up to 128 TiB of virtual address space for individual processes, a 64-bit signed int could be as large as 2^63, which would be larger than the hypothetical maximum size that a 128 TiB virtual memory could reference, so the assumption that the size counter could never overflow would be safe.
- Noughmad 5y ago> It's actually an interesting example where undefined behavior allowed compiler optimization That is literally reason why any behavior is considered undefined. So that the compiler can skip checks to produce better optimized code.
- secondcoming 5y agoAnd so you get an optimal, but broken, program. This helps nobody.
- saagarjha 5y agoActually, many instances of undefined behavior are born out of a desire for portability. Some processors will fault on both of those and the standard wants to be inclusive of those behaviors. Compilers happen to be able to use the definition of undefined behavior to also optimize code, but the concept is born out of practicality.
- ufo 5y agoThe most impressive example I've ever seen of this kind of compiler cleverness is the following function from the "convoluted isEven" competition: bool isEven(int n) { return n == 0 || !isEven(n + 1); } Clang somehow optimizes it to a constant-time implementation, even if we use "unsigned"! https://gcc.godbolt.org/z/nGbn1T https://gcc.godbolt.org/z/nGbn1T
- whimsicalism 5y agoIs this code not relying on UB? Seems like it could/should be optimized to `return true`
- carnitine 5y agoWhat’s the UB?
- deleted 5y ago[deleted]
- whimsicalism 5y agoCalling it on any positive int causes signed integer overflow, which is UB.
- nawgz 5y agosigned integer overflow for positive N
- edflsafoiewq 5y agoIt's only UB for positive n. For negative n, it is an is-even test, so it can't be optimized to return true.
- whimsicalism 5y agoOh yeah - negative numbers exist, doh!
- 5y ago
- thamer 5y agoIt's interesting that size() has to be constant-time. From what I understand of the standard linked from the blog post, it looks like size() being constant-time is a property of Container and not each individual method (§ 23.2.1, page 747). 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?
- plorkyeran 5y agoThe standard's requirements for the standard library types don't imply any corresponding requirement for types you define yourself. If you want to write a container which can't reasonably do O(1) size() then you just don't do O(1) size(). If such a container was added to the standard library, the standard library's Container requirements will be adjusted to permit that.
- chakkepolja 5y agoExactly, most STL algorithms, for example, can be applied using iterators as well. But anyway if GP has specific requirements iterator invalidation might be a problem too, they wouldn't probably want to constrain their interface to that of STL containers.
- tialaramex 5y agoWait, isn't the point of the STL algorithms that they use iterators? 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.
- fhrow4484 5y ago
- jb1991 5y agoThis was just discussed yesterday also: https://news.ycombinator.com/item?id=29007821 https://news.ycombinator.com/item?id=29007821
- loup-vaillant 5y agoIf you’re actually at the point where you care about that kind of performance, you may want to shy away from the STL, and use (or write) something simpler instead.
- TillE 5y agoI've always hated this bit of conventional wisdom, which has become less and less applicable over the past couple decades. STL implementations are now quite highly optimized within their spec. With the one little caveat that they're generally optimized for CPU cycles rather than per object memory usage. 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.
- glandium 5y agoI thought the conventional wisdom was to avoid the STL if you need consistent performance across platforms, because they all have different pitfalls. Things might be different with libc++, now, though, since you can use it in most cases.
- loup-vaillant 5y agoMy point exactly: I can trust the STL’s standardised interface, but performance is often dependent on implementation details, which are bound to vary from platform to platform, or even from computer to computer (assuming a dynamically linked libc++).
- kllrnohj 5y ago> std::vector is super fast for basically everything except for dynamic resizing. 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/container/inlined_vector.h 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
- papito 5y agoIn a Wooooorld, where newer generation of developers does not grasp the concept of database indexes, and network latency is assumed to be zero, one man.....
- robomartin 5y agoIf you work in real time embedded systems you become aware of code constructs that will deliver better performance. I always study the instruction set to see what tools it might reveal. For example, most people might write something like this (pseudocode, "MAX" being a constant): for i=0; i < MAX; i++ <some code> On most processors this runs faster: for i=MAX; i != 0; i-- <some code> This is because most processors have the equivalent of a "CJNZ" or "CJZ" (Compare and Jump if Not Zero; Compare and Jump if Zero) instruction. It is much faster (generally one clock cycle) to determine if the value in a register or accumulator is zero than to load multiple registers and determine "less than" or "less than or equal to". As far as I know, these are not optimizations a compiler is capable of.
- mhh__ 5y agoThat depends if the loop has side effects such that the optimization would be unsound. 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
- ladberg 5y agoThat's absolutely something a compiler can do, and it's easily verifiable: https://godbolt.org/z/3Tze5q594 https://godbolt.org/z/3Tze5q594
- gumby 5y ago> As far as I know, these are not optimizations a compiler is capable of. 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?)
- saagarjha 5y agoCompilers can and do perform these optimizations; they maintain internal tables of instruction costs that guide what code is emitted. It’s just that modern processors don’t really have these kinds of differences, and the ones that do are generally not amenable to high-level compilers for other reasons (extreme register pressure, etc.)
- not2b 5y agoNot all O(1) functions have the same cost. Suppose we have a container that stores its data on the heap, and has a null pointer and no heap object when it is empty. Then Container::empty() const just needs to check that pointer, where Container::size() const has to read the size out of the heap object, so c.size() == 0 has to cost more, as the compiler is unlikely to be able to optimize away the extra accesses.
- deleted 5y ago[deleted]
- avianes 5y ago> 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… size_t count_nodes(const node* p) { size_t size = 0; while (p) { p = p->next; size++; if(size == 1000) return 1000; } return size; } > Sadly, GCC is now unable to optimize away the call. Maybe compilers are not yet all powerful beings? 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; } https://godbolt.org/z/YKWbWb5zr https://godbolt.org/z/YKWbWb5zr