оптимизация: что быстрее?

← →
tButton © (2006-06-09 06:14) [0]

a*2 или a+a, если a: real;?
(сие творится многократно в ходе цикла и потому выбор более быстровыполняемого действия очень важен)

← →
MBo © (2006-06-09 06:39) [1]

Проверь :)

← →
tButton © (2006-06-09 06:58) [2]

> Проверь :)

проверю =)
но это ещё до дому дойти надо =)

← →
Urvin (2006-06-09 08:03) [3]

кажись операция сложения всегда выполнялась быстрее

← →
tButton © (2006-06-09 08:44) [4]

ну, ежели б тут были целые беззнаковые, я бы смело пользовался shl 1 или бы множил на 2 (компилятор сам заменит умножение на степень двойки на shl)
но тут, блин действительные числа... помнится, в процессоре Pentium MMX, был давже встроеный сопроцессор, для операций над числами с плавающей запятой (или это мой склероз надо мной стебается?)

← →
MBo © (2006-06-09 08:53) [5]

> я бы смело пользовался shl 1

приколись:

Unit3.pas.35: b:= a shl 1;
00455ABB 8BDA mov ebx,edx
00455ABD 03DB add ebx,ebx

:)

← →
tButton © (2006-06-09 08:55) [6]

хы =)
а shl 2?)

← →
MBo © (2006-06-09 09:11) [7]

Unit3.pas.35: b:= a shl 3;
00455ABB 8BDA mov ebx,edx
00455ABD 03DB add ebx,ebx
00455ABF 03DB add ebx,ebx
00455AC1 03DB add ebx,ebx

а начиная с shl 4 - уже сдвигом
В любом случае накладные расходы на сам цикл в несколько раз больше, чем на эту арифметику

← →
Сергей М. © (2006-06-09 09:48) [8]

> tButton © (09.06.06 06:14)

Отличие
a := a+a;
от
a := a*2;

всего в одной маш.инструкции - в 1-м случае fadd, а во 2-м fmul

Cовременные FPU выполняют умножение практически столь же быстро, как и сложение, так что ловить здесь блох нет повода ... Лучше будет сосредоточить внимание на оптимальность "подготовительных" операций: загрузку операндов и выгрузку результата - они ощутимо больше влияют на сквозную производительность алгоритма, т.к. при этом для Real-типа всякий раз происходит прямое и обратное преобразование между Real и Extended.

← →
tButton © (2006-06-09 09:50) [9]

> т.к. при этом для Real-типа всякий раз происходит прямое
> и обратное преобразование между Real и Extended.

а можно про это чуть подробнее?

← →
MBo © (2006-06-09 09:55) [10]

>tButton
Ты бы побольше информации про подлежащий оптимизации код привел...

← →
Сергей М. © (2006-06-09 10:04) [11]

Выдержки из мануала IA-32:

FLD—Load Floating Point Value
Description
Pushes the source operand onto the FPU register stack. The source operand can be in single-precision,
double-precision, or double extended-precision floating-point format. If the source
operand is in single-precision or double-precision floating-point format, it is automatically
converted to the double extended-precision floating-point format before being pushed on the
stack.

FST/FSTP—Store Floating Point Value
If the destination size is single-precision or double-precision, the significand of the value being
stored is rounded to the width of the destination (according to rounding mode specified by the
RC field of the FPU control word), and the exponent is converted to the width and bias of the
destination format.

Тоже самое касается инструкций FADD/FMUL, если операнд берется из памяти.

← →
tButton © (2006-06-09 10:48) [12]

> Сергей М. © (09.06.06 10:04) [11]

т.е. имеет смысл отказаться от типа real в пользу extended?

> Ты бы побольше информации про подлежащий оптимизации код
> привел...

могу. код из моего текущего проекта, там просто уйма вычислений и все с числами с плавающей точкой
вот один из методов объекта реализующего систему взаимопритягивающихся частиц
for i:=0 to high(pts) do for j:=0 to high(pts) do begin // i - индекс обрабатываемой точки // j - индекс точки к которой притягиваемся if i=j then continue; // сами на себя не воздействуем dx:=pts[j].x-pts[i].x; // конечная минус начальная dy:=pts[j].y-pts[i].y; g:=Gravity(pts[i], pts[j]); v:=sqrt(2*g/pts[i].m); d:=Dist(pts[i], pts[j]); vx:=dx/d; vy:=dy/d; vx:=vx*v; vy:=vy*v; pts[i].vx:=pts[i].vx+vx*quarq; pts[i].vy:=pts[i].vy+vy*quarq; end;
наработки по оптимизации
high(pts) присвоить переменной и использовать её в цикле вместо постоянного обращения к функии
d:=Dist(pts[i], pts[j]); заменить на sqrt(dx*dx+dy*dy). потому что процедура вычисляет dx и dy по новой

g:=Gravity(pts[i], pts[j]); здесь тоже используется рассчёт дистанции, поэтому есть повод отказаться от процедуры

vx:=dx/d; и vx:=vx*v; можно заменить на d:=v/d; и vx:=dx*d; одной строчкой меньше

v:=sqrt(2*g/pts[i].m); а это то с чего началось, можно объединить с формулой g:=Gravity(pts[i], pts[j]); и упростить.

полный сорц
http://slil.ru/22822987
екзешник
http://slil.ru/22822989

← →
Сергей М. © (2006-06-09 10:58) [13]

> имеет смысл отказаться от типа real в пользу extended?

Да.
Но, естественно, при условии что нет жестких ограничений по объему занимаемой этими переменными памяти приложения.

Если производительность алгоритма столь важна, может быть стоит присмотреться к MMX/SIMD/SSE-расширениям ? Или воспользоваться готовыми библиотеками, эффективно использующими эти расширения, а-ля Intel Math Kernel Library ?

← →
Kolan © (2006-06-09 11:07) [14]

От Real вообще надо отказаться.. ИМХО это из паскаля осталось

← →
tButton © (2006-06-09 11:07) [15]

> Но, естественно, при условии что нет жестких ограничений
> по объему занимаемой этими переменными памяти приложения.

пока приложение использует около 48 байт на частицу системы
стандартная система - 1000 частиц
предельный размер (не дающий уснуть в ожидании отрисовки очередного кадра) 5-7 тысяч частиц
т.е. больших нагрузок на память не предполагается

> Если производительность алгоритма столь важна,

просто необычано важна

> MMX/SIMD/SSE-расширениям ?

признаться, знакомо только слово MMX

> Или воспользоваться готовыми библиотеками, эффективно использующими
> эти расширения

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

← →
palva © (2006-06-09 11:47) [16]

Я бы не корпел над оптимизацией исходного кода, а писал бы формулы максимально понятно для постороннего специалиста-непрограммиста. Только написал бы вычислительное ядро на си. А уж Borland Compiller оптимизирует, как надо. По моему опыту, будет работать заметно быстрее.

← →
ЮЮ © (2006-06-09 11:49) [17]

> 5-7 тысяч частиц
> т.е. больших нагрузок на память не предполагается

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

procedure TForm1.Button1Click(Sender: TObject); var a: Extended; i, j, n: integer; start: Cardinal; begin n := 5000; a := 0; Start := GetTickCount; for i := 1 to n do for j := 1 to n do begin a := a + 1/i ; //a := a + 1/j; end; Button1.Caption := IntToStr(GetTickCount - Start); Caption := FloatToStr(a); end;

Теперь оцени время на выполнение только одной строки.
А теперь раскомментируй вторую.
А ты ещё мечтаешь о сложных рассчетах.

← →
Сергей М. © (2006-06-09 11:50) [18]

> знакомо только слово MMX

MMX, конечно, вчерашний день, хотя многие производители ПО успешно используют MMX и сегодня.

> предвкушая отсутствие внятного руководства по использованию.

Интеловские библ-ки напротив, imho, снабжаются достаточно подробными справками и примерами.

Могу сказать, что, к примеру, пакет Intel Signal Processing Library Suite (IntelSPL) содержит примеры использования пакета даже на Делфи (!), что есть великая редкость для других производителей ПО.

← →
Сергей М. © (2006-06-09 11:58) [19]

http://www.softkey.ru/catalog/program.php?ID=3793&progdesc=long

← →
Sapersky (2006-06-09 12:27) [20]

т.е. имеет смысл отказаться от типа real в пользу extended?

Основатель проекта FastCode пишет, что лучше вообще в пользу Single:

http://dennishomepage.gugs-cats.dk/CodingForSpeedInDelphi.doc

По поводу теории MMX/SSE:

http://www.tommesani.com/

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

Intel Signal Processing Library Suite (IntelSPL)

Если я правильно понял, бесплатно там дают только версию для Linux и for non-commercial use.

← →
Сергей М. © (2006-06-09 12:52) [21]

> бесплатно там дают только версию для Linux и for non-commercial
> use

Ну, как говорится, кто не успел, тот опоздал) .. Ведь когда-то Интел раздавал со своего сайта ISPL "нахаляву" ..

Впрочем на просторах Тырнета найти тот самый "халявный" пакет не представляет особого труда

← →
MBo © (2006-06-09 12:54) [22]

>Sapersky
>Intel Signal Processing Library Suite (IntelSPL)
>Если я правильно понял, бесплатно там дают только версию для Linux и for non-commercial use.

Года 4 назад интеловские библиотеки MKL, SPL, IPL, IJL были в свободном доступе на их сайте, потом они решили на них навариться...

>tButton
некоторые очевидные изменения
for i:=0 to high(pts) do
for j:=i + 1 to high(pts) do // ни к чему каждую точку обрабатывать дважды
begin
d:=1./Dist(pts[i], pts[j]);// одно деление вместо двух
vx:=dx *d;
vy:=dy *d;
pts[i].vx:=pts[i].vx+vx*quarq;
pts[i].vy:=pts[i].vy+vy*quarq;
///////// здесь нужно вставить то же самое для j-й точки
end;

← →
Romkin © (2006-06-09 13:56) [23]

Задача о притягивающихся частицах довольно известна :)
И есть довольно много оптимизаций алгоритма, от выбора способа хранения данных до алгоритма обработки.
Например, можно хранить точки в древовидной структуре, вышележащий узел представляет собой кластер близких точек, и обсчет идет прежде всего для кластеров...

← →
tButton © (2006-06-10 15:53) [24]

иные решения кроме как обсчёт "каждая к каждрй" не приемлимы, ибо они иммитируют, а не моделируют.

оптимизировал алгоритм согласно задумке.
время обсчёта сократилось с 300 с лишним мс до 125 мс
заменил тип всех переменных real на extended
время обсчёта выросло до 220 мс
вернул real - время вернулось к 125 мс
результатом доволен =)

← →
MBo © (2006-06-10 16:12) [25]

>tButton
Повторные вычисления-то убрал?

← →
tButton © (2006-06-10 19:36) [26]

> Повторные вычисления-то убрал?

теперь - да =)

> Задача о притягивающихся частицах довольно известна :)
> И есть довольно много оптимизаций алгоритма, от выбора способа
> хранения данных до алгоритма обработки.
> Например, можно хранить точки в древовидной структуре, вышележащий
> узел представляет собой кластер близких точек, и обсчет
> идет прежде всего для кластеров...
> <Цитата>
>
>
> tButton © (10.06.06 15:53) [24]
> иные решения кроме как обсчёт "каждая к каждрй" не приемлимы,
> ибо они иммитируют, а не моделируют.

Не понял. Возми ты древовидную структуру, где узел есть не что иное, как геометрический центр масс двух других. У тебя же все равно идет сложение векторов. Расход памить увеличится в 2 раза. Из сложности (N+1)N/2 получишь сложность 2*N. Могу ошибаться, прикинул в уме.

> Не понял. Возми ты древовидную структуру, где узел есть
> не что иное, как геометрический центр масс двух других.
> У тебя же все равно идет сложение векторов. Расход памить
> увеличится в 2 раза. Из сложности (N+1)N/2 получишь сложность
> 2*N. Могу ошибаться, прикинул в уме.

честно, не понял =)
1) разница между моделью и иммитацией модели в степени достоверности. иммитация лишь создаёт видимость, на деле я могу просто запузырить каждой частице элиптическую орбиту и вычислять её положение в момент времени.
2) на память наплевать, критична скорость расчётов, а она от памяти слабо зависит.
3) MBo © предложил достаточно хороший вариант оптимизации цикла

> Cовременные FPU выполняют умножение практически столь же
> быстро, как и сложение, так что ловить здесь блох нет повода
> ... Лучше будет сосредоточить внимание на оптимальность
> "подготовительных" операций: загрузку операндов и выгрузку
> результата - они ощутимо больше влияют на сквозную производительность
> алгоритма, т.к. при этом для Real-типа всякий раз происходит
> прямое и обратное преобразование между Real и Extended.
>

вообще то все компиляторы дельфи начиная с delphi 2 не используют тип
real, он оставлен только для совместимости со старым ккодом!
компилятор автоматически подменяет тип real типом extended!

> подменяет тип real типом extended!

double

> tButton ©

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

Моделирует Вселенную, чтобы обратным ходом вернуть все к точке Большого взрыва.

всплыло =)

Ну чем там все дело кончилось-то, в точке взрыва ?

всё. путём =) апокалипсиса небудет =) хотя планеты всё же склонны падать на зведу либо улетать в дальний космос =)

>
> vx:=dx/d; и vx:=vx*v; можно заменить на d:=v/d; и vx:=dx*d;
> одной строчкой меньше

ошибочно, по-моему...

> ошибочно, по-моему...

вместо четырёх расчётов три. пл-млему нормально =)

оптимизация: что быстрее? Найти похожие ветки