Seemingly missing optimization for calling const-vector size() in loop condition

Question

Consider the following code:

int g(std::vector<int>&, size_t);

int f(std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0; i < v.size(); i++)
      res += g(v, i);
   return res;
}

The compiler cannot optimize away the evaluation of v.size() within the loop, since it cannot prove that the size won't change inside g. The assembly generated with GCC 9.2, -O3, and x64 is:

.L3:
    mov     rsi, rbx
    mov     rdi, rbp
    add     rbx, 1
    call    g(std::vector<int, std::allocator<int> >&, unsigned long)
    add     r12d, eax
    mov     rax, QWORD PTR [rbp+8] // load a poniter
    sub     rax, QWORD PTR [rbp+0] // subtract another pointetr
    sar     rax, 2                 // result * sizeof(int) => size()
    cmp     rbx, rax
    jb      .L3

If we know that g does not alter v.size(), we can rewrite the loop as follows:

for (size_t i = 0, e = v.size(); i < e; i++)
   res += g(v);

This generates simpler (and thus faster) assembly without those mov, sub, and sar instructions. The value of size() is simply kept in a register.

I would expect that the same effect could be achieved by making the vector const (I know it's changing the semantics of the program since g now cannot alter vector's elements, but this should be irrelevant to the question):

int g(const std::vector<int>&, size_t);

int f(const std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0; i < v.size(); i++)
      res += g(v, i);
   return res;
}

Now, the compiler should know that those pointers loaded in each loop iteration cannot change and, therefore, that the result of

    mov     rax, QWORD PTR [rbp+8] 
    sub     rax, QWORD PTR [rbp+0] 
    sar     rax, 2

is always the same. Despite that, these instructions are present in the generated assembly; live demo is here.

I have also tried Intel 19, Clang 9, and MSVC 19 with the very same results. Since all the mainstream compilers behave in such a uniform way, I wonder whether there is some rule that disallows this kind of optimization, i.e., moving the evaluation of size() for a constant vector out of the loop.

@slepic This very much depends on the operations performed inside the loop. For instance, in my (academic) case, `g` requires and index as a second argument. Another case generally complicated for iterators is when you need to access multiple vector elements in each iteration. — Daniel Langr, Oct 25 '19 at 07:54
But that should not be a problem. `res=0; i=0; for(auto& val : v) {res+=g(val,v,i); ++i;}` — slepic, Oct 25 '19 at 07:58
or another solution would be to just move the size evaluation out of the loop condition explicitly. `auto size=v.size(); for(size_t i=0; i — slepic, Oct 25 '19 at 08:02
@slepic That's what my second loop version does. However, the question is not about how to iterate over vector elements. The question is about seemingly (for me) missing optimizations. I may easily come up with a use case where there is no loop at all. Such as `v.size(); g(v); v.size();` — can `v.size()` be evaluated only once? The same problem. — Daniel Langr, Oct 25 '19 at 08:06

Max Langhof · Accepted Answer · 2019-10-25T07:50:34.633

Adding const does not mean that g cannot change the size of the vector. Sadly.

You get UB if you modify an object that is itself const. Modifying an object to which you have a const reference is not UB, as long as the original (i.e. referenced) object is not const.

In other words, this is a valid program:

int g(const std::vector<int>& v, size_t)
{
    const_cast<std::vector<int>&>(v).clear();
    return 0;
}

int f(const std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0; i < v.size(); i++)
      res += g(v, i);
   return res;
}

void test()
{
    std::vector<int> v;
    f(v);
}

Note that, if we cannot see the definition of g, the const doesn't even matter even if we disallowed const_cast:

std::vector<int> global_v;

int g(const std::vector<int>& v, size_t)
{
    global_v.clear();
    return 0;
}

int f(const std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0; i < v.size(); i++)
      res += g(v, i);
   return res;
}

void test()
{
    f(global_v);
}

Consider const on references as a reminder and compiler-enforced safeguard for yourself (and others), but not so much as an optimization opportunity for the compiler. However, marking values/objects as const themselves has decent chances of improving optimizations - passing an actual const Something to an opaque function guarantees that Something holds the same thing afterwards (but note that const is not transitive through e.g. pointer or reference members).

Ty, I didn't know that a non-const object bound to a const reference may be modified via `const_cast` applied to that reference. That explains it perfectly, and I did learn something new today :) — Daniel Langr, Oct 25 '19 at 07:49
@bartop To learn something that shouldn't be used is very usefull ;) — Daniel Langr, Oct 25 '19 at 07:59
@bartop There are fringe cases where it makes sense to use it. See e.g. https://stackoverflow.com/questions/123758/how-do-i-remove-code-duplication-between-similar-const-and-non-const-member-func. I'd prefer a higher level way to avoid code duplication between const/non-const member function pairs (e.g. similar to template noexcept stuff) but this is what we have for now. — Max Langhof, Oct 25 '19 at 08:03
@bartop I (and Daniel, I guess) thought that you were referring to `const_cast`, not global mutable state, when you said "should not be used". It's ambiguous. — Max Langhof, Oct 25 '19 at 11:54

score 4 · Answer 2 · answered Oct 25 '19 at 07:41

Sad truth is const in function parameters is not that useful for optimization. Imagine code like this (I know it is not good practice and so forth but for the sake of argument):

int g(const std::vector<int>&v){
    const_cast<std::vector<int> &>(v).push_back(1);
    return 0;
}

int f(const std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0; i < v.size(); i++)
      res += g(v);
   return res;
}

int main(){
    std::vector<int> v{1, 2, 3};
    return f(v);
}

If vector passed to f is not const itself, this is legal code.

Seemingly missing optimization for calling const-vector size() in loop condition

2 Answers2