Улучшение кода, Уменьшение времени работы программ Опции

[Altair]

Быстрые циклы.

Всего тестировалось 4 конструкции:

• "FOR ... TO ... Do...",
• "WHILE... do...",
• "REPEAT ... until ...",
• " If... Then GOTO ..."

Проведение теста:
сортировка массива (array[1..20] of integer) методом пузырька.
Всего было проведено 30 тестов :
10 c n= 10^4;
10 c n= 10^5;
10 c n= 10^6;
и один тест с n=10^7 (один, т.к. с увеличением степени n на 1, время проведения теста увеличивается соответственно в 10 раз)

Результат:
Во всех случаях (каждый тест - новый массив) самой быстрой конструкцией оказалась "While ... do...", следом за ней "If ... then Goto..."

[mj]

на процессорах P2 и ниже
FOR быстрее чем WHILE должно работать на новых процах наоборот,
это связано с внутренней конструкцией процессора.

[Atos]

И Да ЗдравствуетИтерация! Пример: старая добрая задачка о Ханойской башне (нерекурсивный вариант).

Сообщение отредактировано: Atos - 16.03.2004 18:48

[trminator]

Ускорение вычислений mod

Програма считает 50 - 55 секунд (!), до 8 000 000 экспериментов.
Вычисления типа:

c0 := (a * c0 + B) mod m

где m = 2^24 (генератор случайных чисел, если кому интересно)

Код быстрее:

c0 := (a * c0 + B) and (m - 1)

Ускорение -- более чем в 50 раз. Вот так... Прога работает около секунды - полутора.
Когда берем остаток от деления (на степень двойки!), фактически, мы просто оставляем последние m-1 бит числа. А это можно сделать и and'ом

[P@sh@]

Деление на степень двойки

Аналогично быстрое деление на степень двойки - shr, а умножение - shl

если мне не изменяет память,
на команду DIV (деление) 486-е процы тратили до 70-ти тактов!
(для сравнения - битовые команды типа AND/OR и сдвиги выполняются за 1-2 такта)

[P@sh@]

Разворачивание циклов. -=loops unrolling=-

Один из методов оптимизации больших циклов - loops unrolling - "разворачивание"... тело цикла можно скопировать два/четыре раза, уменьшив во столько же раз кол-во итераций... глядишь, процессору удасться их распараллелить, да и на jump-ы время меньше тратится...

[trminator]

P@sh@, сомневаюсь, что игра стОит свеч. Хотя попробовать можно... на jump'ы тратится не только время на их выполнение, если еще учесть, что может неверно сработать "предсказание" процессором, какую команду пускать на конвейер. Хотя это уже оптимизация будет не "качественная", а какая-то "количественная"...

ЗЫ: я ее все равно уже сдал...

[Altair]

Процедуры FAR

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

[BlackShadow]

Специально для Oleg_Z:
В BP есть такая возможность при компиляции модуля указать, что тот может быть оверлейным ({$O+}). Тогда в проге можно будет использовать его таким образом:
[PROGRAM][OVERLAY BUFFER]
[PROGRAM][UNIT1][Y BUFFER]
[PROGRAM][U2][RLAY BUFFER]
Т. е. модули остаются неприкомпиленными, а извращёнными (компилятся в .ovr, вроде) и их надо тягать с собой (как .bgi), а когда надо вызвать чего-нибудь, то прога подгружает нужный модуль в память и работает с ним. Управлять буфером можно функциями из модуля Overlay.
Короче отстой полный.

Ну это не разработки борланда, это и в асме есть.

Покажешь где?

[BlackShadow]

Описалова в книгах достаточно. Посмотрю чего - завтра отпишу. На самом деле, если в разных модулях находятся 2 частовызываемые функции, то на загрузке/выгрузке потеря будет...
А кто автор вот этой загадочной книги по Asm'у?

[trminator]

Как нам говорили на лекции по ОС, оверлей - аналог страничной организации памяти, когда неиспользуемые страницы можно скинуть на диск (swap, pagefile) Так что не совсем dll

[trminator]

А про использование AssignCRT вместо Assign для записи в текстовый файл уже говорили? по Фаронову, наного быстрее

[BlackShadow]

Ну и зкономии ради можно (олимпиадныю трюк) воспользоваться
Assing(Input,'In.Txt');
Reset(Input);
Assign(Output,'Out.Txt');
ReWrite(Output);

[Altair]

Просто есть файловая переменная Input и output только это не ускорит и не уменьшит размера.

[trminator]

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

Есть распространенное мнение, что лучшая сортировка -- quicksort. Да, лучшая. В среднем (O(n*log(n))). В худшем случае ее время -- O(n*n). Если вам нужна гарантия, что ваша сортировка ВСЕГДА выполняется за нлогн, ИМХО, лучше выкинуть быструю сортировку.

Кстати, помогите идентифицировать сортировку. Кажется, это -- пирамидальная:

Код

procedure swap (i, j : word);
var t : integer;
begin
    t := a[i]; a[i] := a[j]; a[j] := t;
end;

procedure sort (n, t : word);
begin
    while ((t shl 1+1 <= n) and (a[t shl 1+1] > a[t]) or
        (t shl 1 <= n) and (a[t shl 1] > a[t])) do
     if (a[t shl 1+1] >= a[t shl 1]) and (t shl 1 +1 <= n) then begin
       swap (t shl 1 +1, t); t := t shl 1+1;
   end else begin
       swap (t shl 1, t); t := t shl 1;
   end;
end;

Раскопал ее в развалинах своего винта. Она работает

[BlackShadow]

trminator, да похоже на пирамидку.
Oleg_Z, использование Input и OutPut действительно ничего не ускорят, но вот размер на объявлении двух новых ФАЙЛОВЫХ переменных сэкономит.
Oleg_Z, извиняй, что так завис с Overlay'ем - малой мой книгу мне только сегодня выделил, а сутра мне не до этого было. Пока чай пил я пролистал главу про эту фигню и нашёл кое-что интересное. Во-первых .Ovr могут прилинковываться к EXE-шнику, но загружаться только по требованию,а во-вторых стандартный модуль Overlay умеет работать с EMS! Т. е. при загрузке программы все модули можно закачать в EMS, а оттуда по требованию скидывать в обычную память и работать с ними.
Кратко о использовании. Оверлейным может быть только модуль откомпилированный с {$O+}, а так же ВСЕ(!) экспортируемые функции должны быть FAR. Т. е. проще дописать и {$F+}. Из стандартных оверлейными, вроде, могут быть только DOS и Printer. Как подключить такой модуль? Вот так:

Код

Uses MyOvrU;
{$O MyOvrU}

Но проблема в том, что НИКАКОЙ инициализации не может быть в таких модулях до инициализации менеджера оверлеев. Но, вобщем, и это не проблема. Давай вспомним, что происходит при запуске такой вот программы:

Код

Uses U1,U2,U3;
Begin
End.

Вызывается стандартный загрузчик Pascal'я, который дописывается в прогу как Entry Point, а затем поочерёдно запускаются блоки инициализации модулей U1,U2,U3 и именно в этом(!) порядке. Затем выполняется Begin-End, после чего управление переходит к Pascal'евском "завершителю". Так вот, если применить такой вот нехитрый трюк и создать модуль типа OvrInit, в котором будет инициализироваться менеджер оверлеев, а в программе записать его первым в списке используемых Unit'ов, то проблема инициализации снимается. Вот так.
Это всё так, на словах, без единой функции модуля Overlay. Не буду их упоминать, т. к. не уверен, что вспомню в точности имена и параметры, но общий принцип таков. Сегодня вечером точно отпишу.

[trminator]

Так... я не закончил про сортировки
ИМХО, использовать, так пирамиду. Мои аргументы:
* Обратите внимание на размер той процедуры, что я привел (я уже уверен, что это -- пирамида =). И сравните ее с размером quicksort'a. Что проще написАть по памяти?
* Как я уже говорил, неплохо бы иметь гарантию, что ваша сортировка выполняется за n*log(n), а не за великий и ужастный n*n Особенно если вы участвуете в олимпиадах. И особенно если задачи составлял тов. Лопатин. Он любит quicksort

Ну и недостатки у пирамидки тоже есть как же без них. В среднем quicksort все же быстрее -- внутренний цикл у него самый быстрый.

[BlackShadow]

trminator, по памяти, может, её и проще, но на рефлексах пишется и пузырёк и QuickSort

[BlackShadow]

Oleg_Z, вот чего у меня в книге есть:
Функции Overlay'а:
OvrClearBuf - очищает буфер
OvrGetBuf - возвр. размер буфера
OvrGetRetry - возвр. размер области испытаний (что за она не въехал, но по-умолчанию тут 0).
OvrInit - инициализирует систему Overla'ев и открывает оверлейный файл.
OvrInitEMS - загружает оверлейный файл в память EMS, если это возможно.
OvrSetBuf - устанавливает размер буфера
OvrSetRetry - догадайся сам, хотя не стоит
Так же тут описана переменная OvrResult:Integer, которая может быть
OvrOK(0) - всё пучком
OvrError(-1) - что-то не пучком
OvrNotFound(-2) - файл не нашёл
OvrNoMemory(-3) - досадно как...
OvrIOError(-4) - файл есть, атолку нет
ObrNoEMSDriver(-5) - и такое бывает
OvrNoEMSMemory(-6) - а драйвер тогда зачем?
Ещё в модуле есть возможность переопределить такую фигню:

Type
  OvrReadFunc=Function(OvrSeg:Word):Integeer;
Var
  OvrReadBuf:OvrReadFunc; { *** }
  OvrFileMode:Byte;

Но зачем и что тут к чему я тоже что-то не того...
А ещё в System есть стадо переменных предназначенных для Overlay'а:
OvrCodeList:Word=0 - список сегментов кода
OvrDebugPtr:Pointer=Nil - для отладчика
OvrDOSHandle:Word=0 - для админа (скорее всего Handle файла)
OvrEMSHandle:Word=0 - Handle EMS-куска
OvrHeapEnd,OvrHeadOrg,OvrHeadPtr,OvrHeapSize:Word=0 - это если без EMS
OvrLoadList:Word=0 - "используется администратором оверлеев". И без коментариев.
Потешное замечание сделано в этой книге: не надо размещать в Overla'ях обработчики прерываний и данные для RegisterBGIDriver и RegisterBGIFont

Далее идёт пример:

{$M 16384,65536,655360}
{$D-,F+}
{D- для того, чтобы Deug-Data не скидывались в Exe-шник. Тогда можно .Ovr приаттачить к самому .Exe}

Uses Crt,Overlay,Ovr_Init,Ovr1,Ovr2;

Var
  ch:Char;

Procedure UseOverlay;
Begin
  OutPut1 {Из Ovr1}
End;

Begin
  Repeat
    clrScr;
    Write('Press any key to start ovrlays or ESC to quit');
    ch:=ReadKey;
    WriteLn;
    If ch<>#27 Then
      UseOverlay
  Until ch=#27
End.

Unit OvrInit;
Interface
Implementation
Uses Overlay,Crt;
CONST
  OvrBufSize=100000;
Begin
  ClrScr;
  OvrInit(ParamStr(0)); {!!! Предполагается, что .Ovr прилеплен к .Exe}
  If OvrResult<>OvrOk Then
  Begin
    WriteLn('ERROR!!!);
    Halt
  End;
  OvrInitEMS;
  If OvrResult<>OvrOk Then
  Begin
    WriteLn('ERROR!!!);
    Halt
  End;
  OvrSetBuf(OvrBufSize);
  If OvrResult<>OvrOk Then
  Begin
    WriteLn('ERROR!!!);
    Halt
  End;
  OvrSetRetry(OvrBufSize Div 3) {Div 3 - оптимальный вариант, но всё ещё не понятно, что за область такая}
End.

Далее берём и Build'им саму прогу. А потом выходим из BP и пишем в cmd Copy /B Proga.Exe+Overlay.Ovr (или что-то типа того). Всё теперь можно запускать.
Хотя рекомендуется не использовать Overlay во время Debug'а (какой геморрой надо преодолеть, чтобы запустить прогу).
Вот так вот. Если ещё чего - спрашивай, может найду...

[Altair]

Oleg_Z, использование Input и OutPut действительно ничего не ускорят, но вот размер на объявлении двух новых ФАЙЛОВЫХ переменных сэкономит

То есть ты хочешь сказать, что если описать :

Код

var
f:file;
f1:file;
f2:file
...

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

-------------
А как подсчитывать количество обращений, скажем к массиву, или к файлу, или к прерыванию?
-------------

Кстати, пока не забыл - здесь говорили что-то о {$M}, так вот если в модуле, то компилер просто игнорирует!

Сообщение отредактировано: Oleg_Z - 31.05.2004 19:49