Почему компиляторы такие глупые? - PullRequest
39 голосов
/ 02 января 2009

Мне всегда интересно, почему компиляторы не могут понять простые вещи, которые очевидны для человеческого глаза. Они делают много простых оптимизаций, но никогда не являются чем-то даже немного сложным. Например, этот код занимает около 6 секунд на моем компьютере, чтобы напечатать нулевое значение (используя Java 1.6):

int x = 0;
for (int i = 0; i < 100 * 1000 * 1000 * 1000; ++i) {
    x += x + x + x + x + x;
}
System.out.println(x);

Совершенно очевидно, что x никогда не изменяется, поэтому независимо от того, как часто вы добавляете 0 к себе, оно остается равным нулю. Таким образом, теоретически компилятор может заменить это на System.out.println (0).

Или даже лучше, это занимает 23 секунды:

public int slow() {
    String s = "x";
    for (int i = 0; i < 100000; ++i) {
        s += "x";
    }
    return 10;
}

Сначала компилятор мог заметить, что я на самом деле создаю строку s размером 100000 "x", чтобы он мог вместо этого автоматически использовать s StringBuilder или, что еще лучше, напрямую заменить ее полученной строкой, поскольку она всегда одинакова. Во-вторых, он не распознает, что я вообще не использую строку, поэтому весь цикл может быть отброшен!

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

РЕДАКТИРОВАТЬ : Конечно, это глупые примеры, которые никогда не должны нигде использоваться. Но всякий раз, когда мне приходится переписывать красивый и очень читаемый код во что-то нечитаемое, чтобы компилятор был доволен и создавал быстрый код, я удивляюсь, почему компиляторы или какой-то другой автоматизированный инструмент не могут выполнить эту работу за меня.

Ответы [ 28 ]

3 голосов
/ 02 января 2009

Потому что мы просто еще не там. Вы могли бы также легко спросить: «Почему мне все еще нужно писать программы ... почему я не могу просто подать документ с требованиями и заставить компьютер написать приложение для меня?»

Авторы компиляторов тратят время на мелочи, потому что это те вещи, которые программисты приложений упускают.

Кроме того, они не могут предполагать слишком много (возможно, ваш цикл был какой-то временной задержкой гетто или что-то в этом роде)?

2 голосов
/ 02 января 2009

Так как другие адекватно ответили на первую часть вашего вопроса, я постараюсь заняться второй, т. Е. «Вместо этого автоматически использует StringBuilder».

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

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

Наконец, как уже говорили другие (я думаю), автор компилятора / оптимизатора может разумно предположить, что программист, пишущий входной код, не безмозглый. Было бы напрасной тратой времени на то, чтобы выделить особые случаи, подобные этим, когда существует множество других, более общих оптимизаций. Кроме того, как уже упоминали другие, казалось бы, мертвый код может иметь реальную цель (блокировка вращения, ожидание занятости перед выходом на системном уровне и т. Д.), И компилятор должен выполнять то, что просит программист (если это синтаксически и семантически верно).

2 голосов
/ 02 января 2009

Это вечная гонка вооружений между авторами компиляторов и программистами.

Непридуманные примеры прекрасно работают - большинство компиляторов действительно оптимизируют явно бесполезный код.

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

В будущем вам понадобится больше надуманных примеров, чем вы разместили здесь.

1 голос
/ 02 января 2009

Я никогда прежде не видел смысла в устранении мертвого кода. Почему программист написал это ?? Если вы собираетесь что-то делать с мертвым кодом, объявите это ошибкой компилятора! Это почти наверняка означает, что программист допустил ошибку - и в тех немногих случаях это не так, директива компилятора для использования переменной будет правильным ответом. Если я добавлю мертвый код в процедуру, я хочу, чтобы он был выполнен - ​​я, вероятно, планирую проверить результаты в отладчике.

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

1 голос
/ 02 января 2009

Практически считается плохой практикой оптимизировать подобные вещи при компиляции в байт-код JVM. javac от Sun имеет некоторые базовые оптимизации, как и scalac, groovyc и т. Д. Короче говоря, все, что действительно зависит от языка, может быть оптимизировано в компиляторе. Однако такие вещи, которые, очевидно, настолько изобретательны, что не зависят от языка, просто выскользнут из политики.

Причина этого в том, что он позволяет HotSpot иметь гораздо более согласованное представление о байт-коде и его шаблонах. Если компиляторы начинают дурачиться с крайними случаями, это уменьшает способность виртуальной машины оптимизировать общий случай, который может не проявляться во время компиляции. Стив Йегги любит говорить об этом: оптимизация часто проще , когда выполняется во время выполнения умной виртуальной машиной. Он даже заходит так далеко, что утверждает, что HotSpot лишает оптимизацию javac. Хотя я не знаю, правда ли это, меня это не удивит.

Подводя итог: компиляторы, нацеленные на виртуальные машины, имеют совсем другой набор критериев, особенно в области оптимизации и, когда это уместно. Не обвиняйте авторов компиляторов в том, что они оставили работу более способной JVM. Как уже неоднократно указывалось в этом потоке, современные компиляторы, ориентированные на нативную архитектуру (например, семейство gcc), чрезвычайно умны на , производя непристойно быстрый код с помощью некоторых очень умных оптимизаций.

1 голос
/ 02 января 2009

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

Причина глупости компиляторов Java является исторической. Во-первых, исходные реализации Java были основаны на интерпретаторе, и производительность считалась неважной. Во-вторых, многие из исходных тестов Java были проблематичными для оптимизации. Я вспоминаю один тест, который очень похож на ваш второй пример. К сожалению, если компилятор оптимизировал цикл, тест получит исключение «деление на ноль», когда попытается поделить базовое число на истекшее время для вычисления оценки производительности. Поэтому при написании оптимизирующего Java-компилятора вы должны быть очень осторожны, НЕ оптимизируя некоторые вещи, так как тогда люди будут утверждать, что ваш компилятор сломан.

1 голос
/ 02 января 2009

На самом деле Java должна использовать построитель строк во втором примере.

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

Конечно, вы можете придумать тривиальные примеры, но количество тривиальных примеров не ограничено. Вы всегда можете думать о чем-то другом, поэтому нет способа поймать их всех.

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

Но в любом случае, это тонна работы, и это не так уж много тебя дает. Люди тратят много времени, пытаясь выяснить способы предотвращения ошибок в программах, а системы типов, подобные тем, что существуют в Java и Scala, являются попытками предотвратить ошибки, но сейчас никто не использует системы типов, чтобы делать заявления о времени выполнения. Насколько я знаю.

Возможно, вы захотите взглянуть на Хаскеля, который, как мне кажется, обладает самой передовой теорией доказательств, хотя я не уверен в этом. Я сам этого не знаю.

1 голос
/ 02 января 2009

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

1 голос
/ 02 января 2009

Абсолютная оптимизация - неразрешимая проблема, то есть нет машины Тьюринга (и, следовательно, нет компьютерной программы), которая могла бы дать оптимальную версию ЛЮБОЙ данной программы.

Некоторые простые оптимизации могут быть (и фактически) выполнены, но в приведенных вами примерах ...

  1. Чтобы обнаружить, что ваша первая программа всегда печатает ноль, компилятор должен обнаружить, что x остается постоянным, несмотря на все итерации цикла. Как вы можете объяснить (я знаю, это не лучшее слово, но я не могу придумать другое) это компилятору?

  2. Как компилятор может узнать, что StringBuilder является подходящим инструментом для работы без ЛЮБОЙ ссылки на него?

В реальных приложениях, если эффективность критична в части вашего приложения, она должна быть написана на языке низкого уровня, таком как C. (Ха-ха, серьезно, я это написал?)

1 голос
/ 04 июня 2009

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

Второй пример не может быть оптимизирован, поскольку самая медленная часть здесь - это распределение / перераспределение памяти, а оператор + = переопределяется в функцию, выполняющую операции с памятью. Разные реализации строк используют разные стратегии размещения.

Я сам также предпочел бы иметь malloc (100000), чем тысячу malloc (100), когда выполняешь s + = "s"; но сейчас эта вещь выходит за рамки компиляторов и должна быть оптимизирована людьми. Это то, что язык D пытается решить, вводя чистых функций .

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

...