Оптимизация и полиморфный код

Нашел оптимальный способ бороться с пересечением кеш-линеек: Последние 4 байта текущей линейки и первые 4 следующей копируются в временную переменную (8 байт) однозначно ничего не пересекающую. При этом кстати автоматически производится префетч. В конце итерации используется обычное чтение из этой переменной.

На копирование уходит по моим прикидкам 2 такта, тогда как чтение напрямую обходится в 10 и более штрафных такта (чтение 3-х значений со смежных линеек).

Ну и практический результат: 620мб/с вместо 540мб/с. Файлик нового алгоритма прилагаю.

[edited]

В fscan.asm вкралась ошибка - параметры макросов не могут

состоять из выражений, поэтом алгоритм проверял каждую ячейку по 4 раза. Вот исправленный участок:

Код (Text):

1.  
2. REPT                    0Ch
3.                         Compset                 a, N 1, 1
4.                         O = N + 10h
5.                         Compset                 c, O, 1, 1
6.                         O = N + 20h
7.                         Compset                 d, O, 1, 1
8.                         O = N + 30h
9.                         Compset                 b, O, 1, 1
10.                         N = N + 1
11.                         ENDM
12.  

Исправление хорошо сказалось на производительности, скорость поиска по максимуму достигала 645мб/с. Для сравнения: AMD Athlon XP 2000+ (1666): 422мб/с, разогнаный до 2600+ (2083):512мб/с (КТ400, DDR333), и Celeron 2400 после разгона до 3246: 840мб/с (Asus P4B533-X). Как видно код очень чувствителен к частоте камня.

_2082663491__ffscan.zip

 

Переделал memcopy benchmark by S_T_A_S_, на макросы. Бесхитростная развертка цикла, работает чуть быстрее чем обычное mmx копирование (+3мб/с), но по сравнению с movntq тормозит.



191175025__memcopy2.Asm

 

>

А разгонял подъёмом частоты шины ?

 

>S_T_A_S_

Верно гнал по шине. Хотя в любом случае, я не ожидал такого ускорения. Да и от Атлона ожидал чуть побольше, все таки со сдвигами он получше справляется.

Соотношения:

Код (Text):

1.  
2. AMD Athlon XP
3. ext.clock 133, FSB266, cpu clock = 1667, scan 420 mb/s
4. ext.clock 167, FSB333, cpu clock = 2083, scan 512 mb/s
5. Intel Celeron
6. ext.clock 100, FSB400, cpu = 2400, scan 645 mb/s
7. ext.clock 133, FSB533, cpu = 3200, scan 840 mb/s
8.  

В приближенных расчетах скорость пропорциональна частоте

FSB, и частоте процессора.

 

Я бы сказал так:

скорость пропорциональна частоте FSB

и частота проца пропорциональна частоте FSB.

т.е. имеем 2 величины (a и b), зависящие от FSB, говорить же, что a зависит от b imho не правильно.

Что бы проверить, зависит ли скорость от частоты ядра, нужно 2 проца с разной частотой, но одинаковой FSB.

 

Да хорошо бы. Удалось еще ускорить после замены в макросах

Код (Text):

1.  
2.  or      ah, al
3.  shl     eax, 1
4. на
5.  ror     eax, 1
6.  

Эти замены для всех регистров позволяют более эффективно параллелить команды: cmp + ror, и setcc отдельно (не парится ?), ориентировочно 3 такта на эти 3 комманды. Алгоритм несколько поменялся, порядок битов теперь соответствует порядку байт.

Еще избавился от двух операций условного перехода.

На неотлаженном коде пока получены след. результаты:

iCel2.4 @2405: 822 mb/sec

iCel2.4 @3200: 1076 mb/sec

AthlonX 2000+ @1667: 465 mb/sec

Похоже на iCel, все таки частота камня что то значит. После отладки буду встраивать его в программу, ибо выжать чего либо еще уже почти невозможно.

[edited]

Delphi не выравнивает процедуры / функции даже по 8 байтной границе, производительность скачет, при изменении совершенно левого кода. Пришлось написать код для принудительного выравнивания, после чего на Athlone скорость достигла 476mb/sec.

Нашел пример использования SMC на нужды оптимизации:

http://algolist.manual.ru/graphics/3dfaq/articles/62.php

_48185361__asm.zip

 

Скачал AMD CodeAnalyst 2.34 и не глядя натравил его на код. Среди тяжелых инструкций он нашел сначала только mov ebp, [esi + 40], которая обращается к данным вне кэша. Пришлось вынести весь prefetch во внешний цикл, от чего скорость возрасла с 476 до 553мб/c.

В принципе неплохой результат, около 3 тактов на кажое проверенное смещение. Сейчас наибольшее торможение вызывает: первая инструкция записи результов mov [edi], ecx - 1,2% ее удельное время выполнения за одну итерацию. Существенно тормозит и чтение невыровненных данных попадающих в различные банки, каждая инструкция читающая их инструкция имеет около 1% удельного времени исполнения.

При всем при этом 47% всего времени тратиться на prefetch цикл.

 

Session Type делал Timer Trigger ?

Попробуй ещё Simulation - там картинки показывают, мне сильно помогли как-то.

 

>S_T_A_S_

Тулза требует файл отладочной информации .pdb для эмуляции конвеера. Delphi+Tasm такой файл сгенерить не могут, может есть конвертор? А так придется написать и на Visual Це++ тестовое приложение, и прилинковать к нем полученые objики, ради получения этого файла.

Пока меня в устраивают текущие достижения. Проверка кода вынесеного prefetch на Селероне дала всего 530мб/с против 822мб/с. Так что с аппартным префетчем он луше работает, что в принципе и обьясняет его превосходство в 0.2% над Атлоном (на одинаковых частотах).

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

[edited]

Запуск на Селероне CA показал, что самая тяжелая инструкция все-таки та что обращается к памяти отсутствующей в кэше. Торможение за счет внещнего префетча, на самом деле объясняется малым размером кэша L1 у Селерона, по сравнению с размером блока подгружаемых данных (64К-64), при этом кэш L2 его не спасает.

Если обратно вставить условные переходы в участке RLE упаковки скорость возрастает до 953мб/с. Однако когда на входе будут реальные данные, ошибочные предсказания переходов скорость сильно снизят, что я конечно проверю.

 

alpet >

Конвертера нет. Есть скрипт, частично решающий задачу. Не для всех случаев, но иногда помогает.

 

Попробую конвертер, но в любом случае буду искать/писать тулзу для извлечения/конвертации отладочной инфы.

Пока же я попробывал этот код прицепить к приложению Це. Удалось его пропустить через AMD CodeAnalyst, результаты меня несколько удивили сначала: инструкции на декодировку лезут по три штуки, и выполнение 3 комманд укладывается в один такт. Missaling добавляет по одному такту на комманду. Но самое главное это delta, для набора одинаково тяжелых инструкций он равен 1, и время выполнения похоже 1 такт. На проверку 64 смещений (одна итерация) в среднем уходит 109 тактов.

Код (Text):

1. ...

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

Возник вопрос: просматривая manual CA, я начал понимать что Event Trigger, работает через performance counters проца. Кто нибудь пытался их использовать (кроме простого замера времени исполнения), и что из этого вышло?

 

alpet >

Попробуй использовать запись через MMX регистры минуя кэш - MOVNTQ.

Иногда даёт неплохой прирост в скорости.

 

2 S_T_A_S_

Я бы с удовольствием - да в большинстве случаев это дело мне нужно в кэше (на крайняк уровня L2). В данном случае проблема не в записи, а в отсутствии необходимой линейки в обоих кэшах, попробую ее префетчить в L2. В худшем случае для 64К смещений получится 16Кбайт результов. Да и потом код при всех достоинствах обязан таки быть совместим с машинами класса PII.

В любом случае весь внешний код роняет прозводительность настолько сильно, что оптимизацией именно этого алгоритма дальше просто бессмысленно. Вчера проверял внутри WGC его - 166 мб/с в обычном режиме (чтение через ReadProcessMemory), и 370 мб/с в Spy-Mode. Может стоит использовать ReadProcessMemory с блоками размером не более чем L1Cache.Size, как-никак она дважды копирует блок памяти с помощью rep movsd, сначала в пространство в ядра, и только потом в пространство процесса?

[edited]

Настроил размер буффера в L2Cache.Size / 2, и скорость поиска возросла до 220мб/с. На Селероне 2.4 при этом недостичь скорости более 180мб/с - сказывается малый объем кэша.

Код (Text):

1. ...

Могут ли три практически подряд идущих в конце каждой итерации инструкции условного перехода, вызывать постоянную ошибку предсказания?

 

Выпустил таки релиз программы. Всем желающим проверить даю линк: http://www.alpet.hotmail.ru/wgc240.zip



Результат весьма хороший, но я планирую его улучшить.

Поискал инфу по PDB файлам, но полезного нашел мало:

http://www.informit.com/articles/article.asp?p=22685&redir=1

http://www.ecn.purdue.edu/~laird/WINE/debugger/msc.c

Код (Text):

1. ...

Вопрос: если использовать обычное копирование в неkэшируемую память (аттрибуты страниц которых настроенны соответствующим образом), можно ли будет добиться производительности сходной с копированием коммандой movntq +sfence ? Ведь копирование в видеопамять таким образом осуществляется.

 

Провел еще мало-мальскую оптимизацию. Теперь эффективность поиска достигла порядка 1,6 тактов на проверку одного смещения (включая не выровненные). По моему больше производительность поднять не удастся. Исходники к программе я открыл для всех кого не отпугивает код на Delphi и TASM. Тут кстати возник вопрос: FASM может генерировать объектники совместимые с Delphi ?



Заодно реализовал возможность проверки только выровненных значений: скорость при сканировании в кэше L1 на AMD2000XP - 4200 МиБ/сек, а в памяти получается около 760 МиБ/сек.

На iCell2400 (+AI Overclk Tuner - на частоту можно не надеятся - вполне может достигать и 3500) этот поиск достигает 1030 МиБ/сек.



МиБ - мебибайт = 1048576 байт, как я узнал оказывается мегабайт на самом деле равен 1000000 байт, причем уже с 1997 года



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

 

Решился таки переписать алгоритмы и на MMX.

Очень не плохой результат получился пока для поиска DWORD значений.

Вот с байтами пока проблема.

Алгоритм должен получать на входе 64 байта, и выдавать 2 множества по 32 бита, где единичные биты соответствуют позициям совпадений.



Вот что будет использоваться пока:

Код (Text):

1.  
2. // File fscaner.cpp
3. #include "stdafx.h"
4. #include "windows.h"
5. typedef unsigned __int64 QWORD;
6.  
7. const QWORD mask = 0x0180018001800180; // 4 битовые пары
8. const QWORD mask2 = 0xFFFF; // 16 lower bits
9.  
10. int _tmain(int argc, _TCHAR* argv[])
11. {
12.     QWORD example = 0; // find zeros
13.  
14.     DWORD bigSize = 64 * 1024 * 1024;
15.     PVOID psrc = VirtualAlloc (NULL, bigSize, MEM_COMMIT, PAGE_READWRITE); 
16.     if (!psrc) return GetLastError ();
17.     ZeroMemory (psrc, bigSize); // for scan zeros
18.     DWORD ticks = GetTickCount ();
19.     _asm
20.     {          
21.         push       eax
22.         push       ecx
23.         push       edx
24.         push       ebx             
25.         push       esi
26.         push       edi     
27.         mov        esi, psrc
28.         mov        edi, bigSize
29.         add        edi, esi     // limit
30.         movq       mm6, example // 8 копий образца
31.         movq       mm5, mask    // Для выделения битовых пар
32.     loop_big:
33.         mov       ebx, 20h
34.         pxor      mm4, mm4
35.     loop_small:
36.         // 16 bytes test per cycle
37.         psllq     mm4, 16      // to high part
38.         movq      mm0, [esi + ebx + 18h]
39.         movq      mm1, [esi + ebx - 08h]
40.         pcmpeqd   mm0, mm6
41.         pcmpeqd   mm1, mm6
42.         pand      mm0, mm5
43.         pand      mm1, mm5  
44.         movq      mm2, mm0
45.         movq      mm3, mm1
46.         psrlq     mm0, 30      // result in low part
47.         psrlq     mm1, 30      // result in high part
48.         por       mm0, mm2
49.         por       mm1, mm3
50.         punpckldq mm0, mm1     // 2 low 32bit parts to one 64bit
51.         psrlq     mm0, 7       // now is normal
52.         movq      mm1, mm0
53.             psrlq     mm0, 28
54.         por       mm0, mm1
55.         punpcklbw mm0, mm0     // pack and complete    
56.         pand      mm0, mask2
57.         por       mm4, mm0     
58.         sub       ebx, 8
59.         jnz       loop_small  
60.         add        esi, 40h  
61.         cmp        esi, edi
62.         jb         loop_big
63.         pop        edi                     
64.         pop        esi
65.         pop        ebx
66.         pop        edx
67.         pop        ecx
68.         pop        eax     
69.         emms
70.     }
71.     ticks = GetTickCount () - ticks;
72.     double speed = 1000 * 64 / ticks; // mb / sec
73.     char tmp [128];
74.     sprintf (tmp, "Scan speed ~= %.2f mb/sec\n", speed);
75.     OutputDebugString (tmp);
76.     VirtualFree (psrc, 0, MEM_RELEASE); // release region
77.     return 0;
78. }
79.  

Но мне не нравится слишком большое количество зависимостей. Может упаковка восьмибайтного множества (для каждого элемента один байт) в восьмибитное и проще как осуществляется?

Алгоритм кстати можно будет запользовать и для поиска строк более 8 байт длинной, если получится достаточно быстрым.



[edited]

В аттаче алгоритм поиска DWORDов. Правда еще не оптимизированный, но уже рабочий.

 

Вот и аттач.

116243119__fscan2.zip

 

Дома добился лучших результатов сканирования - порядка 900мб/сек на AMD AthlonXP 2000+, что очень не плохо для невыровненных значений. Скажем iCell@2400 проигрывает на MMX алгоритме, выдавая около 800мб/сек, хотя это может быть и следствием не правильно рассчитаной дистанции предвыборки (w/prefetchnta).



Старый алгоритм для FASM 709269434__memread2.asm

 

Новые процессоры - новые результаты



_750242187__MemTest2.PNG