Właśnie przeczytałem numer article autorstwa Rico Marianiego, który dotyczył wydajności dostępu do pamięci przy różnych lokalizacjach, architekturze, wyrównaniu i gęstości.Co powoduje ten dziwny spadek wydajności przy * średniej * liczbie przedmiotów?
Autor przygotował tablicę o różnym rozmiarze, zawierającą podwójnie połączoną listę z ładunkiem o rozmiarze int, która została przemieszana do określonego procentu. Eksperymentował z tą listą i znalazł pewne spójne wyniki na swojej maszynie.
Cytując jednego z tabeli wynikowej:
Pointer implementation with no changes
sizeof(int*)=4 sizeof(T)=12
shuffle 0% 1% 10% 25% 50% 100%
1000 1.99 1.99 1.99 1.99 1.99 1.99
2000 1.99 1.85 1.99 1.99 1.99 1.99
4000 1.99 2.28 2.77 2.92 3.06 3.34
8000 1.96 2.03 2.49 3.27 4.05 4.59
16000 1.97 2.04 2.67 3.57 4.57 5.16
32000 1.97 2.18 3.74 5.93 8.76 10.64
64000 1.99 2.24 3.99 5.99 6.78 7.35
128000 2.01 2.13 3.64 4.44 4.72 4.80
256000 1.98 2.27 3.14 3.35 3.30 3.31
512000 2.06 2.21 2.93 2.74 2.90 2.99
1024000 2.27 3.02 2.92 2.97 2.95 3.02
2048000 2.45 2.91 3.00 3.10 3.09 3.10
4096000 2.56 2.84 2.83 2.83 2.84 2.85
8192000 2.54 2.68 2.69 2.69 2.69 2.68
16384000 2.55 2.62 2.63 2.61 2.62 2.62
32768000 2.54 2.58 2.58 2.58 2.59 2.60
65536000 2.55 2.56 2.58 2.57 2.56 2.56
Autor wyjaśnia:
Jest to pomiar bazowy. Możesz zobaczyć, że struktura jest ładnym rundem 12 bajtów i będzie dobrze wyrównana na x86. Patrząc na pierwszą kolumnę, bez tasowania, zgodnie z oczekiwaniami rzeczy stają się coraz gorsze, gdy tablica staje się większa, aż w końcu pamięć podręczna niewiele pomaga i masz najgorsze, co otrzymasz, czyli około 2,55 średnia za sztukę.
Ale coś zupełnie dziwne widać około 32k elementy:
Wyniki dla tasowania nie są dokładnie to, czego się spodziewałem. Przy małych rozmiarach nie ma znaczenia. Spodziewałem się tego, ponieważ zasadniczo cały stół jest gorący w pamięci podręcznej, więc lokalizacja nie ma znaczenia. Gdy tabela rośnie, widać, że tasowanie ma duży wpływ na około 32000 elementów. To 384 tys. Danych. Prawdopodobnie dlatego, że przekroczyliśmy limit 256 KB.
Teraz dziwne jest to, że po tym czasie koszty tasowania faktycznie spadają, do tego stopnia, że później nie ma to żadnego znaczenia. Teraz mogę zrozumieć, że w pewnym momencie przetasowanie lub nie przetasowanie naprawdę nie powinno sprawić żadnej różnicy, ponieważ tablica jest tak duża, że środowisko wykonawcze jest w dużej mierze blokowane przez przepustowość pamięci bez względu na kolejność. Jednak ... istnieją punkty pośrodku, gdzie koszt nielokalności jest w rzeczywistości dużo gorszy niż na końcówce.
To, co spodziewałem się zobaczyć, to to, że tasowanie sprawiło, że szybciej osiągnęliśmy maksymalną zło i tam pozostaliśmy. To, co się dzieje, to to, że w średnich rozmiarach nie-lokalność wydaje się powodować, że wszystko idzie bardzo źle ... I nie wiem dlaczego :)
Pytanie brzmi: Co mogło spowodować to nieoczekiwane zachowanie?
Myślałem o tym przez jakiś czas, ale nie znalazłem dobrego wyjaśnienia. Kod testowy wygląda dla mnie dobrze. Nie sądzę, aby predykcja rozgałęzień procesora była w tym przypadku winowajcą, ponieważ powinna być zauważalna znacznie wcześniej niż 32k i pokazywać znacznie mniejszy skok.
Potwierdziłem to zachowanie na moim pudełku, wygląda dokładnie tak samo.
Pomyślałem, że może to być spowodowane przekazaniem stanu procesora, więc zmieniłem kolejność generowania wierszy i/lub kolumn - prawie żadna różnica w wynikach. Aby się upewnić, wygenerowałem dane dla większej próbki ciągłej.Do łatwego oglądania, umieścić go w programie Excel:
And another independent run for good measure, negligible difference
