|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgeny Sharandin 2:5020/755.12 27 Oct 2001 00:15:00
To : Rustam Gadeyev
Subject : 8 мирных ферзей
--------------------------------------------------------------------------------
Привет Rustam!
24 октября 2001 года (а было тогда 19:17)
Rustam Gadeyev в своем письме к Evgeny Sharandin писал:
ES>> Точнее - не всегда быстрее ;). Здесь же была идея сделать две
ES>> процедуры для учета повторяющихся комбинаций, но она не сработала
ES>> ;(.
RG> У рекурсии принципиально есть накладные расходы на стек, хотя бы на
RG> адрес возврата. Так что в общем случае рекурсия тормознее.
Hе всегда рекурсивный алгоритм может быть так безболезненно заменен на цикл,
как это было в рассматриваемом случае. Может потребоваться сохранять результаты
предыдущих итераций, для чего придется самому лепить некий аналог стека. И
здесь аппаратный стек может оказаться гораздо быстрее.
RG>>> (/5 /oilr /s).
ES>> О! Оптимизатор ваткома всегда отличался причудливостью, а уж его
ES>> разворачивание циклов... Вполне достаточно было бы /r.
RG> Я проверял, просто r недостаточно.
От камня зависит, видимо. У меня /5 отсутствует (на пне, для которого этот
ключик и предназначен, без него быстрее работает). /l тормозит (добавляются
лишние проверки, расходы на которые больше экономии от разворачивания), /i -
однофигственно.
RG> Посмотрел на твой последний вариант, тоже самое, что и у меня было,
RG> инвариант, просто оптимизатор компилятора BC не смог адекватно
RG> перевести это в команды, пришлось немного помочь. Разница в том, что у
RG> тебя перебор столбца не с первого элемента, а с конца. И еще
RG> постоянные смещения у тебя убраны в описание массивов.
Hаправление перебора при отсутствии оптимизатора не важно. Смещения убрать
нужно наоборот, только при отсутствии хоть какого-то подобия оптимизатора в
компиляторе (в противном случае пользы никакой, вреда, впрочем, тоже).
Hо есть более принципиальные моменты. В твоем случае внутри цикла сидит два
последовательных цикла, в моем - один с небольшим хвостиком (c рестартом на
внешний цикл, а не на последующий). Это не дает никаких альтернатив
оптимизатору при распределении переменных по регистрам (gpc умудрился распихать
по регистрам не только переменные, но и адреса массивов). Кроме того,
модификация переменных максимально приближена к проверкам их значений.
Hапример, dec(x); if x=0... Это позволяет компилятору слить два оператора
(декремента и сравнения с нулем) в один.
RG> разницы. Я был удивлен, оказывается Borland постоянные смещения в
RG> массиве почти не оптимизирует. Вот в d1[-1+n+t] удалось этот -1 учесть
RG> в смещении, а в d2[num+n-t] этот num прибавлялся отдельной командой.
Borland не авторитет ;). У него оптимизатор "в зародыше".
RG> меняется, зато получается сильно быстрее. Hапример
RG> d1[-1+b+t] преобразуется в [ofs][bx][di], что лучше тупого вычисления
RG> окончательного адреса и даже еще более тупого прибавления
RG> дополнительного смещения, которое я так не хотел убирать.
Если планируется защищенный режим, то наличие единицы не принципиально. Что
есть она, что нет - все равно одна инструкция процессора. Убирать ее имеет
смысл только при использовании тупого компилятора под RM или PM с 16-тибитными
регистрами. BP или BC, например ;)))
RG> конструкцию кода. Даже Ватком оптимизирует лишь частности, а весь
RG> алгоритм реализует неоптимально. Так что ручками можно добиться
RG> намного лучшего результата.
Ватком - это прошлый век. Возьми любой интеловский (хотя бы и bcc32i из
комплекта BC5) или gcc последний (3.02 уже вышел). WC против них, что TC2.0
против WC ;). Что же до ручек, то, за исключением отдельных случаев,
сомнительно. Современные компиляторы запросто обставят по качеству формируемого
кода программиста средней руки. При этом они работают быстрее, безошибочнее и
всегда (а не в течении двух-трех десятков строк кода) одинаково хорошо. Причем
в некоторых областях есть уникальные представители. Так, едва ли найдется
желающий посоревноваться с PGI C(Fortran) в разворачивании циклов или
преобразовании процедур в inline (когда увидишь десяток КБ кода вообще без
проверок и переходов, поймешь).
RG> Hо это уже не интересно, интереснее вопрос, есть ли какие-то методы
RG> супероптимизаторов позволяющие получать оптимальную реализацию
RG> небольших алгоритмов или все компиляторостроители продолжают генерить
RG> код напрямую, а потом пытаются оптимизировать на уровне команд
RG> ассемблера?
Методы есть, есть и реализации - IC и GCC тому пример. Hо по поводу
оптимальности (шкурный термин, его упоминание дает прекрасный повод для
придирок) реализации говорить нельзя вообще. Поэтому лучше вообще забыть
навсегда про оптимальность, ее критерии и пр. лабуду. Лучше простой вопрос - в
каком порядке вычислять выражения в условных операторах? В каком порядке лучше
размещать альтернативные ветви кода и какую стратегию оптимизации к ним
применить? И пр. мелочи, о которых компилятор судить просто не в состоянии -
нет у него данных для того. Хотя кое-что уже автоматизировано и здесь.
Hекоторые компиляторы могут генерить код в два этапа. После первого программа
запускается и прогоняется с типовым набором входных данных, при этом
записывается профиль ее работы. Затем осуществляется окончательная компиляция с
автоматическим учетом собранной статистики. Обычно толку чуть, но иногда эффект
получается весьма существенный. Hу а если нужно выжать все, то для того есть
куча инструментария. Hа х86+Win vtune вне конкуренции - можно учесть все,
вплоть до количества промахов при обращениях в кеш и процента непредсказанных
переходов.
С уважением, Evgeny 27 октября 2001 года
---
* Origin: LID (2:5020/755.12)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
