Почему G CC не может предположить, что std :: vector :: size не изменится в этом l oop? - PullRequest
Новая
       7

Почему G CC не может предположить, что std :: vector :: size не изменится в этом l oop?

14 голосов
/ 29 января 2020

Я утверждал коллеге, что if (i < input.size() - 1) print(0); будет оптимизирован в этом l oop, так что input.size() не читается на каждой итерации, но оказывается, что это не так! 

void print(int x) {
    std::cout << x << std::endl;
}

void print_list(const std::vector<int>& input) {
    int i = 0;
    for (size_t i = 0; i < input.size(); i++) {
        print(input[i]);
        if (i < input.size() - 1) print(0);
    }
}

Согласно Проводнику компилятора с параметрами g cc -O3 -fno-exceptions мы фактически читаем input.size() каждую итерацию и используем lea для выполнения вычитания! 

        movq    0(%rbp), %rdx
        movq    8(%rbp), %rax
        subq    %rdx, %rax
        sarq    $2, %rax
        leaq    -1(%rax), %rcx
        cmpq    %rbx, %rcx
        ja      .L35
        addq    $1, %rbx

Интересно, что в Rust такая оптимизация происходит. Похоже, i заменяется переменной j, которая уменьшается на каждой итерации, а тест i < input.size() - 1 заменяется чем-то вроде j > 0. 

fn print(x: i32) {
    println!("{}", x);
}

pub fn print_list(xs: &Vec<i32>) {
    for (i, x) in xs.iter().enumerate() {
        print(*x);
        if i < xs.len() - 1 {
            print(0);
        }
    }
}

в компиляторе Explorer соответствующая сборка выглядит следующим образом: 

        cmpq    %r12, %rbx
        jae     .LBB0_4

Я проверил, и я почти уверен, что r12 - это xs.len() - 1, а rbx - счетчик. Ранее add для rbx и mov вне l oop в r12.

Почему это? Похоже, что если G CC может встроить size() и operator[], как он это сделал, он должен знать, что size() не меняется. Но, может быть, оптимизатор G CC считает, что не стоит извлекать его в переменную? Или, может быть, есть какой-то другой возможный побочный эффект, который сделает это небезопасным - кто-нибудь знает?

1 Ответ

10 голосов
/ 29 января 2020

Не встроенный вызов функции cout.operator<<(int) является черным ящиком для оптимизатора (поскольку библиотека только что написана на C ++, а оптимизатор видит только прототип; см. Обсуждение в комментариях). Он должен предполагать, что любая память, на которую может указывать глобальная переменная, была изменена.

(Или вызов std::endl. Кстати, зачем вызывать грипп sh от cout в этой точке вместо просто напечатав '\n'?)

например, , насколько это известно, std::vector<int> &input является ссылкой на глобальную переменную, и один из этих вызовов функций изменяет эту глобальную переменную . (Или где-то есть глобальный vector<int> *ptr, или есть функция, которая возвращает указатель на static vector<int> в каком-то другом модуле компиляции, или каким-либо другим способом, которым функция может получить ссылку на этот вектор, не передавая ссылку на него нами.

Если бы у вас была локальная переменная, адрес которой никогда не был взят, компилятор мог бы предположить, что вызовы не встроенных функций не могли изменить его. способ для любой глобальной переменной хранить указатель на этот объект. ( Это называется Escape Analysis ). Вот почему компилятор может хранить size_t i в регистре при вызовах функций. ( int i можно просто оптимизировать, потому что он затенен size_t i и не используется иным образом.

Он может сделать то же самое с локальными vector (то есть для указателей base, end_size и end_capacity.)

ISO C99 имеет решение этой проблемы: int *restrict foo. Многие компиляторы C ++ поддерживают int *__restrict foo, обещая, что память, на которую указывает foo, только , доступ к которой осуществляется через этот указатель. Чаще всего полезно в функциях, которые принимают 2 массива, и вы хотите пообещать компилятору, что они не перекрываются. Таким образом, он может автоматически векторизовать, не генерируя код, чтобы проверить это и запустить запасной вариант l oop.

Комментарии OP:

В Rust неизменяемая ссылка является глобальная гарантия того, что никто не изменяет значение, на которое вы ссылаетесь (эквивалент C ++ restrict)

Это объясняет, почему Rust может выполнить эту оптимизацию, а C ++ - нет.

Оптимизация вашего C ++

Очевидно, вы должны использовать auto size = input.size(); один раз в верхней части вашей функции, чтобы компилятор знал, что он инвариант al oop. Реализации C ++ не решают эту проблему за вас, поэтому вы должны сделать это самостоятельно.

Вам также может понадобиться const int *data = input.data();, чтобы также поднять нагрузки указателя данных из std::vector<int> «блока управления» , К сожалению, оптимизация может потребовать очень неидиоматических c изменений исходного кода.

Rust - гораздо более современный язык, разработанный после того, как разработчики компиляторов узнали, что было возможно на практике для компиляторов. Это действительно показывает и другие способы, в том числе переносное раскрытие некоторых интересных вещей, которые процессоры могут делать через i32.count_ones, rotate, bit-scan и т. Д. c. Действительно глупо, что ISO C ++ до сих пор не раскрывает ничего из этого, кроме std::bitset::count().

...