OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Суббота, 19 Октябрь, 2019 15:12

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 72 ]  На страницу Пред.  1, 2, 3, 4
Автор Сообщение
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 16:25 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 700
Откуда: Псков
alexus писал(а):
Если интересно, то могу привести код на ассемблере (без ухищрений, чтобы было легче воспринимать).

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 17:02 
Аватара пользователя

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Код:
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


Последний раз редактировалось alexus Понедельник, 24 Октябрь, 2011 17:27, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 17:08 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
Разрисовать бы примерно как здесь... :wink:


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 17:30 
Аватара пользователя

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Владислав Жаринов писал(а):
Разрисовать бы примерно как здесь... :wink:
Вроде бы всё прокомментировано... К сожалению табуляция другая...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 17:35 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 700
Откуда: Псков
albobin писал(а):
подозреваю он будет соответствовать тому о чём уже неоднократно писал Илья Ермаков (повторное использование фрейма в стеке)

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 17:50 
Аватара пользователя

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
albobin писал(а):
albobin писал(а):
подозреваю он будет соответствовать тому о чём уже неоднократно писал Илья Ермаков (повторное использование фрейма в стеке)

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 19:09 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 700
Откуда: Псков
alexus писал(а):
Борьбу с рекурсией тоже можно показать...

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Вторник, 25 Октябрь, 2011 11:27 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
Цитата:
Хм?.. Непонятно, о каких гарантиях идёт речь?..


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

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Вторник, 25 Октябрь, 2011 13:31 
Аватара пользователя

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Вторник, 25 Октябрь, 2011 14:32 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
Это уже выше уровнем, дальше от оборудования...

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

IF ... THEN
A
ELSE
B
END.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Вторник, 25 Октябрь, 2011 15:24 
Аватара пользователя

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

IF ... THEN
A
ELSE
B
END.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Среда, 26 Октябрь, 2011 19:10 

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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 72 ]  На страницу Пред.  1, 2, 3, 4

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB