Sin Cos

← →
zxcxz © (2006-06-15 20:47) [0]

Слышал что функции sin и cos очень тормозные. В игровом приложении каждый кадр нуждается в вычислении большого количества значений от этих функций. Кто знает на сколько эти функции тормозят работу игрового приложения? И рациональнее ли заменить эти функции на выбор процедурой case of приблизительного значения из таблицы синусов и косинусов?

← →
Rial © (2006-06-15 21:02) [1]

Я уже пробовал сделать то, о чем ты говоришь. В итоге выбор приблизительных
значений из массива заранее просчитанных Sin и Cos оказался даже медленнее.
Заренее говорю, что использовал не самый оптимальный алгоритм.
По-моему, если использовать Case, то
тут точность уж совсем низкая получится.

Да не так уж они и тормозят ....
Вот примерные временные характеристики:
SinCos/Random=3.5
SinCos/* =40

← →
DR0N © (2006-06-15 21:44) [2]

А еще говорят присвоение := сильно тормозит процесс, по этому я решил и отрисовал все сцены заранее в bmp, на 1 уровень получилось около двух миллионов бээмпешек, теперь я их просто меняю и все замечательно.

← →
Rial © (2006-06-15 22:02) [3]

> А еще говорят присвоение := сильно тормозит процесс, по
> этому я решил и отрисовал все сцены заранее в bmp, на 1
> уровень получилось около двух миллионов бээмпешек, теперь
> я их просто меняю и все замечательно.
>

Странно, но мне так кажется, что загрузка от 25 bmp-шек размером
даже 800*600 каждую секунду будет сильно тормозить жесткий диск, поэтому
предложенный Вами способ не будет достаточно эффективным.
И как Вы смогли заранее просчитать все картинки ?
Ведь в зависимости от действий пользовалеля изображение может поменяться ?
Или Вами были заранее просчитаны и нарисованы все возможные вариации ?

← →
Nic © (2006-06-15 22:39) [4]

Нее, сначала всё загружается в память :)

← →
ancara © (2006-06-15 23:00) [5]

> DR0N © (15.06.06 21:44) [2]

О, я играл в такую игру!!! DOOM3 называется!! Просто запускаешь LightAlloy, выбираешь файл с игрой doom3.avi и играешь!! Графика обалденная, тока сюжет не очень.... Прошел с первого раза!

← →
ancara © (2006-06-15 23:08) [6]

Не попутал, она вроде просто doom.avi называлась... но не факт...
А по теме: если строить таблицы sin/cos заранее, то их не через case of надо использовать это точно!!! Я пробовал писать их значения в статич. массивы, размером, скажем 1440 элементов (с шагом 0.25 градуса или 15 минут), но заметного прироста не заметил, поэтому присоединяюсь к > Rial © (15.06.06 21:02) [1].
Оптимизация имеет место самая банальная: если в некоторой функции несколько раз используется синус угла в 22 градуса, то логично посчитать этот синус заранее, записать в локальную переменную и не париться. Лучше уж энтузиазм на оптимизацию умножения матриц направить, если уж на то пошло, хотя это будет очередной велосипед.

← →
tButton © (2006-06-16 04:06) [7]

> Оптимизация

оптимизировать прогу это вам не какашки пинать
нефиг в одну функцию упираться

вот, например у FrOmKo в танчиках
есть вариант, когда поворот спрайтов происходит "на лету",
а есть вариант в котором все спрайты поворачиваются заранее
это конечно памяти больше кушает...
зато на медленых машинах даёт прирост скорости
(гонял на буке P233, 64RAM, 2,5Mb SVGA - лётало)

оптимизировать много чего можно
и вместо того, чтоб на синусы грешить
привёл бы лучше кусок кода

← →
DeadMeat © (2006-06-16 09:25) [8]

На оригинальность и супер скорость не претендую, но по моим тестам и для моей ситуации работает шустрее:

var tb_COS: array of single; tb_SIN: array of single; tb_TAN: array of single; bufang: cardinal; AngleStep: cardinal; tb_SIZE: cardinal; function Cos_rn (const X: single): single; asm FLD X FCOS FWAIT end; function Sin_rn (const X: single): single; asm FLD X FSIN FWAIT end; function Tan_rn (const X: single): single; asm FLD X FPTAN FSTP ST(0) FWAIT end; procedure PrepareAnglesTable (step: cardinal); var i: cardinal; rad: single; buflen: cardinal; counter: double; bufrad: single; steper: single; begin AngleStep := step; buflen := 360 * step; tb_SIZE := buflen; SetLength (tb_SIN, buflen); SetLength (tb_COS, buflen); SetLength (tb_TAN, buflen); steper := 1 / step; counter := 0; bufrad := pi / 180; for i := 0 to buflen - 1 do begin rad := bufrad * counter; tb_SIN[i] := Sin_rn (rad); tb_COS[i] := Cos_rn (rad); tb_TAN[i] := Tan_rn (rad / 2); counter := counter + steper; end; end; function GetIndexFromAngle (angle: single): cardinal; begin result := round ((tb_SIZE * cardinal (angle < 0)) + angle * AngleStep) mod tb_SIZE; end; function ghCos (angle: single): single; begin result := tb_COS[GetIndexFromAngle (angle)]; end; function ghSin (angle: single): single; begin result := tb_SIN[GetIndexFromAngle (angle)]; end; function ghTan (angle: single): single; begin result := tb_TAN[GetIndexFromAngle (angle)]; end; procedure ghSinCosTan (const angle: single; var sin, cos, tan: single); begin bufang := GetIndexFromAngle (angle); sin := tb_SIN [bufang]; cos := tb_COS [bufang]; tan := tb_TAN [bufang]; end; procedure ghSinCos (const angle: single; var sin, cos: single); begin bufang := GetIndexFromAngle (angle); sin := tb_SIN [bufang]; cos := tb_COS [bufang]; end;

Готовится так:
- в начале вызываем PrepareAnglesTable (...) с параметром ШАГ, который означает нашу "точность". Т.е. к примеру вызываем с 1000, получаем шаг сетки в 1/1000 = 0.001
- а потом уже можно вызывать функции вычисления (ghSinCosTan, ghSinCos, ghTan, ghSin, ghCos - остальные это внутренние)

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

Если найдете ошибки, сообщите, т.к. до зверской оптимизации пока руки не дошли.

З.Ы. Углы передаются в градусах (0...360). Можно и отрицательные, можно и дробные в зависимости от шага. Если в шаг не попадают, берется ближайшее значение.

← →
Cash © (2006-06-16 12:57) [9]

Умные дядьки говорят, что если для алгоритма БПФ (Быстрое
преобразование Фурье) предусмотреть таблицу синусов и косинусов, то
накладность алгоритма снижается в десятки раз, а в отдельных случаях
(таких много) - в сотни... Но это БПФ, а что у товарища автора - неизвестно...
(Кто знает и делал БПФ, поймут меня... :) )

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

← →
XProger © (2006-06-16 14:48) [10]

DeadMeat, функцию создания таблиц можно ооочень хорошо оптимизировать зная одну аксиому тригонометрии sin(a) = cos(a + pi/2).

← →
DeadMeat © (2006-06-16 15:35) [11]

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

← →
RzCoDer © (2006-06-17 12:33) [12]

> эта функция вызывается один раз при старте и все.

Можно в обще однажды просчитать и записать всё это в файл ;)

← →
Rial © (2006-06-17 17:09) [13]

И при каждом вызове читать из файла, предварительно вычислив позицию. :)

← →
Tsmar (2006-06-18 00:32) [14]

Rial ©
вот это мороз...

← →
O-lysy (2006-11-01 20:23) [15]

подскажите sin 38?

← →
@!!ex © (2006-11-01 20:29) [16]

Хм. Что за странные споры?
Таблица быстрее.
Это доказали id когда делали первый Дум.
Насколько мне известно в то время народ активно доказывал, что такую игру НЕЛЬЗЯ сделать на существующих системах...
И сидели в ступоре когда видели дум....
Дум как раз и использовал заранее просчитанные значения синусов косиносув....
Чем не доказательство, что это быстрее? :))

← →
XProger © (2006-11-01 20:49) [17]

@!!ex, какая там дискретность прицеливания в думе была? Вот-вот... сейчас во времена сверхчувствительных мышей со снайперки стрелять любят многие ;)
sin/cos считать быстрее во время исполнения (в большинстве случаев)

O-lysy, 0,61566147532565827966881109284366

← →
Ketmar © (2006-11-01 20:55) [18]

>[16] @!!ex(c) 1-Nov-2006, 20:29
>Хм. Что за странные споры?
>Таблица быстрее.
да? ты уверен? учитывая, что в DooM не использовали сопроцессор. а теперь помедитируй над скоростью теперешних сопров и над размерами таблицы, которая засоряет собой кэш.

← →
@!!ex © (2006-11-01 21:05) [19]

> XProger © (01.11.06 20:49) [17]

Так о дискретности никто не говорил. :))
ВОпрос ыл: ыстрее или нет, :))

> Ketmar © (01.11.06 20:55) [18]

Согласен. Возможно не прав.

← →
Rial © (2006-11-01 23:18) [20]

> [19] @!!ex © (01.11.06 21:05)
>
> > XProger © (01.11.06 20:49) [17]
>
> Так о дискретности никто не говорил. :))
> ВОпрос ыл: ыстрее или нет, :))

Ответ - не быстрее.

← →
Shirson © (2006-11-02 08:29) [21]

Замерял буквально дня два назад.
Скорость получения синуса / косинуса из функции приблизительно в 3.5 раза медленее, чем выборка из массива преподсчёта (3600 значений).
Выбор осуществлялся не на прямую, а с предварительным контролем и обработкой. Т.е. условно, угол в 500г переводился в 140г.

← →
XProger © (2006-11-02 08:46) [22]

Shirson, делай выборку из массива 360 000 значений...

← →
DeadMeat © (2006-11-02 08:52) [23]

Так никто мой вариант и не оттестил... Его кстати желательно компилить с inline"ом.

← →
Shirson © (2006-11-02 09:04) [24]

XProger, попробую. Просто для моих нужд точности в 0.1° хватало с избытком.

Кстати, Тимур, хотел тебе пару вопросов по твоему движку задать, а у тебя аська в оффлайне беспрерывно. Или ты номер сменил, или шифруешься? :)

← →
Сергей М. © (2006-11-02 11:36) [25]

> zxcxz © (15.06.06 20:47)

Современные высокопроизводительные игровые (и не только) приложения используют на полную мощь MMX/XMM/SSE/SSE2/SSE3/3DNow-расширения системы команд CPU.

А то о чем ты говоришь - это каменный век, в любом из рассматриваемых тобой вариантов.

← →
@!!ex © (2006-11-02 11:44) [26]

> Rial © (01.11.06 23:18) [20]

Смотря при какой дискретности. ;)

← →
Megabyte-CeerCop © (2006-11-02 12:26) [27]

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

1) в цикле 10000000 итерации выщитывал синус заняло на глаз 2 сек.

2) в цикле 10000000 итерации из массива в 1000 элементов выбирал значение и прибавлял к переменной. зпняло 1.5 сек...

а если к этому добавить время на определение позиции в массиве.. прироста не будет точно.

← →
Shirson © (2006-11-02 12:47) [28]

Такие вещи "на глаз" не делаются. GetTickCount даёт более точные результаты, чем глаз :)

← →
Shirson © (2006-11-02 13:17) [29]

Так.

Сделал таблицу на 3"600"000 предзначений.

Делается 10000001 выборок а) из таблицы и б) считая синус функцией.
а) Среднее количество тиков для функции - 1734
б) Среднее количество тиков для таблицы - 328

← →
Сергей М. © (2006-11-02 14:11) [30]

SIMD "спасает отцов русской демократии")

← →
DevilDevil © (2006-11-02 15:51) [31]

Нормальный способ:

procedure SinCos(const Theta: Extended; var Sin, Cos: Extended); asm FLD Theta FSINCOS FSTP tbyte ptr [edx] // Cos FSTP tbyte ptr [eax] // Sin end;

Убыстренный способ (если используешь переменные : single):
type TFLOAT_int = integer; procedure FastSinCos(const Theta: TFLOAT_int; var Sin, Cos: TFLOAT_int); asm FLD eax FSINCOS FSTP ecx // Cos FSTP edx // Sin end;

Пример:
var Angle, sinAngle, cosAngle : single; begin Angle := random; FastSinCos( TFLOAT_int(Angle), TFLOAT_int(sinAngle), TFLOAT_int(cosAngle) );

Ну и напоследок, если используешь градусы, то:
const Deg_To_Rad : double = (PI/180); procedure FastSinCos(const Theta: TFLOAT_int; var Sin, Cos: TFLOAT_int); asm FLD eax FMUL Deg_To_Rad // <- так, если не ошибаюсь FSINCOS FSTP ecx // Cos FSTP edx // Sin end;

<-- по аналогии (и даже проще) найдёшь только синус или только косинус, если не нужны оба значения

P.S. Таблица даст прирост скорости, если:

1) выборка будет inline
2) не будешь "вручную" переводить радианы в градусы
3) не будешь округлять угол "до ближайшего целого"

P.P.S Сопроцессор появился в 386 процессоре

← →
Belorus © (2006-11-02 16:41) [32]

P.P.S Сопроцессор появился в 386 процессоре
Я бы не стал так громко орать о том чего не знаю....

По теме : в i486

← →
Ketmar © (2006-11-02 17:25) [33]

>[32] Belorus(c) 2-Nov-2006, 16:41
>Я бы не стал так громко орать о том чего не знаю....
для данного персонажа это нормально.

> Belorus © (02.11.06 16:41) [32]
> Я бы не стал так громко орать о том чего не знаю....

А чё орёшь тогда? :)

Если быть точным, то и ты неправ:
"... оно было реализовано в виде отдельной микросхемы, то есть его присутствие было необязательным. Микросхема сопроцессора для процессора i8086/88 имела название i8087. ... Как отдельные (...) устройства сопроцессоры сохранялись вплоть до модели i386 и имели название i287 и i387 соответственно. Начиная с модели i486 сопроцессор исполняется в одном корпусе с основным процессором..."

... но если я не ошибаюсь, команды сопроцессора достурны при программировании под 386...

КААЮЮСЬ !!!

const Deg_To_Rad : double = (PI/180); type TFLOAT_int = integer; procedure FastSinCos(const Theta: TFLOAT_int; var Sin, Cos: single); asm FLD eax FMUL Deg_To_Rad // <- так, если не ошибаюсь FSINCOS FSTP dword ptr[ecx] // Cos FSTP dword ptr[edx] // Sin end;

Пример:
var Angle, sinAngle, cosAngle : single; begin Angle := random; FastSinCos( TFLOAT_int(Angle), sinAngle, cosAngle );

Аналогично синус/косинус:

function FastCos (const X: TFLOAT_int): single; asm FLD X FMUL Deg_To_Rad // <- так, если не ошибаюсь FCOS end; function FastSin (const X: TFLOAT_int): single; asm FLD X FMUL Deg_To_Rad // <- так, если не ошибаюсь FSIN end;

P.S. Но мне так кажется(не проверял), что обычный вызов sinAngle := sin(Deg_To_Rad*Angle); будет быстрее. "Почему?" - спросите вы (кроме Кетмара). Потому что функции sqr, sqrt, sin, cos, ... в любой версии Delphi вызываются инлайнами, то есть не тратится лишнего времени на вызов функции как таковой. Всё

P.P.S. Ну а к Кетмару у меня и у некоторых других особое отношение...

Ну, вы тему и развернули!
Я уже не надеялся ее увидеть на первых страницах форума.

for DeadMeat

> На оригинальность и супер скорость не претендую, но по моим
> тестам и для моей ситуации работает шустрее:

Идею понял и перенял, в моем случае прог летает.
Спасиб за идею!

Time(Sin & Cos) / Time(Your Sin & Cos) ~ 3.58

>DevilDevil © (02.11.06 17:43) [35]
...
> const Deg_To_Rad : double = (PI/180);
> type TFLOAT_int = integer;
>
> procedure FastSinCos(const Theta: TFLOAT_int; var Sin, Cos: single);
> asm
> FLD eax
> FMUL Deg_To_Rad // <- так, если не ошибаюсь
> FSINCOS
> FSTP dword ptr[ecx] // Cos
> FSTP dword ptr[edx] // Sin
> end;

Вот так должно работать еще быстрее:

procedure SuperFastSinCos( var Theta, Sin, Cos :Single );
asm
FLD DWORD PTR [EAX]
FMUL Deg_To_Rad
FSINCOS
FSTP DWORD PTR [ECX] // Cos
FSTP DWORD PTR [EDX] // Sin
end;

> rts111 © (11.11.06 13:33) [37]
> procedure SuperFastSinCos( var Theta, Sin, Cos :Single );

огорчу: в твоём случае происходит обращение к памяти по указателю, в моём - напрямую к регистру. Ну и что быстрее? Соглошусь: разница не велика.

>огорчу: в твоём случае происходит обращение к памяти по указателю, в моём - напрямую к
>регистру. Ну и что быстрее? Соглошусь: разница не велика.

Посмотри как компилятор откомилирует:
В твоем случае добавит pop ... push,
а в моем что записано, то будет и после компиляции.

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

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

> регистр сопроцессора
и
> регистр общего назначения

Чем отличаются?

Напиши, как ты вызываешь эту функцию и что примерно на это говорит дизассемблер.

> DevilDevil © (17.11.06 19:11) [38]

Не поленился, проверил :)
Работают такие варианты:

// если обявить TFLOAT_int = integer при вызове SinCos1( TFLOAT_int(v1) , v2 , v3 ) компилятор ругается

// А вот так работает:
type TFLOAT_int = pointer;

// !!! Только все равно нужно передавать не адрес, а значение, pointer - только потому
// чтобы Alpha в SinCos1 воспринимался как 32-витное значение

procedure SinCos1( const Alpha :TFLOAT_int; var Sin,Cos :Single ); register;
asm

// FLD EAX - если так, то не компилится

// можно так сделать
PUSH EAX
FLD DWORD PTR[ESP]
POP EAX

FSINCOS
FSTP DWORD PTR[ECX] // Cos
FSTP DWORD PTR[EDX] // Sin
end;

// Здесь компилятор сам добавляет pop...push, как я понял это потому что Alpha - вещественный тип
procedure SinCos2( const Alpha :single; var Sin,Cos :Single ); register;
asm
FLD Alpha
FSINCOS
FSTP DWORD PTR [EDX]
FSTP DWORD PTR [EAX]
end;

procedure SinCos3( var Alpha {EAX} , Sin {EDX} , Cos {ECX} :Single );
asm
FLD DWORD PTR[EAX]
FSINCOS
FSTP DWORD PTR[ECX] // Cos
FSTP DWORD PTR[EDX] // Sin
end;

procedure TForm1.Button1Click(Sender: TObject);
var
t0,t1,t2 :int64;
i :integer;
v1,v2,v3 :single;
begin
QueryPerformanceCounter(t1);

v1:=Pi/2;

for i:=1 to 1000000 do
SinCos1( TFLOAT_int(v1) , v2 , v3 ); // 1 место(самый быстрый)
//SinCos2( v1 , v2 , v3 ); // 3 место
//SinCos3( v1 , v2 , v3 ); // 2 место

QueryPerformanceCounter(t2);
//QueryPerformanceFrequency(t0);

caption:=inttostr(t2-t1)+" "+floattostr(v[2]);

end;

> DevilDevil © (02.11.06 17:43) [35]
> функции sqr, sqrt, sin, cos, ... в любой версии Delphi
> вызываются инлайнами,

А вот я давно думаю о dcc (уж про v15 точно) крайне пессимистично, и часто правильно:
ведь cos = call @COS, который есть:
procedure _COS; asm FCOS FNSTSW AX SAHF JP @@outOfRange RET @@outOfRange: FSTP st(0) { for now, return 0. result would } FLDZ { have little significance anyway } end; Кстати, ни у кого нет исходников компилера Делфи, хочу сделать там поиск слова optimization, вдруг найду :\
very fast!

> Сергей М. © (02.11.06 11:36) [25]
> приложения используют на полную мощь MMX/XMM/SSE/SSE2/SSE3/3DNow

Кстати, пробовал, ужасно тормозит, видимо, что-то не так делаю! как их юзать то!!! (пытался ускорить DotProduct, никто не делал через SSE2?)
p.s. Тестирование sin/cos таблиц нужно производить не на последовательное их вычисление, а в реальном алгоритме, т.к. так таблица у нас в кэше и всё при тесте, а в реале оно может не совсем так быть.
p.s.s. В DOOMе ещё удобно было, что углы были 0..255 и сами клиппились, удобно...

> ведь cos = call @COS, который есть:

Уренда какая-то. Как я не исполльзовал, вызываются инлайнами. И уж точно не такой код (короче в разы)

> Кстати, пробовал, ужасно тормозит, видимо, что-то не так
> делаю! как их юзать то!!!

Чтобы добиться реального прироста производительности от SSE~, обработку всей последовательности данных в одной подпрограмме. Ещё там фишка с выравниванием данных; в этой подпрограмме как можно реже (а лучше вообще не) использовать обычные команды процессора.

> DevilDevil © (10.12.06 21:24) [45]

Специально проверил, $o+, $a8, $r-, $q-, всё равно компилит вызов на вышеуказанную функцию, у меня Delphi 7 Enterprise build 4.453.
А не можешь пример SSE-кода?

> А не можешь пример SSE-кода?

Не можешь. Советую идти на www.wasm.ru

Sin Cos Найти похожие ветки