Re: 32->16 (565) - Низкоуровневое программирование

Всем привет.

Есть некий цикл, делающий блиттинг куска памяти, преобразовывая на ходу из 32 бит RGB в 16 бит, 565. При ближайшем рассмотрении оказалось, что там делается следующее (тут блок из 2-х точек):

        mov    al, [esi+4]
        add    edi, 4
        shr    al, 3
        mov    bh, [esi+5]
        shl    ebx, 10h
        mov    dl, [esi]
        shr    dl, 3
        mov    ah, [esi+6]
        shl    eax, 10h
        mov    bh, [esi+1]
        shr    ebx, 5
        mov    dh, [esi+2]
        or    eax, edx
        add    esi, 8
        and    eax, 0F81FF81Fh
        and    ebx, 7E007E0h
        or    eax, ebx
        mov    [edi], eax

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

        mov eax, [esi]        
        mov ebx, eax        
        shr ah, 2
        shr eax, 3
        shr ebx, 8
        and eax, 07FFh
        and ebx, 0F800h
        mov edx, [esi + 4]
        or  eax,ebx        
        mov ebx, edx        
        shr dh, 2
        shl ebx, 8
        and edx, 03FF8h
        and ebx, 0F8000000h
        shl edx, 13
        add esi, 8
        or  eax, ebx
        add edi, 4        
        or  eax, edx                
        mov [edi], eax

В результате получили ... снижение производительности (небольшое — буквально тысячные доли процента, но тем не менее, стабильное).
Вопрос — как бы это дело поинтереснее оптимизировать (без MMX — вариант для него уже есть). Тут уже дело, конечно, не в производительности, а просто самому стало интересно. Чувствую, что можно еще выжать из этого, но как —

Видимо, глаз замылился? Интересно будет послушать ваши соображения

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

AS>Есть некий цикл, делающий блиттинг куска памяти, преобразовывая на ходу из 32 бит RGB в 16 бит, 565. При ближайшем рассмотрении оказалось, что там делается следующее (тут блок из 2-х точек):
AS>[/asm]

AS>Очевидно, что читать по байту из выровненой памяти — не самый, скажем так, оптимальный вариант. В связи с чем была предпринята попытка нанести непоправимую пользу:

AS>

AS>        mov eax, [esi]        
AS>        mov ebx, eax        
AS>        shr ah, 2
AS>        shr eax, 3
AS>        shr ebx, 8
AS>        and eax, 07FFh
AS>        and ebx, 0F800h
AS>        mov edx, [esi + 4]
AS>        or  eax,ebx        
AS>        mov ebx, edx        
AS>        shr dh, 2
AS>        shl ebx, 8
AS>        and edx, 03FF8h
AS>        and ebx, 0F8000000h
AS>        shl edx, 13
AS>        add esi, 8
AS>        or  eax, ebx
AS>        add edi, 4        
AS>        or  eax, edx                
AS>        mov [edi], eax
AS>

не вникая в сущность я бы сделал так

        lodsd    
        mov ebx, eax        
        shr ah, 2
        shr eax, 3
        shr ebx, 8
        and eax, 07FFh
        and ebx, 0F800h
        mov edx, [esi]
        or  eax,ebx        
        shr dh, 2
        mov ebx, edx        
        shl ebx, 8
        and edx, 03FF8h
        and ebx, 0F8000000h
        shl edx, 13
        or  eax, ebx
        add esi, 4
        or  eax, edx                
        stosd ; тут мы пишем не в EDI+4 а в EDI, надо EDI перед циклом увеличить на 4

ну и cld вне цикла и коррекция EDI.
нет никакой гарантии, что lods/stosd выполняются быстрей чем mov eax, [esi]; add esi, 4

а так лучше VTUNE посмотреть

СМ>не вникая в сущность я бы сделал так
СМ>

СМ>        lodsd    
СМ>        mov ebx, eax        
СМ>        shr ah, 2
СМ>        shr eax, 3
СМ>        shr ebx, 8
СМ>        and eax, 07FFh
СМ>        and ebx, 0F800h
СМ>        mov edx, [esi]
СМ>        or  eax,ebx        
СМ>        shr dh, 2
СМ>        mov ebx, edx        
СМ>        shl ebx, 8
СМ>        and edx, 03FF8h
СМ>        and ebx, 0F8000000h
СМ>        shl edx, 13
СМ>        or  eax, ebx
СМ>        add esi, 4
СМ>        or  eax, edx                
СМ>        stosd ; тут мы пишем не в EDI+4 а в EDI, надо EDI перед циклом увеличить на 4
СМ>

СМ>ну и cld вне цикла и коррекция EDI.

СМ>нет никакой гарантии, что lods/stosd выполняются быстрей чем mov eax, [esi]; add esi, 4

Конечно, нет. Они выполнятся медленнее

Вопрос не в том, как быстрее работать с памятью — это я и сам знаю. Вопрос в том, как быстрее запаковать 2 32-х битные точки в один 32-х битный регистр в формате 5-6-5 или 5-5-5 — т.е. может есть какой хитрый биттрик.
Впрочем, я потом измерил производтельность еще раз, минимизировав нагрузку на систему — мой вариант дает выигрыш порядка 10% от первоначального.Но вопрос все-равно интересен

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

СМ>>нет никакой гарантии, что lods/stosd выполняются быстрей чем mov eax, [esi]; add esi, 4

AS>Конечно, нет. Они выполнятся медленнее

1. а есть уверенность для всех типов проц?
2. размер уменьшается и больше в кеш попадет

AS>Вопрос не в том, как быстрее работать с памятью — это я и сам знаю. Вопрос в том, как быстрее запаковать 2 32-х битные точки в один 32-х битный регистр в формате 5-6-5 или 5-5-5 — т.е. может есть какой хитрый биттрик.
AS>Впрочем, я потом измерил производтельность еще раз, минимизировав нагрузку на систему — мой вариант дает выигрыш порядка 10% от первоначального.Но вопрос все-равно интересен

СМ>>>нет никакой гарантии, что lods/stosd выполняются быстрей чем mov eax, [esi]; add esi, 4

AS>>Конечно, нет. Они выполнятся медленнее

СМ>1. а есть уверенность для всех типов проц?

Для почти всех — этого достаточно.

СМ>2. размер уменьшается и больше в кеш попадет

То, что умещается в jmp short, и так с гарантией 99% попадает в кеш — а там _весь_ цикл в это попадает

Тут больше дело в обвязке — каждая лишняя команда дает 2-3 процента проигрыша. По командам первоначальный вариант меньше...

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

AS>В результате получили ... снижение производительности

Вот что кэш животворящий делает...

AS>>В результате получили ... снижение производительности

MC>Вот что кэш животворящий делает...

Ага. Меня на самом деле беспокоит ситуация с пайплайнингом, то бишь, как это будет работать на п4 (имеющиеся варианты реализации этого на mmx, как ни странно, медленнее). Надо будет сделать пару тестов... уж больно все недетерменировано.

PS — приведенные куски кода — из аллегро. Руки поотрывал бы, блин.

AS>В результате получили ... снижение производительности (небольшое — буквально тысячные доли процента, но тем не менее, стабильное).
AS>Вопрос — как бы это дело поинтереснее оптимизировать (без MMX — вариант для него уже есть). Тут уже дело, конечно, не в производительности, а просто самому стало интересно. Чувствую, что можно еще выжать из этого, но как —

Видимо, глаз замылился? Интересно будет послушать ваши соображения

Если кому интересно, смог немного улучшить:

        mov eax, [esi + 4]
        mov ebx, eax        
        shl ax, 5
        shl ebx, 16
        shl eax, 8

        mov edx, [esi]
        add esi, 8
        mov bx, dx                
        shr edx, 8
        mov al, bl
        mov ah, dh
        shr al, 3
        shr ebx, 5
        and eax, 0F81FF81Fh
        and ebx, 07E007E0h
        add edi, 4
        or  eax, ebx
        mov [edi-4], eax

Все это вместе дало прибавку порядка 10 процентов над исходным вариантом, и 2.5 процентов над предыдущим. Вероятно, и тут еще есть над чем поработать, потому что даже простая перестановка команд меняет соотношения на проценты

Но Code Analist у меня работать на домашней машине не захотел — просто вываливается с ошибкой доступа по адресу

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

AS>Вероятно, и тут еще есть над чем поработать.
Мне кажется, удобнее конвертировать в 15-битный формат. Например, так:

        mov    eax, [esi + 4]
        mov    ebx, [esi]
        shr    eax, 3
        shr    ebx, 3
        shl    al, 3
        shl    bl, 3
        shl    ax, 3
        shl    bx, 3
        shl    eax, 10
        shr    ebx, 6
        or    eax, ebx
        lea    esi, esi + 8
        mov    [edi], eax
        lea    edi, edi + 4

К сожалению, данный код некорректен, посколько не учитывает возможность ненулевого альфа-байта. При наличии оного, ессно, получается кака.
Маскирование добавляет к нему все те же самые 2 "больших" and.
Ну а во-вторых, что значит "проще"? Это абсолютно разные форматы, и для 5-5-5 отдельные процедуры уже есть

Ну и в третьих — lea с индексными регистрами не есть хорошо.

AS>>Вероятно, и тут еще есть над чем поработать.
M>Мне кажется, удобнее конвертировать в 15-битный формат. Например, так:
M>

M>        mov    eax, [esi + 4]
M>        mov    ebx, [esi]
M>        shr    eax, 3
M>        shr    ebx, 3
M>        shl    al, 3
M>        shl    bl, 3
M>        shl    ax, 3
M>        shl    bx, 3
M>        shl    eax, 10
M>        shr    ebx, 6
M>        or    eax, ebx
M>        lea    esi, esi + 8
M>        mov    [edi], eax
M>        lea    edi, edi + 4
M>

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

AS>К сожалению, данный код некорректен, посколько не учитывает возможность ненулевого альфа-байта. При наличии оного, ессно, получается кака.
Согласен.

AS>Маскирование добавляет к нему все те же самые 2 "больших" and.
Не согласен, одного "большого" AND будет достаточно.

AS>Ну а во-вторых, что значит "проще"?
Ну выглядит логичнее и понятнее

AS>Это абсолютно разные форматы, и для 5-5-5 отдельные процедуры уже есть

Я ориентировался на более раннее сообщение:
AS>Вопрос не в том, как быстрее работать с памятью — это я и сам знаю. Вопрос в том, как быстрее запаковать 2 32-х битные точки в один 32-х битный регистр в формате 5-6-5 или 5-5-5 — т.е. может есть какой хитрый биттрик.
Вот это "5-5-5" меня и заинтересовало.

AS>Ну и в третьих — lea с индексными регистрами не есть хорошо.
Да, но LEA не затрагивает флаги.

AS>>К сожалению, данный код некорректен, посколько не учитывает возможность ненулевого альфа-байта. При наличии оного, ессно, получается кака.
M>Согласен.

AS>>Маскирование добавляет к нему все те же самые 2 "больших" and.
M>Не согласен, одного "большого" AND будет достаточно.

Например? Одна "кака" получается в старшем бите, а вторая кака — в младших, при OR.

AS>>Ну а во-вторых, что значит "проще"?
M>Ну выглядит логичнее и понятнее

Зато тот код работает с любыми непрерывными масками

В аллегро его в макрос вытащили, и для 5-6-5 и 5-5-5 один код пользуется.

В любом случае, спасибо за обсуждение — получается интересно.
Теперь, в общем, я выяснил, что сдвиг — это неправильный способ преобразования даже в форматы с меньшей глубиной цвета (хотя gdi внутри себя именно так и делает). Особенно это хорошо это заметно на 32->8(332). Придется, видимо, делать лукап таблицы.

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

AS>Например? Одна "кака" получается в старшем бите, а вторая кака — в младших, при OR.
Например, заменяем

        or    eax, ebx

на

        or    ax, bx
        and    eax, $7FFF7FFF

Или вместо OR можно MOV использовать.

AS>В любом случае, спасибо за обсуждение — получается интересно.
Согласен.

AS>Теперь, в общем, я выяснил, что сдвиг — это неправильный способ преобразования даже в форматы с меньшей глубиной цвета (хотя gdi внутри себя именно так и делает). Особенно это хорошо это заметно на 32->8(332). Придется, видимо, делать лукап таблицы.
Весьма может быть. В общем, если чего интересное получится, напишите, хорошо?

M>Или вместо OR можно MOV использовать.

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

AS>>Теперь, в общем, я выяснил, что сдвиг — это неправильный способ преобразования даже в форматы с меньшей глубиной цвета (хотя gdi внутри себя именно так и делает). Особенно это хорошо это заметно на 32->8(332). Придется, видимо, делать лукап таблицы.
M>Весьма может быть. В общем, если чего интересное получится, напишите, хорошо?

Интересные результаты, пожалуй, только для обратного преобразования. То бишь 5-5(6)-5 -> 0-8-8-8
Общепринято его делать при помощи 2-х лукап таблиц. Оказывается, можно сделать быстро банальными сдвигами.
Смысл вот в чем. Классическая формула преобразования глубины цвета — dst = (src* dst_max)/src_max. При ближайшем рассмотрении битового представления src и dst видно, что, вообще говоря, остатки циклически повторяются. То бишь для (5->8) потчти всегда получается (54321) -> (54321)(543). Для 5->8 находится 4 исключения, где ошибка на единичку, а для 6->8 — 8 исключений, тоже с ошибкой в единичку, что, вероятно, на качество результата не влияет.

Я попробовал это реализовать — для 5-5-5 -> 8-8-8 получается очень эффективная процедура кодирования, результат быстрее, чем с использованием таблиц. Для 5-6-5 дело похуже, немного медленнее получается, и вариантов оптимизации не видно. Но, к сожалению, нормально оптимизировать это для 24 битов не получается — таблицами удобнее, поскольку сдвиги (а, точнее, вращения) можно (и нужно) в самих таблицах делать.

Да, и что самое интересное. Выяснилось, что результаты, получаемые при помоши преобразования только на сдвигах, полностью совпадают с оными от gdi (в отличие от таблиц, которые дают _абсолютно_ правильный результат). Так что, вестимо, gdi на линейке NT довольно неглупые люди писали

А с учетом того, что реализация gdi всего в 2 раза медленнее моей, и учитывая накладные раходы на вызов блиттинга в gdi, можно подумать, что там даже и поэффективней закодировано. Я ж говорю — есть тут биттрики, точно. Надо просто искать...

От:	Andrew S	http://alchemy-lab.com
Дата:	23.01.07 19:34
Оценка:

	От:	Сергей Мухин
	Дата:	24.01.07 06:10
	Оценка:

От:	Andrew S	http://alchemy-lab.com
Дата:	24.01.07 11:13
Оценка:

	От:	Сергей Мухин
	Дата:	24.01.07 12:29
	Оценка:

От:	Andrew S	http://alchemy-lab.com
Дата:	24.01.07 12:37
Оценка:

	От:	Michael Chelnokov
	Дата:	24.01.07 19:10
	Оценка:

	От:	maxxlu
	Дата:	27.01.07 14:45
	Оценка:

	От:	maxxlu
	Дата:	30.01.07 19:53
	Оценка:	8 (1)

	От:	maxxlu
	Дата:	31.01.07 18:56
	Оценка: