Por que o GCC não pode assumir que std :: vector :: size não será alterado nesse loop?

Afirmei a um colega de trabalho que if (i < input.size() - 1) print(0);seria otimizado nesse loop para que input.size()não seja lido em todas as iterações, mas acontece que esse não é o caso!

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

De acordo com o Compiler Explorer com as opções gcc -O3 -fno-exceptions, na verdade, estamos lendo input.size()cada iteração e usando leapara executar uma subtração!

        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

Curiosamente, no Rust, essa otimização ocorre. Parece que ié substituído por uma variável jque é decrementada a cada iteração, e o teste i < input.size() - 1é substituído por algo parecido 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);
        }
    }
}

No Explorer do compilador, o assembly relevante se parece com isso:

        cmpq    %r12, %rbx
        jae     .LBB0_4

Eu verifiquei e tenho certeza que r12é xs.len() - 1e rbxé o contador. Anteriormente, há um addfor rbxe um movfora do loop r12.

Por que é isso? Parece que, se o GCC for capaz de alinhar o size()e, operator[]como fez, deve saber que size()isso não muda. Mas talvez o otimizador do GCC julgue que não vale a pena puxá-lo para uma variável? Ou talvez haja algum outro efeito colateral possível que tornaria isso inseguro - alguém sabe?

A função não-inline chamada para cout.operator<<(int)é uma caixa preta para o otimizador (porque a biblioteca é apenas escrita em C ++ e tudo o que o otimizador vê é um protótipo; consulte a discussão nos comentários). Ele deve assumir que qualquer memória que possa ser apontada por um var global foi modificada.

(Ou a std::endlchamada. BTW, por que forçar um flush de cout nesse ponto em vez de apenas imprimir um '\n'?)

por exemplo, pelo que sabemos, std::vector<int> &inputé uma referência a uma variável global e uma dessas chamadas de função modifica essa variável global . (Ou há um global em vector<int> *ptralgum lugar, ou há uma função que retorna um ponteiro para a static vector<int>em alguma outra unidade de compilação, ou de alguma outra maneira que uma função possa obter uma referência a esse vetor sem que seja passada uma referência a ele por nós.

Se você tivesse uma variável local cujo endereço nunca tivesse sido usado, o compilador poderia assumir que chamadas de função não embutidas não poderiam modificá-la. Porque não haveria maneira de nenhuma variável global manter um ponteiro para esse objeto. ( Isso é chamado de Análise de escape ). É por isso que o compilador pode manter size_t ium registro nas chamadas de função. ( int ipode simplesmente ser otimizado porque é ocultado size_t ie não usado de outra forma).

Poderia fazer o mesmo com um local vector(ou seja, para os ponteiros base, end_size e end_capacity.)

ISO C99 tem uma solução para este problema: int *restrict foo. Muitas compilações de C ++ oferecem suporte int *__restrict foopara prometer que a memória apontada por fooé acessada apenas por esse ponteiro. Mais comumente útil em funções que levam 2 matrizes e você deseja prometer ao compilador que elas não se sobrepõem. Portanto, ele pode se auto-vetorizar sem gerar código para verificar isso e executar um loop de fallback.

O OP comenta:

No Rust, uma referência não mutável é uma garantia global de que ninguém mais está alterando o valor ao qual você tem uma referência (equivalente a C ++ restrict)

Isso explica por que o Rust pode fazer essa otimização, mas o C ++ não.

Otimizando seu C ++

Obviamente, você deve usar auto size = input.size();uma vez no topo de sua função para que o compilador saiba que é um loop invariável. As implementações de C ++ não resolvem esse problema para você, então você deve fazer isso sozinho.

Também pode ser necessário const int *data = input.data();elevar cargas do ponteiro de dados do std::vector<int>"bloco de controle". É lamentável que a otimização possa exigir alterações muito não-idiomáticas da fonte.

Rust é uma linguagem muito mais moderna, projetada após os desenvolvedores de compiladores aprenderem o que era possível na prática para compiladores. Isso realmente mostra em outras maneiras, também, incluindo portably expondo alguns dos fresco CPUs coisas pode fazer via i32.count_ones, girar, bit-scan, etc. É realmente estúpido que a ISO C ++ ainda não expõe qualquer um destes portably, exceto std::bitset::count().