[Bill 0]

Наверное признаком DSP является не только наличие быстрого умножителя с накопителем, а в значительной мере, аппаратная поддержка пересылок без команд mov и аппаратная поддержка организации циклов: индексации в массивах и переходов. В общем всего, что связано с матричными вычислениями

Я как раз об этом и написал. Выполнение цикла за 1 такт.

[Tium 0]

x86 тащит за собой жуткое количество устаревшего барахла - достаточно взглянуть на справочник по командам. Несколько сотен инструкций! Конечно, совместимость, я все понимаю, но есть сильное ощущение какой-то телеги с мусором. MMX/SSE/SSE2 трудно назвать удачными расширениями. Наверное, у Интела просто не осталось способа резко поднять производительность. Но получить хорошее ускорение хоть на MMX, хоть на SSE2 весьма непросто, в том числе из-за накладных расходов. Кстати, искать подстроку на MMX - по-моему, сомнительная идея. Как мало-мальски изящно проверить результат? Проще сравнивать строки как 32-битовые integer без всякого MMX. Уже быстрее, чем побайтно.

 

Эх, сам был энтузиастом лет 5-6 назад :(

[Evgeny_CD 0]

...x86 тащит за собой жуткое количество устаревшего барахла - достаточно взглянуть на справочник по командам. Несколько сотен инструкций! Конечно, совместимость, я все понимаю, но есть сильное ощущение какой-то телеги с мусором. MMX/SSE/SSE2 трудно назвать удачными расширениями. Наверное, у Интела просто не осталось способа резко поднять производительность. Но получить хорошее ускорение хоть на MMX, хоть на SSE2 весьма непросто, в том числе из-за накладных расходов. Кстати, искать подстроку на MMX - по-моему, сомнительная идея. Как мало-мальски изящно проверить результат? Проще сравнивать строки как 32-битовые integer без всякого MMX. Уже быстрее, чем побайтно....

Видимо, это какой-то тайный закон Мэрфи, который знают Интел & AMD. Как говорят дети "почему все, что полезное - невкусное?". На свете существует штук 5 правильных процессорных архитектур MIPS | PowerPC | Alpha | Sparc | ARM ( с некоторой натяжкой ) - но их суммарные тиражи много меньше, чем у кривого x86. И перспектив покончить с безобразием нет. AMD продает Alchemy, Intel собирается продавать PXA. :maniac:

[defunct 0]

Кстати, искать подстроку на MMX - по-моему, сомнительная идея. Как мало-мальски изящно проверить результат? Проще сравнивать строки как 32-битовые integer без всякого MMX. Уже быстрее, чем побайтно.

Это не сомнительная идея. Это уже реализованная и проверенная идея. В fastcode первое место заняли функции поиска именно с использованием MMX. Можете посмотреть результаты и взять исходники заинтересовавших вас функций http://dennishomepage.gugs-cats.dk/PosChallenge.htm

ссылка у меня почему-то в данный момент не открывается, но взята она из вполне достоверного источника:

http://qc.borland.com/qc/wc/qcmain.aspx?d=14084

 

Если вам интересна эта тема, то у меня где-то осталась тестовая программа А. Шарахова, которая позволяет довольно изящно проверить результат. В программе проверяются и сравниваются по быстродействию различные функции поиска, написанные под IA-32 и под все виды ускорителей для x86. Сам когда-то хотел принять участие в PosChallenge, но не сложилость.

[Tium 0]

[Видимо, это какой-то тайный закон Мэрфи, который знают Интел & AMD. Как говорят дети "почему все, что полезное - невкусное?". На свете существует штук 5 правильных процессорных архитектур MIPS | PowerPC | Alpha | Sparc | ARM ( с некоторой натяжкой ) - но их суммарные тиражи много меньше, чем у кривого x86. И перспектив покончить с безобразием нет. AMD продает Alchemy, Intel собирается продавать PXA. :maniac:

Да, и вписывая нелегкие алгоритмы в 8 регистров общего назначения, я жестоко завидовал RISC-"коллегам по цеху". У них команд было мало, а регистров много!

[Tium 0]

Это не сомнительная идея. Это уже реализованная и проверенная идея. В fastcode первое место заняли функции поиска именно с использованием MMX. Можете посмотреть результаты и взять исходники заинтересовавших вас функций http://dennishomepage.gugs-cats.dk/PosChallenge.htm

Очень хочу посмотреть, но эта (первая) ссылка у меня дала ошибку 404.

 

ссылка у меня почему-то в данный момент не открывается, но взята она из вполне достоверного источника:

http://qc.borland.com/qc/wc/qcmain.aspx?d=14084

 

Если вам интересна эта тема, то у меня где-то осталась тестовая программа А. Шарахова, которая позволяет довольно изящно проверить результат. В программе проверяются и сравниваются по быстродействию различные функции поиска, написанные под IA-32 и под все виды ускорителей для x86. Сам когда-то хотел принять участие в PosChallenge, но не сложилость.

Эта вторая ссылка открылась, там сказано про программу А.Шарахова, которая "3.20 times faster than the current RTL Pos function". Но при этом "It is using basic IA32 instructions only and will run on all processors after 386." Если у вас есть исходный текст поиска с ММХ, интересно было бы посмотреть. Хотя бы на ключевые операторы. Учиться никогда не поздно. :)

[defunct 0]

Эта вторая ссылка открылась, там сказано про программу А.Шарахова, которая "3.20 times faster than the current RTL Pos function". Но при этом "It is using basic IA32 instructions only and will run on all processors after 386." Если у вас есть исходный текст поиска с ММХ, интересно было бы посмотреть. Хотя бы на ключевые операторы. Учиться никогда не поздно. :)

 

Новых функций, о которых на той странице идет речь у меня нет.

Есть тестовая программа за 2004 год с исходниками на которой тестировались функции, тогда еще Шарахов не писал свои функции на ассемблере, но там есть моя функция (posdefmmx), написанная совместно с GuAV, не принимавшая участие в fastcode и функции John'a PosJohnMMXA/B на 2004-й год - победители PosChallenge. Программу с исходниками прикрепил. Существенный выигрыш от MMX проявляется естественно только при поиске в длинных строках (SubBench2 в программе), на коротких строках там поиск выполняется на IA-32.

PosBV.zip

[Tium 0]

Новых функций, о которых на той странице идет речь у меня нет.

Есть тестовая программа за 2004 год с исходниками на которой тестировались функции, тогда еще Шарахов не писал свои функции на ассемблере, но там есть моя функция (posdefmmx), написанная совместно с GuAV, не принимавшая участие в fastcode и функции John'a PosJohnMMXA/B на 2004-й год - победители PosChallenge. Программу с исходниками прикрепил. Существенный выигрыш от MMX проявляется естественно только при поиске в длинных строках (SubBench2 в программе), на коротких строках там поиск выполняется на IA-32.

Спасибо, скопировал, буду изучать. :) Сообщу, что получилось. Почему засомневался - писал как-то FastCopy на SSE2. На коротких строках победил IA-32, на длинных - SSE2, но, насколько помню, исключительно за счет unrolled пар movdqa/movntdq.

[defunct 0]

писал как-то FastCopy на SSE2. На коротких строках победил IA-32, на длинных - SSE2, но, насколько помню, исключительно за счет unrolled пар movdqa/movntdq.

 

В задаче поиска ускорение за счет pcmpeqb и movq (с выравниваением на границу QWord).

[Tium 0]

Так, вроде разобрался. У вас основную работу делают характерные группы операторов типа:

 

Метка:

MovQ MM7, [EDx] // load a part of buffer that needs to be scaned

PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant)

PACKSSWB MM7, MM7

MovD EAx, MM7 // get mixed dword

Test EAx, EAx // was there at least 1 bit set?

Jnz CharFound2 // yes - 1st char of the constant was found

 

Add EDx,8 // correct index

Sub ECx,8 // and buffer size

Cmp ECx,4

Jg Метка

 

Здесь вы ищете начало совпадения строки и подстроки - это в общем случае бОльшая часть работы.

То же самое можно сделать иначе. В моем примере ecx содержит число слов в строке, а edx в каждом байте - искомый начальный байт подстроки:

 

MainCycle:

mov esi, DWORD PTR[edi] // Загружаем очередные 4 байта строки

xor esi, edx

 

test esi, 0xFF

jz short Lab_1

test esi, 0xFF00

jz short Lab_2

test esi, 0xFF0000

jz short Lab_3

test esi, 0xFF000000

jz short Lab_4

 

add edi, 4

sub ecx, 1

jnz short MainCycle

 

Метки Lab_1..Lab_4 можно использовать, например, так:

Lab_4:

add eax, 1

Lab_3:

add eax, 1

Lab_2:

add eax, 1

Lab_1:

add eax, 1

тогда получим индекс искомого байта в DWORD. Или можно сдвигом получить совп.байт+остаток регистра (чтобы сравнивать дальше).

 

В тесте я брал строки разной длины и искал в них заведомо отсутствующий байт. Результаты получились следующие (на двух разных ПК с P4):

строка 1000 байт: версия IA-32 быстрее на 10-20%

строка 4000 байт: ММХ и IA-32 примерно равны

строка 8Мб: ММХ быстрее на 13-25%

 

MMX кроме графики применим хотя бы для банального поиска подстроки в строке (сравнение сразу 8 байт с одним шаблонным байтом) и подобных задач. Выигрыш по сравнению с IA-32 получается коллосальным (в 4-5 раз).

 

Где же здесь 4-5 раз?

 

Выходит то, о чем я и говорил: получить серьезное ускорение с SIMD-расширений x86 непросто. Лично мне это удавалось на операциях типа умножений векторов, или при параллельном делении - тогда IA-32 отстает безнадежно. Но и то, требуется полный цикл оптимизации, начиная с алгоритма (скажем, для ММХ - переход к целочисленному варианту).

[defunct 0]

В тесте я брал строки разной длины и искал в них заведомо отсутствующий байт. Результаты получились следующие (на двух разных ПК с P4):

строка 1000 байт: версия IA-32 быстрее на 10-20%

строка 4000 байт: ММХ и IA-32 примерно равны

строка 8Мб: ММХ быстрее на 13-25%

Неправда Ваша. Результаты и близко не соответствуют действительности. Пересмотрите пожалуйста. Для проверки можете использовать приведенную выше программу Шарахова. (Длинными там считаются строки более 64 байт).

[Tium 0]

Неправда Ваша. Результаты и близко не соответствуют действительности. Пересмотрите пожалуйста.

Что ж, вполне мог и ошибиться. Но ведь я привел код, который сравнивал. Что-то в нем неадекватно?

Для проверки можете использовать приведенную выше программу Шарахова.

Уточните, пожалуйста, это файл PosBV.zip? Если да, то код MMX взят именно оттуда.

(Длинными там считаются строки более 64 байт).

Интересный вопрос, что такое длинная строка. По-моему, если она помещается в 2..4 линии кэша, то длинной ее считать нельзя.

[defunct 0]

Интересный вопрос, что такое длинная строка. По-моему, если она помещается в 2..4 линии кэша, то длинной ее считать нельзя.

Я тоже так считаю. Однако, даже на строках длиной в 64 байта поиск с помощью MMX выполняется быстрее.

Уточните, пожалуйста, это файл PosBV.zip?

Да, (exe-шник в архиве предназначается для оценки скорости). SubBench1 - короткие строки (до 8-ми символов). SubBench2 "длинные" - все остальные (больше 8ми символов), доминирует размер 64 байта.

 

Но ведь я привел код, который сравнивал. Что-то в нем неадекватно?

В коде ничего неадкватного нет, и трактовка кода у Вас правильная. Однако результат сравнения несправедлив. Вероятно Вы рассматривали при тестировании какой-то частный случай (к примеру один из частных случаев - искомая подстрока находится постоянно очень близко к началу строки, при этом сказывается замедление вызываемое инициализацией MMX). Рассматривайте также и худший случай - когда искомой подстроки в строке нет.

[Tium 0]

В коде ничего неадкватного нет, и трактовка кода у Вас правильная. Однако результат сравнения несправедлив. Вероятно Вы рассматривали при тестировании какой-то частный случай (к примеру один из частных случаев - искомая подстрока находится постоянно очень близко к началу строки, при этом сказывается замедление вызываемое инициализацией MMX). Рассматривайте также и худший случай - когда искомой подстроки в строке нет.

Кажется, я где-то выше писал, что при тестировании рассматривал только один случай - именно наихудший - когда подстроки в строке нет. Для этого вот таким образом был сформирован бинарный файл размером 8x10**6 байт:

for (int iIdx=0; iIdx < iFileLen; iIdx++)

sOutput[iIdx] = iIdx % 0xFF;

(Это писалось в Memory-mapped файл)

 

Он состоял из значений от 0 до 0xFE, а 0xFF отсутствовал. Именно он и искался в строке. Были проверены варианты с длиной 1000, 4000 байт и с полным файлом. Вот код, запускавший нужную функцию:

 

for (int i=0; i<CYCLE_QUANT; i++){

GetProcClocksFull(&i64Time);

 

// int iResult = TestMMX(pbSubStr,pbStr,1000);

// int iResult = TestMMX(pbSubStr,pbStr,iBufLen);

// int iResult = TestIA32(pbSubStr,pbStr,1000);

int iResult = TestIA32(pbSubStr,pbStr,iBufLen);

 

GetProcClocksFull(&i64Time2);

DWORD dwDeltaTime = (DWORD)((i64Time2 / 1000) - (i64Time / 1000));

// DWORD dwDeltaTime = (DWORD)((i64Time2) - (i64Time));

ToLog(REPORT_FILE,"%u\n",dwDeltaTime);

}

 

Чтобы не спорить впустую, проще довериться цифрам. Я подготовлю несколько файлов для запуска и выложу их здесь.

Изменено 3 июля, 2006 пользователем AndrewKirs

[Tium 0]

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

 

Коротко говоря: defunct прав и не прав одновременно. Прав, потому что на ММХ можно получить заметный выигрыш (для P4 Intel говорил, что "хорошо" - это 10%). Не прав, потому что выигрыш будет не 3-4 раза, и не на любой задаче.

 

Вот данные по выигрышу ММХ на задаче поиска отсутствующего байта, полученные на моем P4:

 

16 байт: 18% - 21%

128 байт: 1.48 - 2.28 раза

1000 байт: 1.42 - 1.84 раза

8 млн.байт: 1.54 - 1.55 (для I вызова I прогона - 1.25).

 

Это суммарный результат, "сырые" данные в файле Report.Full.P4.txt. Тестовые программы для ММХ и для IA32 включали по два прогона, в каждом по 10 вызовов тестовой функции. Всего получилось 8 программ для ММХ и 8 - для IA32 (4 варианта длин "только чтение" и 4 варианта "чтение/поиск"). Обратите внимание, что результаты либо в тактах, либо в тактах, деленных на 1000. Первая цифра в первом тестовом прогоне стабильно больше - здесь выигрыш ММХ сводится к нескольким процентам. Для второго прогона вычисляется среднее за 10 вызовов функции. Соответственно, есть 2 паттерна применения подобных функций. По моим результатам получается, что наиболее удачный для MMX паттерн - повторяющийся поиск строк длиной порядка 100-1000 байт, выигрыш составит 1.5 - 2 раза. То есть получается что-то вроде поиска в большом массиве или списке, строковые элементы которого расположены вместе в едином блоке памяти. В принципе, реально, хотя выигрыш и не в 3-4 раза. Поиск в большом файле - даст меньший выигрыш, и только при повторном поиске.

 

В любом случае, есть смысл "разгонять" только "узкие места" программы. Не факт, что скорость программы будет зависеть именно от поиска. Например, поиск в буфере 8 млн.байт на IA32 занял 14.5 млн.тактов(машина 1.7ГГц). Это значит 0.0085 сек.

 

Выигрыш под x64 гораздо больше (3 раза на 8 мб), но там новая архитектура и об оптимизации нужно думать тоже заново.

 

В целом, я такого мнения об ММХ - он мне кажется "тяжеловатым", что ли. "Легкие" команды IA32 стартуют "с места" и требуют по 0.5/1 такта, в 2 параллельных потока. Поэтому полезно использовать их всегда, когда возможно.

 

Конкретно, мне удавалось получать хороший выигрыш на ММХ на графических задачах с большим числом целочисленных умножений. Но, например, при копировании данных ММХ/SSE/SSE2 выигрывали только начиная с определенного размера (16 Кб).

 

Attached-файлы: Report.RO.P4.txt - тесты для ММХ/IA32, разные длины буферов, только чтение; Report.Full.P4.txt - то же, но с поиском.

 

exe-файлы, наверное, выкладывать не стану. Если кому нужны, пишите - передам вместе с инструкциями по использованию.

Report.Full.P4.txt

Report.RO.P4.txt