Здравствуйте!

ЗАДАЧА
Пишу sw просмотра файла в некотором граф. векторном формате.
Содержимое файла можно упрощенно представить как совокупность координат ломанных.

При отображении на экран произвожу преобразование координат из внутренних в экранные.
Преобразование имеет вид:
x' = k1*x + b1
y' = k2*y + b2

ВОПРОС:
Преобразование выполняется очень часто (к тому же в файле порядка млн. точек)
Это фактически умножение вектора на число и сложение вектора с числом.
Есть желание пооптимизировать функцию преобразования координат.
КАК? ПОСОВЕТУЙТЕ!

Была идея использовать для умножения векторов MMX инструкции.
НО
1) Нет желания писать на ассемблере, а библиотека Intel (подключаемый файл #include "mmintrin.h") похоже доступна только с VC 7.0.Так просто библиотеки для MMX на просторах INET я не встретил. К тому же я пока сижу на Builder, и даже , если соберусь перейти на VC, не хочется ограничивать себя последней версией VC.
2) У меня массив из миллиона int, а для MMX это придётся свести к порциям по 4 short. Не факт, что выйдет выигрыш.

ЧТО ВЫ СКАЖЕТЕ НАСЧЁТ ММХ?

заранее Спасибо!!!

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

VV>Здравствуйте!

VV>ЗАДАЧА
VV>Пишу sw просмотра файла в некотором граф. векторном формате.
VV>Содержимое файла можно упрощенно представить как совокупность координат ломанных.

VV>При отображении на экран произвожу преобразование координат из внутренних в экранные.
VV>Преобразование имеет вид:
VV>x' = k1*x + b1
VV>y' = k2*y + b2

VV>ВОПРОС:
VV>Преобразование выполняется очень часто (к тому же в файле порядка млн. точек)
VV>Это фактически умножение вектора на число и сложение вектора с числом.
VV>Есть желание пооптимизировать функцию преобразования координат.
VV>КАК? ПОСОВЕТУЙТЕ!

VV>Была идея использовать для умножения векторов MMX инструкции.
VV>НО
VV>1) Нет желания писать на ассемблере, а библиотека Intel (подключаемый файл #include "mmintrin.h") похоже доступна только с VC 7.0.Так просто библиотеки для MMX на просторах INET я не встретил. К тому же я пока сижу на Builder, и даже , если соберусь перейти на VC, не хочется ограничивать себя последней версией VC.
VV>2) У меня массив из миллиона int, а для MMX это придётся свести к порциям по 4 short. Не факт, что выйдет выигрыш.

VV>ЧТО ВЫ СКАЖЕТЕ НАСЧЁТ ММХ?

VV>заранее Спасибо!!!

если нет возможности попользовать Intel C compiler, то тогда ручками — ММХ, SSE, SSE2. Прибыль получится очень даже ощутимая — ускорение чтения/записи из кучи, векторное умножение, сложение, вычитание, .... раскрутка циклов. Суммарно можно наскрести (в зависимости от реализации конечно ) от 2 до 10 раз совершенно реально.

Здравствуйте, Sergey A. Sablin, Вы писали:


SAS>если нет возможности попользовать Intel C compiler, то тогда ручками — ММХ, SSE, SSE2. Прибыль получится очень даже ощутимая — ускорение чтения/записи из кучи, векторное умножение, сложение, вычитание, .... раскрутка циклов. Суммарно можно наскрести (в зависимости от реализации конечно ) от 2 до 10 раз совершенно реально.

Большое спасибо.
Может всё таки подскажете — в каких средах/компиляторах и где вообще доступны c-библиотеки для mmx, sse, sse2?

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

VV>Здравствуйте, Sergey A. Sablin, Вы писали:


SAS>>если нет возможности попользовать Intel C compiler, то тогда ручками — ММХ, SSE, SSE2. Прибыль получится очень даже ощутимая — ускорение чтения/записи из кучи, векторное умножение, сложение, вычитание, .... раскрутка циклов. Суммарно можно наскрести (в зависимости от реализации конечно ) от 2 до 10 раз совершенно реально.

VV>Большое спасибо.
VV>Может всё таки подскажете — в каких средах/компиляторах и где вообще доступны c-библиотеки для mmx, sse, sse2?

что ты имеешь ввиду под "c-библиотеки для mmx, sse, sse2"? Это ассемблер и его писать нужно ручками, если же ты говоришь об intrinsic-функциях, то в VC7 и интелевом компиллере. Также последний умеет самостоятельно оптимизить код с помощью SSE2 — совершенно без твоего участия. Говорят помогает.

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

VV>Здравствуйте, Sergey A. Sablin, Вы писали:

SAS>>если нет возможности попользовать Intel C compiler, то тогда ручками — ММХ, SSE, SSE2. Прибыль получится очень даже ощутимая — ускорение чтения/записи из кучи, векторное умножение, сложение, вычитание, .... раскрутка циклов. Суммарно можно наскрести (в зависимости от реализации конечно ) от 2 до 10 раз совершенно реально.

VV>Большое спасибо.
VV>Может всё таки подскажете — в каких средах/компиляторах и где вообще доступны c-библиотеки для mmx, sse, sse2?

Вижу здесь много не совсем конкретного написали. Во-первых, компилятор такие циклы оптимизирует достаточно грамотно.

Во-вторых, главное тут для скорости отвязаться от дробных чисел. ТО есть например коэффициенты K домножить га 0x1000 и затем результат сдвинуть на >>12 бит.

В-третьих. Складывать и умножать действительно надо векторами. И использовать разумеется ММХа, SSы, и Сри Дэ Нау.

А четыре -- ето для поддержки всего этого добра скачать просто напросто Microsoft Visual Studio 6.0 processor pack. И будет счастье и заодно с сэмплами где уже есть реализованные на асме функции перемножения и сложения векторов. остаётся только на этапе запуска программы детектить тип процессора(для чего опять таки есть сэмпл в паке).

P.S. в циклах желатель использовать указатели для итераторов.
P.P.S На днях ускорили один видеоэффект в 10 раз! Путём замены дробных чисел на целые, загона косинуса в таблицу и уменьшением количества вычислений(типа 5*5*5*5*5=((5*5)^2)*5). правда он стал нечитаемым.

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

VV>Здравствуйте, Sergey A. Sablin, Вы писали:


SAS>>если нет возможности попользовать Intel C compiler, то тогда ручками — ММХ, SSE, SSE2. Прибыль получится очень даже ощутимая — ускорение чтения/записи из кучи, векторное умножение, сложение, вычитание, .... раскрутка циклов. Суммарно можно наскрести (в зависимости от реализации конечно ) от 2 до 10 раз совершенно реально.

да... Чуть не забыл операции лучше производить над участками памяти которые влазят в кэш процессора. Это даёт значительный выйгрыш по скорости. то есть ежели кэш два кила, а работаем с четырьмя векторами, хде 4-х байтные элементы, то имеем длину 2048/4/4=128 елементов в векторе. Что это значит: Исходный вектор например 1024 элементов. Надо разбивать его на участки по 128 элементов и извращаться на ними. Надеюсь понятно объяснил.

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

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

VV>>Здравствуйте, Sergey A. Sablin, Вы писали:


SAS>>>если нет возможности попользовать Intel C compiler, то тогда ручками — ММХ, SSE, SSE2. Прибыль получится очень даже ощутимая — ускорение чтения/записи из кучи, векторное умножение, сложение, вычитание, .... раскрутка циклов. Суммарно можно наскрести (в зависимости от реализации конечно ) от 2 до 10 раз совершенно реально.

PSP>да... Чуть не забыл операции лучше производить над участками памяти которые влазят в кэш процессора. Это даёт значительный выйгрыш по скорости. то есть ежели кэш два кила, а работаем с четырьмя векторами, хде 4-х байтные элементы, то имеем длину 2048/4/4=128 елементов в векторе. Что это значит: Исходный вектор например 1024 элементов. Надо разбивать его на участки по 128 элементов и извращаться на ними. Надеюсь понятно объяснил.

Почитайте на досуге математику хардварного префетча из интелевого и амдшного instruction set'а. И еще про софтверный префетч. Может еще раза в два ускорите.
В общем случае вычисления (читай код и данные) нужно использовать в таком порядке, в котором процессор будет способен распознать(предугадать) чего вы хотите в следующий момент, что не есть то, что вы написали. При особом желании, ему(процессору) в этом можно помочь.

Относительно вашего примера (я так понял что задача все так же) — вычисляя y=a*x+b для двух векторов совершенно не нужно их делит на куски, достаточно просто производить вычисления последовательно по всей длине векторов — процессор автоматически подгрузит в кэш необходимые вам данные. А вот если вы начнете прыгать в произвольном порядке по этим векторам, то никакое разбиение и даже префетчи вам не помогут. И не дай вам бог распределить вектор на адрес не кратный 16 — хоть пачками обрабатывайте вектора, кэш-сплит убъет насмерть все ваши поползновения чтения из кэша для каждого четвертого ссе2 регистра при 64 байтной длине кэш линии.

Здравствуйте, Sergey A. Sablin, Вы писали:



SAS>Относительно вашего примера (я так понял что задача все так же) — вычисляя y=a*x+b для двух векторов совершенно не нужно их делит на куски, достаточно просто производить вычисления последовательно по всей длине векторов — процессор автоматически подгрузит в кэш необходимые вам данные. А вот если вы начнете прыгать в произвольном порядке по этим векторам, то никакое разбиение и даже префетчи вам не помогут. И не дай вам бог распределить вектор на адрес не кратный 16 — хоть пачками обрабатывайте вектора, кэш-сплит убъет насмерть все ваши поползновения чтения из кэша для каждого четвертого ссе2 регистра при 64 байтной длине кэш линии.

Спасибо за многочисленные реккомендации.
Насчёт последовательных вычислений.
У меня x,y ДОЛЖНЫ храниться в видет массива TPoint (т.к. затем идут вызовы PolyLine). Поэтому говорить о последовательном обращении к y-ам (например) не приходится...Будет постоянный скачок через 1.(пропускаем x — преобразуем y — пропускаем х — преобразуем y итд.) Выходит, что, судя по вашей последней фразе, никакого выигрыша от использования MMX etc. не выйдет?

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

VV>Здравствуйте, Sergey A. Sablin, Вы писали:



SAS>>Относительно вашего примера (я так понял что задача все так же) — вычисляя y=a*x+b для двух векторов совершенно не нужно их делит на куски, достаточно просто производить вычисления последовательно по всей длине векторов — процессор автоматически подгрузит в кэш необходимые вам данные. А вот если вы начнете прыгать в произвольном порядке по этим векторам, то никакое разбиение и даже префетчи вам не помогут. И не дай вам бог распределить вектор на адрес не кратный 16 — хоть пачками обрабатывайте вектора, кэш-сплит убъет насмерть все ваши поползновения чтения из кэша для каждого четвертого ссе2 регистра при 64 байтной длине кэш линии.

VV>Спасибо за многочисленные реккомендации.
VV>Насчёт последовательных вычислений.
VV>У меня x,y ДОЛЖНЫ храниться в видет массива TPoint (т.к. затем идут вызовы PolyLine). Поэтому говорить о последовательном обращении к y-ам (например) не приходится...Будет постоянный скачок через 1.(пропускаем x — преобразуем y — пропускаем х — преобразуем y итд.) Выходит, что, судя по вашей последней фразе, никакого выигрыша от использования MMX etc. не выйдет?
это не совсем произвольный доступ (это даже в некоторых случаях лучше, чем x отдельно и y отдельно) — такие ситуации очень просто обрабатываются. Если я правильно понял, то у тебя такая ситуация:

x0, y0, x1, y1, x2, y2, x3, y3 ...

тебе нужно сделать преобразование yi=a*xi+b. собсна вот код на целочисленном SSE:
ecx — начало твоего вектора,
eax — a (short)
edx — b (short)
x и y — short, результат допустим тоже short, и для простоты промежуточные результаты тоже не могут превышать short

__asm
{
movd mm2, eax
movd mm3, edx
pshufw mm2, mm2, 0 // [a, a, a, a]
pshufw mm3, mm3, 0 // [b, b, b, b]

movq mm0, qword ptr [ecx] // [trash, x1, trash, x0]
movq mm1, qword ptr [ecx+8] // [trash, x3, trash, x2]
pand mm0, x0000ffff0000ffff // [0, x1, 0, x0]
pand mm1, x0000ffff0000ffff // [0, x3, 0, x2]
packssdw mm0, mm1 // [x3, x2, x1, x0]
movq mm4, mm0

pmullw mm4, mm2 // [a*x3, a*x2, a*x1, a*x0]
paddw mm4, mm3 // [a*x3+b, a*x2+b, a*x1+b, a*x0+b] = [y3, y2, y1, y0]
movq mm1, mm0
punpcklwd mm0, mm4 // [y1, x1, y0, x0]
punpckhwd mm1, mm4 // [y3, x3, y2, x2]

movq qword ptr [ecx], mm0
movq qword ptr [ecx+8], mm1
}

заворачиваем это в цикл и в общем всё. Дальше scheduling с помощью какой-нить VTune или AMD CodeAnalyst.

Здравствуйте, Sergey A. Sablin, Вы писали:


SAS>тебе нужно сделать преобразование yi=a*xi+b. собсна вот код на целочисленном SSE:
Спасибо за код. Он мне, я думаю, поможет при разборе полётов.
Однако преоразование совершенно другое -> См 1 сообщение топика:

x' = k1*x + b1
y' = k2*y + b2

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

VV>Здравствуйте, Sergey A. Sablin, Вы писали:


SAS>>тебе нужно сделать преобразование yi=a*xi+b. собсна вот код на целочисленном SSE:
VV>Спасибо за код. Он мне, я думаю, поможет при разборе полётов.
VV>Однако преоразование совершенно другое -> См 1 сообщение топика:

VV>

VV>x' = k1*x + b1
VV>y' = k2*y + b2

еще проще

eax — [k2, k1] (short, short)
edx — [b2, b1] (short, short)

__asm
{
movd mm2, eax
movd mm3, edx
pshufw mm2, mm2, 0x44 // [k2, k1, k2, k1]
pshufw mm3, mm3, 0x44 // [b2, b1, b2, b1]

movq mm0, qword ptr [ecx] // [y1, x1, y0, x0]
movq mm1, qword ptr [ecx+8] // [y3, x3, y2, x2]

pmullw mm0, mm2 // [k2*y1, k1*x1, k2*y0, k1*x0]
pmullw mm1, mm2 // [k2*y3, k1*x3, k2*y2, k1*x2]
paddw mm0, mm3 // [k2*y1+b2, k1*x1+b1, k2*y0+b2, k1*x0+b1] = [y1', x1', y0', x0']
paddw mm1, mm3 // [k2*y3+b2, k1*x3+b1, k2*y2+b2, k1*x2+b1] = [y3', x3', y2', x2']

movq qword ptr [ecx], mm0
movq qword ptr [ecx+8], mm1
}