Производительность языков программирования. Часть 1
В предыдущих частях была проделана реализация совершенно однотипного приложения на нескольких разных языках программирования. Сначала мы рассмотрели реализации на 10-ти самых часто употребляемых языков в разработке реальных проектов, а затем — такие же реализации на языках новых, или более экзотических, или имеющих ограниченные сферы применения. Целью такого сравнения было посмотреть как внешне, не предвзятым взглядом, выглядит однотипный код, когда он записан на разных языках.
Но мы также можем проделать и грубые сравнительные оценки производительности разноязыковых реализаций, чему и посвящены эта и следующая части обзора.
Примечание: Подобные оценки не могут служить критерием качества и даже производительности. Различные по идеологии языки будут иметь совершенно различающуюся относительную производительность на различных классах задач. Поэтому речь может идти только о сравнении порядков производительности и на определённом классе задач.
Примечание: Не ищите какого-то скрытого смысла и подтекста в том порядке, в котором представлены различные языки — они описаны в том произвольном порядке, в котором они хронологически тестировались.
Задача
Для сравнения производительности непригодна задача, демонстрируемая в предыдущей части. Поэтому нам предстоит снова реализовать линейку идентичных приложений на разных языках для такого сравнения. Задачу мы хотим использовать вычислительного сорта, простейшую и в реализации и понимании, которая имела бы очень высокую степень роста от размерности (например экспоненциальную), чтобы можно было в самых широких пределах изменять интегральную потребность в вычислительных операциях.
Для грубых оценок вполне пригодна задача рекурсивного вычисления чисел Фибоначчи. Эта функция настолько проста, что её формулировка будет просто показана в изложении кода на языке C.
Примечание (для дотошной публики) : Существуют 2 определения последовательности чисел Фибоначчи: а). F1=0, F2=1, FN=FN-1+FN-2 и б). F1=1, F2=1, FN=FN-1+FN-2. Как легко видеть, эти последовательности сдвинуты на 1 член, так что не стоит ломать копья по этому поводу: можно использовать любую форму. Мы будем использовать 2-ю.
Существуют эффективные алгоритмы вычисления последовательности чисел Фибоначчи (циклические, слева направо). Мы же сознательно будем использовать неэффективную рекурсивную реализацию (справа налево), именно в той форме, как выражения записаны выше. При таком алгоритме задача как раз удовлетворяет требованию высогой степени роста вычислительной сложности, о которой было сказано ранее.
Подготовка приложений к исполнению очень различается между рассматриваемыми языками: где-то это просто исходный код, который подаётся на вход интерпретатора, в других случаях требуется компиляция в промежуточный байт-код или компиляция в исполняемый машинный код. Все промежуточные фазы подготовки, где они требуются, сведены в один Makefile.
Многие языковые средства предполагают и предоставляют те или иные способы оптимизации выполнения (например, уровень оптимизации, указываемый компилятору). Там, где мне известны способы оптимизации выполнения, будет использоваться максимальный уровень оптимизации.
Запуск команд на хронометраж мы станем делать командами вида:
# time nice -19 <команда_fibo> 30
- команда выполняется от root, чтобы позволить повысить приоритет (nice -9) задачи выше нормального, снизив дисперсию результатов;
-
хронометраж выполняется системной командой
time
(не будем вмешиваться в процесс временных измерений); - параметр (30, порядковый номер числа Фибоначчи) определяет размерность задачи, объём вычислений в зависимости от него нарастает экспоненциально.
По каждой реализации показан один запуск, но на самом деле их делалось достаточно много (серией, до 10 и более), а показанный в тексте — это средний, самый устойчивый вариант (при измерении временных интервалов повторяемость всегда является проблемой). Не используем результаты 1-го запуска в серии, чтобы обеспечить для разных запусков серии идентичные условия кэширования.
Результаты выполнения могут радикально меняться в зависимости от версии используемых инструментальных средств (компилятора, интерпретатора). Поэтому в итогах выполнения будет показываться версия используемого программного обеспечения.
Язык C
Листинг 1. Реализация задачи на языке C (fibo_c.c):
#include <stdio.h> unsigned long fib( int n ) { return n < 2 ? 1 : fib( n - 1 ) + fib( n - 2 ); } int main( int argc, char **argv ) { unsigned num = atoi( argv[ 1 ] ); printf( "%ld\n", fib( num ) ); return 0; }
Выполнение:
$ gcc --version gcc (GCC) 4.8.2 20131212 (Red Hat 4.8.2-7) ... # time nice -19 ./fibo_c 30 1346269 real 0m0.013s user 0m0.010s sys 0m0.002s
Можно предположить, что приложение, компилированное из C кода, будет самым быстрым. Поэтому именно эти цифры мы станем использовать как базовые значения для сравнения.
C++
Реализация будет выглядеть так:
Листинг 2. Реализация на языке C++ (fibo_c.cc):
#include <iostream> #include <stdlib.h> using namespace std; unsigned long fib( int n ) { return n < 2 ? 1 : fib( n - 1 ) + fib( n - 2 ); } int main( int argc, char **argv ) { unsigned num = atoi( argv[ 1 ] ); cout << fib( num ) << endl; return 0; }
Из этого единого кода будет создано 2 приложения — компиляцией GCC и компиляцией Clang:
$ g++ -O3 fibo_cc.cc -o fibo_cc $ clang++ fibo_cc.cc -o fibo_cl
Выполнение приложения, собранного GCC:
# time nice -19 ./fibo_cc 30 1346269 real 0m0.014s user 0m0.012s sys 0m0.002s
Здесь время абсолютно равное случаю реализации C, в пределах статистической погрешности, что и следовало ожидать.
Выполнение приложения, собранного Clang:
$ clang++ --version clang version 3.3 (tags/RELEASE_33/final) Target: i386-redhat-linux-gnu Thread model: posix # time nice -19 ./fibo_cl 30 1346269 real 0m0.035s user 0m0.033s sys 0m0.001s
Здесь всё гораздо хуже! Это в 2.7 раза медленнее, чем для GCC. Но в объяснение этого может быть то, что в команде компиляции Clang вообще не устанавливалась опция оптимизации (-O...).
Java
Листинг 3. Реализация задачи на Java (fibo.java):
public class fibo { public static long fib( int n ) { return n < 2 ? 1 : fib( n - 1 ) + fib( n - 2 ); } public static void main( String[] args ) { int num = new Integer( args[ 0 ] ).intValue(); System.out.println( fib( num ) ); } }
Компиляция приложения выполняется в реализации OpenJDK:
$ java -version java version "1.7.0_51" OpenJDK Runtime Environment (fedora-2.4.5.1.fc20-i386 u51-b31) OpenJDK Server VM (build 24.51-b03, mixed mode) $ javac fibo.java $ ls -l *.class -rw-r--r-- 1 olej olej 594 Фев 15 16:09 fibo.class
Если то же самое проделать с оригинальном Oracle JDK, то временные результаты могут отличаться.
Выполнение:
# time nice -19 java fibo 30 1346269 real 0m0.176s user 0m0.136s sys 0m0.047s
Выполнение JVM байт-кода Java здесь в 13.5 раз медленнее, чем компилированного в машинные команды кода C.
Python
Аналогичный код на Python:
Листинг 4. Реализация на Python (fibo.py):
#!/usr/bin/python # -*- coding: utf-8 -*- import sys def fib( n ) : if n < 2 : return 1 else: return fib( n - 1 ) + fib( n - 2 ) n = int( sys.argv[ 1 ] ) print( "{}".format( fib( int( sys.argv[ 1 ] ) ) ) )
Для этого кода (он написан в совместимом синтаксисе) мы можем также предложить 2 различных способа исполнения:
-
Python версии 2:
$ python --version Python 2.7.5 # time nice -19 python fibo.py 30 1346269 real 0m1.109s user 0m1.100s sys 0m0.005s
-
Python версии 3:
$ python3 --version Python 3.3.2 # time nice -19 python3 fibo.py 30 1346269 real 0m1.838s user 0m1.823s sys 0m0.009s
Первое, что здесь сразу бросается в глаза: Python 2 быстрее Python 3 на 65%. Это достаточно ожидаемо — это естественная плата за существенно расширенный синтаксис. Ряд публикаций показывают даже существенно большую разницу на определённых классах задач, до 2-х или 3-х раз.
А вот в сравнении с нативным компилированным кодом C Python 2 проигрывает до 100 (85) раз! Это тоже соответствует тому, что звучит в публикациях.
Ruby
Листинг 5. Реализация задачи на Ruby (fibo.rb):
#!/usr/bin/ruby # coding: utf-8 def fib( n ) return n < 2 ? 1 : fib( n - 1 ) + fib( n - 2 ) end puts fib( ARGV[ 0 ].to_i )
Выполнение:
$ ruby --version ruby 2.0.0p353 (2013-11-22 revision 43784) [i386-linux] # time nice -19 ruby fibo.rb 30 1346269 real 0m0.566s user 0m0.554s sys 0m0.009s
Здесь время выполнения, на удивление (непонятно почему), почти в 2 раза (1.77) лучше, чем у Python, и медленнее нативного кода C примерно в 43 раза.
Perl
Листинг 6. Реализация задачи на Perl (fibo.pm):
#!/usr/bin/perl sub fib { my $n = shift; $n < 2 ? 1 : fib( $n - 1 ) + fib( $n - 2 ) } $f = fib( $ARGV[ 0 ] ); print "$f\n";
Выполнение:
$ perl --version This is perl 5, version 18, subversion 2 (v5.18.2) built for i386-linux-thread-multi ... # time nice -19 perl fibo.pm 30 1346269 real 0m2.335s user 0m2.329s sys 0m0.002s
Здесь проигрыш нативному коду C составляет свыше 179 раз! Но это достаточно естественно и ожидаемо — Perl не язык для вычислений, и его ниша это текстовая обработка.
JavaScript
Листинг 7. Реализация на JavaScript (файл fibo.js):
#!/usr/bin/js -U var fib = function( n ) { // функциональный литерал return n < 2 ? 1 : fib( n - 1 ) + fib( n - 2 ); } print( fib( arguments[ 0 ] ) )
Выполнение приложения (начиная с уточнения версии):
$ js -v JavaScript-C 1.8.5 2011-03-31 # time nice -19 js fibo.js 30 1346269 real 0m0.689s user 0m0.683s sys 0m0.005s
Этот результат удивил: это почти те же цифры, что и у Ruby, и в 2 раза лучше, чем Python. От нативного кода C здесь отставание в 53 раза.
PHP
Эквивалент задачи, выраженный на языке PHP:
Листинг 8. Реализация PHP (файл fibo.php):
#!/usr/bin/php <?php function fib( $n ) { return $n < 2 ? 1 : fib( $n - 1 ) + fib( $n - 2 ); } echo fib( $argv[ 1 ] ), "\n"; ?>
Выполнение приложения:
$ php --version PHP 5.5.9 (cli) (built: Feb 11 2014 08:25:04) Copyright (c) 1997-2014 The PHP Group Zend Engine v2.5.0, Copyright (c) 1998-2014 Zend Technologies # time nice -19 php fibo.php 30 1346269 real 0m1.307s user 0m1.292s sys 0m0.013s
Это в 108 раз медленнее, чем эквивалентное C приложение.
Lua
Листинг 9. Реализация задачи на языке Lua (файл fibo.lua):
#!/usr/bin/lua fib = function( n ) -- функциональный литерал if( n < 2 ) then return 1 else return fib( n - 1 ) + fib( n - 2 ) end end print( fib( arg[ 1 ] + 0 ) )
Выполнение такого приложения (с проверкой версии Lua):
$ lua Lua 5.2.2 Copyright (C) 1994-2013 Lua.org, PUC-Rio > # time nice -19 lua fibo.lua 30 1346269 real 0m0.629s user 0m0.624s sys 0m0.003s
Это те же результаты, что и у JavaScript и Ruby.
bash
Можно ли организовать подобные вычисления в интерпретаторе bash, учитывая, что функции bash могут возвращать только значения кода завершения в пределах [0...255], т. е. в нашем смысле — не имеющие возвращаемых вычисленных значений? Прежде всего, можно организовать подобные вычисления, если сам скрипт будет рекурсивно вызывать свои копии. Вот только то и всего:
Листинг 10. Реализация задачи в bash (файл fido.sh):
#!/bin/bash if [ "$1" -lt "2" ] then echo "1" else f1=$($0 `expr $1 - 1`) f2=$($0 `expr $1 - 2`) echo `expr $f1 + $f2` fi
Я не рискну вызывать такое решение с аргументом 30 (как остальные варианты) — я просто не дождусь решения... Но выполняется такого скрипт вполне успешно:
$ bash --version GNU bash, version 4.2.37(1)-release (i486-pc-linux-gnu) … # time nice -19 ./fibo.sh 10 89 real 0m1.137s user 0m0.350s sys 0m0.475s # time nice -19 ./fibo.sh 12 233 real 0m2.979s user 0m0.935s sys 0m1.248s # time nice -19 ./fibo.sh 14 610 real 0m7.857s user 0m2.528s sys 0m3.166s
Получается, что скрипт bash вычисляет функцию от 8 столько же, сколько не очень «спешному» Perl требуется для вычисления функции от 29 (это при экспоненциальном то росте!):
# time nice -19 perl fibo.pm 29 832040 real 0m1.464s user 0m1.448s sys 0m0.004s
Практического смысла показанная реализация bash не имеет, но сама такая возможность интересна. Другой возможностью может быть искусственно организованная рекурсия (с очередью, стеком возвратов) при вызове функции внутри скрипта:
Листинг 11. Внутренняя рекурсия в bash (файл fido_f.sh):
#!/bin/bash declare -a res fib () { if [ "$1" -lt 2 ] then res[ $1 ]=1. else. fib `expr $1 - 1` let s=${res[ `expr $1 - 1` ]}+${res[ `expr $1 - 2` ]} res[ $1 ]=$s fi } res[ 0 ]=1 fib $1 echo ${res[ $1 ]}
Здесь уже совсем другие результаты:
# time nice -19 ./fibo_f.sh 30 1346269 real 0m0.157s user 0m0.037s sys 0m0.083s # time nice -19 ./fibo_f.sh 60 2504730781961 real 0m0.337s user 0m0.075s sys 0m0.167s
Для N=60 результат даже превосходит результаты выполнения нативного C кода. Но здесь мы просто наблюдаем результат обмана: при вычислениях сделана «оптимизация» и фактически рекурсивное вычисление выродилось в циклическое, не порождающее 2-х деревьев рекурсивных вызовов.
Ресурсы для скачивания
- этот контент в PDF
- Архив программных кодов (speed.tgz | 6.83KB)
Похожие темы
- А. Гриффитс : GCC. Полное руководство. Platinum Edition, М.: «ДиаСофт», 2004, ISBN 966-7992-33-0, стр. 624
- Java™ Platform, Standard Edition 6 API Specification.
- Учебник Python 3.1.
- Ruby.
- Юкихиро Мацумото : Программирование на языке Ruby. Идеология языка, теория и практика применения.
- Том Кристиансен, Брайан Де Фой, Ларри Уолл, Джон Орвант : Программирование на Perl, 4-е издание, Сп-Б.: «Символ-Плюс», 2013, ISBN: 978-5-93286-214-8, стр. 1048.
- Introduction to the JavaScript shell.
- Руководство по PHP.
- Lua 5.1 Reference Manual.
- Справочное руководство по языку Lua 5.1.
- Lua programming language information and resources.
- Mendel Cooper : Advanced Bash-Scripting Guide — Искусство программирования на языке сценариев командной оболочки, перевод: Андрей Киселев.