Dlaczego GCC nie może zakładać, że rozmiar std :: vector :: nie zmieni się w tej pętli?

Zwróciłem się do współpracownika, if (i < input.size() - 1) print(0);który zoptymalizowałby się w tej pętli, aby input.size()nie był czytany przy każdej iteracji, ale okazuje się, że tak nie jest!

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

Według Compiler Explorera z opcjami gcc -O3 -fno-exceptionsczytamy input.size()każdą iterację i używamy leado odejmowania!

        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

Co ciekawe, w Rust występuje taka optymalizacja. Wygląda na to, że izostaje zastąpiony zmienną, jktóra jest zmniejszana przy każdej iteracji, a test i < input.size() - 1jest zastępowany przez coś podobnego 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);
        }
    }
}

W Eksploratorze kompilatorów odpowiedni zestaw wygląda następująco:

        cmpq    %r12, %rbx
        jae     .LBB0_4

Sprawdziłem i jestem prawie pewien, że r12jest xs.len() - 1i rbxjest licznikiem. Wcześniej istnieje pętla addfor rbxi movzewnętrzna dla pętli r12.

Dlaczego to? Wygląda na to, że jeśli GCC jest w stanie wprowadzić size()i operator[]tak jak miało to miejsce, powinien wiedzieć, że size()to się nie zmienia. Ale może optymalizator GCC ocenia, że ​​nie warto wyciągać go do zmiennej? A może jest jakiś inny możliwy efekt uboczny, który uczyniłby to niebezpiecznym - czy ktoś wie?

Nieliniowe wywołanie funkcji do cout.operator<<(int)jest czarną skrzynką dla optymalizatora (ponieważ biblioteka jest właśnie napisana w C ++ i wszystko, co widzi optymalizator, jest prototypem; patrz dyskusja w komentarzach). Musi zakładać, że każda pamięć, na którą może wskazywać zmienna globalna, została zmodyfikowana.

(Lub std::endlpołączenie. BTW, po co wymuszać kolor w tym momencie zamiast po prostu drukować '\n'?)

np . jak wiadomo, std::vector<int> &inputjest odwołaniem do zmiennej globalnej, a jedno z tych wywołań funkcji modyfikuje zmienną globalną . (Albo jest vector<int> *ptrgdzieś globalny , albo jest funkcja, która zwraca wskaźnik do static vector<int>jakiegoś innego urządzenia kompilacyjnego, lub w inny sposób, że funkcja może uzyskać odwołanie do tego wektora bez przekazywania nam przez niego odwołania.

Jeśli masz zmienną lokalną, której adres nigdy nie został pobrany, kompilator może założyć, że wywołania funkcji innych niż wbudowane nie mogą jej mutować. Ponieważ żadna zmienna globalna nie byłaby w stanie utrzymać wskaźnika do tego obiektu. ( To się nazywa Analiza ucieczki ). Dlatego kompilator może przechowywać size_t irejestr w wywołaniach funkcji. ( int imożna go po prostu zoptymalizować, ponieważ jest zasłonięty size_t ii nie jest używany w inny sposób).

To samo może zrobić z lokalnymi vector(tj. Dla wskaźników base, end_size i end_capacity).

ISO C99 ma rozwiązanie tego problemu: int *restrict foo. Wiele kompilacji C ++ obsługuje int *__restrict fooobietnicę, że pamięć wskazywana przez foojest dostępna tylko przez ten wskaźnik. Najczęściej przydatny w funkcjach, które zajmują 2 tablice i chcesz obiecać kompilatorowi, że się nie nakładają. Może więc automatycznie wektoryzować bez generowania kodu, aby to sprawdzić i uruchomić pętlę rezerwową.

Komentarze PO:

W Rust niezmienne odwołanie jest globalną gwarancją, że nikt inny nie mutuje wartości, do której masz odwołanie (odpowiednik C ++ restrict)

To wyjaśnia, dlaczego Rust może dokonać takiej optymalizacji, a C ++ nie.

Optymalizacja C ++

Oczywiście powinieneś użyć auto size = input.size();raz na górze swojej funkcji, aby kompilator wiedział, że jest to niezmienna pętla. Implementacje C ++ nie rozwiązują tego problemu, więc musisz to zrobić sam.

Może być również konieczne const int *data = input.data();podniesienie obciążenia wskaźnika danych z std::vector<int>„bloku kontrolnego”. To niefortunne, że optymalizacja może wymagać bardzo nieidiomatycznych zmian źródła.

Rust jest znacznie bardziej nowoczesnym językiem, zaprojektowanym po tym, jak twórcy kompilatorów dowiedzieli się, co było w praktyce możliwe dla kompilatorów. Naprawdę pokazuje to również na inne sposoby, w tym przenośnie odsłaniając niektóre fajne rzeczy, które procesory mogą zrobić poprzez i32.count_ones, obracanie, skanowanie bitów itp. To naprawdę głupie, że ISO C ++ nadal nie ujawnia żadnego z nich przenośnie, z wyjątkiem tego std::bitset::count().