Теория оптимизации программ

[Sonic86]

Существует ли какая-нибудь теория оптимизации программ на произвольных ЯП или на процедурных ЯП или на функциональных, желательно машинно-независимая?
С одной стороны, можно придумать довольно много безусловно оптимизирующих преобразований по принципу "не повторяйся" (я выписал себе штук 10 правил, могу написать, если нужны будут примеры), есть вероятностные оптимизации, есть оптимизации условные - для какого-то распределения выходных данных, есть вообще "дилеммы" - время vs память, время vs длина программы и т.п. С другой стороны, в общем случае с задачей оптимизации все должно быть плохо (неразрешима). И как-то ничего больше мне не придумывается, но теория явно должна быть.

Соответствующего курса у меня даже близко не было, потому я вообще ничего не знаю и, поковыряв интернет, нашел некую теорию схем программ. Я ее немного почитал и она мне теперь представляется как нечто сферическое в вакууме - я вообще ничего не понимаю и не вижу никакого ее контакта с реальностью.
Это устаревшая/неиспользуемая теория? Или она жива и развивается? (хотя вот смотрю книжку Ершова - вроде все понятно и осмысленно)
Какая вообще есть литература на эту тему?

[arseniiv]

Sonic86 в сообщении #1101838 писал(а):

(я выписал себе штук 10 правил, могу написать, если нужны будут примеры)

О, можно? Было бы неплохо сравнить с внутренними ощущениями.

Написал пару наивных гипотез и стёр; лучше тоже послушать, если кто-то знает больше.

[rockclimber]

Я буквально недавно наткнулся на статью в википедии Мёртвый код, там по ссылкам можно походить в связанные статьи, в них упоминаются ссылки на какие-то теоретические (или близкие к теоретическим) публикации. Попробуйте там посмотреть.

А если что, мне тоже интересно.

[Sonic86]

rockclimber в сообщении #1101855 писал(а):

Я буквально недавно наткнулся на статью в википедии Мёртвый код, там по ссылкам можно походить в связанные статьи, в них упоминаются ссылки на какие-то теоретические (или близкие к теоретическим) публикации. Попробуйте там посмотреть.

Кстати, читал, вещь хорошая.
Только там ссылаются только на книгу Ахо, Сети, Ульман Компиляторы — принципы, технологии, инструменты, 2003. и на книги на инглише, а на него у меня времени и сил мало. А книга Ахо посвящена компиляторам, из теории там только регулярные и КС-языки, остальное приводится как отдельные задачи и решения, это все не имеет ничего общего с тем, что написано в теории схем программ (хотя я только до синтаксического анализа дочитал, м.б. там дальше что-то есть)
https://ru.wikipedia.org/wiki/SSA - например вот это я ниасилил.
И вообще в Вике все выглядит как разрозненный набор задач и трюков, а не как общая теория. С другой стороны, задача удаления всех неиспользуемых переменных и неиспользуемых значений выглядит вполне разрешимой в общем случае.

Есть еще некая теория компиляции - есть она или нет? о чем она? насколько сильна? какая литература?
Еще есть на вид советская Теория вычислительных процессов (например вот: http://savestud.su/metodichki/82/Teoriy ... sobie.html) - тут даже авторов нет, куча формализма и идея мне пока не видна. Это теория? Она устарела, нет? Что может? Как соотносится с другими теориями?
http://pco.iis.nsk.su/WikiGrapp/%D0%A1% ... 0%BC%D0%BC
https://www.hse.ru/data/2015/12/07/1080 ... %D0%BC.pdf - вот тут есть описание теории схем программ и история. Ничего вообще не понимаю совершенно!
В общем, ничего не вижу, барахтаюсь в пустоте.

arseniiv в сообщении #1101847 писал(а):

О, можно? Было бы неплохо сравнить с внутренними ощущениями.

Только у меня тут немного не так: у меня есть оптимизирующие преобразования, а есть эквивиалентные. Композиция их может порождать оптимизирующее преобразование, которого нет в исходном списке. Я пишу только оптимизирующие преобразования. И они разной степени формализованности.
Язык = PL/SQL
1. Удалить неиспользуемые переменные.
2. Удалить команды, результат которых не используется, но определен.
3. Если в коде переменная инициализирована константой, то можно заменить все вхождения переменной на константу.
4. Если в коде есть одно и то же вычисление >1 раза - вычислить его в переменную и заменить вычисления на переменную.
5. Выражения вида if A then P1 end if; if A then P2 and if; $\Leftrightarrow$ if A then P1; P2; end if; при условии, что истинность $A$ после исполнения $P_1$ не изменилась.
6. if true then P end if; $\Leftrightarrow$ P;
7. if false then P end if; $\Leftrightarrow$ null;
8.

for i in a..b loop
  if i <= C then
    P
  end if;
end loop;

$\Leftrightarrow$

for i in a..least(b,C) loop
P;
end loop;

(проблемы, когда $C<a$ опущены)
9. Если для всех $i,j$ P(i) Q(j) коммутативны, то

for j in 1..iCnt loop
  P;
end loop;
for j in 1..iCnt loop
  Q;
end loop;

$\Leftrightarrow$

for j in 1..iCnt loop
  P;
  Q;
end loop;

10. Если у множества истинных значений $P$ имеется легкая для вычисления перечисляющая функция $f$, то дл некоторой функции $m$

for j in 1..n loop
  if P(j) then
    C;
  end if;
end loop;

$\Leftrightarrow$

for k in 1..m loop
  j := f(k);
  C;
end loop;

11. Если в массиве хранятся строки вида $AS(j)B$, то достаточно хранить $S(j)$, остальное вытащить в функцию.

[rockclimber]

Sonic86 в сообщении #1101874 писал(а):

Кстати, читал, вещь хорошая.
Только там ссылаются только на книгу Ахо, Сети, Ульман Компиляторы — принципы, технологии, инструменты, 2003. и на книги на инглише, а на него у меня времени и сил мало.

Я наткнулся на этот набор статей буквально дня два или три назад, поэтому вообще мало чего полезного могу сказать. Мне показалось при беглом прочтении, что там чуть больше ссылок.

Sonic86 в сообщении #1101874 писал(а):

Язык = PL/SQL

Кто-то начал беспокоиться об оптимизации PL/SQL кода с помощью последних достижений науки? Медведь в лесу сдох, надо полагать?
Вообще довольно нетипичный язык. Обычно на нем пишут довольно разрозненные куски кода, которые по частям вызываются с клиента. И части могут быть довольно маленькими и вообще никак друг с другом не связаны. И содержать большие портянки SQL-запросов, где совсем другая оптимизация нужна. Если не секрет, можете пару слов о проекте сказать? Интересно же.

Sonic86 в сообщении #1101874 писал(а):

4. Если в коде есть одно и то же вычисление >1 раза - вычислить его в переменную и заменить вычисления на переменную.

Используется синтаксис PL/SQL

a := my_sequence.NEXTVAL;
b := my_sequence.NEXTVAL;

Оптимизировать будете?

Sonic86 в сообщении #1101874 писал(а):

9. Если для всех $i,j$ P(i) Q(j) коммутативны, то

А это дает хоть сколько-нибудь измеряемый выигрыш? Мне казалось, что нет. Я даже настолько уверен был, что никогда не проверял

[iifat]

Как понимаю, есть множество работ Ершова со товарищи, не устаревших и по сей день. Сильно не верю, что автоматическая оптимизация превзойдет ручную более чем процентов на 10. Оптимизация средствами языка — вообще полная безнадёга, если этот язык не Цэ++ или Algol-68.

Sonic86 в сообщении #1101874 писал(а):

Удалить команды, результат которых не используется, но определен

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

Sonic86 в сообщении #1101874 писал(а):

Если в коде переменная инициализирована константой, то можно заменить все вхождения переменной на константу

... поимев уйму геморроя при смене константы...

Sonic86 в сообщении #1101874 писал(а):

Если в коде есть одно и то же вычисление >1 раза - вычислить его в переменную и заменить вычисления на переменную

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

[aa_dav]

Какой то единой дисциплины я не знаю и возможно она и невозможна.
Но в теории алгоритмов оные подробно исследованы на алгоритмическую сложность и затраты памяти.
Лет 20-30 назад были актуальны ручные микрооптимизации в компилируемых языках, сейчас, правда, сильно потерявшие актуальность в связи с сильными оптимизирующими компиляторами.
Для разработчиков последних производители процессоров выпускают Optimization Guide-ы, руководствуясь, однако, которыми, правда, можно до сих пор "вручную" микрооптимизировать код в некоторых случаях. (иногда, впрочем, очень сильно, т.к. по кешу оптимизировать компиляторы не умеют до сих пор)
Оптимизация баз данных - это отдельный огромный пласт.

[whitefox]

Sonic86 в сообщении #1101874 писал(а):

хотя я только до синтаксического анализа дочитал, м.б. там дальше что-то есть

Есть. Глава 9. Машинно-независимые оптимизации.

[Sonic86]

whitefox в сообщении #1101943 писал(а):

Есть. Глава 9. Машинно-независимые оптимизации.

Благодарю! Упустил, буду читать тоже.

aa_dav в сообщении #1101934 писал(а):

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

Литературы не подскажете?

rockclimber в сообщении #1101911 писал(а):

Кто-то начал беспокоиться об оптимизации PL/SQL кода с помощью последних достижений науки? Медведь в лесу сдох, надо полагать?

Язык взят исключительно для примера: он достаточно бедный и безглючный. Если бы язык был богаче, список оптимизирующих преобразований был бы еще больше. С таким же успехом я мог бы взять C++, Pascal, м.б. Delphi, Lua какой-нибудь - любой C-подобный процедурный язык. Соответственно всевозможные обсуждения БД тоже не интересуют и сказать я ничего о них не могу. Хотя запросы тоже можно оптимизировать.
Кстати, еще забыл:
12.

if A then C1; C2; else C3; C2; end if;

$\Leftrightarrow$

if A then C1; else C3; end if; C2;

13. Если $P$ не зависит от $j$ и iCnt >0, то

for j in 1..iCnt loop 
P; 
Q; 
end loop;

$\Leftrightarrow$

P; 
for j in 1..iCnt loop 
Q; 
end loop;

rockclimber в сообщении #1101911 писал(а):

Если не секрет, можете пару слов о проекте сказать? Интересно же.

проекта нет, не отстать бы от жизни

iifat в сообщении #1101933 писал(а):

Как понимаю, есть множество работ Ершова со товарищи, не устаревших и по сей день.

Спасибо, буду знать.

iifat в сообщении #1101933 писал(а):

Сильно не верю, что автоматическая оптимизация превзойдет ручную более чем процентов на 10.

согласен

iifat в сообщении #1101933 писал(а):

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

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

iifat в сообщении #1101933 писал(а):

омимо проблем с опознанием действительно одних и тех же выражений, специфика именно языков СУБД в том, что арифметика быстрая, а работа с БД медленная. Ввиду чего оптимизация общих подвыражений — дело не слишком-то полезное.

Опять же, СУБД не интересует.

Давайте от темы не отклоняться.
Кроме теории схем программ есть еще теории оптимизации программ? Что насчет вышеперечисленных, есть ли другие?
Теория схем программ исчерпывается книжками Ершова, Янова, Котова и т.п. или еще что-то есть?

[aa_dav]

Sonic86 в сообщении #1101948 писал(а):

Литературы не подскажете?

Ну тот же Кнут незабвенный. Но он тяжеловесен донельзя. Как альтернативу я бы предложил https://ru.wikipedia.org/wiki/%D0%90%D0 ... 0%B8%D0%B7
Это всё про https://ru.wikipedia.org/wiki/%D0%92%D1 ... 1%82%D1%8C

[Maslov]

Sonic86 в сообщении #1101838 писал(а):

Существует ли какая-нибудь теория оптимизации программ на произвольных ЯП или на процедурных ЯП или на функциональных, желательно машинно-независимая?

Sonic86, с какой целью оптимизируете?

Оптимизировать можно время, память, читаемость, время разработки, сопровождаемость, тестируемость и еще много чего. Цели оптимизации часто конфликтуют (в частности, минимизация памяти и времени выполнения конфликтуют почти всегда), поэтому универсальных способов тут нет.

Полистайте книгу С.Макконнелла "Совершенный код": там много чего полезного с точки зрения практики.

[mustitz]

Sonic86 в сообщении #1101874 писал(а):

2. Удалить команды, результат которых не используется, но определен.

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

Sonic86 в сообщении #1101874 писал(а):

3. Если в коде переменная инициализирована константой, то можно заменить все вхождения переменной на константу.

Если от переменной явно или неявно взят адрес, или переменная может изменяться из другого потока?

int x = 4;
memset(&x, 0, sizeof(int));
// ....

Sonic86 в сообщении #1101874 писал(а):

4. Если в коде есть одно и то же вычисление >1 раза - вычислить его в переменную и заменить вычисления на переменную.

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

В общем, много нюансов. Поэтому в C было добавлено ключевое слово restrict. Кстати, можно почитать стандарт С и C++, там описано много оптимизаций, которые может делать компилятор. Соответственно, надо писать код с учётом этих оптимизаций.

Если брать теорию, то мне больше нравится старый двухтомник Ахо, Ульман, «Теория синтаксического анализа, перевода и компиляции», 1978. Она более математична, чем книга Дракона. Там глава 11 (последняя во втором томе) как раз посвящена оптимизации. Если брать практику, то одна из самых простых дорог — генерация кода LLVM, который затем может быть оптимизирован средствами самого LLVM.

[rockclimber]

Sonic86 в сообщении #1101948 писал(а):

Язык взят исключительно для примера: он достаточно бедный и безглючный.

Я буквально пару недель назад напоролся на очень неприятный глюк (см. обсуждение тут). Это пока единственный известный мне глюк такого рода, но неприятно то, что типичная ошибка этапа компиляции вылезает только в рантайме. Другие языки такого себе не позволяют обычно. Oracle, насколько я знаю, в курсе, но считает, что это нормально. Случай не ваш конечно (раз вы в БД не лезете), просто, скорее, как иллюстрация того, что и на старуху бывает проруха.

Sonic86 в сообщении #1101948 писал(а):

С таким же успехом я мог бы взять C++, Pascal, м.б. Delphi, Lua какой-нибудь - любой C-подобный процедурный язык.

Ну вот я бы не сказал, что с таким же успехом. Хоть я и фанат PL/SQL, но для вашей задачи он мало подходит, имхо. Может, вам все-таки что-то более классическое взять?

mustitz в сообщении #1101983 писал(а):

Если от переменной явно или неявно взят адрес, или переменная может изменяться из другого потока?

Конкретно в PL/SQL этого нет.

[Munin]

Под "оптимизацией" понимаются две сильно разные вещи:
- оптимизация порядка сложности алгоритма;
- оптимизация, не меняющая порядка сложности.

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

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

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

[arseniiv]

Munin в сообщении #1102047 писал(а):

а второй не нужно

Ну здрасьте. Нет, нужно. Только надо вооружаться сначала правильными средствами и знать, где места узкие, а где нет, и почему, чтобы не оптимизировать без разбору. Имеется в виду сравнительно высокоуровневая оптимизация: например, изменение структуры данных: вместо итератора, к примеру, дерево какое, если нужно постоянно узнавать, содержится ли в множестве элемент.

-- Чт фев 25, 2016 20:27:46 --

Хотя когда язык позволяет низкоуровневую, конечно, и та. Компиляторы пишут люди!