가로 대 세로 브라우징

Question

두 개의 거의 동일한 부호를 고려하자 :

우선 대신 탭 번째 [I] [J]에

for (int k=0;k<1000;k++) 
{ 
    for (int i=0;i<600;i++) 
    { 
     for (int j=0;j<600;j++) 
     { 
       tab[j][i] = i *j; 
     } 
    } 
} 

for (int k=0;k<1000;k++) 
{ 
    for (int i=0;i<600;i++) 
    { 
     for (int j=0;j<600;j++) 
     { 
       tab[i][j] = i *j; 
     } 
    } 
} 

둘째 우리 탭이 있습니다 [j] [i].
첫 번째 코드가 훨씬 빠릅니다.

질문
왜 첫 번째 코드가 더 빠릅니까? 프로그램이 셀 캐시로 이동하고, 다음은 캐시를 통해 접근이 셀을 포함 먼저 전체 블록을 액세스하려고 할 때 때문에

내 직감
그것을입니다. 메모리의 배열은 연속적인 셀로 표현되기 때문에 첫 번째 경우에는 두 번째 경우보다 메모리에 대한 액세스가 훨씬 적습니다.

Answer 1

캐시 위치 때문입니다. 프로세서 캐시 라인은 한 번에 여러 개의 배열 요소를 포함 할 수 있지만 인접 주소에서만 가져올 수 있습니다.

첫 번째 경우에는 캐시 히트가 더 많습니다. 두 번째 배열 인덱스를 반복 할 때 인접 요소에 액세스합니다. 일부 요소에 액세스하면 프로세서가이 요소를 캐시 라인에로드하고 다음 인접 액세스는 캐시 적중을 생성합니다. 더 이상 메모리 액세스를 필요로하지 않습니다.

두 번째 경우 첫 번째 인덱스를 반복 할 때 일부 요소를로드 할 때 캐시 줄이 채워지지만 다음 액세스는 같은 줄에없는 요소에 대한 것입니다. Thie는 프로세서가 캐시에 또 다른 라인을로드하게합니다. 캐시가 모든 행을 동시에 보유 할 수 없으면 이전에로드 된 행을 버리고 나중에 다시로드해야합니다. 이렇게하면 메모리 액세스 수가 크게 증가하므로 실행 시간이 늘어납니다.

Answer 2

네 이론이 맞습니다.

배열 전체에서 단일 요소에 액세스 할 때 전체 배열이 너무 커서 캐시에 맞출 수 없기 때문에 메모리를 캐시에서 스위치 아웃해야합니다.

요소에 순차적으로 액세스 할 때 각 메모리 블록은 캐시로 들어가고 나가기 만하면됩니다. 또한 캐시의 마지막 블록 만 사용하면 가장 편리 할 때 이전 블록을 메모리에 다시 쓸 수 있습니다.

Answer 3

다른 응답에서 올바르게 식별 된 문제뿐만 아니라 대부분의 최신 CPU에는 자동 프리 페치가 있다는 점에서 두 번째 문제가 있습니다. 특정 수의 캐시 라인이 순차 주소에서로드되면 자동 프리 페치가 시작되고 추가 캐시 라인이 추론 적으로로드됩니다. 결과적으로 DRAM 대기 시간의 영향이 제거되면 성능이 크게 향상 될 수 있습니다. 비 순차적으로 메모리에 액세스하는 경우이 이점을 얻지 못하고 프리 페치가 이후에 필요하지 않은 캐시 라인을로드하는 경우 카운터 생산성이 저하 될 수 있습니다.