이 C ++ for 루프의 실행 시간에 중요한 차이가있는 이유는 무엇입니까?

이 C ++ for 루프의 실행 시간에 중요한 차이가있는 이유는 무엇입니까?

---

이 질문에 이미 답변이 있습니다.

• 2D 배열을 반복 할 때 루프의 순서가 성능에 영향을 미치는 이유는 무엇입니까? 7 답변

나는 루프를 겪고 있었고 루프에 액세스하는 데 상당한 차이가 있음을 발견했습니다. 두 경우 모두 이러한 차이를 일으키는 원인이 무엇인지 이해할 수 없습니까?

첫 번째 예 :

실행 시간; 8 초

for (int kk = 0; kk < 1000; kk++)
{
    sum = 0;
    for (int i = 0; i < 1024; i++)
        for (int j = 0; j < 1024; j++)
        {
            sum += matrix[i][j];
        }
}

두 번째 예 :

실행 시간 : 23 초

for (int kk = 0; kk < 1000; kk++)
{
    sum = 0;
    for (int i = 0; i < 1024; i++)
        for (int j = 0; j < 1024; j++)
        {
            sum += matrix[j][i];
        }
}

교환 만하면 실행 시간 차이가 큰 원인

matrix[i][j] 

...에

matrix[j][i]

?

---

메모리 캐시 문제입니다.

matrix[i][j]더 많은 연속 메모리 액세스 기회가 matrix[j][i]있기 때문에 보다 캐시 적중률이 matrix[i][j]높습니다.

예를 들어, 액세스 할 때 matrix[i][0], 캐시 메모리를 함유하는 연속적인 세그먼트를 로딩 할 수있다 matrix[i][0], 즉, 액세스 matrix[i][1], matrix[i][2]이후, ..., 속도 캐싱 혜택 matrix[i][1], matrix[i][2]...에 가깝다 matrix[i][0].

그러나에 액세스 matrix[j][0]하면 matrix[j - 1][0]캐시되지 않았고 캐시되지 않았을 수 있으며 캐시 속도의 이점을 얻을 수 없습니다. 특히, 행렬은 일반적으로 메모리의 연속적인 큰 세그먼트로 저장되며 캐셔는 메모리 액세스 동작을 예측하고 항상 메모리를 캐시 할 수 있습니다.

그것이 matrix[i][j]더 빠른 이유 입니다. 이것은 CPU 캐시 기반 성능 최적화에서 일반적입니다.

---

성능 차이는 컴퓨터의 캐싱 전략으로 인해 발생합니다.

2 차원 배열 matrix[i][j]은 메모리에서 긴 값 목록으로 표시됩니다.

예를 들어 배열 A[3][4]은 다음과 같습니다.

1 1 1 1   2 2 2 2   3 3 3 3

이 예에서 A [0] [x]의 모든 항목은 1로 설정되고 A [1] [x]의 모든 항목은 2로 설정됩니다.

첫 번째 루프가이 행렬에 적용되는 경우 액세스 순서는 다음과 같습니다.

1 2 3 4   5 6 7 8   9 10 11 12

두 번째 루프 액세스 순서는 다음과 같습니다.

1 4 7 10  2 5 8 11  3 6 9 12

프로그램이 배열의 요소에 액세스하면 후속 요소도로드합니다.

예 : 당신은에 액세스하는 경우 A[0][1], A[0][2]그리고 A[0][3]너무로드됩니다.

따라서 첫 번째 루프는 필요한 경우 일부 요소가 이미 캐시에 있으므로로드 작업을 덜 수행해야합니다. 두 번째 루프는 해당 시점에 필요하지 않은 항목을 캐시로로드하여 더 많은로드 작업을 수행합니다.

---

다른 사람들은 왜 한 형태의 코드가 다른 형태보다 메모리 캐시를 더 효율적으로 사용하는지에 대해 잘 설명했습니다. 여러분이 알지 못하는 배경 정보를 추가하고 싶습니다 . 오늘날 주 메모리 액세스 비용이 얼마나 비싼 지 알지 못할 것입니다 .

이 질문에 게시 된 숫자는 나에게 올바른 야구장에있는 것으로 보이며, 매우 중요하기 때문에 여기에서 재현 할 것입니다.

Core i7 Xeon 5500 Series Data Source Latency (approximate)
L1 CACHE hit, ~4 cycles
L2 CACHE hit, ~10 cycles
L3 CACHE hit, line unshared ~40 cycles
L3 CACHE hit, shared line in another core ~65 cycles
L3 CACHE hit, modified in another core ~75 cycles remote
remote L3 CACHE ~100-300 cycles
Local Dram ~60 ns
Remote Dram ~100 ns

마지막 두 항목의 단위 변경에 유의하십시오. 사용중인 모델에 따라이 프로세서는 2.9–3.2GHz에서 실행됩니다. 수학을 더 간단하게 만들기 위해 3GHz라고합시다. 따라서 한주기는 0.33333 나노초입니다. 따라서 DRAM 액세스도 100-300 사이클입니다.

The point is that the CPU could have executed hundreds of instructions in the time it takes to read one cache line from main memory. This is called the memory wall. Because of it, efficient use of the memory cache is more important than any other factor in overall performance on modern CPUs.

---

The answer depends a little bit on exactly how the matrix is defined. In a fully dynamically allocated array, you'd have:

T **matrix;
matrix = new T*[n];
for(i = 0; i < n; i++)
{
   t[i] = new T[m]; 
}

So, every matrix[j] will require a new memory lookup for the pointer. If you do the j loop outside, the inner loop can re-use the pointer for matrix[j] every for the whole inner loop.

If the matrix is a simple 2D array:

T matrix[n][m];

then the matrix[j] will simply be a multiplication by 1024 * sizeof(T) - which can be done by adding 1024 * sizeof(T) the loop index in the optimised code, so should be relatively fast either way.

On top of that, we have cache locality factors. Caches have "lines" of data that is typically 32 to 128 bytes per line. So if your code reads address X, the cache will load up with values 32 to 128 bytes around X. So if the NEXT thing you need is only sizeof(T) forward from the current location, it's highly likely already in the cache [and modern processors also detects that you are going round in a loop reading every memory location, and pre-loads the data].

In the case of j inner loop, you are reading a new location of sizeof(T)*1024 distance for each loop [or possiblya greater distance if it's dynamically allocated]. This means that the data being loaded will not be useful for the next loop, because it's not in the next 32 to 128 bytes.

And finally, it's entirely possible that the first loop is more optimised, thanks to SSE instructions or similar, which allow the calculation to be run even quicker. But this is probably marginal for such a large matrix, as the performance is highly memory bound at this size.

---

Memory hardware is not optimized to deliver individual addresses: instead it tends to operate on larger chunks of continuous memory called cache lines. Every time you read one entry of your matrix, the entire cache line it lies in also gets loaded into cache along with it.

The faster loop ordering is set up to read memory in order; each time you load a cache line, you use all of the entries in that cache line. Each pass through the outer loop, you read each matrix entry only a single time.

The slower loop ordering, however, only uses a single entry from each cache line before moving on. Thus, each cache line has to get loaded multiple times, once for each matrix entry in the line. e.g. if a double is 8 byes and a cache line is 64 bytes long, then each pass through the outer loop has to read each matrix entry eight times rather than a single time.

---

All that said, if you had turned optimizations on, you would probably see no difference: optimizers understand this phenomenon, and good ones are capable of recognizing that they can swap which loop is the inner loop and which loop is the outer loop for this particular code snippet.

(also, a good optimizer would have only done one pass through the outermost loop, because it recognizes the first 999 times through are irrelevant to the final value of sum)

---

The matrix is stored in memory as a vector. Accessing it the first way accesses the memory sequentially. Accessing it the second way requires jumping around memory locations. See http://en.wikipedia.org/wiki/Row-major_order

---

If you access j - i the j dimension is cached so the machine code does not have to change it every time, the second dimension isnt cached, so you actually delete the cache every time what causes the difference.

---

Based on the concept of locality of reference, it is very likely for a piece of code to access memory locations that are adjacent. So more values are loaded into the cache than what is asked for. This means more cache hits. Your first example is satisfying this well while you code in second example is not.

참고URL : https://stackoverflow.com/questions/26583536/why-is-there-a-significant-difference-in-this-c-for-loops-execution-time