forum.boolean.name - Методы оптимизации

forum.boolean.name (http://forum.boolean.name/index.php)

- FAQ (http://forum.boolean.name/forumdisplay.php?f=15)

- - Методы оптимизации (http://forum.boolean.name/showthread.php?t=1615)

MiXaeL

01.10.2006 19:44

Методы оптимизации

Итак, что же такое оптимизация? А это просто изменение исходного кода программы / добавление новых модулей с целью повышения её быстродействия. Рассмотрим конкретный пример:

Код:

 

...

If MouseHit(1) PickUnit()

...

Function PickUnit()

  Pick=CameraPick(camera,MouseX(),MouseY())

  For u.unit = each unit

    If Pick=u\model SelectUnit(u)

  Next

End Function

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

1) "Отброс невозможных вариантов"
Нетрудно заметить, что при нажатии кнопки мыши мы можем выделить только одного юнита, значим мы можем изменить код функции так:

Код:

 

Function PickUnit()

  Pick=CameraPick(camera,MouseX(),MouseY())

  For u.unit = each unit

    If Pick=u\model 

        SelectUnit(u)

        Return

    EndIf

  Next

End Function

Итак, мы в среднем увеличили скорость выполнения цикла в два раза!

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

Код:

 

Function PickUnit()

  Pick=CameraPick(camera,MouseX(),MouseY())

  If Pick=0 Return

  For u.unit = each unit

    If Pick=u\model SelectUnit(u)

    Return

  Next

End Function

Здесь важно заметить, что подразумевается, что кроме юнитов никакие другие объекты не выделяются. Если это не так, то можно попробовать сделать следующее:

Код:

Function CreateUnit()

  u.unit= New unit

  ...

  NameEntity(u\model,"Unit")

  ...

End Function

 

Function PickUnit()

  Pick=CameraPick(camera,MouseX(),MouseY())

  If Pick=0 Return

  If EntityName$(u\model)<> "Unit" Return

  For u.unit = each unit

    If Pick=u\model 

        SelectUnit(u)

        Return

    EndIf

  Next

End Function

P.S. Если вы имеете дело не с функцией, или кроме цикла (не обязательно цикла) имеется что-то ещё, то для первого случая нужно использовать Exit, а для второго If...End If.

jimon

01.10.2006 19:57

Re: Методы оптимизации

ето очень и очень конкретный пример оптимизации

MiXaeL

01.10.2006 20:08

Методы оптимизации

Конечно, рассмотренные выше методы не являются исчерпывающими. Рассмотрим ещё несколько видов оптимизации:

1) "Замена условий формулой"
Это просто замена нескольких IF одной формулой. Вот основные виды:

а)"Переключатель двух состояний"
То есть просто переменная, которая может принимать значения 1 или 0 :

Код:

If KeyHit(57) N=1-N

или

Код:

If KeyHit(57) N=Not(N)

Всё просто.

б)"Преключатель N состояний"
Это переменная, которая может принимать значения 0,1...N :

Код:

If KeyHit(57) K=(K+1) Mod N

в)"Минимумы и максимумы"
Часто используется для переменных, которые возратают (или уменьшаются) только до какого-то определенного значения (например для скорости):

Код:

Speed=Speed + (1 And Speed < 2)*.5

г)"Модули"
Используется реже, например здесь:
вместо

Код:

If EntityPitch(cam)<75 And EntityPitch(cam)>-75 Then

можно использовать

Код:

If Abs(EntityPitch(cam))<75 Then

2)"Исключение медленных операций"
Например, если вам надо определить расстояние между точками в 2D ( в 3D всегда исрользуйте EntityDistance - эта команда значительно быстрее любых подсчетов через координаты!), вы наверняка используете что-то вроде этого:

Код:

 

d=Sqr((x1-x2)^2+(y1-y2)^2)

 

If d<10 Then

  ...

End If

Но вы должно быть знаете, что Sqr - ОЧЕНЬ МЕДЛЕННАЯ команда, поэтому лучше написать так (как бы возвести все в квадрат):

Код:

 

d=(x1-x2)^2+(y1-y2)^2

 

If d<100 Then

  ...

End If

Результат от этого не изменится, а скорость выполнения увеличится!

P.S. Ну вот вроде всеB) ! Если знаете что-то еще, добавляйте.

jimon

01.10.2006 20:21

Re: Методы оптимизации

про If KeyHit(57) K=(K+1) Mod N незнал :)
пасибки :)

tormoz

01.10.2006 22:08

Re: Методы оптимизации

а мгновенный доступ к елементу типа без перебора ?

Object -есть такая фишка.

Цитата:

Function CreateUnit()
u.unit= New unit
...
name$=Handle (u)
NameEntity u\model, name$
...
End Function

Function PickUnit()
Pick=CameraPick(camera,MouseX(),MouseY())
If Pick
u.unit=Object.unit(EntityName(Pick))
If u<>Null
SelectUnit(u)
EndIf
EndIf
End Function

Platon

02.10.2006 08:25

Re: Методы оптимизации

Цитата:

Сообщение от jimon

про If KeyHit(57) K=(K+1) Mod N незнал :)

Лучше такую конструкцию не юзать, ибо она наоборот медленнее чем

Код:

K = K + 1

If K > N Then K = 0

Раз в 10 быстрее чем mod.

Цитата:

а)"Переключатель двух состояний"
То есть просто переменная, которая может принимать значения 1 или 0 :

Код:

If KeyHit(57) N=1-N

или

Код:

If KeyHit(57) N=Not(N)

Всё просто.

Тут как раз первый вариант предпочтительнее, ибо быстрее в 2-3 раза чем NOT.

Цитата:

Код:

Speed=Speed + (1 And Speed < 2)*.5

Здесь тоже лучше такую конструкцию не использовать, ибо медленне чем

Код:

If x < 10 Then x = x * 0.5

раза в 2-3

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

jimon

02.10.2006 08:48

Re: Методы оптимизации

Цитата:

Тут как раз первый вариант предпочтительнее, ибо быстрее в 2-3 раза
чем NOT.

not выполняется ALU в один такт
что является самой быстрой операцией за все время существования процесоров

Цитата:

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

необязательно, хотя возможно

Цитата:

Здесь тоже лучше такую конструкцию не использовать, ибо медленне чем
If x < 10 Then x = x * 0.5

раза в 2-3

тоже самое, притом компилятор всеравно обе конструкции разворачивает

и надо писать все в одном сообщении !

Platon

02.10.2006 08:53

Re: Методы оптимизации

jimon
Этот топик по Блицу или по ассемблеру а?
Может написав на ассемблере такую конструкцию с Not, она будет быстрее выполняться, чем эта же конструкция с Sub, а блиц интерпретирует хз. как. Если неверишь, то проверь практически что будет быстрее работать.

jimon

02.10.2006 18:08

Re: Методы оптимизации

втом то и дело что блиц конвертит код в asm :)

pax	02.10.2006 20:31

Re: Методы оптимизации

Цитата:

Сообщение от Michael

1) "Отброс невозможных вариантов"
Нетрудно заметить, что при нажатии кнопки мыши мы можем выделить только одного юнита, значим мы можем изменить код функции так:

Код:

 

Function PickUnit()

  Pick=CameraPick(camera,MouseX(),MouseY())

  For u.unit = each unit

    If Pick=u\model SelectUnit(u)

    Return

  Next

End Function

Итак, мы в среднем увеличили скорость выполнения цикла в два раза!

Ну в "среднем" из цикла производится выход сразу же после проверки первого элемента... работать правильно будет вот так:
[highlight=blitzbasic]
Function PickUnit()
Pick=CameraPick(camera,MouseX(),MouseY())
For u.unit = each unit
If Pick=u\model
SelectUnit(u)
Return
EndIf
Next
End Function
[/highlight]
;)

impersonalis

02.10.2006 22:02

Re: Методы оптимизации

Цитата:

Сообщение от jimon

про If KeyHit(57) K=(K+1) Mod N незнал :)
пасибки :)

Эта формула была в топике про форумлы в разделе по алгоритмике

pax	02.10.2006 22:13

Re: Методы оптимизации

А вообще правильнее выход из цикла выполнять так:

[highlight=blitzbasic]
Function PickUnit()
Pick=CameraPick(camera,MouseX(),MouseY())
For u.unit = each unit
If Pick=u\model
SelectUnit(u)
Exit
EndIf
Next
End Function [/highlight]
Return производит выход из функции или подпрограммы, а не из цикла. Выход из цикла выполнятся оператором Exit.

MiXaeL

02.10.2006 22:14

Re: Методы оптимизации

2 PAX:
А я это писал (насчет Exit).

pax	02.10.2006 22:58

Re: Методы оптимизации

Цитата:

Сообщение от Michael

2 PAX:
А я это писал (насчет Exit).

Перечитал первый пост еще раз... извините что повторился :pardon:

tormoz

03.10.2006 01:00

Re: Методы оптимизации

Спор бессмысленен, есть способ найти элемент без перебора. Я его привел.

impersonalis

03.10.2006 01:06

Re: Методы оптимизации

Удобным так же может оказаться более абстрактная реализация, описанного tormoz-ом метода: присваивать имени меша (name) хендл информационной структуры, а не хендл типа, поставленного в соответсвиее мешу напрямую. Это позволяет проводить более непривязанный анализ, и даже создать жалкое подобие ООП: в функцию передаётся entity пикунтого меша, из имени entity извлекается квази-укзатель на информационную структуру, получаем доступ к структуре, узнаём: к какому типу объектов поставлен в соответствие данный меш, квази-укзатель на конкретный элемент этого типа, и всё что нам необходимо.

HolyDel

03.10.2006 02:56

Re: Методы оптимизации

добавлю еще немного про оптимизацию.

во первых постарайтесь избегать делений например a/5 лучше заменить на a*0.2, так как второй вариант раза в три быстрее.

если число нужно умножить на что то вроде 2, 4, 8, 16 и т.д. или тем более разделить то можно обойтись логическим сдвигом (который рулит:) ). например a/16 можно заменить на a shr 4, для умножения соответственно a shl 4. четверка это степень двойки для число 16.

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

очень быстро выполняются логические операции (or, xor, and, not).

пока все.

jimon

03.10.2006 08:52

Re: Методы оптимизации

Цитата:

во первых постарайтесь избегать делений например a/5 лучше заменить на a*0.2, так как второй вариант раза в три быстрее.

зависит от процесора

Цитата:

если число нужно умножить на что то вроде 2, 4, 8, 16 и т.д. или тем более разделить то можно обойтись логическим сдвигом (который рулит :) )

ето правильно, хотя некоторые компиляторы сами меняют умножение\деление на сдвиги

Цитата:

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

ето время настолько минимально что его можно не учитывать

Цитата:

очень быстро выполняются логические операции (or, xor, and, not).

все логические операции являются самыми быстрыми из всех вообще

Platon

03.10.2006 13:08

Re: Методы оптимизации

Цитата:

Сообщение от jimon

втом то и дело что блиц конвертит код в asm :)

А какая разница? Главное как он конвертит.
Ты у себя проверял оба варианта? (с not state и c 1-state)
Я проверил - 1-state быстрее выполняется, у меня по крайней мере.

И еще, может я чего то не допонял, почему это NOT быстрее SUB? Ну теоретически-то да - быстрее, но на практике у меня одинаковы :)
Проверял на пурике

Код:

state = #False

time = GetTickCount_();timeGetTime_()

For i = 0 To 10000000

   ;                          ;Ticks

   !MOV eax, dword[v_state]   ;1

   !NOT eax                   ;1

   !MOV dword[v_state], eax   ;1

Next

MessageBox_(0, Str(timeGetTime_() - time), "", #MB_OK)



state = #False

time = GetTickCount_();timeGetTime_()

For i = 0 To 10000000

   ;                          ;Ticks

   !MOV eax, 1                ;1

   !SUB eax, dword[v_state]   ;2

   !MOV dword[v_state], eax   ;1

Next

MessageBox_(0, Str(timeGetTime_() - time), "", #MB_OK)



End

оба варианта показывают 31
ЗЫ
Может дело в проце?
P4 630 Prescott 3.0 Ghz 2x

jimon

03.10.2006 18:57

Re: Методы оптимизации

Cyan
тут лутче писать на чистом asm
и двух ядерный проц тут ничего толком не дает
хотя лутче проверить еще на amd
мож какаято оптимизация в cpu стоит ? :) хотя хз - я же не intel :)

Platon

04.10.2006 07:41

Re: Методы оптимизации

jimon
Писал и на чистом асм в пурике, и на FASM - один и тот же результат - скорость выполнения одинаковая.

jimon

04.10.2006 08:44

Re: Методы оптимизации

Cyan значит ето скорость ALU... :)

Часовой пояс GMT +4, время: 14:19.