А почему вы в одно сравнение вынесли тесты консольных приложений (c++ и java) и тесты под вэб, которые выполняются на вэб-сервере? По-моему их так сравнивать неуместно.
Как видно по ссылке на оригинал, php и python точно так же тестировались в консоли. Никто не заставляет использовать эти языки только для веба :) Как и никто не запрещает писать cgi на ассемблере. Как и говорил автор, у каждого языка своя ниша.
И еще, тот факт, что long и int в java не одно и тоже, что в c++
100000000 операций с областями памяти в 8 и 4 байта не одно и тоже, что с 4 и 2 байта.
насчет области памяти в 2 байта — это очень вряд ли, отдельные переменные выравниваются по машинному слову
кстати, если уж на то пошло, в питоне вообще разрядность числа ограничена виртуальной памятью
К сожалению, сейчас у меня нет такой возможности. Но, уже после написания статьи, пришла мысль, что действительно стоило бы тестировать бОльший набор языков и по бОльшему числу параметров (кроме циклов взять создание классов, вызовы методов, простых функций, статический, динамический контекст).
Думаю, в скором времени будут другие тесты — самому всё ещё любопытно.
HQ9++ можно слегка доработать (до HQ9++T например), и потом использовать студентами в курсах «написать задание на любом ОО-языке» в виде сдачи иходников программы main.hq9:«T» и её компилятора (а команде Т в рамках языка будет совершенно случайно реализовываться то, что требовалось по заданию)
соррри за бред, была такая идея сделать так в этом семестре, только заломало почему-то :)
Более того, иногда компилятор лучше «знает» как создать более оптимизированный код под конкретную систему/процессор. И хороший asm-код для одной системы может уступать С++ коду на другой. Да и вообще в таких тестах, говоря что тестируют язык, должны понимать что компилятор/транслятор и есть этот самый язык. А в асме компилятор, по большому счету это программист :)
На самом деле асм отрабатывает (на x86) где-то в полтора раза быстрее чем неоптимизированный C++ код и медленнее, чем оптимизированный (всё-таки gcc не зря флажки разные имеет :) )
а почему оптимизация использовалась только для c++, а не для всех? я не говорю о том, что какой то язык при оптимизации может обогнать другой. просто было бы очень интересно на это глянуть.
Просто потому, что я знал, как включить её в компляторе (gcc). Но референсной была выбрана версия без оптимизации.
Кстати, не подскажете, как её включить для python/java (пока не силён в опциях)?
Про Python:
Замените range() на xrange(),
Для некоторой оптимизации можно запускать файл, как `python -O ./Test01.py` (в ключе буква, а не цифра),
либо использовать сторонние библиотеки типа psyco.
Замена range на xrange не всегда даёт прирост производительности, кстати. Иногда бывает быстрее просто породить весь список целиком, чем «генератором» «генерить» :)
Попробовал сейчас range и xrange, после первого прогона разница около 20 секунд.
Даже учитывая то, что кроме python'a на компьютере выполняется куча других программ, разница достаточная.
Для Java нужно как минимум запускать ява-машину с ключом -server (то есть в режиме для сервера). В нем больше ресурсов затрачивается на JIT-компиляцию при первоначальном запуске.
Еще на самом деле стоит удлинить время выполнения теста, чтоб время JIT-компиляции меньше влияло на результат.
Про Python зная, что JIT есть в PyPy и psyco.
Про Ruby знаю, что JIT есть в JRuby, Rubinius (типа PyPy), MacRuby, IronRuby, Ruby.NET. В случае JRuby это JVM JIT, в случае IronRuby и Ruby.NET — CLR JIT.
Нет, для надёжности запускал по 5 раз. С «nice -n -9», дабы никто не мешал. На большее не хватило терпения. Когда убедился, что числа более-менее постоянны, брал наиболее близкий к среднему результат.
Надо брать минимум, потому что никакие посторонние процессы не могут заставить процесс выполняться быстрее, чем он может, только медленнее :). Об этом писал Крис Касперски
почему в коде на Java делается операция вывода на экран, а после этого только замеряется время
System.out.println(«answer: » + r);
System.out.println(«run time (millis): » + (System.currentTimeMillis() — start));
да! у меня разница в 0.2 сек, а если расчет делать как делается для C++ то получается разница в секунду. это на C2D 1.86, т.е. у автора она будет еще больше.
Версия явы:
java version «1.6.0_14»
Java(TM) SE Runtime Environment (build 1.6.0_14-b08)
Java HotSpot(TM) 64-Bit Server VM (build 14.0-b16, mixed mode)
Может стоит попробовать запустить яву с ключом -server?
"-server" прироста не даёт, как дома, так и на машине, что комментом выше. Поэтому сразу без него и пускал. Пока что не знаю почему.
Кажется, я понял, почему у меня так тормозит: 32-х битная версия. Сейчас попробую найти среди контактов кого-нибудь с 64-х битной и потестить
На самом деле запускать надо только с ключем -server. в 1.6 java на сколько я знаю по умолчанию запускается с ключем -server.
Разница в том, что в клиенской части, выделяется минимальная память, и минильный кэш, и по мере необходимости ресурсы добавляются, что весьма тормозит выполнение кода. В серверной части такого нету.
P.S. правильней все-таки считать время выполнение не по запуску приложения, а внутри приложения(потому что язык java все-таки язык интерпретатор). к примеру:
(количество итераций можно задавать через параметр при запуске)
package com;
public class Test01 {
public static void main(String[] args) {
final int countIteration;
long totalWorkingTime = 0;
if (args != null && args.length > 0) {
countIteration = Integer.parseInt(args[0]);
} else {
countIteration = 10;
}
for (int k = 0; k < countIteration; k++) {
final long start = System.currentTimeMillis();
int r = 0;
for (int i = 0; i < 10000; i++) {
for (int j = 0; j < 10000; j++) {
r = (r + (i * j) % 100) % 47;
}
}
final long iterationTime = System.currentTimeMillis() — start;
totalWorkingTime += iterationTime;
System.out.println(«time:» + iterationTime + "\nanswer: " + r);
}
System.out.println(«Total average time: » + (totalWorkingTime / countIteration));
}
}
Не вижу не одной причины, по какой psyco не ускорит этот код раз в 10 в любом окружении. Как раз для него задачка)
def test():
r = 0
rng = range(0, 10000)
for i in rng:
for j in rng:
r = (r + (i * j) % 100) % 47
print("answer: ", r)
if __name__ == '__main__':
import psyco
psyco.bind(test)
test()
Видимо, так. Могу только предположить, что при работе psyco.full() psyco требуется получить код, который компилировать, для этого он ставит хук на вызовы функций и при обращении компилирует их по возможности.
там заброшенная и неподдерживаемая черная магия)
Силы автора направлены на PyPy, интерпретатор питона с JIT, реализованный на питоне (вот тут все делается средствами языка), который должен все ускорить до небывалых высот.
Как сказал мой очень хороший друг — сравнивать так данные языки на равных несерьезно, т.к. одно написаны на другом.
Заодно он подкинул мне ссылку на более подробное сравнение языков, которой я бы, в свою очередь, хотел поделиться с Вами — http://shootout.alioth.debian.org/
О друге скажу следующее — человек очень серьезно занимается программированием. В данный момент работает над своей операционной системой и языком программирования. Не планирует сделать, а уже написал рабочие прототипы, которые развивает дальше.
А в чём проблема такого сравнения? Сейчас границы «специфичности» слегка стираются, и каждый из приведённых языков вполне прокатывает в качестве языка «общего назначения». Стало быть, двойной цикл + вычисление математического выражения не выглядит ни для одного из языков совсем уж чужеродным.
Ну да, я понимаю, что на одних пишут веб-скрипты, на других игры, на третьих апплеты и т.д. Тут понятно, на С++ апплет не напишешь. Но если язык используется именно как general purpose language, почему бы не устроить простой тест производительности?
Если быть уж совсем честным — а какой Вы результат ожидаете от такого сравнения? Что он сподвигнет изучать тот или иной язык? У каждого языка, все-таки, своя специфика применения. Опять же, в большинстве своем интерпретируемый язык будет уступать. Опять же, какая модель вычисления используемся, какова реализация? Большинство интерпретируемых языков используют стековую ВМ, которая по производительности почти на порядок уступает регистровой.
Да, мне было интересно увидеть эти цифры, но это всё настолько относительно…
Да мне многого и не надо — предположим, ко мне приходит приятель и говорит: я запрограммировал расчёт такой-то математической модели, она у меня работает на языке Х и считает примерно сутки задачу среднего размера.
Тогда я смогу сказать что-то вроде: перейдя на язык Y, ты смог бы посчитать задачу среднего размера за 10 часов. Вот и всё.
Тут я — согласен. Все равно, не стоит забывать, что изучение языка — дело ни одной минуты. У каждого языка есть свои особенности, тонкости и «узкие» места.
По вашей ссылке профессионалы в своих языках оптимизируют алгоритмы от и до, стараясь выжать по максимуму. Автор же этой заметки вообще в питоне не в зуб ногой, чего вы хотели?: )
; Evaluation took:
; 10.62 seconds of real time
; 10.296644 seconds of user run time
; 0.032002 seconds of system run time
; 20,399,873,134 CPU cycles
; 0 page faults and
; 0 bytes consed.
;
39
loop1 :: Int -> Int -> Int
loop1 0 x = x
loop1 n x = loop1 (n-1) (loop2 10000 x n)
loop2 :: Int -> Int -> Int -> Int
loop2 0 r _ = r
loop2 j r i = loop2 (j-1) ((r + ( (i * j) `rem` 100)) `rem` 47) i
Да тут совсем не хаскелльный код, уж очень императивный. Даже смотриться уродливо (автор ни при чем). Имхо, тут как раз можно попробовать реализовать нормальными средствами, не переписывая алгоритм один-в-один — уж слишком хаскеллю это не идёт.
1) Скорее наоборот. С С++ мегаофигены пока не надо следить за памятью. Иначе рискуешь воткнуться в sigsegv.
2) ocaml и erlang очень разные языки, «окамли и эрланги» — непоятно по какому признаку вы их обьединили. По наличию gc? так в python и java он тоже есть. По «функциональности» языка? так ocaml позволяет писать не функционально и приведенный пример как раз написан императивно… Поясните пожалуйста вашу мысль.
Valgrind хорош, спору нет, но он не панацея. Нужно иметь полный code coverage при тестировании, чтобы его вывод имел смысл. Если ваши тесты не покрывают всего кода, (там к примеру обработки ошибок или редко встречающиеся условия), то valgrind будет просто не в курсе о том, что там может быть что-то с памятью.
То есть, как писал Дейкстра " Тестирование может доказать наличие ошибок, но никогда не докажет их отсутствие". Поэтому образно говоря в языках с встроенным управлением памяти надо постараться, чтобы слохопотать NullPointer, а в C надо очень стараться чтобы не схлопотать.
В Питоне надо вставить весь код в функцию. В вашем варианте переменные записываются в массив globals(), что сильно влияет на результат. После таких изменений, код начал работать более, чем в полтора раза быстрее. Ну и range надо заменить на xrange, который и следует использовать в таких циклах. С Psyco, как описано выше в комментах, код будет работать еще быстрее.
def main():
r = 0
for i in xrange(0, 10000):
for j in xrange(0, 10000):
r = (r + (i * j) % 100) % 47
print("answer: ", r)
main()
Немного оффтоп: для измерения времени выполнения лучше использовать System.Diagnostics.Stopwatch, т.к. DateTime.Now берется из установок ОС, а Stopwatch замеряет время выполнения конкретного потока.
Хотя не думаю, что в данном случае это сильно повлияло на результат.
clock()
r = 0.0
i = 0.0
while i < 10000.0:
j = 0.0
while j < 1000.0: # !!!
r = (r + (i * j) % 100.0) % 47.0
j += 1.0
i += 1.0
print("answer: ", r, clock())
exit()
Выдаёт 10.19, ну а с j<10000 в 10 раз больше)
Если использовать int вместо float результат ухудшается примерно на 14%.
Дело в том, что в Python целые числа хранятся специальным образом, позволяя производит вычисления с оооочень большими значениями (a = 1024**1024)
Другими словами, Ваш первый вариант при переходе с R12 на R13 ускорился почти на треть — с 28 сек до 19 сек. Однако…
А рекзультаты на функциях улучшились чуть-чуть с 7.7 и 8.1 до 7.1 и 8.0 сек…
Посмотрел, почему run2 получился немного медленнее чем run (хотя по смыслу это вроде то же самое).
После дизассемблирования beam файла оказалось, что loop1 и loop2 адресуются статически, типа
{move,{integer,10000},{x,0}}.
{move,{x,2},{y,0}}.
{call,3,{test,loop2,3}}. < == Вот оно
{gc_bif,'-',{f,0},1,[{y,0},{integer,1}],{x,2}}.
{move,{x,0},{x,1}}.
{move,{x,2},{x,0}}.
{call_last,2,{test,loop1,2},1}.
А в dotimes вызывается преданная ей функция, которая в свою очередь создает переменную-функцию.
Типа в dotimes:
{function,dotimes,3,14}.
{label,13}.
{func_info,{atom,test},{atom,dotimes},3}.
{label,14}.
{test,is_eq_exact,{f,15},[{x,0},{integer,0}]}.
{move,{x,2},{x,0}}.
return.
{label,15}.
{allocate_zero,2,3}.
{gc_bif,'-',{f,0},3,[{x,0},{integer,1}],{y,1}}.
{move,{x,2},{x,4}}.
{move,{x,1},{x,2}}.
{move,{x,4},{x,1}}.
{move,{x,2},{y,0}}.
{call_fun,2}. < == Вот вызов
{move,{y,0},{x,1}}.
{move,{x,0},{x,2}}.
{move,{y,1},{x,0}}.
{call_last,3,{test,dotimes,3},2}.
$r = 0;
for my $i (0..9999) {
for my $j (0..9999) {
$r = ($r + ($i * $j) % 100) % 47;
}
}
print "answer: $r\n";
На языке Perl скорость увеличивается на 30%, предлагаю поправить скрипт для чистоты экперимента.
Также непонятно почему выбрана не самая последняя версия Perl 5.10.0
У меня скрипт выполнялся 27 секунд
Действительно. Почему на Python автор вынес инициализацию данных в range, а на Perl — нет? В таком случае на каждой итерации не происходит проверки условия.
У меня perl5.10.0 выполнял скрипт в среднем 60 секунд из 5 запусков. Машина:
$ uname -a; grep -i mhz /proc/cpuinfo
Linux desktop 2.6.27.19-3.2-default #1 SMP 2009-02-25 15:40:44 +0100 i686 i686 i386 GNU/Linux
cpu MHz : 3215.441
cpu MHz : 3215.441
Дополню, если добавить вначало прагму use integer (чтобы все вычисления были целочисленными), результат становится — 22 секунды
Кстати, по поводу руби-скрипта который выполнялся 30 сек а не 200, подозреваю что у человека просто мощный процессор, у меня вот например — core 2 duo 6850, там что на тестовой конфигурации автора топика думаю будет раза в 2-3 дольше выполнятся
В каком месте «хак»?
Так и должна выглядеть программа на языке Perl,
правда тут с Benchmark'ом, т.е. программа сама замеряет сколько времени этот код выполняется,
ну от него легко избавиться.
Просто в тестировании языков программирования без использования их особенностей ключевых я не вижу смысла.
Опять же — psycho для питона — хак, а тут — pure Perl, никаких библиотек внешних даже нету… используется только стандартная прагма
Для python и perl описал под диаграммой возможности дополнительного ускорения.
Но, чёрт возьми, ведь в самом начале хотелось без «заточки кода» под каждый конкретный язык, сравнение просто общих операций :)
ps: а можно ли при использовании «use integer» пользоваться вычислениями с плавающей точкой? или более точно определять типы переменных?
Типов переменных как таковых в перле нет. Эта прагма отключает вычисления с плавающей точкой в текущем блоке кода, соответственно все вычисления происходят быстрее.
Прагмы в Perl действуют в пределах блока кода где они объявлены, в любой момент их можно отменить (no integer, например).
В частности эта — документирована (то есть присутствует в официальной документации) и является фичей языка (коих там много =) ), целью которой является ускорение частей когда где используется ТОЛЬКО целочисленная арифметика.
Не настолько хорошо знаком с внутренностями интерпретатора, но могу сделать предположение: следить за локальными переменными «проще», чем за глобальными. Как и в случае с Python.
Судя по всему, здесь играет роль либо версия (у меня 1.8 — то, что извлеклось из портов gentoo), либо разрядность процессора (у меня всё ещё 32-битная машинка, в отличие от большинства приводящих результаты здесь, увы мне)
О, за ссылку спасибо, обязательно прочитаю (только вот у меня очередь на прочтение уже который год всё растёт и растёт, но сейчас она — PriorityQueue :) ).
А по сравнению — ведь в споре рождается истина. Я не претендовал на «нахождение самого лучшего языка», я просто решил замерить кто и как справится с брутфорс-задачей. В процессе общения с читателями код (в скриптовых языках) претерпел некоторые изменения, производительность выросла. Вариант на Java тоже ускорился, в 5 раз относительно начального варианта.
Интересно, занимательно, даже, как мне кажется, «общеобразовательно полезно» :)
Я вас от всей души поздравляю, вы протестировали производительность арифметических выражений. Да ещё и на достаточно некачественных примерах кода. Не думаю, что это что-нибудь отражает в реальности.
P.S. shootout.alioth.debian.org
задачи на арифметические выражения — вполне реальный класс задач. Навскидку — любая статобработка. Навскидку — raytracing… Автор вполне ясно объяснил свои намерения в статье, поэтому я считаю ваш упрёк не состоятелен.
PS про shootout уже несколько раз писали в обсуждении.
Скажите, вы будете делать raytracing на PHP? Я — нет. Если бы статья была озаглавлена «производительность математики в реализациях разных ЯП», я был бы согласен с автором. А так — это просто фигня на постном масле, непонятно для кого и непонятно что выражающая. Даже несмотря на пояснение в тексте статьи. Типа да, круто, C++ быстрее сделает рейтрейсинг, чем Python, ну и в чём смысл всего этого?
пузомерки (benchmarks) дают возможность представлять не только «кто шустрее», но «насколько шустрее».
К примеру у вас есть питоновская программа, которая реализует какую-то логику. Надо добавить числодробительный модуль. Можно написать на питоне, можно сделать вставку на C. Имеет смысл возиться с С? не имея представления какой может быть выигрыш — не ответишь.
Очень неприятно читать такое нытьё, выше писали подобные комменты в стиле «я негодую» уже несколько человек и автор уже несколько раз отвечал. Может хватит?
Незадолго перед тестом (может с неделю тому) я видел человека, всерьёз разрабатывающего OCR на PHP. Примеров неэффективного применения языков как средств разработки можно найти достаточно, и некоторые из них сделаны не для забавы, увы
PHP кстати прогрессирует.
У меня под Windows версия 5.2.6 выполняла код 32 секунды, версия 5.2.10 — 28 секунд, 5.3.0 — 24 секунды.
Правда 5.2.6 и 5.2.10 были скомпилированы VC6, а 5.3.0 — VC9, может еще и этим разница объясняется.
Я смотрю тут перловики со стажем :)
C-style тут не при чем, сейчас докажу :) Он конечно медленнее range, но не трагически.
Этот кусок перлкода можно ускорить раза в полтора, тупо объявив все переменные локальными.
Не забывайте use strict; Он конечно жрет часть памяти и производительности, но это стоит того, эти потери много меньше, чем от пропущенного my ;)
Ну и использование контексных переменный чуть-чуть ускоряет.
Про use integer уже сказали, его можно применять контекстно. Да и хак это такой же, как на Java вместо float использовать int ;)
#~ use strict;
use Benchmark;
Benchmark::timethese(1_000, {
'A' => sub {
#~ use integer;
$r = 0;
for ($i = 0; $i < 100; $i++) {
for ($j = 0; $j < 100; $j++) {
$r = ($r + ($i * $j) % 100) % 47;
}
}
},
'B' => sub {
#~ use integer;
my $r = 0;
for (my $i = 0; $i < 100; $i++) {
for (my $j = 0; $j < 100; $j++) {
$r = ($r + ($i * $j) % 100) % 47;
}
}
},
'C' => sub {
#~ use integer;
my $r = 0;
for my $i (0..99) {
for my $j (0..99) {
$r = ($r + ($i * $j) % 100) % 47;
}
}
},
'D' => sub {
#~ use integer;
my $r = 0;
for my $i (0..99) {
$r = ($r + ($i * $_) % 100) % 47 for 0..99;
}
},
});
Автор — молодец, что затронул такую тему. То есть, взялся честно изучить различные инструменты. Тема большая, очень важная, и я надеюсь, что автор напишет по ней ещё как минимум одну заметку.
Что касается сути, то я бы хотел сказать следующее. Тест, выбранный автором, представляет собой два вложенных цикла с постоянными границами. Такие вещи уже давно оптимизируются компиляторами вдоль и поперёк — и в данном случе это не очень хорошо, потому что реальный функционал кода на разных языках на выходе из оптимизатора получается очень разный. Это первое.
Второе. Этот алгоритм, если хотите, «частный случай», который совсем нечасто возникает в реальной жизни.
Что же мы используем в реальных программах и как сделать тест ближе к практике? Прежде всего, границы цикла должны быть вычисляемыми (неконстантными) переменными (границы объекта-контейнера). Во-вторых, внутри цикла должно идти не просто вычисление (математика), но и работа с разными переменными. В идеале, тест должен проводиться на контейнерах (!). Потому что реальная производительность в реальных программах характеризуется связкой язык+контейнеры. Скорее всего, имеет смысл даже сделать два теста — с контейнерами и без.
Автору спасибо большое. Если будет продолжение буду очень рад.
А теперь несколько комментариев-вопросов:
1) Какая jre использовалась? SunJDK, OpenJDK, java от IBM и т.д. Тоже самое касается и С++ компилера. Подозреваю что это gcc 4.х, но всё же. Ещё нужно бы Intel CC протестировать, поговаривают, что он математику хорошо умеет оптимизировать.
Да, и почему нет теста с -O3? (или может я просто всё это не заметил это в тексте)
2) Предлагаю в будущем протестировать ещё код, который активно занимается выделением и очисткой памяти в куче. Думаю, так будет интереснее =)
Версии софта были (по ссылке на старую версию статьи).
gcc с флагом -O3 и даже -O99 относительно -O2 прироста не дал. Дополнительное -funroll-loops дало около 5% к -O2, что не так весомо.
На самом деле сейчас хочу собрать всё что разбросано по комментариям и агрегировать. А потом, да, можно будет попробовать работу с массивами, списками, строками, вызовами функций, созданием классов и много ещё с чем попробовать :)
Я провёл параллель на моё железо через производительность теста на питоне в той же версии. Так как языки скриптовые, должно было дать относительно верный результат
Там при m>3 начинаются проблемы со стеком, придётся придумывать алгоритм, а во время рабочего дня думать на посторонние темы — ой :)
Но на m=3 вполне можно считать до N=13:
Результаты при многократных запусках достаточно стабильные:
$ javac Test01.java && time java -Xss8m Test01
real 0m39.349s
user 0m37.870s
sys 0m0.104s
$ javac Test01.java && time java -Xss8m -server Test01
real 0m19.630s
user 0m18.705s
sys 0m0.068s
$ g++ Test01.cpp -o Test01 && time ./Test01
real 1m0.333s
user 0m57.472s
sys 0m0.104s
$ g++ Test01.cpp -O2 -o Test01 && time ./Test01
real 0m26.549s
user 0m25.246s
sys 0m0.048s
Машинка (на работе):
$ cat /proc/cpuinfo |fgrep 'model name'
model name: Intel® Pentium® 4 CPU 3.20GHz
model name: Intel® Pentium® 4 CPU 3.20GHz
#include <iostream>
using namespace std;
int main(void) {
long r = 0;
for (unsigned int i = 0; i < 10000; ++i) {
for (unsigned int j = 0; j < 10000; ++j) {
r = (r + (i * j) % 100);
}
}
r %= 47;
cout << "answer: " << r << endl;
}
0.21 сек против 0.67 сек эталонного варианта за счет банальной эрудиции
Однако, на моём unsigned увеличивает время работы в полтора(!) раза. Проверил по 5 запусков.
На рабочем компе unsigned ускоряет исполнение почти в полтора раза (1.3).
Похоже, что у меня неправильный ноут, неправильный линукс и неправильный gcc.
Коплю на новое железо, похоже, пора
За счет вашей «банальной эрудиции» изменился ответ :) Происходит переполнение long'а.
А вообще не вижу смысла в оптимизации самого алгоритма — это же только синтетический тест. Если бы надо было оптимизировать этот кусок кода, то можно просто написать:
Чудо-оптимизация «long r = 39» отличается тем, что от входных параметров(10000, 10000, 100, 47) ответ уже не зависит.
В 8-байтный long число 4740000000 помещается. Если хотите придираться к переполнению, то есть машины, где произведение 10000*10000 будет не входить в 2-байтовый int.
Я имел в виду, что оптимизация этого кода без привязки к конкретной задаче не имеет смысла.
А вообще я с вами согласен — алгоритмическая оптимизация рулит :) Но надо при этом быть осторожным, чтобы не изменился результат.
10000, 10000, 100, 47 — это не входные параметры. Это константы в программе. Поэтому строго говоря оптимизатор имеет полное право сделать сверку выражений и достаточно умный оптимизатор в итоге будет иметь просто число 39.
DisableDebugger
r.i = 0
t=ElapsedMilliseconds()
For i = 0 To 10000
For j = 0 To 10000
r = (r + (i * j) % 100) % 47
Next j
Next i
e=ElapsedMilliseconds()-t
MessageRequester("", StrF(e/1000, 3)+" секунд")
Проверял на компе с процессором близким к «P4-1.8Ггц», т. е. как и автора статьи.
Тест был выполнен за 3 секунды.
100000000 операций с областями памяти в 8 и 4 байта не одно и тоже, что с 4 и 2 байта.
кстати, если уж на то пошло, в питоне вообще разрядность числа ограничена виртуальной памятью
Думаю, в скором времени будут другие тесты — самому всё ещё любопытно.
соррри за бред, была такая идея сделать так в этом семестре, только заломало почему-то :)
# %ecx = r = 0
xorl %ecx, %ecx
movl $10000, %eax
_loop1:
movl $10000, %ebx
_loop2:
# сохранили
pushl %ebx
pushl %eax
# eax = i * j
decl %eax
decl %ebx
mull %ebx
# edx = eax % 100
xorl %edx, %edx
movl $100, %ebx
divl %ebx
# ecx = ecx® + edx
addl %edx, %ecx
# ecx = ecx % 47
movl %ecx, %eax
xorl %edx, %edx
movl $47, %ebx
divl %ebx
movl %edx, %ecx
# восстановили регистры
popl %eax
popl %ebx
decl %ebx
jnz _loop2
decl %eax
jnz _loop1
# здесь в %ecx имеем результат
общий вид здесь: dchekmarev.ru/blog/article/1249836445
Кстати, не подскажете, как её включить для python/java (пока не силён в опциях)?
Замените range() на xrange(),
Для некоторой оптимизации можно запускать файл, как `python -O ./Test01.py` (в ключе буква, а не цифра),
либо использовать сторонние библиотеки типа psyco.
Даже учитывая то, что кроме python'a на компьютере выполняется куча других программ, разница достаточная.
Использовать range имеет смысл обычно для небольших диапазонов.
range — создает список в памяти.
xrange — возвращает обьект-итератор.
Использование xrange приводит к экономии памяти.
Кроме того, тест выполнялся на python3, где xrange вообще отсутвует, его функции перебрал на себя просто range.
без psyco 36.94 сек
c psyco.full() 4.38 сек
с заменой range на xrange
без psyco 35.44 сек
c psyco.full() 4.55 сек
Еще на самом деле стоит удлинить время выполнения теста, чтоб время JIT-компиляции меньше влияло на результат.
Python 2.4.3
в python его роль, когда нужно, выполняет psyco
Про Python зная, что JIT есть в PyPy и psyco.
Про Ruby знаю, что JIT есть в JRuby, Rubinius (типа PyPy), MacRuby, IronRuby, Ruby.NET. В случае JRuby это JVM JIT, в случае IronRuby и Ruby.NET — CLR JIT.
System.out.println(«answer: » + r);
System.out.println(«run time (millis): » + (System.currentTimeMillis() — start));
c++ без оптимизации:
answer: 39
real 0m0.872s
user 0m0.840s
sys 0m0.008s
С оптимизацией -О2
answer: 39
real 0m2.682s
user 0m2.672s
sys 0m0.000s
mono:
answer: 39
run time (millis): 3731.452
java:
#time java ru.dchekmarev.test.performance.Test01
answer: 39
run time (millis): 877
real 0m0.992s
user 0m0.932s
sys 0m0.012s
Так-что никакиь 16 секунд нет ;)
Попробовал на одном из серверов:
$ cat /proc/cpuinfo |fgrep 'model name'
model name: Dual-Core AMD Opteron(tm) Processor 2218
model name: Dual-Core AMD Opteron(tm) Processor 2218
model name: Dual-Core AMD Opteron(tm) Processor 2218
model name: Dual-Core AMD Opteron(tm) Processor 2218
# time nice -n -9 java ru.dchekmarev.test.performance.Test01
answer: 39
run time (millis): 4653
real 0m6.540s
user 0m4.697s
sys 0m0.017s
java version «1.6.0_14»
Java(TM) SE Runtime Environment (build 1.6.0_14-b08)
Java HotSpot(TM) 64-Bit Server VM (build 14.0-b16, mixed mode)
Может стоит попробовать запустить яву с ключом -server?
Кажется, я понял, почему у меня так тормозит: 32-х битная версия. Сейчас попробую найти среди контактов кого-нибудь с 64-х битной и потестить
Разница в том, что в клиенской части, выделяется минимальная память, и минильный кэш, и по мере необходимости ресурсы добавляются, что весьма тормозит выполнение кода. В серверной части такого нету.
P.S. правильней все-таки считать время выполнение не по запуску приложения, а внутри приложения(потому что язык java все-таки язык интерпретатор). к примеру:
(количество итераций можно задавать через параметр при запуске)
package com;
public class Test01 {
public static void main(String[] args) {
final int countIteration;
long totalWorkingTime = 0;
if (args != null && args.length > 0) {
countIteration = Integer.parseInt(args[0]);
} else {
countIteration = 10;
}
for (int k = 0; k < countIteration; k++) {
final long start = System.currentTimeMillis();
int r = 0;
for (int i = 0; i < 10000; i++) {
for (int j = 0; j < 10000; j++) {
r = (r + (i * j) % 100) % 47;
}
}
final long iterationTime = System.currentTimeMillis() — start;
totalWorkingTime += iterationTime;
System.out.println(«time:» + iterationTime + "\nanswer: " + r);
}
System.out.println(«Total average time: » + (totalWorkingTime / countIteration));
}
}
r = 0
i1 = range(0, 10000)
зачем 10000 раз генерить второй список (range)?
Время выполнения упало с 1.82 с при вашем варианте к 1.16 с при моём.
без него:
real 0m37.201s
user 0m36.144s
sys 0m0.142s
с psyco:
real 0m3.104s
user 0m2.895s
sys 0m0.036s
Ускорение в 12+ раз. Если проецировать на результаты питона из статьи, с psyco должно быть быстрее, чем java, и немного недотягивать до c++.
Я-то тупо psyco.full() запускал, как quickstart guide написано :).
psyco.sourceforge.net/psycoguide/unsupported.html
Силы автора направлены на PyPy, интерпретатор питона с JIT, реализованный на питоне (вот тут все делается средствами языка), который должен все ускорить до небывалых высот.
Python 3 почему то главный тормоз:
Unladen Swallow:
Psyco:
Жалко, что пока unladen не так крут.
А как насчет вывода на консоль? Все-таки операция я потоками (streams)…
-server
-agressiveots
и тд
Язык: jscript.
Процессор: Intel Core 2 Quad CPU Q6600 2.40GHz.
Память: DDR3 4096 MBytes.
Проходов: 50.
Среднее время: 33634 мс.
Разброс: 33531 мс — 33703 мс.
P.S.: Накладные расходы на каждый тест в сумме менее 0.1 мс, точнее не получается.
Вот результат для Javascript, Google v8.
1 var r = 0;
2 for(var i=0; i<10000; i++) {
3 for(var j=0; j<10000; j++) {
4 r = (r + (i * j) % 100) % 47;
5 }
6 }
7 print(r+"\n");
~/tmp$ time ~/Projects/V8/v8/shell ./dzmitryc.js
39
real 0m3.243s
user 0m3.194s
sys 0m0.022s
Заодно он подкинул мне ссылку на более подробное сравнение языков, которой я бы, в свою очередь, хотел поделиться с Вами — http://shootout.alioth.debian.org/
А за ссылку спасибо, да, там куда серьёзнее
Ну да, я понимаю, что на одних пишут веб-скрипты, на других игры, на третьих апплеты и т.д. Тут понятно, на С++ апплет не напишешь. Но если язык используется именно как general purpose language, почему бы не устроить простой тест производительности?
Да, мне было интересно увидеть эти цифры, но это всё настолько относительно…
Тогда я смогу сказать что-то вроде: перейдя на язык Y, ты смог бы посчитать задачу среднего размера за 10 часов. Вот и всё.
gcc 4.3
real 0m1.586s
user 0m1.500s
sys 0m0.024s
gcj 4.3
real 0m7.114s
user 0m6.952s
sys 0m0.028s
java 1.6.0_14
real 0m7.500s
user 0m7.264s
sys 0m0.012s
java 1.6.0_14 server
real 0m0.116s
user 0m0.060s
sys 0m0.016s
python2.6
real 0m57.403s
user 0m55.363s
sys 0m0.272s
Но я совсем не ожидал, что PHP окажется быстрей Питона, на котором работает известный всем своей производительностью Джанго. Приятно удивлён.
Тем не менее, здесь результаты сравнения PHP и Python другие
shootout.alioth.debian.org/debian/benchmark.php?test=all&lang=php&lang2=python&box=1
Что-то подсказывает мне, что мы в этом посте тоже к этому придём коллективными усилиями :)
let r = ref 0;;
let tstfunc x =
for i = 1 to x do
for j = 1 to x do
r := (!r + (i * j) mod 100) mod 47;
done;
done;;
tstfunc 10000;;
Printf.printf «Result %d\n» !r;;
и дальше
$ ocamlopt speedtest.ml -o sptest
$ time ./sptest
Result 39
real 0m6.364s
user 0m6.136s
sys 0m0.044s
6 секунд на amd 4000+
(defun tst () (let (( r 0)) (dotimes (i 10000) (dotimes (j 10000) (setf r (mod (+ r (mod (* i j) 100)) 47) ) )) r))
* (compile-file «test.lisp»)
* (load «test»)
; Loading #p"/home/w/sandbox/test.x86f".
T
* (time (tst))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 10.62 seconds of real time
; 10.296644 seconds of user run time
; 0.032002 seconds of system run time
; 20,399,873,134 CPU cycles
; 0 page faults and
; 0 bytes consed.
;
39
То есть 10 сек
module Main where
loop1 :: Int -> Int -> Int
loop1 0 x = x
loop1 n x = loop1 (n-1) (loop2 10000 x n)
loop2 :: Int -> Int -> Int -> Int
loop2 0 r _ = r
loop2 j r i = loop2 (j-1) ((r + ( (i * j) `rem` 100)) `rem` 47) i
main = do
putStr «Result „
print (loop1 10000 0)
$ghc -O test.hs -o tesths
$time ./tesths
Result 39
real 0m7.442s
user 0m7.316s
sys 0m0.028s
7 c хвостиком (примерно полвосьмого) секунд
myfunc :: [Int] -> Int
myfunc r = foldl (\ r1 i -> foldl (\r2 j -> (r2 + (i*j) `rem` 100 ) `rem` 47) r1 r) 0 r
main = do
putStr «Result „
print (myfunc [0..10000])
time ./test1
Result 39
real 0m7.503s
user 0m7.216s
sys 0m0.032s
2) ocaml и erlang очень разные языки, «окамли и эрланги» — непоятно по какому признаку вы их обьединили. По наличию gc? так в python и java он тоже есть. По «функциональности» языка? так ocaml позволяет писать не функционально и приведенный пример как раз написан императивно… Поясните пожалуйста вашу мысль.
То есть, как писал Дейкстра " Тестирование может доказать наличие ошибок, но никогда не докажет их отсутствие". Поэтому образно говоря в языках с встроенным управлением памяти надо постараться, чтобы слохопотать NullPointer, а в C надо очень стараться чтобы не схлопотать.
Например, время старта VM у java не учитывается, а у php/python — идёт в плюс.
выполняется в среднем 3620 мс (Pen D 3200)
Если для r int заменить на long, время возрастает примерно в 1,7 раз
странно но у меня ваш код другие цифры показал
2) архитектура Core всяко лучше
Хотя не думаю, что в данном случае это сильно повлияло на результат.
from time import clock
clock()
r = 0.0
i = 0.0
while i < 10000.0:
j = 0.0
while j < 1000.0: # !!!
r = (r + (i * j) % 100.0) % 47.0
j += 1.0
i += 1.0
print("answer: ", r, clock())
exit()
Выдаёт 10.19, ну а с j<10000 в 10 раз больше)
Если использовать int вместо float результат ухудшается примерно на 14%.
Дело в том, что в Python целые числа хранятся специальным образом, позволяя производит вычисления с оооочень большими значениями (a = 1024**1024)
соппсно, тест изначально составлен неверно — нужно, чтобы получалось 42
-export([start/0]).
start() -> lists:foldl(fun(I, R) -> lists:foldl(fun(J, R2) -> (R2 + (I * J) rem 100) rem 47 end, R, lists:seq(0, 10000)) end, 0, lists:seq(0, 10000)).
Eshell V5.7.2 (abort with ^G)
1> c(test).
{ok,test}
2> timer:tc(test, start, []).
{31674407,39}
31сек
-export([start/0]).
start() ->
Seq = lists:seq(0, 10000),
lists:foldl(fun(I, R) -> lists:foldl(fun(J, R2) -> (R2 + (I * J) rem 100) rem 47 end, R, Seq) end, 0, Seq).
Eshell V5.7.2 (abort with ^G)
1> c(test, [native, {hipe, o3}]).
{ok,test}
2> timer:tc(test, start, []).
{27637857,39}
3> c(test).
{ok,test}
4> timer:tc(test, start, []).
{24428678,39}
p.s. AMD Athlon(tm) X2 Dual Core Processor BE-2300
-module(test).
-export([start/0,run/0]).
start() ->
Seq = lists:seq(0, 10000),
lists:foldl(fun(I, R) -> lists:foldl(fun(J, R2) -> (R2 + (I * J) rem 100) rem 47 end, R, Seq) end, 0, Seq).
run() ->
loop1(10000,0).
loop1(0,X) -> X;
loop1(N,X) ->
X1 = loop2(10000,X,N),
loop1(N-1,X1).
loop2(0,X,_) ->X;
loop2(J,R2,I) ->
R = (R2 + (I * J) rem 100) rem 47,
loop2(J-1,R,I).
3> c(test,[native]).
{ok,test}
5> timer:tc(test,start,[]).
{28965824,39}
6> timer:tc(test,run,[]).
{7921692,39}
7>
То есть вашим вариантом на моей машине — 28 сек, переписаным — 8 сек.
run2() -> dotimes(10000, fun(I, R) -> dotimes(10000, fun(J, R2) -> (R2 + (I * J) rem 100) rem 47 end, R) end, 0).
dotimes(0, _, Acc) -> Acc;
dotimes(T, F, Acc) -> dotimes(T-1, F, F(T, Acc)).
1> c(test, [native]).
{ok,test}
2> timer:tc(test, start, []).
{22927752,39}
3> timer:tc(test, run, []).
{10201462,39}
4> timer:tc(test, run2, []).
{11048724,39}
А какая версия erlang'а у вас? У меня такие результаты на erlang R13b.
Попробовал на R13B1 —
6> timer:tc(test,start,[]).
{19239320,39}
7> timer:tc(test,run,[]).
{7114840,39}
8> timer:tc(test,run2,[]).
{8048659,39}
На R12B5 — 2> timer:tc(test,start,[]).
{28226647,39}
3> timer:tc(test,run,[]).
{7789521,39}
4> timer:tc(test,run2,[]).
{8189215,39}
Другими словами, Ваш первый вариант при переходе с R12 на R13 ускорился почти на треть — с 28 сек до 19 сек. Однако…
А рекзультаты на функциях улучшились чуть-чуть с 7.7 и 8.1 до 7.1 и 8.0 сек…
После дизассемблирования beam файла оказалось, что loop1 и loop2 адресуются статически, типа
{move,{integer,10000},{x,0}}.
{move,{x,2},{y,0}}.
{call,3,{test,loop2,3}}. < == Вот оно
{gc_bif,'-',{f,0},1,[{y,0},{integer,1}],{x,2}}.
{move,{x,0},{x,1}}.
{move,{x,2},{x,0}}.
{call_last,2,{test,loop1,2},1}.
А в dotimes вызывается преданная ей функция, которая в свою очередь создает переменную-функцию.
Типа в dotimes:
{function,dotimes,3,14}.
{label,13}.
{func_info,{atom,test},{atom,dotimes},3}.
{label,14}.
{test,is_eq_exact,{f,15},[{x,0},{integer,0}]}.
{move,{x,2},{x,0}}.
return.
{label,15}.
{allocate_zero,2,3}.
{gc_bif,'-',{f,0},3,[{x,0},{integer,1}],{y,1}}.
{move,{x,2},{x,4}}.
{move,{x,1},{x,2}}.
{move,{x,4},{x,1}}.
{move,{x,2},{y,0}}.
{call_fun,2}. < == Вот вызов
{move,{y,0},{x,1}}.
{move,{x,0},{x,2}}.
{move,{y,1},{x,0}}.
{call_last,3,{test,dotimes,3},2}.
А это функция которая вызывается:
{function,'-run2/0-fun-1-',2,21}.
…
{make_fun2,{test,'-run2/0-fun-0-',3},2,29791076,1}.
…
То есть простыми словами — решение с dotimes создает дополнительно 10000 переменных типа функция, которые потом собираются garbage коллектором.
code.google.com/p/unladen-swallow/
На языке Perl скорость увеличивается на 30%, предлагаю поправить скрипт для чистоты экперимента.
Также непонятно почему выбрана не самая последняя версия Perl 5.10.0
У меня скрипт выполнялся 27 секунд
У меня perl5.10.0 выполнял скрипт в среднем 60 секунд из 5 запусков. Машина:
Кстати, по поводу руби-скрипта который выполнялся 30 сек а не 200, подозреваю что у человека просто мощный процессор, у меня вот например — core 2 duo 6850, там что на тестовой конфигурации автора топика думаю будет раза в 2-3 дольше выполнятся
#!/usr/bin/perl
use integer;
use Benchmark;
$t = timeit(1,sub {
$r = 0;
for my $i (0..9999) {
for my $j (0..9999) {
$r += $i * $j % 100;
$r %= 47;
}
}
print "answer: $r\n";
});
print "time: ",timestr($t);
Но на такой код уже менять, наверное не буду, т.к. по-моему, это уже «хак» ;)
Так и должна выглядеть программа на языке Perl,
правда тут с Benchmark'ом, т.е. программа сама замеряет сколько времени этот код выполняется,
ну от него легко избавиться.
Просто в тестировании языков программирования без использования их особенностей ключевых я не вижу смысла.
Опять же — psycho для питона — хак, а тут — pure Perl, никаких библиотек внешних даже нету… используется только стандартная прагма
Но, чёрт возьми, ведь в самом начале хотелось без «заточки кода» под каждый конкретный язык, сравнение просто общих операций :)
ps: а можно ли при использовании «use integer» пользоваться вычислениями с плавающей точкой? или более точно определять типы переменных?
Для общие операции в каждом языке свои общие общепринятые (и даже идиоматические) способы выражения. :)
Прагмы в Perl действуют в пределах блока кода где они объявлены, в любой момент их можно отменить (no integer, например).
В частности эта — документирована (то есть присутствует в официальной документации) и является фичей языка (коих там много =) ), целью которой является ускорение частей когда где используется ТОЛЬКО целочисленная арифметика.
Оригинальный перл скрипт — 42.323s
вариант что выше но без «my» — 31.186s
вариант с «my» — 29.767s
кстати не знал что my такой полезный в этом плане, кстате почему ??
perl, v5.8.8
$ sudo nice -n -9 time ruby 1.rb
answer: 39
20.99 real 20.81 user 0.05 sys
Версия руби:
$ ruby -v
ruby 1.9.1p129 (2009-05-12 revision 23412) [i386-darwin9]
А по сравнению — ведь в споре рождается истина. Я не претендовал на «нахождение самого лучшего языка», я просто решил замерить кто и как справится с брутфорс-задачей. В процессе общения с читателями код (в скриптовых языках) претерпел некоторые изменения, производительность выросла. Вариант на Java тоже ускорился, в 5 раз относительно начального варианта.
Интересно, занимательно, даже, как мне кажется, «общеобразовательно полезно» :)
Неужели Вам никогда не приходилось копать воду или измерять сферического коня просто потому, что любопытно?
P.S. shootout.alioth.debian.org
PS про shootout уже несколько раз писали в обсуждении.
К примеру у вас есть питоновская программа, которая реализует какую-то логику. Надо добавить числодробительный модуль. Можно написать на питоне, можно сделать вставку на C. Имеет смысл возиться с С? не имея представления какой может быть выигрыш — не ответишь.
У меня под Windows версия 5.2.6 выполняла код 32 секунды, версия 5.2.10 — 28 секунд, 5.3.0 — 24 секунды.
Правда 5.2.6 и 5.2.10 были скомпилированы VC6, а 5.3.0 — VC9, может еще и этим разница объясняется.
C-style тут не при чем, сейчас докажу :) Он конечно медленнее range, но не трагически.
Этот кусок перлкода можно ускорить раза в полтора, тупо объявив все переменные локальными.
Не забывайте use strict; Он конечно жрет часть памяти и производительности, но это стоит того, эти потери много меньше, чем от пропущенного my ;)
Ну и использование контексных переменный чуть-чуть ускоряет.
Про use integer уже сказали, его можно применять контекстно. Да и хак это такой же, как на Java вместо float использовать int ;)
#~ use strict;
use Benchmark;
Benchmark::timethese(1_000, {
'A' => sub {
#~ use integer;
$r = 0;
for ($i = 0; $i < 100; $i++) {
for ($j = 0; $j < 100; $j++) {
$r = ($r + ($i * $j) % 100) % 47;
}
}
},
'B' => sub {
#~ use integer;
my $r = 0;
for (my $i = 0; $i < 100; $i++) {
for (my $j = 0; $j < 100; $j++) {
$r = ($r + ($i * $j) % 100) % 47;
}
}
},
'C' => sub {
#~ use integer;
my $r = 0;
for my $i (0..99) {
for my $j (0..99) {
$r = ($r + ($i * $j) % 100) % 47;
}
}
},
'D' => sub {
#~ use integer;
my $r = 0;
for my $i (0..99) {
$r = ($r + ($i * $_) % 100) % 47 for 0..99;
}
},
});
>perl math.pl
Benchmark: timing 1000 iterations of A, B, C, D…
A: 5 wallclock secs ( 5.04 usr + 0.00 sys = 5.04 CPU) @ 198.49/s (n=1000)
B: 4 wallclock secs ( 3.82 usr + 0.00 sys = 3.82 CPU) @ 261.64/s (n=1000)
C: 4 wallclock secs ( 3.54 usr + 0.00 sys = 3.54 CPU) @ 282.41/s (n=1000)
D: 3 wallclock secs ( 3.26 usr + 0.00 sys = 3.26 CPU) @ 306.65/s (n=1000)
>Exit code: 0 Time: 16.124
PS: Пардон за форматирование, теги не работают :(
ps: очень удивила разница между php и perl, помню раньше всегда и все говорили что perl гораздо быстрее.
Что касается сути, то я бы хотел сказать следующее. Тест, выбранный автором, представляет собой два вложенных цикла с постоянными границами. Такие вещи уже давно оптимизируются компиляторами вдоль и поперёк — и в данном случе это не очень хорошо, потому что реальный функционал кода на разных языках на выходе из оптимизатора получается очень разный. Это первое.
Второе. Этот алгоритм, если хотите, «частный случай», который совсем нечасто возникает в реальной жизни.
Что же мы используем в реальных программах и как сделать тест ближе к практике? Прежде всего, границы цикла должны быть вычисляемыми (неконстантными) переменными (границы объекта-контейнера). Во-вторых, внутри цикла должно идти не просто вычисление (математика), но и работа с разными переменными. В идеале, тест должен проводиться на контейнерах (!). Потому что реальная производительность в реальных программах характеризуется связкой язык+контейнеры. Скорее всего, имеет смысл даже сделать два теста — с контейнерами и без.
А теперь несколько комментариев-вопросов:
1) Какая jre использовалась? SunJDK, OpenJDK, java от IBM и т.д. Тоже самое касается и С++ компилера. Подозреваю что это gcc 4.х, но всё же. Ещё нужно бы Intel CC протестировать, поговаривают, что он математику хорошо умеет оптимизировать.
Да, и почему нет теста с -O3? (или может я просто всё это не заметил это в тексте)
2) Предлагаю в будущем протестировать ещё код, который активно занимается выделением и очисткой памяти в куче. Думаю, так будет интереснее =)
gcc с флагом -O3 и даже -O99 относительно -O2 прироста не дал. Дополнительное -funroll-loops дало около 5% к -O2, что не так весомо.
На самом деле сейчас хочу собрать всё что разбросано по комментариям и агрегировать. А потом, да, можно будет попробовать работу с массивами, списками, строками, вызовами функций, созданием классов и много ещё с чем попробовать :)
Перл надо тестить 5.10? и Руби 1.9.1
Но на m=3 вполне можно считать до N=13:
Результаты при многократных запусках достаточно стабильные:
$ javac Test01.java && time java -Xss8m Test01
real 0m39.349s
user 0m37.870s
sys 0m0.104s
$ javac Test01.java && time java -Xss8m -server Test01
real 0m19.630s
user 0m18.705s
sys 0m0.068s
$ g++ Test01.cpp -o Test01 && time ./Test01
real 1m0.333s
user 0m57.472s
sys 0m0.104s
$ g++ Test01.cpp -O2 -o Test01 && time ./Test01
real 0m26.549s
user 0m25.246s
sys 0m0.048s
Машинка (на работе):
$ cat /proc/cpuinfo |fgrep 'model name'
model name: Intel® Pentium® 4 CPU 3.20GHz
model name: Intel® Pentium® 4 CPU 3.20GHz
Код здесь
0.21 сек против 0.67 сек эталонного варианта за счет банальной эрудиции
Однако, на моём unsigned увеличивает время работы в полтора(!) раза. Проверил по 5 запусков.
На рабочем компе unsigned ускоряет исполнение почти в полтора раза (1.3).
Похоже, что у меня неправильный ноут, неправильный линукс и неправильный gcc.
Коплю на новое железо, похоже, пора
А вообще не вижу смысла в оптимизации самого алгоритма — это же только синтетический тест. Если бы надо было оптимизировать этот кусок кода, то можно просто написать:
:)
В 8-байтный long число 4740000000 помещается. Если хотите придираться к переполнению, то есть машины, где произведение 10000*10000 будет не входить в 2-байтовый int.
А вообще я с вами согласен — алгоритмическая оптимизация рулит :) Но надо при этом быть осторожным, чтобы не изменился результат.
from time import clock
def test():
r = 0
for i in xrange(0, 10000):
for j in xrange(0, 10000):
r = (r + (i * j) % 100) % 47
return r
print( «answer: », test(), clock() )
DisableDebugger
r.i = 0
t=ElapsedMilliseconds()
For i = 0 To 10000
For j = 0 To 10000
r = (r + (i * j) % 100) % 47
Next j
Next i
e=ElapsedMilliseconds()-t
MessageRequester("", StrF(e/1000, 3)+" секунд")
Проверял на компе с процессором близким к «P4-1.8Ггц», т. е. как и автора статьи.
Тест был выполнен за 3 секунды.
JavaScript (браузер, консоль отдельно)
и другие