Производительность на массивах или матрицах

Question

Я разговаривал с другом сегодня .. и он сказал мне что-то, что я не знаю, если это правда, поэтому я решил спросить здесь.

У него есть огромная матрица, в которой у него есть такие предметы:

 1 2 3 4 .. 1000
1001 ...... 2000
2001 ...... 3000
....

Во всяком случае .. он говорил, что эффективнее пройти его 1 2 3 4 .. в C, потому что в C массив хранится в памяти строка за строкой. Он однажды проверил это в коде для обхода одной из этих огромных структур столбец за столбцом и строка за строкой, и времена были разными. Один из них более эффективен, чем другой.

но я думал, как это может изменить ситуацию ...

Я имею в виду, что для доступа к * (i + 1) и * (i + 1000) в непрерывном массиве памяти требуется одинаковое время. право

Ted

Answer 1

Он прав на местность отсчета (в частности, пространственная местность).Ближайшие адреса будут предварительно выбраны / кэшированы для ускорения доступа.Таким образом, если вы нажмете адрес памяти p, то адрес памяти p + 1 и другие близлежащие адреса будут предварительно выбраны и кэшированы для ускорения доступа к ним, тогда как для доступа к p + 1000, скорее всего, потребуется еще одно отключение по шине памяти.

(Кстати, описываемый вами макет порядок основных строк . Некоторые языки (например, Fortran) используют порядок основных столбцов .)

Answer 2

См. Порядок следования строк .

В языке C элементы хранятся строка за строкой.Кэширование означает, что при обращении к *i в кэше, скорее всего, будет *(i+1), поэтому он быстрее.

Важность упоминания языка C состоит в том, что не все языки таковы.Известно, что Фортран использует мажорный столбец.Так что иногда вы можете найти матрицу мажорной строки с именем C-смежную , а мажорную колонку с именем Fortran-смежную .

Answer 3

Да, это правда.По моему опыту, вы можете примерно вдвое снизить производительность, обходя матрицу неправильно.

Причина в том, что большая часть вашего оборудования построена на множестве предположений о том, как оно будет вероятно использовать, а затем они используют эти знания для достижения лучшей производительности.В этом случае соответствующим принципом является «Пространственная локальность», концепция, которая «если вам недавно был нужен адрес N, то вам, вероятно, скоро понадобится содержимое адреса N + 1».

Ваша RAM предназначенапо этой причине передавать память в пакетном режиме.Когда вы запрашиваете одно слово данных, он начинает загружать больший непрерывный кусок памяти, так что он готов к тому моменту, когда вы , вероятно, попросите об этом мгновение спустя.

И сам процессорделает то же самое.Его кеш устроен по тому же принципу.Он хранит целые строки кэша (обычно 16 или 32 байта, если память служит) вместо отдельных байтов или слов.Таким образом, когда вы запрашиваете один байт, вся строка кэша считывается в кэш, так что соседние данные также доступны, если вам это нужно.

Если вы пересекаете матрицу столбец за столбцом, то каждый доступ к памятинаходится по адресу, который находится далеко от предыдущего, таким образом, нет никакой пространственной локализации, и поэтому и кэш ЦП, и ваша ОЗУ не могут предсказать, какие данные им следует предварительно выбрать, и в итоге вы ожидаете передачи данных вамвремя.

Answer 4

Процессоры исходят из предположения, что если вы извлекаете часть памяти, которая вам скорее всего понадобится в ближайшее время для других близлежащих данных, и, таким образом, предварительно вносите в кэш немного больше. Хиты кэша очень быстрые, поэтому код, использующий это преимущество, будет быстрее, чем код, который этого не делает. Вот почему быстрее обойти соседние элементы данных, чем прыгать вокруг. (Так что да, он прав)

Answer 5

У Ульриха Дреппера есть отличная статья, в которой описывается поведение кеша, помимо прочего, связанное с системой памяти современных компьютеров. Это на http://www.akkadia.org/drepper/cpumemory.pdf.