elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Память: последовательный доступ vs случайный доступ. Как замерить?
elizarov

Есть множество книг, инструментов и заметок про скорость работы памяти. Общеизвестен факт о том, что случайный доступ в оперативную память работает существенно дольше последовательного доступа (то же относится и к жесткому диску). Но как эти знания и замеры применить к конкретной задаче и платформе? Вот недавно пролетала замечательная ссылка Latency Numbers Every Programmer Should Know, где написано, что "L1 Cache Reference" это 0.5 наносекунд, а "Main memory reference" это 100 нс, то есть в 200 раз медленней. Так ли это на самом деле? Как это соотнести с реальным кодом на языке высокого уровня?

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

Чтобы сравнить именно скорость работы памяти при последовательном доступе со скоростью при случайном доступе, надо написать такой код, который позволит воплотить оба способа доступа используя одинаковый набор инструкций и будет, в то же время, максимально простым. Если взять массив целых чисел a в котором N элементов, где N это степень двойки (я проводил замеры на 225 чисел, занимающих 128МБ памяти), то на языке Java это можно сделать следующим образом:

    private int run(int step) { 
        int sum = 0; 
        int i = 0; 
        do { 
            sum += a[i]; 
            i = (i + step) & (N - 1); 
        } while (i != 0); 
        return sum; 
    } 

Если step выставлен в 1, то массив a будет сканироваться последовательно, а если взять большой step, который взаимнопрост с количеством элементов в массиве N (то есть нечетен) и составляет существенную часть от N то, с точки зрения памяти, доступ будет вполне случайным. Суммирование элементов нужно для того, чтобы компилятор не соптимизировал (не убрал) бы доступ к массиву. Это одна из самых простых операций которую можно сделать над элементами массива для проведения такого теста. Полный код доступен здесь.

На моем ноутбуке при использовании Java HotSpot Server (1.7.0_02) последовательный доступ занимает в среднем 1.33 ± 0.06 нс на итерацию цикла, а случайный доступ занимает 25.51 ± 0.46 нс. Отличие в 19 раз. Здесь учтено не только время доступа в память, но и все операции по организации цикла, поэтому для последовательного доступа полученное время превышает собственно время доступа в память, да и код полагается исключительно на автоматический prefetch процессора для последовательного доступа. При последовательном доступе этот код читает 3 ГБ в секунду из основной памяти, что далеко до предела моего Intel Core i5 520M c двумя каналами DDR3 на 532 МГц. Но я и хочу показать разницу в скорости разного доступа к памяти на коде вполне обычного доступа к массиву.

Однако, код одинаковый для обоих тестов, а значит что при его использовании для случайного доступа в паять именно время доступа в память существенно доминирует. То есть время доступа к случайной ячейке памяти составляет около 25 нс или около 66 тактов на турбо-частоте 2.66 ГГц на которой работает процессор в этом тесте. Это не 100 нс, но все равно существенно дольше чем даже нетривиальные вычисления.

Наблюдательный читатель заметит, что в тестах на производительность хеш-таблиц получались времена порядка 100 нс если всё было хорошо перемешано. А ведь на каждый элемент хеш-таблицы нужно два доступа в память даже в самом лучше случае нахождения элемента с первого раза. Один раз чтобы прочитать саму таблицу, а второй раз чтобы прочитать найденный объект по ссылке. То есть половина или даже больше времени работы самой быстрой хеш-таблицы обусловлено исключительно временем работы с памятью. Я еще вернусь к этому наблюдению.

UPDATE: Немного больше о последовательном доступе здесь.


  • 1
У intel есть fixed stride prefetcher (http://goo.gl/zqWub). Может быть он здесь и срабатывает? Это вполне объясняет << 100нс?

Он срабатывает при последовательном доступе. Это объясняет ~1 нс на последовательный доступ. При таком же "случайном" — нет, ибо он умеет работать только в пределах одной страницы.

Странно, здесь ничего явно про страницы нет:

Using this IP history array, it’s possible to detect iterating
loads that exhibit a perfect stride access pattern (An – An-1
= Constant) and thus predict the address required for the
next iteration. A prefetch request is then issued to the L1
cache. If the prefetch request hits the cache, the prefetch
request is dropped. If it misses, the prefetch request propa-
gates to the L2 cache or memory.

Я вообще не уверен что низкоуровневая система что-то знает про страницы. Я думал что cache-line сейчас 64 бита.

А как она может не знать про страницы?

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

CPU context-switching

Оптимизационный хардкор, о да, детка, да! :)

Верно я понимаю, что сказанное в прикладном смысле больше актуально для однопоточного кода, ибо в многопоточном первым кандидатом на внимание остается вопрос переключения контекстов, которое занимает на порядок больше времени чем собственно доступ к памяти (http://blog.tsunanet.net/2010/11/how-long-does-it-take-to-make-context.html)?
Переключение контекстов, впрочем, делается на i386 (если я верно в курсе) тоже через основную память, что, с одной стороны не добавляет скорости а с другой вызывает вопрос - почему?

Re: CPU context-switching

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

Разные _малые_ step, в т.ч. отрицательные, покажи пжлст.

Зависимость времени доступа к памяти от шага прохода

Шаг (x4 байт)Время (нс)Шаг (x4 байт)Время (нс)
 1 1.306 ± 0.045   -1 1.319 ± 0.047
 3 2.003 ± 0.070   -3 2.045 ± 0.063
 5 3.199 ± 0.103   -5 3.248 ± 0.104
 7 4.202 ± 0.118   -7 4.226 ± 0.114
 9 5.242 ± 0.114   -9 5.357 ± 0.149
11 6.447 ± 0.201  -11 6.484 ± 0.170
13 7.513 ± 0.286  -13 7.452 ± 0.205
15 8.496 ± 0.209  -15 8.571 ± 0.178
17 9.598 ± 0.219  -17 9.619 ± 0.237
19 10.486 ± 0.232 -19 10.578 ± 0.192
21 11.370 ± 0.209 -21 11.350 ± 0.233
23 12.051 ± 0.198 -23 12.171 ± 0.227
25 12.952 ± 0.196 -25 12.924 ± 0.241



Edited at 2012-06-21 07:22 am (UTC)

Re: Зависимость времени доступа к памяти от шага проход

Большое спасибо. Не подскажешь структуру страничной организации памяти в используемом окружении? Когда я с этим в первый (и последний) раз разбирался, мы еще регулярно общались лично :-)

И второй, связанный вопрос - эффекты TLB miss (в том числе TLB&L1 miss, TLB&L1&L2 miss) - присутствуют/появятся только при большем размере массива/не фиксируются?

Re: Зависимость времени доступа к памяти от шага проход

Обычный x86 32bit http://en.wikipedia.org/wiki/File:X86_Paging_4K.svg

Размер достаточно большой (128MB памяти) -- больше чем все-все кеши. Таким образом, все эффекты присутсвуют в полной мере.


Re: Зависимость времени доступа к памяти от шага проход

Ан нет. Ошибся. PAE включен. Вот такая организация памяти: http://en.wikipedia.org/wiki/File:X86_Paging_PAE_4K.svg

Re: Зависимость времени доступа к памяти от шага проход

То есть, блоки 4K, 2M, 1G. Задействуемой страничной информации вроде как 256K+512.

Покажи, пож, шаги: n*0x100+1, n*0x20000+1, ну и золотое сечение (N*(sqrt(5)-1)/2, округленное до нечетного) как в некотором смысле антиэталон.


Re: Зависимость времени доступа к памяти от шага проход

Для "случайного доступа" я именно округленное золотое сечение и использую. Цитирую код: RND_STEP = (int)((Math.sqrt(5) - 1) / 2 * N) | 1;.

Про остальное как-нибудь отдельно напишу.


Edited at 2012-06-21 11:27 am (UTC)

  • 1
?

Log in

No account? Create an account