Powolne pisanie do tablicy w C++

Question

Zastanawiam się, czy jest to oczekiwane zachowanie w C++. Poniższy kod jest uruchamiany na około 0,001 MS:

for(int l=0;l<100000;l++){ 
     int total=0; 
     for(int i = 0; i < num_elements; i++) 
     { 
      total+=i; 
     } 
    } 

Jednak jeśli wyniki są zapisywane na tablicy, czas realizacji pędy do 15 MS:

int *values=(int*)malloc(sizeof(int)*100000); 
     for(int l=0;l<100000;l++){ 
      int total=0; 
      for(unsigned int i = 0; i < num_elements; i++) 
      { 
       total+=i; 
      } 
      values[l]=total; 
     } 

mogę docenić, że pisanie do tablica wymaga czasu, ale czy czas jest proporcjonalny?

Zdrówko wszyscy

Answer 1

Pierwszy przykład może zostać zaimplementowany przy użyciu tylko rejestrów procesora. Dostęp do nich jest miliard razy na sekundę. Drugi przykład wykorzystuje tak dużo pamięci, że z pewnością przepełnia pamięć podręczną L1 i ewentualnie L2 (w zależności od modelu procesora). To będzie wolniejsze. Mimo to, 15 ms/100 000 zapisów wychodzi na 1,5 ns na zapis - efektywnie 667 Mhz. To jest , a nie wolno.

Answer 2

Wygląda na to, że kompilator optymalizuje pętli się całkowicie w pierwszym przypadku.

Łączny efekt pętli to operacja "no-op", więc kompilator po prostu ją usuwa.

Answer 3

Podejrzewam, że to, co widzisz, jest efektem działania virtual memory i prawdopodobnie stronicowania. Wywołanie malloc przydzieli porządną porcję pamięci, która jest prawdopodobnie reprezentowana przez kilka wirtualnych stron. Każda strona jest osobno połączona z pamięcią procesową.

Możesz również mierzyć koszt połączenia pod numer malloc w zależności od tego, w jaki sposób ustawiłeś czas w pętli. W obu przypadkach wydajność będzie bardzo wrażliwa na opcje optymalizacji kompilatora, opcje wątkowania, wersje kompilatora, wersje uruchomieniowe i prawie wszystko. Nie można bezpiecznie założyć, że koszt jest liniowy w stosunku do wielkości przydziału. Jedyną rzeczą, którą możesz zrobić, to zmierzyć go i wymyślić, jak najlepiej zoptymalizować , gdy zostanie udowodnione, że jest to problem.

Answer 4

To bardzo proste. W pierwszym przypadku Masz tylko 3 zmienne, które mogą być łatwo zapisane w GPR (rejestrach ogólnego przeznaczenia), ale to nie znaczy, że są tam cały czas, ale prawdopodobnie są w pamięci podręcznej L1, co oznacza, że można uzyskać bardzo szybko.

W drugim przypadku Masz więcej niż 100k zmiennych i potrzebujesz około 400kB do ich przechowywania. To zdecydowanie za dużo dla rejestrów i pamięci podręcznej L1. W najlepszym przypadku może to być pamięć podręczna L2, ale prawdopodobnie nie wszystkie z nich będą znajdować się w L2. Jeśli coś nie jest w rejestrze, L1, L2 (zakładam, że twój procesor nie ma L3) oznacza to, że musisz wyszukać go w pamięci RAM i wymaga to więcej czasu.