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

[Olej]

В качестве вычислительных я бы остановилась на прямых методах решения СЛАУ - метод Гаусса с выбором главного элемента или метод Гаусса-Жордана, например.

И ещё: какой ещё другой класс задач может использоваться для сравнения?

Алгоритмы сортировки, может быть? Пузырьковая сортировка и метод Гаусса часто используются в обработке числовых данных, всем известны и вроде не являются уж совсем простыми.

1. С сортировкой идея хорошая. Хотя это и не вычислительная задача. Но это и есть ещё один класс задач - обменные задачи в памяти. Степерь сложности (роста) пузырьковой сортировки, как мне помниться, O(n^2), что очень плохо для практики, но может быть недостаточно для получения измеримых времён выполнения. Надо пробовать.

2. С вычислительными задачами вы как-то своим сообщениям меня подтолкнули , сразу возник хороший вариант: вычисление автокорреляционной функции или Фурье преобразование, только не по алгоритму БПФ, быстрому, а "в лоб", там тоже O(n^2).

3. Что касаемо "метод Гаусса с выбором главного элемента или метод Гаусса-Жордана" - то я просто не помню что это. Лет 30-35 назад знал, сейчас забыл за ненадобностью.
Вы ссылочку киньте на какой-пибудь популярный вики?
Думаю, что такой же подобной задачей будет, из той же области, обращение квадратной матрицы (?).

[Виктория]

...
3. Что касаемо "метод Гаусса с выбором главного элемента или метод Гаусса-Жордана" - то я просто не помню что это. Лет 30-35 назад знал, сейчас забыл за ненадобностью.
Вы ссылочку киньте на какой-пибудь популярный вики?
Думаю, что такой же подобной задачей будет, из той же области, обращение квадратной матрицы (?).

Метод Гаусса на Википедии
или На Machinelearning

[Olej]

Есть ещё вопрос:
- скоростные характеристики любого языка и его исполняющей системы будут радикально зависеть от класса решаемых задач ... об этом уже много говорилось;
- предыдущее сравнение - это механизм вызовов функций (с передачей параметров etc. ...), то что там рекурсия - это не столь важно;
- интересно бы такое же параллельное сравнение на других классах задач...
- наприер, на сугубо вычислительных, с вещественной математикой, может что-то из области вычисления математических спец. функций рядами ... но нужно работу большой производительности, что-то из рядов с плохой сходимостью, хорошо бы ещё с зависмостью вычислительной сложности O(n) высокого порядка, где n, скажем, 1/eps, а eps - точность, величина сходимости (1e5, 1e7, 1e9, ...).

Мне эту "задачку", в такой постановке, подкинули редакторы при публикации этих заметок на IBM DeveloperWorks.
Не сам придумал

[Olej]

И ещё: какой ещё другой класс задач может использоваться для сравнения?

Алгоритмы сортировки, может быть? Пузырьковая сортировка

Сделал!

Пока сравнение только 3-х языков, которые меня на сейчас интересуют: C, C++, Go.
И разных компиляторов: GCC + Clang для C, GCCGO + GoLang для Go.

Makefile:

Код: Выделить всё

TASK = sort_c sort_cc sort_cl sort_go sort_gc

all: $(TASK)

%: %.c
        gcc -Wall -O0 $< -o $@
%: %.cc
        g++ -Wall -O0 $< -o $@
%: %.go
        gccgo -Wall $< -g -O0 -o $@

sort_cl: sort_c.c
        clang -O0 $< -o $@

sort_gc: sort_go.go
        go build -o $@ -compiler gc $<

clean:
        rm -f $(TASK)

Выполнение:

Код: Выделить всё

$ time ./sort_c 20000
199990000

real	0m1.500s
user	0m1.494s
sys	0m0.000s

$ time ./sort_cc 20000
199990000

real	0m19.007s
user	0m18.946s
sys	0m0.009s

$ time ./sort_cl 20000
199990000

real	0m1.451s
user	0m1.447s
sys	0m0.001s

$ time ./sort_go 20000
199990000

real	0m2.303s
user	0m2.295s
sys	0m0.006s

$ time ./sort_gc 20000
199990000

real	0m1.141s
user	0m1.140s
sys	0m0.000s

[Olej]

Выполнение:

- То, что C++ отстаёт от остальных участников практически на порядок — это указывает только на нечестность такого сравнения: код на C++ написан с использованием средств STL, шаблонного типа vector<long long> и итераторов, в то время, как все остальные варианты — прямой адресацией элементов массива. Такая реализация в C++ сделана специально, чтобы показать гибкость STL механизмов.

- Удивила компиляция кода C компилятором Clang: результаты лучше, чем у GCC (по крайней мере, без вовлечения оптимизации).

- Язык Go (в варианте GCC) если и уступает C по скорости, то только порядка 50%, при том предоставляя гибкость и выразительную мощность соизмеримую с C++ с использованием STL (см. код).

- Окончательно удивил результат, показанный Go из проекта Clang (родной проект развития Go) — такой код оказался быстрее, чем код C компилированный GCC (базовая связка для проектов Linux)!

[Olej]

Скриптовый язык Tcl

[fibo.tcl]

Код: Выделить всё

proc tcl::mathfunc::fib {n} {
  if { $n < 2 } {
     return 1
} else { 
     return [expr {fib($n-1) + fib($n-2)}]
  }
}
puts [tcl::mathfunc::fib [lindex $argv 0]]

Код: Выделить всё

time nice -9 tclsh fibo.tcl 30
1346269

real    0m2.042s
user    0m2.014s
sys     0m0.016s

Сделал между делом оценивание скорости такого решения.
Средние (из нескольких) показателей:

Код: Выделить всё

[Olej@modules speed]$ time ./fibo.tcl 30
1346269

real	0m0.830s
user	0m0.830s
sys	0m0.000s

Код: Выделить всё

[Olej@modules speed]$ time ./fibo_c 30
1346269

real	0m0.005s
user	0m0.004s
sys	0m0.000s

По сравнению с C компилированной программой это раз в 160 медленнее.

Итого, 18 рассмотренных пока реализации раскладываются по вот таким логарифмическим кластерам:

Код: Выделить всё

Фактор скорости    Язык
1 ... 2           C, GCC C++, Go
2 ... 5           Cobj C++, PureBasic
5 ... 10          Ocaml
10 ... 20         Java
20 ... 50         Lua, Scheme, Haskell
50 ... 100        Python 2, Ruby, JavaScript, Scala 
100 ... 200       Perl, Python 3, PHP
200 ... 500       bash

Т.е. Tcl где-то в одном кластере с Perl, Python 3, PHP.

[Виктория]

- например, на сугубо вычислительных, с вещественной математикой, может что-то из области вычисления математических спец. функций рядами ... но нужно работу большой производительности, что-то из рядов с плохой сходимостью, хорошо бы ещё с зависмостью вычислительной сложности O(n) высокого порядка, где n, скажем, 1/eps, а eps - точность, величина сходимости (1e5, 1e7, 1e9, ...).

Метод бисекции (дихотомии), м.б.? А зачем O(n) высокого порядка? Чтобы оценить возможности распараллеливания?

[Olej]

- например, на сугубо вычислительных, с вещественной математикой, может что-то из области вычисления математических спец. функций рядами ... но нужно работу большой производительности, что-то из рядов с плохой сходимостью, хорошо бы ещё с зависмостью вычислительной сложности O(n) высокого порядка, где n, скажем, 1/eps, а eps - точность, величина сходимости (1e5, 1e7, 1e9, ...).

Метод бисекции (дихотомии), м.б.? А зачем O(n) высокого порядка? Чтобы оценить возможности распараллеливания?

Нет. Всё гораздо прозаичнее :
- у меня есть 3-4-5 компьютеров очень разного возраста и очень разной производительности...
- у тех, кто захочет повторять тесты могут тоже быть компьютеры с производительностью, отличающейся на порядок...
- при фиксированных n у кого-то тест займёт 0.03 сек. (по time ...) и это не корректно для сравнений, потому как вблизи нижнего предела разрешения временной шкалы...
- а у кого-то при этом же n это займёт 1-2 мин. ... и это очень тоскливое занятие.

Вариацией n хорошо бы вывести время прогона в диапазон 10-100 сек.
А для этого общий объём вычислительной работы (на очень разном оборудовании) вариацией n нужно изменять на 3-4 порядка.

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

[Lepton]

Язык программирования Euphoria (для вычисления чисел Фибоначчи)

Код: Выделить всё

$ eui -v
Euphoria Interpreter v4.0.5 
   Linux, Using System Memory
   Revision Date: 2012-10-15, Id: 62d94559f849

[fibo.ex]

Код: Выделить всё

include std/convert.e
sequence i = command_line()

function fib(integer n)
if n<2 then return 1 end if
return fib(n-1)+fib(n-2)
end function

printf(1,"%d\n",fib(to_integer(i[$])))

выполнение

Код: Выделить всё

$ time eui fibo.ex 30
1346269

real    0m1.389s
user    0m1.264s
sys     0m0.120s

тут проблема в "отжирании времени" преобразованием аргумента командной строки (comand_line()/to_integer()), без них выполняется быстрее:
[fibo.ex]

Код: Выделить всё

function fib(integer n)
if n<2 then return 1 end if
return fib(n-1)+fib(n-2)
end function
printf(1,"%d\n",fib(30))

выполнение

Код: Выделить всё

$ time eui fibo.ex
1346269

real    0m1.000s
user    0m0.977s
sys     0m0.020s

Для сравнения

Код: Выделить всё

$ gcc --version
gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2

$ time ./fibo_c 30
1346269

real    0m0.042s
user    0m0.037s
sys     0m0.005s

[Lepton]

Euphoria v4.1.0 (beta)

Код: Выделить всё

$ eui -v
Euphoria Interpreter v4.1.0 development
   64-bit Linux, Using System Memory
   Revision Date: 2014-01-16 02:53:44, Id: 5783:d41527402a7a

Код: Выделить всё

--fibo.ex
include std/convert.e
sequence i = command_line()

function fib(integer n)
if n<2 then return 1 end if
return fib(n-1)+fib(n-2)
end function

printf(1,"%d\n",fib(to_integer(i[$])))
---------------
$ time eui fibo.ex 30
1346269

real    0m0.887s
user    0m0.743s
sys     0m0.141s

Код: Выделить всё

--fibo.ex
function fib(integer n)
if n<2 then return 1 end if
return fib(n-1)+fib(n-2)
end function
printf(1,"%d\n",fib(30))
---------------
$ time eui fibo.ex
1346269

real    0m0.574s
user    0m0.551s
sys     0m0.022s