Оптимизированный доступ к памяти.

Всех приветствую. Читаю книгу Криса - "Техника оптимизации программ" и возникло несколько вопросов. У меня на старом четвёртом пне(Northwood) DDR1, развётка цикла при чтении и правда даёт выйгрыш, правда несколько меньший чем писал Крис, 2 ~ 50%, 4 ~ 65. На современном Core 2 Duo E8500 DDR3, выйгрыша нет вообще, только незначительные колебания туда-сюда. Но главное меня интересуют параллельные операции при непоследовательном доступе. Я не совсем понимаю почему нужно разносить операции чтения, на длину кэш линий. Почему нельзя разбить на большие диапазоны, чем кэш линий? Например я сделал следующее (так же Core 2 Duo E8500 DDR3):

Код (Text):

1. count >>= 4; //Делим размер в байтах на 16 ( 4 для int, ещё 4 для разбивки на 4 блока)
2.  
3. //Объявляем указатели на блоки.
4. int* pSrc1 = ((int*)pSrc);
5. int* pSrc2 = ((int*)pSrc) + count;
6. int* pSrc3 = ((int*)pSrc) + count * 2;
7. int* pSrc4 = ((int*)pSrc) + count * 3;
8. for(int i=0; i<count; i++)
9. {
10.     x += pSrc1[i];
11.     x += pSrc2[i];
12.     x += pSrc3[i];
13.     x += pSrc4[i];
14. }

Размер массива 0x3000000 байт, выровненный на 16 байт. В итоге получил падение в районе 15% - 20%. Прошу разъяснить эти моменты. И как вообще нужно оптимизировать данные операции на современном и не очень железе?

 

То просто предвыборка в кэше неработает она расчитанна на 1 поток. А у тебя 4 потока.
Но порт загрузки расчитанн на 4 потока. Это значит что на самом деле там идет кэширование 4 линеек кэша.
Поэтому промох приходиться 4 раза на 16 обращений. Штраф за промах 15 тиков.
В прямом методе чтение занимает так. При раскрутке 4 чтени за такт.

16/(4+4*15)= 0.25 падение в 4 раза.

Что касается Northwood то там внутреняя шина рассчитанна на 3 микро инструкции на такт. А у Core эта шина на 6.
Поэтому Northwood в 4 раза прирост не имеет упирается в пропускную способность этой шины. Плюс архитектура убогая.

Отсюда имеем
4/3=1.5 прирост
8/5=1,6

А вообще я подозриваю что интел просто у core местами подняла внутреннию частоту в 2-3 раза.

 

В принципе можно, если осторожно

Во-первых, нужно учитывать особенности работы кэшей.
Вопрос: ты этот код на Northwood-e пробовал ? По идее должен быть полный облом из-за конфликта данных в L1, т.к. на Northwood-e L1 не может одновременно хранить данные с адресами кратными 64К - при каждом mov будет перезагрузка линееr из L2.
На атлонах при развороте на 4 тоже будет облом, но помягче - у атлонов L1 кэш всего 2-way, а не 4-way, как на пеньках, т.е. в нем невозможно одновременно хранить более 2-х линеек с адресами, кратными (размер_L1)/(2*64)

Во-вторых, нужно учитывать особенности хардварных префетчеров. Крис вроде как на древнем PIII экспериментировал возможно без HW-префетчера. В P4, PM и Core префетчер может отслеживать несколько потоков данных, а в атлонах - фиг его знает (вроде как только один, если не путаю). Но опять же префетчер отключить невозможно и соотв-но он пытается выполнять свою работу и грузить данные с упреждением (на 128 или 256 байт вперед). А ты со своим параллельным чтением 4-х далеко разнесенных адресов нарушаешь эту идилию и в итоге не известно "кто победит"

В-третьих, ... Хватит на сегодня, утро вечера мудренее

 

TermoSINteZ
Это всё вроде очевидные, но не очень интересные вещи: Развёртка, размер страницы памяти, последовательный доступ вперёд. Хочется выжать больше, что Крис и пытался сделать.

leo

Не понял, можно поподробней? Что такое HW префетч и 2/4-way L1 кэш? И как оно влияет на всё это? Идилия похоже портиться на 4 чтении.

Во первых у меня погрешность измерений в районе 10%, что не радует. Во вторых такое впечатление что VTune потихоньку деградирует, но не будем о грустном.
Потестил ещё немного, и вот что получилось:

Это по идее самый тормозной код, но если в count передать константное значение, то компилятор (VS2003 и VS2005) нехило разворачивает цикл в 6-8 раз, но тут есть проблема что он не знает как выровнены данные, хотя сильно это на результат не влияет.

Код (Text):

1. int foo(const void* pSrc, int count)
2. {
3.     int x = 0;
4.     count >>= 2;
5.  
6.     for(int i=0; i<count; i++)
7.         x += ((int*)pSrc)[i];
8.  
9.     return x;
10. }

Этот код на P4 быстрее предыдущего, хотя как оказалось не так как я писал ранее, а всего процентов на 20-30. Зато компилятор интересно поступает, читает не последовательно, а c такими смещениями: -4, -8, 0, 4. Что не понятно, ведь последовательное должно быть лучше.

Код (Text):

1. int foo2(const void* pSrc, int count)
2. {
3.     int x = 0;
4.     count >>= 2;
5.  
6.     for(int i=0; i<count; i+=4)
7.     {
8.         x += ((int*)pSrc)[i];
9.         x += ((int*)pSrc)[i+1];
10.         x += ((int*)pSrc)[i+2];
11.         x += ((int*)pSrc)[i+3];
12.     }
13.     return x;
14. }

Это на P4 вообще сплошной тормоз медленнее самого первого варианта в 10-20 раз, не понимаю отчего это произошло. Железобетонный кэш промах? Но всё равно что-то много.

Код (Text):

1. int foo4(const void* pSrc, int count)
2. {
3.     int x = 0;
4.     count >>= 4; //Делим размер в байтах на 16 ( 4 для int, ещё 4 для разбивки на 4 блока)
5.  
6.     //Объявляем указатели на блоки.
7.     int* pSrc1 = ((int*)pSrc);
8.     int* pSrc2 = ((int*)pSrc) + count;
9.     int* pSrc3 = ((int*)pSrc) + count * 2;
10.     int* pSrc4 = ((int*)pSrc) + count * 3;
11.     for(int i=0; i<count; i++)
12.     {
13.         x += pSrc1[i];
14.         x += pSrc2[i];
15.         x += pSrc3[i];
16.         x += pSrc4[i]; //Здесь более 800 тактов!
17.     }
18.     return x;
19. }

Это пытался сделать как Крис советовал, но прироста нет никакого, примерно вровень с 4x разворачиванием.

Код (Text):

1. int foo5(const void* pSrc, int count)
2. {
3.     const int size_cash_line = 128>>2; //cash line in dword
4.     int x = 0;
5.     count >>= 2;
6.     int *p = (int*)pSrc;
7.     for(int i=0; i<count; i += size_cash_line*4)
8.     {
9.         x += p[i];
10.         x += p[i + size_cash_line*1];
11.         x += p[i + size_cash_line*2];
12.         x += p[i + size_cash_line*3];
13.         for (int j=i+1; j<i+size_cash_line; j++)
14.         {
15.             x += p[j];
16.             x += p[j + size_cash_line];
17.             x += p[j + size_cash_line*2];
18.             x += p[j + size_cash_line*3];
19.         }
20.     }
21.     return x;
22. }

Видимо E8500 намного лучший проц, раз для него всё это побоку. Но последний тест по-идее должен сильнее влиять на память, но прироста что-то не ощущается.

 

Booster

Куда уж подробней

1) HWP - это хардварный (аппаратный) префетч. Появился он в старшей модели PIII (0.13 мкм Tualatin) и в P4. А Крис экспериментировал с более ранним PIII без HW-префетча (<800Мгц - наверняка Coppermine), поэтому и выигрыш от софтварного префетча у него получался больше. На современных же компах эти ухищрения, а также использование инструкций prefetch, при последовательном чтении данных мало что дают, т.к. рулит HWP. Читаем:

2) 2-way\4-way - это способы организации кэша. Грубо говоря, кэш это не один сплошной массив строк (с одним входом), а матрица\таблица с несколькими колонками = входами (way). Например, 64К кэш с 2-way делится на 2 колонки по 32К, а 4-way на 4 колонки по 16К. Номер строки таблицы, в которую попадают данные, однозначно определяется младшими разрядами адреса данных (например для 32К колонок 15-ю мл.битами). При этом данные могут быть записаны в одну из колонок - либо в свободную, либо содержащую более старые данные (вытеснение данных). Поскольку число колонок (way) ограничено 2, 4 и т.п., то одновременно в кэше могут храниться не более 2, 4 и т.п. данных с адресами, кратными размеру колонки в Кб. В "научных" терминах размер колонки называется алиасингом адресов кэша, а число колонок - размером набора (N-way set)
Поэтому когда делаешь разворот цикла по кратным адресам нужно учитывать алиасинг и число way кэша. У атлонов L1 имеет размер 64К и всего 2-way. Поэтому разворот на 4 с адресами кратными 64К/2=32К (алиасинг) будет приводить к тормозам за счет постоянного вытеснения данных из L1 и соотв-но для атлонов подобный разворот можно делать только на 2, а не на 4. Если же делать разворот "по Крису", то подобных проблем не возникает, т.к. адреса различаются на 4*64(размер линейки) < 32К и соотв-но пишутся не в одну строку таблицы, а в разные

3) Причину жуткого облома в P4 я уже называл - это конфликт данных в L1 (data conflict). Связано это с тем, что в P4 для ускорения работы с кэшем в плане трансляции виртуальных адресов в физические придумали комбинированный способ адресации L1 под названием virtually addressed, physically tagged. На деле это означает, что при проверке наличия данных в одной из колонок (way) кэша сравниваются не сразу физические адреса как в других архитектурах, а сначала проверяются младшие разряды виртуального адреса и только потом производится проверка физ.адресов. В Northwood-е для начальной проверки юзается всего 16 бит, поэтому в одном наборе не могут одновременно присутсвовать данные с вирт.адресами кратными 64К, т.к. процессор при первой проверке будет хватать не те данные, потом спохватываться и перезагружать их из L2 по физ.адресу.
В итоге при развороте цикла на 4 по адресам, кратным 64К, на 3-х мувах из 4-х в цикле возникает конфликт данных в L1 и соотв-но перезагрузка линеек из L2

 

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

 

leo
Спасибо. Наверное и правда HW префетч делает бессмысленным и даже вредными все эти махинации с памятью, ибо простой последовательный доступ является самым оптимальным, и даже развёртка особо не нужна.

Код (Text):

1. Причину жуткого облома в P4 я уже называл - это конфликт данных в L1 (data conflict). Связано это с тем, что в P4 для ускорения работы с кэшем в плане трансляции виртуальных адресов в физические придумали комбинированный способ адресации L1 под названием virtually addressed, physically tagged. На деле это означает, что при проверке наличия данных в одной из колонок (way) кэша сравниваются не сразу физические адреса как в других архитектурах, а сначала проверяются младшие разряды виртуального адреса и только потом производится проверка физ.адресов.

Уменьшение ассоциативности для ускорения трансляции? Странно.

 

Ещё прошу прокомментировать такой момент, когда тестировал то решил посмотреть как ведут себя ассемблерные варианты. Так вот цикл с loop ну просто жесть тормозной. Я и раньше слышал что он тормоз, но не подозревал что на столько.

Код (Text):

1. mov ecx, count
2. l1:
3.   add eax, dword ptr [edx] ;24 события.
4.   add edx, 4 ;33 события
5.   sub ecx, 1
6.   jne l1

Код (Text):

1. mov ecx, count
2. l1:
3.   add eax, dword ptr [edx] ;102 события.
4.   add edx, 4 ;66 события
5.   loop l1

Это пипец, loop при чтении больших объёмов данных, медленнее в 3 раза! И это на E8500.

 

Прокомментировать не могу, т.к. сам не понимаю как из достаточно простых операций можно делать таких монстров - по официальным манам Intel и AMD латентность loop на P4 и атлонах составляет 8 тактов, а по А.Фогу то на Core2 loop состоит аж из 11 микро-опов. Нафига столько, не знаю %(

 

Если учесть, что на Northwood код с loop не отстаёт от джампа. Ведь при чтении главным тормозом всё же должна быть память, а не проц. Как такой код на мощном Core 2 Duo может отставать в три раза для меня загадка.
Кстати и такой код отстаёт на коре в 2 раза от обычного обхода массива.

Код (Text):

1. int foo2(const int** pSrc, int count)
2. {
3.     int x = 0;
4.    
5.     const int *p = *pSrc;
6.     while (p)
7.     {
8.         x += *p;
9.         p = (int*)*p;
10.     }
11.  
12.     return x;
13. }

Понятно, что зависимость по данным, но штука в том, что в данном случае указатели указывают на следующие элементы, то есть инициализируются так - p = (int)&p[i+1];
На P4 снова нет падения, что вполне объяснимо аппаратным префетчем. Чем объяснить падение на коре совершенно не понятно.

 

Э-э, как бы это помягче... Одним словом - все в мире относительно

А для меня - нет. Во-первых, частота CPU у "коры" примерно та же, что и у "северного леса", а частота памяти наверняка как минимум раза в два выше (DDR2 против DDR), поэтому если память и тормозит, то на P4 больше, а на коре меньше.
Во-вторых, а в чем мощь, брат ? Если частоты примерно одинаковы, то на зависимых операциях "кора идет лесом", т.е. работает так же как и замшелый северный лес. С другой стороны, независимые операции кора может выполнять аж до 4 шт. за такт, а лес только 3. Соотв-но кора более чувствительна ко всяким "добавкам". Например, при "обычном обходе массива" при соотв.оптимизации можно уложиться в 4 мопа на цикл (загрузить, сложить, изменить счетчик\индекс, перейти), поэтому теоретически кора может все эти 4 мопа уложить в 1 такт, а лес только в 2. Но при добавлении еще одного, 5-го мопа, коре уже потребуется 2 такта на цикл, т.е. сразу получим "отставание на коре в 2 раза", а у леса как было 2 такта, так и осталось, т.к. 5 < 2*3=6

В силу сказанного, нет ничего удивительного в том, что добавление еще одной зависимой операции чтения в большей степени влияет на Core2 нежели на P4 Northwood
PS: Ради интереса приведи частоты CPU, FSB и ОЗУ для P4 и Core2

 

Параметры такие:
Core 2 Duo E8500 3,16 ГГц/1333MHz/6M, DDR3 1333MHz.
P4 2400/533MHz, DDR 400MHz.

Мне конечно приходило в голову, что комп с лесом быстрее упирается в пропускную способность памяти, но что разница может быть такой. На P4 разница ноль, а на коре в разы. Хотя конечно частота DDR3 в три раза выше, да и параметры у неё вроде получше.

Это я не понял, ведь кора с архитектурой P6, а лес NetBurst.

 

Booster

Это мягко говоря не так. То есть, формально, конечно Core2 построен на тех же принципах, что и Pentium Pro, но раза в два с лишним эффективнее на той же частоте. А лес всего-навсего NetBurst - архитектура, которую многие не любят, и я, каюсь, в том числе.

Неверно. Даже наоборот, можно сказать

[offtop]
leo

В Ваттах
[/offtop]

 

Ustus

Почему-же не так? Конечно P6 лучше NetBurst-а.

Да, был не прав, латентность у неё вроде выше. Но в данном случае она не должна влиять, так как данные извлекаются последовательно и плотно.

 

И ещё я не понимаю почему Крис пишет, что скорость запись байтов равна скорости записи двойных слов. Скорее всего запись определяется латентностью, так как префетча здесь быть не может. Даже если запись всё равно идёт побайтово, то не факт что так будет везде и всегда. Да и от памяти зависит. У меня на P4, хоть и на немного (5%-10%), но всё таки запись двойных слов стабильно быстрее. ^)

 

Ну, во-первых, у Криса и в мануалах написано, что записываемые данные помещаются сначала в буферы записи, а вовсе не сразу в память.
Во-вторых, предвыборки нет, но если в кэше уже есть то, куда мы пишем, то из буфера записи данные помещаются в кэш, помечая эту строку "грязной"
Так что в моём понимании запись определяется вовсе не латентностью.
leo, я прав?

 

Tier
Согласен, там отложенная запись, и значит больше пропускная способность. Но всё равно думаю, что есть разница гоняем ли мы цикл 4000 или 1000 раз.

 

Booster
Я так полагаю: за счёт того, что запись dword'ами является раскруткой цикла записи байтами в 4 раза, то именно из-за раскрутки мы и получим преимущество. Если запись байтами развернуть в 4 раза (т.е. записывать по четыре байта за итерацию, но не одним dword'ом, а именно байтами), то мы скомпенсируем разницу.
Отсюда, возможно, и идёт вывод о том, что разницы в скорости записи байтами и dword'ами нету... Повторю: возможно... я так думаю...

 

Tier
Это не развёртка, а меньшее кол-во выполняемых команд. При развёртке главная фишка - параллельность, а не уменьшение суммарных тактов цикла. У меня есть прирост от записи dword-ами, а вот от развёртки нету. Так что это всё очень индивидуально, но всё равно по-моему есть смысл делать развёртку и писать двойными словами.