С++ 2d изменение скорости доступа к базам данных на основе [a] [b] порядка?

Возможный дубликат:
Почему моя программа медленна при циклическом переходе через ровно 8192 элементов?

Я искал программу, которую я использую, чтобы просто суммировать элементы массива 2d. Опечатка привела к тому, что мне показалось, по крайней мере, некоторые очень странные результаты.

При работе с массивом матрица [SIZE] [SIZE]:

for(int row = 0; row < SIZE; ++row)
    for(int col = 0; col < SIZE; ++col)
        sum1 += matrix[row][col];

Выполняется очень быстро, однако приведенная выше строка sum1... изменяется:

sum2 += matrix[col][row]

Как я однажды сделал это на случай аварии, не осознав этого, я заметил, что моя среда выполнения сильно возрастает. Почему это?

Ответы

Ответ 1

Это связано с кэшированием поведения вашей программы.

Массивы - это только последовательные блоки памяти, поэтому, когда вы обращаетесь к [row] [column], вы последовательно получаете доступ к памяти. Это означает, что страница данных, к которой вы обращаетесь, находится на одной странице, поэтому доступ выполняется намного быстрее.

Когда вы выполняете [столбец] [строка], вы больше не обращаетесь к этой памяти, поэтому в итоге вы получите больше промахов в кеше, поэтому ваша программа будет работать намного медленнее.

Ответ 2

Расположение памяти matrix[row][col] и matrix[row][col + 1] смежны.

Расположение памяти matrix[row][col] и matrix[row + 1][col] разделяется величиной SIZE элементов.

Компьютеры, такие как доступ к памяти SEQUENTIALLY не СЛУЧАЙНО, при этом смежный доступ быстрее. Для аналогии думаю, что производительность жесткого диска, последовательное чтение/запись всегда лучше, чем случайное чтение/запись. Это связано с тем, как ваш процессор кэширует память и пытается предсказать, что вам нужно.

Ответ 3

Это потому, что в более быстром случае предварительная выборка памяти CPU действительно полезна, поскольку вы выполняете линейный цикл. В медленном случае вы прыгаете по памяти, и поэтому предварительная выборка имеет мало эффекта, поскольку данные вряд ли будут в кеше.

Ответ 4

Это зависит от того, как упорядочена матрица. Вы получаете доступ к массиву либо в строке-строке, либо в столбце-столбце. В зависимости от того, как он хранится в памяти, скорость будет отличаться между двумя

Ответ 5

2d array - это просто указатель на указатель. Поэтому он выглядит как

[*p][*p][*p]
  |   |   |
  v   v   v
 [d] [d] [d]
 |a| |a| |a|
 |t| |t| |t|
 [a] [a] [a]

Поэтому, когда вы вызываете данные по не-главному массиву (что указывают эти указатели), ваша ОС помещает его в кэш CPU.