Optymalizowanie mutowalnych i niezmiennych wektorów matematycznych

Question

Który styl kodowania najlepiej nadaje się do optymalizacji kompilatora? W szczególności interesuje mnie 1) minimalizowanie liczby tymczasowych wartości, które są natychmiast odrzucane, oraz 2) automatyczna wektoryzacja, tj. Generowanie instrukcji SIMD dla arytmetyki.

Załóżmy, że ma tej struktury:

#define FOR_EACH for (int i = 0; i < N; ++i) 

template<typename T, unsigned N> 
struct Vector { 
    void scale(T scalar) { 
     FOR_EACH v[i] *= scalar; 
    } 

    void add(const Vector<T, N>& other) { 
     FOR_EACH v[i] += other.v[i]; 
    } 

    void mul(const Vector<T, N>& other) { 
     FOR_EACH v[i] *= other.v[i]; 
    } 

    T v[N]; 
}; 

Przykład zastosowania tej struktury:

Vector<int, 3> v1 = ...; 
Vector<int, 3> v2 = ...; 
v1.scale(10); 
v1.add(v2); 
v1.mul(v2); 

To podejście jest zmienny.

Alternatywą niezmienne podejście mogłoby wyglądać tak:

template<typename T, unsigned N> 
struct Vector { 
    Vector(const Vector<T, N>& other) { 
     memcpy(v, other.v, sizeof(v)); 
    } 

    Vector<T, N> operator+(const Vector<T, N>& other) const { 
     Vector<T, N> result(*this); 
     FOR_EACH result.v[i] += other.v[i]; 
     return result; 
    } 

    Vector<T, N> operator*(T scalar) const { 
     Vector<T, N> result(*this); 
     FOR_EACH result.v[i] *= scalar; 
     return result; 
    } 

    Vector<T, N> operator*(const Vector<T, N>& other) const { 
     Vector<T, N> result(*this); 
     FOR_EACH result.v[i] *= other.v[i]; 
     return result; 
    } 

    T v[N]; 
}; 

Przykład użycia:

Vector<int, 3> v1 = ...; 
Vector<int, 3> v2 = ...; 
auto result = (v1 * 10 + v2) * v2; 

---

Teraz nie jestem zaniepokojony z projektu API w tym pytaniu. Załóżmy, że oba rozwiązania są opłacalne w tym względzie.

Również zamiast int w kodzie przykładowym może być również float lub double.

Co mnie interesuje, to: który projekt może być łatwiej przeanalizowany przez nowoczesny kompilator C++? Nie koncentruję się na żadnym konkretnym kompilatorze. Jeśli masz doświadczenie z dowolnym kompilatorem i wiesz, jak radzi sobie z optymalizacjami, o które pytam, podziel się swoim doświadczeniem.

• Druga wersja produkuje wiele wartości tymczasowych. Czy kompilator może się ich pozbyć, jeśli w ostatecznym rozrachunku włącza wszystkie wywołania operatora i widzi wszystkie wyrażenia arytmetyczne w nich zawarte? (Zakładam, że bez wstawiania żaden kompilator nie może wyeliminować tymczasowych ze względu na możliwe efekty uboczne).

• Pierwsza wersja minimalizuje liczbę tymczasowych, ale konstruuje ściśle sekwencyjne obliczenia. Czy kompilator nadal może wydedukować intencje i zmienić kolejność operacji w sposób, który minimalizuje liczbę operacji i pozwala na ich równoległość (na poziomie instrukcji CPU)?

• Jak trudne jest dla współczesnego kompilatora wektoryzować powyższe pętle?

Answer 1

O ile rozumiem, pierwszy przykład jest łatwy do wektoryzacji, o ile istnieje wsparcie w docelowej architekturze. Dzieje się tak dlatego, że w kolejnych iteracjach nie ma zależności danych między elementami.

Jeśli masz pętle, w których występują zależności między elementami w kolejnej iteracji, w niektórych przypadkach można je usunąć za pomocą pipeline. Programowanie potokowe pomaga w wektoryzacji.

W niektórych architekturach obliczenia zmiennoprzecinkowe nie są łatwe do wykalibrowania ze względu na ograniczone jednostki wykonawcze zmiennoprzecinkowe.

W drugim przykładzie są tymczasowe, które można wyeliminować przez wstawianie.

Przydatne linki:

http://software.intel.com/en-us/articles/vectorization-writing-cc-code-in-vector-format

http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=1540953&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D1540953