Есть массив DWORD'ов. Нужна максимально быстрая процедура для его обнуления. memset не предлагать!

Здравствуйте, Alfarn, Вы писали:

A>Есть массив DWORD'ов. Нужна максимально быстрая процедура для его обнуления. memset не предлагать!

А чем плох memset ?

Здравствуйте, Аноним, Вы писали:

А>А чем плох memset?

У меня очень критично по скорости, хотелось бы оптимизацию на асме, именно для обнуления массива

Здравствуйте, Alfarn, Вы писали:

A>Здравствуйте, Аноним, Вы писали:

А>>А чем плох memset?

A>У меня очень критично по скорости, хотелось бы оптимизацию на асме, именно для обнуления массива

Я точно не помню синтакис инструкции, но попробуй lodsb или lodsw с префиксом числа повторений.

Здравствуйте, Alfarn, Вы писали:

A>Есть массив DWORD'ов. Нужна максимально быстрая процедура для его обнуления. memset не предлагать!

С использованием MMX или без ?
Размер массива ?

Здравствуйте, Alfarn, Вы писали:

A>Есть массив DWORD'ов. Нужна максимально быстрая процедура для его обнуления. memset не предлагать!
ZeroMemory(... ) работает достаточно быстро...

> Я точно не помню синтакис инструкции, но попробуй lodsb или lodsw с
> префиксом числа повторений.
>
Только не lods, а stos!!!

cld    ;Идём слева направо
mov    ecx,РазмерМассиваВБайтах
shr    ecx,2    ;Делим на 4, получаем количество элементов в массиве
xor    eax,eax    ;То, что будем записывать в массив - 0
mov    edi,АдресМассива
rep    stosd    ;Сохраняем значение eax по адресу edi, ecx=ecx-1, edi=edi+4, если ecx=0, то заканчиваем выполнение команды

Здравствуйте, Stanky, Вы писали:

S>Только не lods, а stos!!!

S>

S>cld    ;Идём слева направо
S>mov    ecx,РазмерМассиваВБайтах
S>shr    ecx,2    ;Делим на 4, получаем количество элементов в массиве
S>xor    eax,eax    ;То, что будем записывать в массив - 0
S>mov    edi,АдресМассива
S>rep    stosd    ;Сохраняем значение eax по адресу edi, ecx=ecx-1, edi=edi+4, если ecx=0, то заканчиваем выполнение команды
S>

ну, memset как раз так и работает..

> ну, memset как раз так и работает..
>
Ну не совсем, но близко!!!
memset — универсальная штука, а здесь расчитанно именно под конкретную задачу!!!

Здравствуйте, Stanky, Вы писали:

>> ну, memset как раз так и работает..
>>
S>Ну не совсем, но близко!!!
S>memset — универсальная штука, а здесь расчитанно именно под конкретную задачу!!!

Ну очень близко:
int array[64];
memset(array, 0, 64);
0040110D 33 C0 xor eax,eax
0040110F B9 10 00 00 00 mov ecx,10h
00401114 8D 7C 24 08 lea edi,[esp+8]
00401118 F3 AB rep stos dword ptr [edi]

> Ну очень близко:
>
Ну ладно, пусть это тоже самое, что и memset, но как-нидь это мона ускорить?
Даст чего-нидь 64-х разрядная шина данных или нет?

> 0040110F B9 10 00 00 00 mov ecx,10h
>
А вот это кстати враньё!!! Откуда в функции взялось конкретное значение количества элементов?
Тут должно быть: lea edi,[esp+4]!!!

Да и всё-равно memset универсальна и должна проверять размер на кратность 4, ну или адрес на границу двойного слова!!!

> Тут должно быть: lea edi,[esp+4]!!!
>
Упс: lea ecx,[esp+4]!!!

Здравствуйте, Stanky, Вы писали:

>> 0040110F B9 10 00 00 00 mov ecx,10h
>>
S>А вот это кстати враньё!!! Откуда в функции взялось конкретное значение количества элементов?
S>Тут должно быть: lea edi,[esp+4]!!!

Так она ж инлайном встроена.

S>Да и всё-равно memset универсальна и должна проверять размер на кратность 4, ну или адрес на границу двойного слова!!!

Это если функция.

Здравствуйте, Stanky, Вы писали:

>> Тут должно быть: lea edi,[esp+4]!!!
>>
S>Упс: lea ecx,[esp+4]!!!

Да не lea, а mov.

> Это если функция.
>
Да ладно, не обращайте внимание — ночью на меня тупёж наступал!!!

Здравствуйте, Alfarn, Вы писали:

A>Есть массив DWORD'ов. Нужна максимально быстрая процедура для его обнуления. memset не предлагать!

Я думаю, быстрее чем команда STOS ничего найти не удастся...

Здравствуйте, zix, Вы писали:

zix>Здравствуйте, Alfarn, Вы писали:

A>>Есть массив DWORD'ов. Нужна максимально быстрая процедура для его обнуления. memset не предлагать!

zix>Я думаю, быстрее чем команда STOS ничего найти не удастся...
если обнуляемый массив нормально выровнен через mmx быстрее будет

Здравствуйте, mokc0der, Вы писали:

A>>>Есть массив DWORD'ов. Нужна максимально быстрая процедура для его обнуления. memset не предлагать!

zix>>Я думаю, быстрее чем команда STOS ничего найти не удастся...
M>если обнуляемый массив нормально выровнен через mmx быстрее будет

Точно!

mmx,(3dnow, 3dnow+) sse, sse2 самое быстрое последнее 128 бит за цикл.

Здравствуйте, OpenGL, Вы писали:

OGL>mmx,(3dnow, 3dnow+) sse, sse2 самое быстрое последнее 128 бит за цикл.
не возможности протестировать sse2, но разницы между обнулением через mmx(64bit) и xmm(128bit) нет ни какой. Это протестировано

Здравствуйте, zix, Вы писали:

zix>Здравствуйте, Alfarn, Вы писали:

A>>Есть массив DWORD'ов. Нужна максимально быстрая процедура для его обнуления. memset не предлагать!

zix>Я думаю, быстрее чем команда STOS ничего найти не удастся...

Крис Касперски описывал алгоритм, который позволяет сделать функции memset,memcpy быстрее. Для этого надо знать про кэши. Суть в том, чтобы периодически обращаться к памяти, которая будет обрабатываться позже, а затем продолжать операции.
В итоге к тому моменту когда очередь дойдет до той памяти, её содержимое уже будет в кэше.

Несколько стратегий (можно комбинировать):
1) находим точку вычищаемого блока, начинающуюся на границе N байт (где N — сколько байт будем чистить одной инструкцией), и чистим начиная с нее (т.е. соблюдая выравнивание); остальное дотираем вручную.
2) возможно, поможет TLB priming. Вообще говоря, этот прием предназначен скорее для чтения данных, но, может статься, ускорит и запись. Речь идет о том, чтобы каждый раз перед переходом записи на границу новой страницы (4К) заранее обращаться к одному элементу на этой странице, чтобы ее данные успели подгрузиться в TLB (Transaction Lookaside Buffer).
3) ну и, конечно, если доступен набор команд MMX, можно юзать MMX-инструкции, а еще лучше SIMD 2. На P4 инструкция MOVAPS ворочает по 128 бит за одну операцию. Если так роскошествовать не получается, можно пользоваться MOVQ. Между прочим, MOVAPS требует 16-байтного выравнивания точки записи.

Кроме того, есть еще как минимум 2 интересных подхода.
I) воспользоваться страничной адресацией: замапить на весь требуемый диапазон логического адресного пространства одну и ту же (или несколько) страницу памяти, которую предварительно зануляем. Есть некоторые шансы (не проверял), что VirtualAlloc, например, 32 страниц будет работать быстрее, чем заполнение нулями 32*4=128 Кб данных. Режим защиты можно указать PAGE_WRITECOPY — тогда при любых изменениях этой области памяти будут создаваться новые физические страницы.
II) пропатчить процесс, обрабатывающий данные, так, чтобы он их вообще не читал, а сразу полагал равными 0. По окончании нужной операции можно пропатчить обратно. Проблема, которая видна сразу же — если в том процессе работает несколько потоков, одновременно обрабатывающих одним кодом разные области данных, будет плохо.

Slicer

Здравствуйте, Alfarn, Вы писали:

A>Есть массив DWORD'ов.
A>Нужна максимально быстрая процедура для его обнуления. memset не предлагать!

Думаю, альтернативы для memset (или его клонов) просто нет.

Что касается ассемблера, то самая быстрая получается инструкция movq.
В принципе, то как следует работать с кэшем вот здесь.
Пример, правда, для AMD и для memcpy. Но я переделывал его для memset и для memcmp.
Работает и на Intel и на AMD.

S>Что касается ассемблера, то самая быстрая получается инструкция movq.
Точно не MOVAPS и иже с ней? Разрядность-то поболее будет.

Slicer

Все оказалость намного интереснее. CreateFileMapping работает очень быстро (7-8 тысяч тактов на моем Athlon64) даже при выделении блоков памяти порядка 64Мб — и при этом создаваемые страницы считаются зануленными. Т.е. сама подготовка памяти происходит моментально. Правда, можно проиграть при ее реальном использовании

Slicer

Здравствуйте, MShura, Вы писали:

M> Здравствуйте, zix, Вы писали:
M>
zix>> Здравствуйте, Alfarn, Вы писали:
M>
A>>> Есть массив DWORD'ов. Нужна максимально быстрая процедура для его
A>>> обнуления. memset не предлагать!
M>
zix>> Я думаю, быстрее чем команда STOS ничего найти не удастся...
M>
M> Крис Касперски описывал алгоритм, который позволяет сделать функции
M> memset,memcpy быстрее. Для этого надо знать про кэши. Суть в том, чтобы
M> периодически обращаться к памяти, которая будет обрабатываться позже, а
M> затем продолжать операции. В итоге к тому моменту когда очередь дойдет
M> до той памяти, её содержимое уже будет в кэше.

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

-- Всего хорошего!
-- Alex Alexandrov, e-mail: alex_alexandrov@fromru.com

Здравствуйте, Alex Alexandrov, Вы писали:


[Sorry, skipped]

M>> Крис Касперски описывал алгоритм, который позволяет сделать функции
M>> memset,memcpy быстрее. Для этого надо знать про кэши. Суть в том, чтобы
M>> периодически обращаться к памяти, которая будет обрабатываться позже, а
M>> затем продолжать операции. В итоге к тому моменту когда очередь дойдет
M>> до той памяти, её содержимое уже будет в кэше.
AA>
AA> Непонятно. Если ты последовательно забиваешь память нулями, то каждая
AA> линейка кэша будет ровно один раз прочитана и ровно один раз сброшена
AA> обратно — чего хитрить-то?
AA>
AA> -- Всего хорошего!
AA> -- Alex Alexandrov, e-mail: alex_alexandrov@fromru.com

Хотя стоп — если имелась в виду инструкция PREFETCH, то нормально — действительно поможет.

-- Всего хорошего!
-- Alex Alexandrov, e-mail: alex_alexandrov@fromru.com

Здравствуйте, Alex Alexandrov, Вы писали:

AA>Хотя стоп — если имелась в виду инструкция PREFETCH, то нормально — действительно поможет.

А я вот не думаю, что поможет. Что проку от предвыборки, если нам надо не читать, а писать данные? Тут наоборот должна помочь именно опережающая запись одной ячейки в следующую страницу. Потому что 1) в отличие от чтения, код не ждет завершения операции (из-за чего, видимо, и ввели PREFETCH), 2) выполняется TLB priming. А больше вроде как ничего и не надо.

А чем вас, господа, не устроило мое предложение поизвращаться с файл-маппингом?

Slicer

Здравствуйте, Slicer [Mirkwood], Вы писали:

SM> Здравствуйте, Alex Alexandrov, Вы писали:
SM>
AA>> Хотя стоп — если имелась в виду инструкция PREFETCH, то нормально -
AA>> действительно поможет.
SM>
SM> А я вот не думаю, что поможет. Что проку от предвыборки, если нам надо
SM> не читать, а писать данные? Тут наоборот должна помочь именно
SM> опережающая запись одной ячейки в следующую страницу. Потому что
SM> 1) в отличие от чтения, код не ждет завершения операции (из-за чего,
SM> видимо, и ввели PREFETCH), 2) выполняется TLB priming. А больше вроде
SM> как ничего и не надо.
SM>
SM> А чем вас, господа, не устроило мое предложение поизвращаться с
SM> файл-маппингом?
SM>
SM> Slicer

Политика записи по умолчанию — write-back. Т.е. происходит запись в кэш и немедленный возврат, а в основную память данные записываются асинхронно. Однако кэш и для чтения, и для записи один, поэтому перед записью линейка должна быть прочитана из памяти. PREFETCH помогает это сделать заранее.
Насчет TLB. Кэширование и трансляция адресов — вещи ортогональные. Одно другому не мешает. Только опять же упредить трансляцию адресов можно только в случае наличия аналога PREFETCH для TLB. Т.е. что-то типа PREFETCHTLB. Поскольку в противном случае (попытки упреждающей записи одной ячейки в следующую страницу) при последовательном проходе (мы же рассматриваем обнуление, так?) выгоды не будет. Какая разница, произойдет TLB_MISSED penalty на твоей упреждающей записи или на первой записи при реальном переходе на следующую страницу...

-- Всего хорошего!
-- Alex Alexandrov, e-mail: alex_alexandrov@fromru.com

AA>Политика записи по умолчанию — write-back. Т.е. происходит запись в кэш и немедленный возврат, а в основную память данные записываются асинхронно. Однако кэш и для чтения, и для записи один, поэтому перед записью линейка должна быть прочитана из памяти. PREFETCH помогает это сделать заранее.
Хм, надо обратиться к первоисточникам. На самом деле, идея та, что микрооперации инструкции записи начнут выполнение в одном из конвейеров, а т.к. от результата записи никакие другие инструкции кода не зависят, то можно сразу же запускать последующие команды кода. Но это что касается "deeply pipelined" процессоров (как P4), а вот для остальных, может, и не так.

AA>Насчет TLB. Кэширование и трансляция адресов — вещи ортогональные. Одно другому не мешает. Только опять же упредить трансляцию адресов можно только в случае наличия аналога PREFETCH для TLB. Т.е. что-то типа PREFETCHTLB. Поскольку в противном случае (попытки упреждающей записи одной ячейки в следующую страницу) при последовательном проходе (мы же рассматриваем обнуление, так?) выгоды не будет. Какая разница, произойдет TLB_MISSED penalty на твоей упреждающей записи или на первой записи при реальном переходе на следующую страницу...
Ну, см. предыдущий ответ — penalty на данную операцию записи ведь не вызовет полный останов всех конвейеров.

Slicer

SM>Ну, см. предыдущий ответ — penalty на данную операцию записи ведь не вызовет полный останов всех конвейеров.
А, не то объяснял )) В смысле — так застрянет одна операция, а если выполнить первый доступ к странице уже при последовательной записи, застрянут столько инструкций, сколько успеет набиться в конвейеры до окончания загрузки в TLB. Хотя, с другой стороны, может, ты и прав — все равно, вроде бы (не уверен) микрооперации доступа к памяти обслуживает всего один модуль процессора, так что ждать в любом случае придется всем последующим пишущим инструкциям.

Slicer

Здравствуйте, Alfarn, Вы писали:

A>Есть массив DWORD'ов. Нужна максимально быстрая процедура для его обнуления. memset не предлагать!

Раз DWORD то скорее всего под виндой , тогда удобно юзать эти:

void ZeroMemory(
PVOID Destination,
SIZE_T Length
);


PVOID SecureZeroMemory(
PVOID ptr,
SIZE_T cnt
);

Первая это по сути макро (может оптимизироваться по разному при компиляции — подставлять конкретные значения и т.д.).
Вторая — функция (inline).

Здравствуйте, Alfarn, Вы писали:

A> Есть массив DWORD'ов. Нужна максимально быстрая процедура для его
A> обнуления. memset не предлагать!

Еще, кстати, можно ускорить обнуление путем его отложения на некоторое время. Суть простая: памяти делается VirtualProtect(PAGE_NOACCESS), потом ловим исключения Access Violation и если ошибка доступа произошла на странице из нашего массива — делаем VirtualProtect(PAGE_READWRITE), обнуляем страницу и возвращаем EXCEPTION_CONTINUE_EXECUTION. Особенно может улучшить производительность, если не факт, что вся обнуляемая память будет задействована в будущем. Минусы — код обнуления размазывается по нескольким местам.

-- Всего хорошего!
-- Alex Alexandrov, e-mail: alex_alexandrov@fromru.com

Здравствуйте, mokc0der, Вы писали:

M>Здравствуйте, OpenGL, Вы писали:

OGL>>mmx,(3dnow, 3dnow+) sse, sse2 самое быстрое последнее 128 бит за цикл.
M>не возможности протестировать sse2, но разницы между обнулением через mmx(64bit) и xmm(128bit) нет ни какой. Это протестировано

Дело в том что я имел ввиду параллельное выполнение и использование U V конвееров тогда разница будет заметна.
Там за такт два mov можно сделать!

Здравствуйте, Alfarn, Вы писали:

A>Есть массив DWORD'ов. Нужна максимально быстрая процедура для его обнуления. memset не предлагать!

Можно попробовать посмотреть на результаты компилятора Intel C Compiler. Я предполагаю использование /O3. При том, что компилятор может вычислить размер обнуляемой памяти на этапе компиляции он генерирует примерно следующий код. Первой инструкцией он обнуляет 1 из xmm регистров (SSE инструкции), а затем просто выполняет mov за movом в память, двигаясь от младших адресов к старшим. Таких movов лично я видел пару страниц. Учитывая, что обнуление памяти — частая задача, я думаю, что такое поведение специально запрограммировано и даёт наилучшие результаты. Естествено для P4. Будет ли такой код оптимальным для Athlon неизвестно.