Кажется, отсутствует оптимизация для вызова const-vector size () в состоянии цикла - PullRequest
Новая
       14

Кажется, отсутствует оптимизация для вызова const-vector size () в состоянии цикла

4 голосов
/ 25 октября 2019

Рассмотрим следующий код: 

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;
}

Компилятор не может оптимизировать оценку v.size() в цикле, поскольку он не может доказать, что размер не изменится внутри g. Сборка, сгенерированная с помощью GCC 9.2, -O3 и x64: 

.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

Если мы знаем, что g не изменяет v.size(), мы можем переписать цикл следующим образом: 

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

Создает более простую (и, следовательно, более быструю) сборку без этих инструкций mov, sub и sar. Значение size() просто хранится в регистре.

Я ожидаю, что тот же эффект может быть достигнут путем создания вектора const (я знаю, что это меняет семантику программы, поскольку gтеперь не может изменять элементы вектора, но это не должно относиться к вопросу): 

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;
}

Теперь компилятор должен знать, что эти указатели, загруженные в каждой итерации цикла, не могут измениться и, следовательно, результат 

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

всегда одинаково. Несмотря на это, эти инструкции присутствуют в сгенерированной сборке;Демо-версия здесь .

Я также попробовал Intel 19, Clang 9 и MSVC 19 с теми же результатами. Поскольку все основные компиляторы ведут себя одинаково, Интересно, есть ли какое-то правило, запрещающее этот вид оптимизации, т. Е. Выведение оценки size() для постоянного вектора из цикла .

Ответы [ 2 ]

6 голосов
/ 25 октября 2019

Добавление const не означает, что g не может изменить размер вектора. К сожалению.

Вы получите UB, если измените объект, который сам по себе const. Изменение объекта, на который у вас есть ссылка const, не является UB, если исходный (то есть ссылочный) объект не является const.

Другими словами, это допустимая программа: 

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);
}

Обратите внимание, что, если мы не можем увидеть определение g, const даже не имеет значения, даже если мы запретим 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);
}

Рассматривайте const для ссылок как напоминание и принудительную защиту для себя (и других), но не столько как возможность оптимизации для компилятора. Однако маркировка значений / объектов как const сама по себе имеет хорошие шансы на улучшение оптимизации - передача фактического const Something в непрозрачную функцию гарантирует, что Something будет содержать то же самое впоследствии (но обратите внимание, что const не является транзитивным, например, черезуказатель или ссылочные элементы).

4 голосов
/ 25 октября 2019

Грустная правда в том, что const в параметрах функции не так уж полезен для оптимизации. Представьте себе код, подобный этому (я знаю, что это не хорошая практика и так далее, но ради аргумента): 

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);
}

Если вектор, переданный в f, не является const сам по себе, это юридический код.

...