Содержание

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

Фото автора
Олег Цилюрик
Опубликовано 17.06.2014

В предыдущих частях была проделана реализация совершенно однотипного приложения на нескольких разных языках программирования. Сначала мы рассмотрели реализации на 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-х деревьев рекурсивных вызовов.

Ресурсы для скачивания

Похожие темы

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Open source
ArticleID=974651
ArticleTitle=Производительность языков программирования. Часть 1
publish-date=06172014