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

Всего тестировалось 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..."

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

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

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

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

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

Код быстрее:


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

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

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

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

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

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

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

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

Процедуры FAR

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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'а (какой геморрой надо преодолеть, чтобы запустить прогу).
Вот так вот. Если ещё чего - спрашивай, может найду...

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

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

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

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

А, если ты напишешь так:

Думаешь он под b ничего не выделит?
А не веришь - проверь.

Сколько пишет?


1). Ты же за FPC взялся? Помнишь я тебе про свойства говорил? Вот так и подсчитать.
2). См п. 1
3). Перехватить и увеличивать счётчик.


Возможно.

Взято из ООП. Объектно-ориентированное программирование

Мой вариант:

Begin и end лишние видимо я поставил, а вот объединить два промежутка, это мысль.
romtek, а скорость увеличится?
ИМХО так только нагляднее, а сорость не увеличится.

Вспомнил один момент такой. При работе с дробями, практичнее фразы типа b:=a/10 заменять на b:=a*0.1
Ну, это так, мелочи...

Нет, ассемблер нужно применять только для шлифовки критических участков кода (черт, это не моя фраза, и не помня откуда она )
Чаще сам алгоритм можно переработать используя только стандартные средства.
Кстати конструкция if a and b then хуже, чем
if a then if b then, т.к. в случае провала первой подцели (а), второя не будет проверятся!

---------
APAL, ИМХО пора бы эту тему закрепить.

моя вроде

Complete boolean evaluation (compiler option)

Да уж, Oleg_Z, это действительно отключается директивами. Другое дело - преобразование сложных логических вычислений. Например:
(a And Not B) Or (Not a And B) = a Xor b.

BlackShadow, в следующий раз оформляй логические выражения в тег кода.
Насчет преобразования сложных логических вычислений - а все ли логические функции выполняются с одинаковай скоростью ???
Или есть смысл упрощать сложные логические конструкции?
Например если 10^n раз проверяется


То может это заменить на

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

В первом случае имеем 2 операции, а во втором - 3

Да, но во первых операция NOT ИМХО должна выполняться быстрее, а во вторых есть обратный ход.

Вот еще:
Если в программе используется write и writeln, то следует убрать последнюю, а использовать только write и управляющие символы.
Доказательство преимущества этого способа:
1 байт с проги снимется, т.к. writeln и write процедуры вне кода описанны, и компилтруются в расчете на FAR.
А так, вместо 2 байт на дальнюю модель памяти (т.е. на адрес процедуры) уйдет только 1 байт!


====== добавил позже =======

Облом. Я проверил все.
1. Логические операции бесполезно упрощать!
2. Writeln работает быстрее, чем write('ddfd',#13,#10), и к тому же на 100 кб(!!) меньше код получается (использовался один раз).
3. Сильно уменьшает код (на 150-200 кб) следующие директивы (применять только на уже оптимизированных программах)

(взял с сурсов.) Очень полезные директивы.
Только две первые не влияют на размер.

REAL почти в 2 раза медленнее ВСЕХ других числовых типов

доказательство в присоединенном коде.

Oleg_Z
Real потому медленнее, что у него размер нестандартный - 48 бит, кто его такой выдумал, интересно ? а все более-менее современные процы оптимизированы на работу с 32/64-бит данными. к тому же этот тип не поддерживается сопроцессором, поэтому его либо надо переконвертать в нормальный, либо эмулировать...

насчет директив - все они есть в диалоговом окошке "Опции компилятора" или как его там. если убрать все проверки, тогда конечно меньше будет объем кода, да и быстрее чуть-чуть, а почему первые две не влияют на размер ? видимо мат.функции хоть и в двух версиях написаны (с сопроцессором и софтварно), но компилируются всегда вместе...

Int64 появился только в 32-битных компиляторах. По своей сути он - то же самое, что LongInt для BP: работа в EAX и EDX вместо AX и DX. Скорость сравнима...
А вот Real - это либо эмуляция либо содвижок...

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

Взято из этой статьи:http://russian.joelonsoftware.com/Articles...actions.html#c4

А эту статью прочитал просто с наслаждением:Back to Basics

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

З. Ы. : лучший способ инициализации "любомерного" массива одинаковыми значениями - это Fillchar (если меня память не подводит, то в Pascal'е эта функция называется так).

В каком именно Паскале?


Ну, я же не лось...

Нет, в принципе, интуитивно понятно, что вроде бы на следующий элемент переходить удобнее, чем на n-й, но почему такой большой выигрыш? Тут увеличиваем смещение на единицу, там - на некоторое чиcло... Или для считывания слеующего элемента есть более быстрая команда? Хотя, наверное, я чушь порю... асм только-только начал трогать. Нельзя ли объяснить "на пальцах", как в обоих случаях будет действовать компилтор?

Borland Turbo Pascal 7.0
TMT pascal
да и во всех других, скорее всего, есть

Действительно... Просто никогда её не использовал. Во всех примерах, на которых нас обучали, это делалось в цикле. Как-то прошёл мимо неё, хотя был уверен, что все основные функции помню. К тому же в описании не конкретно про массив, а просто про байты некоторой переменной говорилось. Будем знать.

Про оптимизацию я, кажется, понял. Она может достигаться применением цепочечных команд, которые позволяют процессору одновременно и работать и с регистром, и со счётчиком(как раз сегодня у нас лекция была). Так?
Но, интересно, компилятор Паскаля знает, когда выгодней их использовать?
Или только ассемблерными вставками?

Странно, тестирую бытсрую и пирамидальную на скорость, первая бысрее... может я ошибся где-то ?
Вот код:

Да, все верно,
пирамида медленнее чем "быстрая сортировка".




---
ЗЫ: спасибо trminator'y за помощь при проведении теста и разбор результатов.

Просто память физически устроена как конденсаторы [в каком бы то не было виде] в виде матрицы, и поэтому для перехода на следующий элемент требуется изменение только RAS цикла, и перехода считывателя на несколько мм а для перехода на ячейку в другом месте RAS и CAS счетчика...

Могу путать где RAS а где CAS - но при больших объемах используемой памяти значение большое...

Как нам объясняли, кэш нужен для хранения значения ЯПамяти при обновлении ячеек...

Обмен значений в переменных.

Для увеличения скорости работы программы при обмене значениями двух чисел a и b вместо конструкции


или конструкции

желательно использовать буферную переменную:


Тестируем скорость выполнения операции обмена:


Результаты тестирования: