OberonCore
https://forum.oberoncore.ru/

Оптимизация алгоритмов
https://forum.oberoncore.ru/viewtopic.php?f=5&t=3620
Страница 4 из 4

Автор:  albobin [ Понедельник, 24 Октябрь, 2011 16:25 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

alexus писал(а):
Если интересно, то могу привести код на ассемблере (без ухищрений, чтобы было легче воспринимать).

Приведите, подозреваю он будет соответствовать тому о чём уже неоднократно писал Илья Ермаков (повторное использование фрейма в стеке)

Автор:  alexus [ Понедельник, 24 Октябрь, 2011 17:02 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Код:
procedure QuickSort(var a: TAOFI; const left, right: Integer);

   procedure QS_Asm(const l, r: Integer); register;
   var   left, right   : Integer;
   asm
      mov   [left],edx
      mov   [right],ecx
      mov   edi,[esi + edx * 4]
      mov   ebx,-1

   @@1:   cmp   ecx,edx         ; if (j = i) then
      je   @@5         ; goto @@5
      or   ebx,ebx         ; if (d = False) then
      jz   @@2         ; goto @@2
      mov   eax,[esi + ecx * 4]   ; eax := a[j]
      cmp   edi,eax         ; if (x <= a[j]) then
      jle   @@3         ; goto @@3 ( dec(j) )
      mov   [esi + edx * 4],eax   ; a[i] := a[j]
      not   ebx         ; d := False
      jmp   @@4         ; goto @@4 ( inc(i) );
   @@2:   mov   eax,[esi + edx * 4]   ; eax := a[i]
      cmp   eax,edi         ; if (a[i] <= x) then
      jle   @@4         ; goto @@4 ( inc(i) )
      mov   [esi + ecx * 4],eax   ; a[j] := a[i]
      not   ebx         ; d := True

   @@3:   dec   ecx         ; dec(j)
      jmp   @@1         ; goto loop_start
   @@4:   inc   edx         ; inc(i)
      jmp   @@1         ; goto loop_start

   @@5:   mov   [esi + edx * 4],edi   ; a[i] := x
      dec   edx         ; dec(i)
      inc   ecx         ; inc(j)
      cmp   [left],edx      ; if (left >= i) then
      jge   @@6         ; goto @@6
      xchg   ecx,[left]      ; save ecx
      xchg   ecx,edx         ; edx := left; ecx = i;
      call   QS_Asm
      mov   ecx,[left]      ; restore ecx (j)
   @@6:   cmp   ecx,[right]      ; if (j >= right) then
      jge   @@7         ; goto @@7
      mov   edx,ecx         ; edx := j
      mov   ecx,[right]      ; ecx := right
      call   QS_Asm
   @@7:
   end;
asm
   push   ebx
   push   esi
   push   edi
   mov   esi,eax   ; esi = address array
   call   QS_Asm
   pop   edi
   pop   esi
   pop   ebx
end;


ebx -> d
edx -> i
ecx -> j
esi -> address of array

Автор:  Владислав Жаринов [ Понедельник, 24 Октябрь, 2011 17:08 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Разрисовать бы примерно как здесь... :wink:

Автор:  alexus [ Понедельник, 24 Октябрь, 2011 17:30 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Владислав Жаринов писал(а):
Разрисовать бы примерно как здесь... :wink:
Вроде бы всё прокомментировано... К сожалению табуляция другая...

Автор:  albobin [ Понедельник, 24 Октябрь, 2011 17:35 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

albobin писал(а):
подозреваю он будет соответствовать тому о чём уже неоднократно писал Илья Ермаков (повторное использование фрейма в стеке)

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

Автор:  alexus [ Понедельник, 24 Октябрь, 2011 17:50 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

albobin писал(а):
albobin писал(а):
подозреваю он будет соответствовать тому о чём уже неоднократно писал Илья Ермаков (повторное использование фрейма в стеке)

Ошибся в подозрениях. Подумал, что Вы собирались показать борьбу с рекурсией. Но это не важно. Любопытство моё удовлетворено, спасибо.
Борьбу с рекурсией тоже можно показать...

Автор:  albobin [ Понедельник, 24 Октябрь, 2011 19:09 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

alexus писал(а):
Борьбу с рекурсией тоже можно показать...

Мой проявленный интерес носит отчасти праздный характер, будет лучше если Вы найдёте действительно заинтересованного собеседника по сабжу.

Автор:  Илья Ермаков [ Вторник, 25 Октябрь, 2011 11:27 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Цитата:
Хм?.. Непонятно, о каких гарантиях идёт речь?..


Я имею в виду, что если в стандарте языка будет указано, что "компилятор языка обязан трансформировать статически обнаруженный концевой рекурсивный вызов", то я смогу писать алгоритм, полагаясь на этот факт (например, программировать "бесконечно" работающий КА); а иначе на каком-нибудь компиляторе получу вылет за стек после первой же тысячи-другой переходов автомата :)

Цитата:
Ух, тут бы не ошибиться... если в одной процедуре количество формальных параметров, передаваемых через стек, будет иным, чем в той процедуре, откуда прыгали (jump), то... проблемы возникнут при разгрузке стека. Тоже относится к совокупному размеру локальных переменных...

Ну, jump компилятор пусть генерирует, если процедуры без параметров (например, прыгаем между вложенными процедурами), а в противном случае пусть обычный call, но сначала разгружает стек уже оконченной вызывающей процедуры. Да, да, есть ещё вопрос, как с VAR-параметрами - можно запретить.
Вообще, этот механизм может решить все проблемы, когда одномерное структурное программирование "жмёт". Вместо goto - концевая передача управления от процедуры к процедуре.
Может быть, стоит не делать оптимизацию концевого вызова, а ввести отд. оператор, который обозначает совершение такого вызова с завершением вызывающей процедуры.

Нюансов много, но простой вариант найти можно, а овчинка выделки стоит. Оптимизация рекурсий, автоматность, строгий вариант goto для алгоритмов управляющего характера - всё одним средством.

Автор:  alexus [ Вторник, 25 Октябрь, 2011 13:31 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Илья Ермаков писал(а):
Я имею в виду, что если в стандарте языка будет указано, что "компилятор языка обязан трансформировать статически обнаруженный концевой рекурсивный вызов", то я смогу писать алгоритм, полагаясь на этот факт (например, программировать "бесконечно" работающий КА); а иначе на каком-нибудь компиляторе получу вылет за стек после первой же тысячи-другой переходов автомата :)
Не думаю, что это хорошая идея... Проще/правильнее сделать работу на основе сообщений. В противном случае, единожды скомпилированный код будет работать по одной и той же схеме, что не очень гибко... Представьте, что в том же QiuckSort вместо концевых вызовов отсылаются соответствующие сообщения. По мере возможности исполнитель обрабатывает эти сообщения... параллельно (каждое сообщение определяет свою часть массива, и эти части не пересекаются, это очень удобно для параллельной обработки). Сообщения можно упорядочить, по "уровню вложенности" (чем больше "уровень вложенности", тем позже обрабатывается/ниже приоритет сообщения).
А если делать переходы, то точки перехода нужно оставить программируемыми, типа:
Код:
jmp [jump_address]
Тогда адрес перехода можно будет менять в зависимости от условий/результата выполнения данного перехода или... извне.
Илья Ермаков писал(а):
Ну, jump компилятор пусть генерирует, если процедуры без параметров (например, прыгаем между вложенными процедурами), а в противном случае пусть обычный call, но сначала разгружает стек уже оконченной вызывающей процедуры.
Разгрузив стек до перехода, мы утрачиваем контекст исполнения (фактические параметры, локальные переменные, результаты...). Сообщения всё же лучше... Их можно перенаправлять, перехватывать, игнорировать, откладывать, переставлять в каком-то заданном порядке, обобщать, делать пакетную обработку и т.п...
Илья Ермаков писал(а):
Да, да, есть ещё вопрос, как с VAR-параметрами - можно запретить.
Простым запрещением эту задачу не решить, IMHO. Нужен полноценный аппарат разрешения конфликтов.
Илья Ермаков писал(а):
Вообще, этот механизм может решить все проблемы, когда одномерное структурное программирование "жмёт". Вместо goto - концевая передача управления от процедуры к процедуре.
Может быть, стоит не делать оптимизацию концевого вызова, а ввести отд. оператор, который обозначает совершение такого вызова с завершением вызывающей процедуры.
Собственно, что-то всё равно нужно... либо адрес возврата, либо адрес перехода, альтернатива им... halt/передача управления системе, но это не слишком разумно.
Илья Ермаков писал(а):
Нюансов много, но простой вариант найти можно, а овчинка выделки стоит. Оптимизация рекурсий, автоматность, строгий вариант goto для алгоритмов управляющего характера - всё одним средством.
... сообщением... :)

Автор:  Илья Ермаков [ Вторник, 25 Октябрь, 2011 14:32 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Это уже выше уровнем, дальше от оборудования...

По поводу принятия решения о переходе:
так никто не запрещает писать

IF ... THEN
A
ELSE
B
END.

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

Автор:  alexus [ Вторник, 25 Октябрь, 2011 15:24 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Илья Ермаков писал(а):
Это уже выше уровнем, дальше от оборудования...
Не обязательно выше... Уровень определяется абстракциями, которыми мы оперируем. Можно считать, что нижний уровень абстракций - оператор, например, i := 8;, а кто то думает, что процессор посылает сообщение контроллеру памяти, записать в двойное слово, по адресу [ebp - 12], значение 8... :)
Илья Ермаков писал(а):
По поводу принятия решения о переходе:
так никто не запрещает писать

IF ... THEN
A
ELSE
B
END.

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

Автор:  Владислав Жаринов [ Среда, 26 Октябрь, 2011 19:10 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

alexus писал(а):
Владислав Жаринов писал(а):
Разрисовать бы примерно как здесь... :wink:
Вроде бы всё прокомментировано... К сожалению табуляция другая...
Ну, это не в смысле Вам рисовать - а что исходный техноязык как раз для того, чтобы визуализировать ассемблер... :)

Страница 4 из 4 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/