На самом деле проблема оптимизировать алгоритм в другую O-оценку в том, что обычно используются уже эффективные алгоритмы. Кто сортирует руками если есть sort? Кроме того, многие места которые можно было бы оптимизировать определяют наблюдаемое поведение системы (например, делают ввод-вывод).

Project VGA

Оказывается, я был не совсем прав про Project VGA. Их сайт по-прежнему существует в другом домене: http://wacco.mveas.com/ Но ни на сайте, ни в рассылке ничего нового с февраля 2008-го.

Не сложность. Как это делать, многие (в т.ч. я) знают. Нет серьезного практического применения.

Одно дело знать, другое дело сделать. Тебе видимо подобный софт не особо нужен, но это же не повод экстраполировать на всех. Да, можно использовать коммерческий софт, но свободный обладает рядом преимуществ, с ним я могу делать все что захочу и даже его допиливать под свои нужды, не иметь геморроя с лицензиями. А что касается производства многослойных плат, то сейчас вполне можно сделать небольшую 4-6 слойку за 20-30 тыс. рублей по нормам 0.1 мм зазор/0.2 мм отверстие, не так уж и много для серьезного любителя, всякие геймеры покупают компы за 50 т.р. и больше и никого это особо не удивляет. Проблема в том, что те кому это реально надо, предпочитают пользоваться коммерческим софтом, только и всего.

который заранее распознает алгоритм переписывает код?

А всякие там polyhedral optimisations что делают, по твоему?

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

А если ты напишешь компилятор, который меняет класс эквивалентности, то тебе нобе^W пулю дадут.

Вот не надо тут ля-ля разводить. Почти все компиляторы делают loop fusion, например.

это не меняет класс эквивалентности.

это не меняет класс эквивалентности.

Раз уж ты так настаиваешь на незыблемости класса эквивалентности при оптимизации, вот тебе пример:

int  f(int n)
{
   if(n <= 1)
     return 1;

   return f(n-1) + f(n-2);
}

Эта функция при тупом вычислении имеет экспоненциальную сложность. Можно преобразовать этот алгоритм в алгоритм с линейной сложностью:

int g(int n)
{
  if(n <= 1)
    return 1;

  int n0 = 1, n1 = 1,tmp;

  for(int i = 0;i < n;i++)
  {
    tmp = n1;

    n1 += n0;

    n0 = tmp;
  }

  return n0;
}

Я могу сделать оптимизатор, который распознает некоторый класс функций, подобный f и преобразует их код в код, подобный функции g. Это будет корректный оптимизатор с точки зрения стандарта C.

Нет никакой «логической сущности» алгоритма при формальном рассмотрении алгоритма. Точно также не существует алгоритма отдельно от машины, на которой он исполняется. Алгоритм --- это упорядоченный набор инструкций для некоторой машины. Оптимизация алгоритма --- это построение другого алгоритма, который в некотором смысле «лучше» исходного (например быстрее на некотором наборе входных данных или на всех данных), но в то же время эквивалентен исходному в том смысле, что после его завершения результат его работы совпадает с результатом работы исходного алгоритма.

Если приведенный выше пример кажется искуственным, могу предложить еще один: оптимизация хвостовой рекурсии в gcc, которая реально там присутствует (выполнение этой оптимизации не гарантируется, но возможно в некоторых случаях). Временная сложность при этом конечно же не меняется, но требуемый объём памяти падает с O(n) до O(1), ибо перестает засираться стек. Сложность по требуемой памяти ты не упоминал, но если уж ты требуешь сохранения временной сложности, то чем память хуже?

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

Приведенный тобой пример неплох. Спасибо. Но как ты сказал он искусственный. Ну напишешь ты оптимизатор на такой конкретный случай, но останется еще миллиарды других случаев.

Логическая сущность алгоритма очень даже существует. Возьми к примеру алгоритм поиска оптимального потока через граф. Программа не может сама придумать новый алгоритм, который выполняет тоже действие за более короткое время. ты вынужден будешь просто писать распознавалки используемых алгоритмов. А это сизифов труд. Так как все оптимальные на сегодняшний день алгоритмы уже есть в разных либах. Кому надо, тот и использует.

Тебе никакая polyhedral оптимизация никогда из пузырьковой сортировки не сделает быструю.

С сортировкой оно ничего не сделает. А вот из трех вложенных циклов (O(N^3)) запросто может сделать один (O(N)).

это если быдлокод последней стадии. А в более-менее индусско-студо коде ты ничего не сделаешь.

Логическая сущность алгоритма очень даже существует.

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

Напомню, с чего вообще начался весь сыр-бор. Yampp сделал весьма спорное заявление, что основной (ну или одной из основных) проблемой проектирования логических схем (в частности для FPGA) являются хреновые компиляторы. Я с этим не согласен, поскольку все, что в принципе могут эти компиляторы --- это применить некоторые преобразования, которые в некоторых случаях приведут к более эффективным схемам (например, с точки зрения максимальной рабочей частоты для синхронных схем). Но гарантий-то никаких нет, что результат работы этих компиляторов оптимален для любого заданного описания на Verilog! Поэтому слишком навороченный компилятор, который производит кучу неочевидных преобразований по своему усмотрению, станет скорее головной болью для его пользователя нежели мощным инструментом. Если в случае программ, как правило, можно допустить, чтобы компилятор в некоторых местах сгенерировал говённый код, поскольку если выполняется этот код редко, то и хрен бы с ним, то в случае синхронной цифровой схемы наличие пары соединений с большой задержкой приведет к тому, что вся схема не будет работать на заданной частоте, а когда разработчик попытается понять, что же надо сделать, его ждет большой сюрприз, поскольку эти медленные соединения вообще не имеют никаких следов в исходном коде из-за глубокой оптимизации. Общая проблема оптимизирущих компиляторов в том, что как правило они находят в коде некоторые шаблонные структуры (набор которых зависит от конкретной версии компилятора) и пытаются их оптимизировать. При этом стоит немного отойти от шаблона и оптимизация не сработает или сработает плохо. Если бы компилятор гарантированно производил оптимальную схему по описанию, то разработчику бы было совершенно насрать на то, что он перехерачивает все что только можно; но поскольку таких гарантий нет, то когда результат работы компилятора не устраивает разработчика, разработчик желает понять где же узкое место и агрессивная оптимизация этому не очень-то помогает.

Это если, например, код после кросс-модульного инлайна. Вперед, накодь оптимально и не по-индусски. Я уж не говорю про динамически сгенеренный код.

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

Напомню, с чего вообще начался весь сыр-бор. Yampp сделал весьма спорное заявление, что основной (ну или одной из основных) проблемой проектирования логических схем (в частности для FPGA) являются хреновые компиляторы. Я с этим не согласен, поскольку все, что в принципе могут эти компиляторы --- это применить некоторые преобразования, которые в некоторых случаях приведут к более эффективным схемам (например, с точки зрения максимальной рабочей частоты для синхронных схем). Но гарантий-то никаких нет, что результат работы этих компиляторов оптимален для любого заданного описания на Verilog! Поэтому слишком навороченный компилятор, который производит кучу неочевидных преобразований по своему усмотрению, станет скорее головной болью для его пользователя нежели мощным инструментом.

Ставим вопрос иначе.

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

ХОРОШИМ я называю компилятор, в котором реализован математический аппарат, на момент создания этого компилятора опубликованный в открытой печати, или его неопубликованный аналог с теми же или лучшими характеристиками.

По аналогиии, ХРЕНОВЫМ я называю неустаревший компилятор, порождаемый которым код заведомо может быть улучшен применением на одной из стадий компиляции опубликованных в открытой печати процедур оптимизации. (То есть не использующий имеющиеся достижения математики.)

Касательно FPGA, компилятор Xilinx ISE по этому определению является хреновым, поскольку качество порождаемого кода значительно улучшается при внедрении в процесс дополнительных утилит qFlow/tFlow, алгоритмы которых опубликованы в ряде диссертаций, а код доступен для скачивания. Компилятор Alterа Quartus, по всей вероятности, не превосходит по качеству компилятор Xilinx.

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

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

Но мы же не говорим о таких идиотских случаях.

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

Шведы молодцы, не то что русские линуксоспециалисты только языками молоть и теоретизировать про хаскель.

Стыдобища - это ваше скольково, а тут студенты не ягу бухают на сачке, а делают вполне конкретную вещь, к тому же открытую.

Напомните мне, где упоминалось про 'скольково', а то запамятовал) Что касается данных шведов - никто не против, если они реальную пользу принесут обществу.

только этот один цикл будет делать N^3 операций, так что сложность не понизится.

Тупой, да? Он будет делать N операций.

Если распрямить три вложенных цикла, каждый по N, то будет N^3 операций. Например, задача сложить все числа в 3х мерной матрице со стороной N. Как не оптимизируй - результат N^3.

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

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

Loop fusion часто приводит к strength reduction. Внутренние циклы могут заменяться атомарными векторными операциями.

Ты видимо не знаешь что такое O(f(N)). Это АСИМПТОТИЧЕСКАЯ сложность, а векторные операции всегда имеют конечный размер.