Почему компиляторы такие глупые? - 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 ]

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

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

x = 0
sleep 6 // Let's assume this is defined somewhere.
print x

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

Код и компилятор, который его обрабатывает, являются инструментами, и вы должны быть кузнецом, если хотите эффективно их использовать. Сколько 12 "бензопил откажется попробовать срубить 30" дерево? Сколько упражнений автоматически переключится в режим удара, если обнаружит бетонную стену?

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

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

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

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

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

107 голосов
/ 06 января 2009

О, я не знаю. Иногда компиляторы довольно умны. Рассмотрим следующую программу на C:

#include <stdio.h>  /* printf() */

int factorial(int n) {
   return n == 0 ? 1 : n * factorial(n - 1);
}

int main() {
   int n = 10;

   printf("factorial(%d) = %d\n", n, factorial(n));

   return 0;
}

В моей версии GCC (4.3.2 при тестировании Debian ), когда компилируется без оптимизации, или -O1, он генерирует код для factorial(), как вы ' Я ожидал, используя рекурсивный вызов для вычисления значения. Но на -O2 он делает что-то интересное: он компилируется в плотный цикл:

    factorial:
   .LFB13:
           testl   %edi, %edi
           movl    $1, %eax
           je  .L3
           .p2align 4,,10
           .p2align 3
   .L4:
           imull   %edi, %eax
           subl    $1, %edi
           jne .L4
   .L3:
           rep
           ret

Довольно впечатляет. Рекурсивный вызов (даже не хвостовой) полностью исключен, поэтому теперь факториал использует пространство стека O (1) вместо O (N). И хотя у меня есть только очень поверхностные знания о сборке x86 (на самом деле AMD64 в данном случае, но я не думаю, что какие-либо расширения AMD64 используются выше), я сомневаюсь, что вы могли бы написать лучшую версию вручную. Но что поразило меня, так это код, сгенерированный на -O3. Реализация факториала осталась прежней. Но main() изменилось:

    main:
   .LFB14:
           subq    $8, %rsp
   .LCFI0:
           movl    $3628800, %edx
           movl    $10, %esi
           movl    $.LC0, %edi
           xorl    %eax, %eax
           call    printf
           xorl    %eax, %eax
           addq    $8, %rsp
           ret

Видите строку movl $3628800, %edx? gcc предварительно вычисляет factorial(10) во время компиляции. Он даже не вызывает factorial(). Невероятный. Моя шляпа перед командой разработчиков GCC.

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

(Адаптировано из публикации в моем блоге .)

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

Говоря с точки зрения C / C ++:

Ваш первый пример будет оптимизирован большинством компиляторов. Если java-компилятор от Sun действительно выполняет этот цикл, то это ошибка компилятора, но, поверьте мне, любой пост-компилятор 1990 C, C ++ или Fortran полностью исключает такой цикл.

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

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

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

Компиляторы имеют прогнозируемую . Это может время от времени выглядеть глупо, но это нормально. Цели автора компилятора:

  • Вы должны иметь возможность просматривать свой код и делать разумные прогнозы относительно его производительности.

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

  • Если небольшое изменение выглядит для программиста так, как будто оно должно повысить производительность, оно по крайней мере не должно ухудшать производительность (если в оборудовании не происходят удивительные вещи).

Все эти критерии препятствуют "магическим" оптимизациям, которые применяются только к угловым случаям.


В обоих ваших примерах переменная обновляется в цикле, но не используется в других местах . Этот случай на самом деле довольно сложен, если вы не используете какую-то платформу, которая может сочетать устранение мертвого кода с другими оптимизациями, такими как копирование или постоянное распространение. Для простого оптимизатора потока данных переменная не выглядит мертвой. Чтобы понять, почему эта проблема сложная, см. Статью Лернера, Гроува и Чамберса в POPL 2002 , в которой используется именно этот пример и объясняется, почему она сложная.

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

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

Это описано в HotSpot FAQ , под вопросом «Я пишу простой цикл для определения времени простой операции, и она медленная. Что я делаю неправильно?».

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

Серьезно? Зачем кому-то писать такой код в реальном мире? ИМХО, код, а не компилятор - это «глупая» сущность здесь. Я, например, совершенно счастлив, что авторы компиляторов не тратят впустую свое время, пытаясь оптимизировать что-то подобное.

Редактировать / Разъяснение: Я знаю, что код в вопросе приведен в качестве примера, но это только подтверждает мою точку зрения: либо вы должны пытаться, либо быть совершенно невежественным, чтобы написать крайне неэффективный код, подобный этому. Задача компилятора - не держать нас за руку, поэтому мы не пишем ужасный код. Как люди, которые пишут код, мы обязаны знать достаточно о наших инструментах, чтобы писать эффективно и четко.

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

Ну, я могу говорить только о C ++, потому что я новичок в Java. В C ++ компиляторы могут свободно игнорировать любые языковые требования, установленные стандартом, при условии, что наблюдаемое поведение равно как если бы компилятор фактически эмулировал все правила, которые помещаются Стандарт. Наблюдаемое поведение определяется как любое чтение и запись в изменчивые данные и вызовы библиотечных функций . Учтите это:

extern int x; // defined elsewhere
for (int i = 0; i < 100 * 1000 * 1000 * 1000; ++i) {
    x += x + x + x + x + x;
}
return x;

Компилятору C ++ разрешено оптимизировать этот фрагмент кода и просто добавить правильное значение x, которое будет получено из этого цикла один раз, потому что код ведет себя как если бы цикл никогда не происходил, и нет изменчивых данных или библиотечных функций, которые могут вызвать побочные эффекты. Теперь рассмотрим изменчивые переменные:

extern volatile int x; // defined elsewhere
for (int i = 0; i < 100 * 1000 * 1000 * 1000; ++i) {
    x += x + x + x + x + x;
}
return x;

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


Говоря о Java, я проверил ваш цикл, и бывает, что GNU Java Compiler (gcj) занимает слишком много времени, чтобы завершить ваш цикл (он просто не завершился, и я его убил). Я включил флаги оптимизации (-O2), и это произошло, сразу же распечатав 0:

[js@HOST2 java]$ gcj --main=Optimize -O2 Optimize.java
[js@HOST2 java]$ ./a.out
0
[js@HOST2 java]$

Может быть, это наблюдение может быть полезным в этой теме? Почему это происходит так быстро для gcj? Ну, одна из причин, безусловно, заключается в том, что gcj компилируется в машинный код, и поэтому у него нет возможности оптимизировать этот код на основе поведения кода во время выполнения. Он собирает все свои сильные стороны вместе и пытается оптимизировать как можно больше во время компиляции. Однако виртуальная машина может скомпилировать код Just in Time, как показано в выходных данных java для этого кода:

class Optimize {
    private static int doIt() {
        int x = 0;
        for (int i = 0; i < 100 * 1000 * 1000 * 1000; ++i) {
            x += x + x + x + x + x;
        }
        return x;
    }
    public static void main(String[] args) {
        for(int i=0;i<5;i++) {
            doIt();
        }
    }
}

Выход для java -XX:+PrintCompilation Optimize:

1       java.lang.String::hashCode (60 bytes)
1%      Optimize::doIt @ 4 (30 bytes)
2       Optimize::doIt (30 bytes)

Как видим, JIT компилирует функцию doIt 2 раза. Основываясь на наблюдении за первым выполнением, он компилирует его во второй раз. Но он имеет один и тот же размер, что и байт-код, два раза, предполагая, что цикл все еще на месте.

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

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

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

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

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

Некоторые оптимизации позаботятся о втором примере, который вы опубликовали, но я думаю, что я видел его больше на функциональных языках, а не на Java. Большая вещь, которая усложняет работу на новых языках, это monkey-patching . Теперь += может иметь побочный эффект , что означает, что если мы его оптимизируем, это потенциально неправильно (например, добавление функции к +=, которая выводит текущее значение, будет означать совсем другую программу).

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

Просто проще потратить лишний момент и убедиться, что вы пишете именно то, что вы действительно хотите, чтобы компьютер делал. :)

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

Компиляторы в целом очень умные.

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

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

Даже если ваш пример прост, все же могут возникнуть сложные ситуации.

Что касается вашего аргумента StringBuilder, это НЕ задание компилятора выбирать, какие структуры данных использовать для вас.

Если вам нужны более мощные оптимизации, перейдите на более строго типизированный язык, такой как fortran или haskell, где компиляторам предоставляется гораздо больше информации для работы.

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

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

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

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

...