Производительность стека в языках программирования

Question

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

public class Fib { 
public static int fib(int n) { 
    if (n < 2) return 1; 
    return fib(n-1) + fib(n-2); 
} 

public static void main(String[] args) { 
    System.out.println(fib(Integer.valueOf(args[0]))); 
} 
} 

ИТАК точка в том, что с помощью этого алгоритма с входом 40 я получил эти тайминги:

C: 2.796s 
Ocaml: 2.372s 
Python: 106.407s 
Java: 1.336s 
C#(mono): 2.956s 

Они взяты в поле Ubuntu 10.04, используя версии каждого языка, доступные в официальных репозиториях, на двухъядерном процессоре Intel.

Я знаю, что функциональные языки, такие как ocaml, имеют замедление, которое происходит от обработки функций в качестве граждан первого порядка и не имеют проблем объяснять время работы CPython из-за того, что это единственный интерпретируемый язык в этом тесте, но я был впечатлен по времени java, которое составляет половину c для одного и того же алгоритма! Не могли бы вы приписать это компиляции JIT?

Как вы объясните эти результаты?

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

EDIT 2 : Я обновил среду выполнения ocaml, используя оптимизирующий компилятор ocamlopt. Также я опубликовал стенд на https://github.com/hoheinzollern/fib-test. Не стесняйтесь делать дополнения к нему, если хотите :)

Answer 1

Одна из возможностей заключается в том, что компилятор C оптимизируется на предположение, что первая ветвь (n < 2) является еще более часто используемой. Это нужно делать только во время компиляции: сделать предположение и придерживаться его.

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

Вы может быть в состоянии увидеть разницу путем переворачивания логики if:

public static int fib(int n) { 
if (n >= 2) return fib(n-1) + fib(n-2); 
return 1; 
} 

Это стоит попробовать, так или иначе :)

Как всегда, проверьте настройки оптимизации для всех платформ. Очевидно, что настройки компилятора для C - и на Java, попробуйте использовать клиентскую версию Hotspot и версию сервера. (Обратите внимание, что вам нужно работать более секунды или около того, чтобы действительно получить полную выгоду от Hotspot ... может быть интересно поставить внешний вызов в цикле, чтобы получить прогон минуты или около того.)

Answer 2

Вы говорите, что очень мало о конфигурации (бенчмаркинга, детали все: commandlines, компьютер, используемый, ...)

Когда я пытаюсь воспроизвести для OCaml я получаю:

let rec f n = if n < 2 then 1 else (f (n-1)) + (f (n-2)) 

let() = Format.printf "%d@." (f 40) 


$ ocamlopt fib.ml 
$ time ./a.out 
165580141 

real 0m1.643s 

Это находится на Intel Xeon 5150 (Core 2) на частоте 2,66 ГГц. Если я использую байт-код OCaml-компилятор ocamlc, с другой стороны, я получаю время, подобное вашему результату (11s).Но, конечно, для выполнения сравнения скорости нет причин использовать компилятор байт-кода, если вы не хотите сравнивать скорость самой компиляции (ocamlc поражает скоростью компиляции).

Answer 3

Возможно, вы захотите проверить уровень оптимизации вашего компилятора C. С gcc -O3, что имеет большое значение, падение с 2,015 секунды до 0,766 секунды, что составляет около 62%.

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

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

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

Для чего это необходимо, эти тайминги C были для семи трасс с выбросами, выведенными до усреднения.

---

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

int fib(unsigned int n) { 
    int t, a, b; 
    if (n < 2) return 1; 
    a = b = 1; 
    while (n-- >= 2) { 
     t = a + b; 
     a = b; 
     b = t; 
    } 
    return b; 
} 

дополнительно снижается время, необходимое, от 0,766 до 0,078 секунды секунд, дальнейшее сокращение на 89% и снижение на необычайные 96% от исходного кода.

---

И, как последняя попытка, вы должны попробовать следующее, который сочетает в себе справочную таблицу с расчетами за пределами определенной точки:

static int fib(unsigned int n) { 
    static int lookup[] = { 
     1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 
     610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 
     46368, 75025, 121393, 196418, 317811, 514229, 832040, 
     1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 
     24157817, 39088169, 63245986, 102334155, 165580141 }; 
    int t, a, b; 

    if (n < sizeof(lookup)/sizeof(*lookup)) 
     return lookup[n]; 
    a = lookup[sizeof(lookup)/sizeof(*lookup)-2]; 
    b = lookup[sizeof(lookup)/sizeof(*lookup)-1]; 
    while (n-- >= sizeof(lookup)/sizeof(*lookup)) { 
     t = a + b; 
     a = b; 
     b = t; 
    } 

    return b; 
} 

Это сокращает время еще раз, но я подозреваю, что мы «Здесь мы сталкиваемся с уменьшением прибыли.

Answer 4

Обратите внимание, что если виртуальная точка Java Hotspot достаточно умна для memoise вызовов fib(), она может сократить экспоненциальную стоимость алгоритма примерно до линейной стоимости.

Answer 5

Я могу объяснить производительность Python. Производительность Python для рекурсии в лучшем случае ужасна, и ее следует избегать, как чуму при кодировании в ней. Тем более, что переполнение стека происходит по умолчанию при глубине рекурсии только 1000 ...

Что касается производительности Java, это потрясающе. Редко, что Java бьет C (даже при очень небольшой оптимизации компилятора на стороне C) ... что JIT может делать, это memoization или tail recursion ...

Answer 6

С помощью C вы должны либо объявить функцию фибоначчи " inline "или, используя gcc, добавьте аргумент -finline-functions к параметрам компиляции. Это позволит компилятору выполнять рекурсивную вставку. Это также причина, почему с -O3 вы получаете лучшую производительность, она активирует -finline-functions.

Редактировать Вам необходимо хотя бы указать -O/-O1, чтобы иметь рекурсивную вставку, также если функция объявлена ​​встроенной.На самом деле, тестируя себя, я обнаружил, что объявляя функцию inline и используя -O в качестве флага компиляции или просто используя -O -finline-functions, мой рекурсивный код фибоначчи был быстрее, чем с -O2 или -O2 -finline-functions.

Answer 7

Я написал версию наивной функции Фибоначчи на С и скомпилировал ее на ассемблере в gcc (4.3.2 Linux). Затем я скомпилировал его с помощью gcc-O3.

Неоптимизированная версия была длиной 34 строки и выглядела как прямой перевод кода C.

Оптимизированная версия была длиной 190 строк и (это было трудно сказать, но) она оказалась инлайн по крайней мере, звонки для значений до около 5.

Answer 8

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

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