Dlaczego lokalizacja pamięci podręcznej ma znaczenie dla wydajności tablicy?

Question

Dlaczego lokalizacja pamięci podręcznej ma znaczenie dla wydajności tablicy?

Na poniższym blogu znajduje się stwierdzenie o przewadze tablic nad listami linkowanymi:

Tablice mają lepszą lokalizację pamięci podręcznej, która może mieć dość dużą różnicę w wydajności.

Co to znaczy? Nie rozumiem, w jaki sposób lokalizacja pamięci podręcznej może zapewnić ogromne korzyści z wydajności.

42

language-agnostic arrays linked-list

Author: Michael Petrotta, 2012-08-22

Source

2 answers

Zazwyczaj, gdy używasz tablicy, masz dostęp do elementów znajdujących się blisko siebie. Jest to szczególnie ważne podczas uzyskiwania dostępu do tablicy sekwencyjnie.

Gdy uzyskujesz dostęp do pamięci, jej fragmenty są buforowane na różnych poziomach. lokalizacja pamięci podręcznej odnosi się do prawdopodobieństwa, że kolejne operacje będą w pamięci podręcznej, a tym samym będą szybsze. W tablicy zwiększasz szanse na dostęp do elementów sekwencyjnych znajdujących się w pamięci podręcznej.

Z listami, przez kontrprzykład, nie ma gwarancji, że elementy, które pojawiają się kolejno na liście, są faktycznie rozmieszczone blisko siebie w pamięci. Oznacza to mniej trafień pamięci podręcznej i pogorszenie wydajności.

6

Author: paddy,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-08-22 03:01:17

score 67 · Accepted Answer

Zobacz moją odpowiedź na temat przestrzennej i czasowej lokalności .

W szczególności tablice są sąsiadującymi blokami pamięci, więc duże ich fragmenty zostaną załadowane do pamięci podręcznej po pierwszym dostępie. To sprawia, że dostęp do przyszłych elementów tablicy jest stosunkowo szybki. Z drugiej strony listy połączone niekoniecznie znajdują się w ciągłych blokach pamięci i mogą prowadzić do większej liczby braków pamięci podręcznej, co wydłuża czas potrzebny na dostęp do nich.

Rozważ następujące możliwe układy pamięci dla tablicy data i połączonej listy l_data dużych struktur

Address      Contents       | Address      Contents
ffff 0000    data[0]        | ffff 1000    l_data
ffff 0040    data[1]        |   ....
ffff 0080    data[2]        | ffff 3460    l_data->next
ffff 00c0    data[3]        |   ....
ffff 0100    data[4]        | ffff 8dc0    l_data->next->next
                            | ffff 8e00    l_data->next->next->next
                            |   ....
                            | ffff 8f00    l_data->next->next->next->next

Gdybyśmy chcieli zapętlić tę tablicę, pierwszy dostęp do ffff 0000 wymagałby od nas przejścia do pamięci, aby ją odzyskać (Bardzo powolna operacja w cyklach procesora). Jednak po pierwszym dostÄ ™ pie reszta tablicy znalazĹ 'a siÄ ™ w buforze, a kolejne dostÄ ™ py byĹ' y by znacznie szybsze. Z połączoną listą, pierwszy dostęp do ffff 1000 również wymagałby od nas przejścia do pamięci. Niestety procesor będzie buforował pamięć bezpośrednio otaczająca to miejsce, powiedzmy aż do ffff 2000. Jak widać, nie uchwyci to żadnego z pozostałych elementów listy, co oznacza, że gdy przejdziemy do access l_data->next, ponownie będziemy musieli przejść do pamięci.