캐시 지역성이 어레이 성능에 중요한 이유는 무엇입니까?

캐시 지역성이 어레이 성능에 중요한 이유는 무엇입니까?

---

다음 블로그 에는 연결 목록에 비해 배열의 장점에 대한 설명이 있습니다.

어레이는 성능면에서 상당히 큰 차이를 만들 수있는 더 나은 캐시 지역성을 가지고 있습니다.

그게 무슨 뜻입니까? 캐시 지역성이 어떻게 엄청난 성능 이점을 제공 할 수 있는지 이해하지 못합니다.

---

공간 및 시간적 지역성에 대한 내 대답을 참조하십시오 .

특히 어레이는 연속적인 메모리 블록이므로 첫 번째 액세스시 큰 덩어리가 캐시에로드됩니다. 따라서 어레이의 향후 요소에 비교적 빠르게 액세스 할 수 있습니다. 반면에 연결된 목록이 반드시 연속적인 메모리 블록에있는 것은 아니며 더 많은 캐시 미스로 이어질 수 있으며, 이에 액세스하는 데 걸리는 시간이 늘어납니다.

배열 data및 l_data대형 구조체의 연결된 목록 에 대해 다음과 같은 가능한 메모리 레이아웃을 고려하십시오.

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

이 배열을 반복하려면에 대한 첫 번째 액세스를 ffff 0000위해 메모리로 이동하여 검색해야합니다 (CPU주기에서 매우 느린 작업). 그러나 첫 번째 액세스 후 나머지 어레이는 캐시에 있으며 후속 액세스는 훨씬 더 빠릅니다. 연결 목록을 사용하면에 대한 첫 번째 액세스 ffff 1000도 메모리로 이동해야합니다. 불행히도 프로세서는이 위치를 직접 둘러싼 메모리를 최대 ffff 2000. 보시다시피, 이것은 실제로 목록의 다른 요소를 캡처하지 않습니다. 즉 l_data->next, 액세스 할 때 다시 메모리로 이동해야 함을 의미합니다.

---

일반적으로 배열을 사용할 때 서로 가까이있는 항목에 액세스합니다. 이것은 배열에 순차적으로 액세스 할 때 특히 그렇습니다.

메모리에 액세스 할 때 메모리 청크는 다양한 수준에서 캐시됩니다. 캐시 지역 성은 연속 작업이 캐시에있어 더 빠를 가능성을 나타냅니다. 배열에서는 캐시에있는 순차 요소 액세스 가능성을 최대화합니다.

목록을 사용하면 반례로 목록에 순차적으로 나타나는 항목이 실제로 메모리에서 서로 근처에 정렬된다는 보장이 없습니다. 이는 더 적은 캐시 적중과 성능 저하를 의미합니다.

참조 URL : https://stackoverflow.com/questions/12065774/why-does-cache-locality-matter-for-array-performance