Also, the compiler doesn't know the structure find is traversing doesn't alias other objects (the key, for example). And it needs to pay attention to what side effects the compare functor might have (probably none, but not definitely none, without analysis).
Also, it's easy to write inherently efficient code that uses std::map, so compiler authors might not have seen optimising inefficient uses as a priority.
A quick with "gcc -S" shows you're right. I don't know if a whole program optimisation can do any better, although probably not.
I feel silly, because I've been generally trying to prioritise clarity over micro-optimisation, which normally means _not_ using an extra local variable (unless it makes it equally or more clear, as in some loops, or is necessary, as in cpu-bound inner loops) and now I wonder if I'm wrong.
I wonder, _should_ C++ be able to apply "const" somewhere to say "this function doesn't change any global or static state"? Would it help?
You can specify the const keyword when defining a class method, indicating that it's permissible to apply the method to a const instance of that class.
But the semantics aren't quite the same. It's easy to imagine functions that don't change any state and are safe to apply to a const object, but which nonetheless don't reliably return the same value if called twice. (For instance, a function that returns the number of nanoseconds until the object's expiry date, or one that returns the current contents of the file whose pathname is stored in the object. eta: or, come to think of it, a function that simply dereferences a pointer stored in the object! Much simpler, and no need to invoke the mysterious concurrency of the real world :-)
So you actually want a marker less like "const" and more like "pure", indicating that whatever the function does has no side effects and depends on only the obvious input values, so that the optimiser is permitted to assume that apparently identical calls to it are actually identical and fold them together.
const is a semantic contract, and an overloaded-function differentiator, which is more to ensure correctness for the benefit of user code than intended to be any help at all to the compiler.
Apart from overload resolution, I believe there is never any circumstance in which changing the constness of a function would affect how it compiled. In the very most extreme case, it might const_cast<MyType *>(this).
Conversely, except in the actually-quite-common case where polymorphic objects or function pointers impinge, the compiler could, in theory, recursively annotate functions with their purity. But take a look at just how deep the call stack gets when you say if (dictionary.count(key) && dictionary[key]==value), having regard to all the std::pair accessors, forwardings to the underlying red-black tree, std::less calls, etc. While determining purity and eliminating a richer set of common sub-expressions is conceptually possible, and might even be achievable in time better than O(n2) on program size, it's a tall order.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Also, it's easy to write inherently efficient code that uses std::map, so compiler authors might not have seen optimising inefficient uses as a priority.
I feel silly, because I've been generally trying to prioritise clarity over micro-optimisation, which normally means _not_ using an extra local variable (unless it makes it equally or more clear, as in some loops, or is necessary, as in cpu-bound inner loops) and now I wonder if I'm wrong.
I wonder, _should_ C++ be able to apply "const" somewhere to say "this function doesn't change any global or static state"? Would it help?
constkeyword when defining a class method, indicating that it's permissible to apply the method to aconstinstance of that class.But the semantics aren't quite the same. It's easy to imagine functions that don't change any state and are safe to apply to a const object, but which nonetheless don't reliably return the same value if called twice. (For instance, a function that returns the number of nanoseconds until the object's expiry date, or one that returns the current contents of the file whose pathname is stored in the object. eta: or, come to think of it, a function that simply dereferences a pointer stored in the object! Much simpler, and no need to invoke the mysterious concurrency of the real world :-)
So you actually want a marker less like "const" and more like "pure", indicating that whatever the function does has no side effects and depends on only the obvious input values, so that the optimiser is permitted to assume that apparently identical calls to it are actually identical and fold them together.
Apart from overload resolution, I believe there is never any circumstance in which changing the constness of a function would affect how it compiled. In the very most extreme case, it might const_cast<MyType *>(this).
Conversely, except in the actually-quite-common case where polymorphic objects or function pointers impinge, the compiler could, in theory, recursively annotate functions with their purity. But take a look at just how deep the call stack gets when you say if (dictionary.count(key) && dictionary[key]==value), having regard to all the std::pair accessors, forwardings to the underlying red-black tree, std::less calls, etc. While determining purity and eliminating a richer set of common sub-expressions is conceptually possible, and might even be achievable in time better than O(n2) on program size, it's a tall order.