Pole dostęp za pośrednictwem tablicy jest wolniejszy dla typów z kilku pól

Question

Poniżej krótki, ale kompletny przykładowy program

const long iterations = 1000000000; 

T[] array = new T[1 << 20]; 
for (int i = 0; i < array.Length; i++) 
{ 
    array[i] = new T(); 
} 

Stopwatch sw = Stopwatch.StartNew(); 
for (int i = 0; i < iterations; i++) 
{ 
    array[i % array.Length].Value0 = i; 
} 

Console.WriteLine("{0,-15} {1} {2:n0} iterations/s", 
    typeof(T).Name, sw.Elapsed, iterations * 1000d/sw.ElapsedMilliseconds); 

z T zastąpiony przez następujące typy

class SimpleClass     struct SimpleStruct 
{         { 
    public int Value0;     public int Value0; 
}         } 

class ComplexClass     struct ComplexStruct 
{         { 
    public int Value0;     public int Value0; 
    public int Value1;     public int Value1; 
    public int Value2;     public int Value2; 
    public int Value3;     public int Value3; 
    public int Value4;     public int Value4; 
    public int Value5;     public int Value5; 
    public int Value6;     public int Value6; 
    public int Value7;     public int Value7; 
    public int Value8;     public int Value8; 
    public int Value9;     public int Value9; 
    public int Value10;     public int Value10; 
    public int Value11;     public int Value11; 
}         } 

daje następujące interesujące wyniki na moim komputerze (Windows 7 .NET 4.5 32-bitowy)

 
SimpleClass  00:00:10.4471717 95,721,260 iterations/s 
ComplexClass  00:00:37.8199150 26,441,736 iterations/s 
SimpleStruct  00:00:12.3075100 81,254,571 iterations/s 
ComplexStruct 00:00:32.6140182 30,661,679 iterations/s 

Pytanie 1: Dlaczego numer ComplexClass jest o wiele wolniejszy niż SimpleClass? Wydłużony czas wydaje się wzrastać liniowo wraz z liczbą pól w klasie. Zapis na pierwszym polu klasy z dużą ilością pól nie powinien być bardzo różny od zapisu do pierwszego pola klasy z tylko jednym polem, nie?

Pytanie 2: Dlaczego jest ComplexStruct wolniejsza niż SimpleStruct? Spojrzenie na kod IL pokazuje, że i jest zapisywane bezpośrednio do tablicy, a nie do lokalnej instancji ComplexStruct, która jest następnie kopiowana do tablicy. Tak więc nie powinno być żadnych kosztów ogólnych związanych z kopiowaniem kolejnych pól.

Pytanie dodatkowe: Dlaczego numer ComplexStruct jest szybszy niż ComplexClass?

---

Edit: Zaktualizowane wyniki badań o mniejszej tablicy T[] array = new T[1 << 8];:

 
SimpleClass  00:00:13.5091446 74,024,724 iterations/s 
ComplexClass  00:00:13.2505217 75,471,698 iterations/s 
SimpleStruct  00:00:14.8397693 67,389,986 iterations/s 
ComplexStruct 00:00:13.4821834 74,172,971 iterations/s 

więc praktycznie żadnej różnicy między SimpleClass i ComplexClass, a tylko niewielka różnica między SimpleStruct i ComplexStruct. Jednak wydajność znacznie spadła dla SimpleClass i SimpleStruct.

---

Edit: A teraz z T[] array = new T[1 << 16];:

 
SimpleClass  00:00:09.7477715 102,595,670 iterations/s 
ComplexClass  00:00:10.1279081 98,745,927 iterations/s 
SimpleStruct  00:00:12.1539631 82,284,210 iterations/s 
ComplexStruct 00:00:10.5914174 94,419,790 iterations/s 

Wynik dla 1<<15 jest jak 1<<8, a wynik dla 1<<17 jest jak 1<<20.

Answer 1

możliwa odpowiedź na pytanie 1:

Twój CPU odczytuje pamięci do pamięci podręcznej strony naraz.

Przy większym typie danych można dopasować mniej obiektów do każdej strony pamięci podręcznej. Nawet jeśli piszesz tylko jedną wartość 32-bitową, nadal potrzebujesz strony w pamięci podręcznej procesora. W przypadku mniejszych obiektów można przejść przez kolejne pętle, zanim będzie trzeba odczytać z pamięci głównej.

Answer 2

Nie posiadam dokumentacji potwierdzającej to, ale przypuszczam, że może to być kwestia lokalizacji. Będąc złożonymi klasami szerszymi pod względem pamięci, dostęp do odległych obszarów pamięci, sterty lub stosu zajmie dłużej jądro. Żeby być obiektywnym, muszę powiedzieć, że różnica między twoimi miarami brzmi naprawdę wysoko, ponieważ problem jest winą systemu.

O różnicy między klasami i strukturami nie mogę tego również udokumentować, ale może być tak dlatego, że na tej samej zasadzie co wcześniej stos jest buforowany częściej niż regiony sterty, co prowadzi do mniejszej liczby pomyłek w pamięci podręcznej.

Czy uruchomiłeś program z aktywnymi optymalizacjami?

Edycja: dokonaniu niewielkiej test na ComplexStruct i wykorzystywane StructLayoutAttribute z LayoutKind.Explicit jako parametru, następnie dodano FieldOffsetAttribute z 0 jako parametr do każdej dziedziny konstrukcji. Czasy zostały znacznie zredukowane i myślę, że były w przybliżeniu takie same jak te z SimpleStruct. Uruchomiłem go w trybie debugowania, debugger włączony, bez optymalizacji. Podczas gdy struktura zachowała swoje pola, jej wielkość w pamięci została obcięta, podobnie jak czasy.

Answer 3

Odpowiedź 1: ComplexClass jest wolniejszy następnie SimpleClass bo cache CPU jest stałym rozmiarze, więc mniej ComplexClass obiekty mieszczą się w pamięci podręcznej w czasie. Zasadniczo widzisz wzrost ze względu na czas wymagany do pobrania z pamięci. To może być bardziej jasne (extream), jeśli przejdziesz do pamięci podręcznej i zmniejszysz szybkość swojej pamięci RAM.

Odpowiedź 2: Tak samo jak w przypadku odpowiedzi 1.

Bonus: Tablica struktur jest ciągłym blokiem struktur, do którego odwołuje się tylko wskaźnik tablicy. Tablica klas jest ciągłym blokiem odwołań do instancji klasy, do których odwołuje się wskaźnik tablicy. Ponieważ klasy są tworzone na stercie (w zasadzie tam, gdzie zawsze jest miejsce), nie są one w jednym ciągłym i uporządkowanym bloku. Jest to świetne rozwiązanie do optymalizacji przestrzeni, ale jest złe w przypadku buforowania procesora. W rezultacie, podczas iteracji przez tablicę (w kolejności) będzie więcej braków pamięci podręcznej procesora z dużą tablicą wskaźników do dużych klas, a następnie będzie istniała kolejność iteracji tablicy struktur.

Dlaczego SimpleStruct jest wolniejszy następnie SimpleClass: Z tego, co rozumiem, jest kwota narzutu na elemencie (gdzieś około 76 ukąszeń mi powiedziano). Nie jestem pewien, co to jest i dlaczego tam jest, ale spodziewam się, że jeśli miałbyś uruchomić ten sam test używając natywnego kodu (skompilowanego w C++), zobaczyłbyś, że macierz SimpleStruct działa lepiej. Ale to tylko zgadnij.

---

Tak czy inaczej, wygląda to interesująco. Mam zamiar wypróbować to dziś wieczorem. Opublikuję moje wyniki. Czy można uzyskać kompletny kod?

Answer 4

Zmodyfikowałem twój benchmark trochę, by usunąć moduł, który prawdopodobnie odpowiada za dużą część zużywanego czasu, i wydajesz się porównywać czasy dostępu do pól, a nie arytmetyki int modulus.

const long iterations = 1000; 
    GC.Collect(); 
    GC.WaitForPendingFinalizers(); 
    //long sMem = GC.GetTotalMemory(true); 
    ComplexStruct[] array = new ComplexStruct[1 << 20]; 
    for (int i = 0; i < array.Length; i++) { 
     array[i] = new ComplexStruct(); 
    } 
    //long eMem = GC.GetTotalMemory(true); 
    //Console.WriteLine("memDiff=" + (eMem - sMem)); 
    //Console.WriteLine("mem/elem=" + ((eMem - sMem)/array.Length)); 
    Stopwatch sw = Stopwatch.StartNew(); 
    for (int k = 0; k < iterations; k++) { 
     for (int i = 0; i < array.Length; i++) { 
      array[i].Value0 = i; 
     } 
    } 
    Console.WriteLine("{0,-15} {1} {2:n0} iterations/s", 
     typeof(ComplexStruct).Name, sw.Elapsed, (iterations * array.Length) * 1000d/sw.ElapsedMilliseconds); 

(zastępując typ dla każdego testu). Mam te wyniki (w mln wewnętrzne przypisań Pętla/SEC):

SimpleClass 357.1 
SimpleStruct 411.5 
ComplexClass 132.9 
ComplexStruct 159.1 

Te liczby są bliżej, co by się było spodziewać w miarę klasy vs wersji struktury. Myślę, że wolniejsze czasy dla wersji złożonych są wyjaśniane przez efekt pamięci podręcznej procesora większych obiektów/struktur. Używanie skomentowanego kodu pomiaru pamięci pokazuje, że wersje struct zużywają mniej pamięci. Dodałem GC.Collect po tym, jak zauważyłem, że kod mierzący pamięć wpłynął na względne czasy wersji struct vs class.