Pull to refresh

Comments 59

Скрытый текст
<?php
$t = microtime(1);
function fib ($n)
{
    if ($n < 3) return 1;
    return fib($n - 1) + fib($n - 2);
}
echo fib(30) . "\n";
echo microtime(1) - $t;


PHP 5.4.34 (cli) (built: Oct 15 2014 21:58:00)
> 0.32301807403564

PHP 5.5.21 (cli) (built: Jan 21 2015 14:42:18)
> 0.32501792907715

PHP 5.6.6 (cli) (built: Feb 18 2015 16:02:19)
> 0.30201697349548

PHP 7.0.0-dev (cli) (built: Feb 5 2015 00:20:59) (без JIT)
> 0.0590071105957
Скорость работы программ на ассемблере может быть более 50% медленнее, чем программ на си/си++, скомпилированных с максимальной оптимизаций;
Однозначно ложное утверждение. Нет ничего быстрее ассемблера. Есть неотимально написанный софт. Одна из причин — слишком сильно отдаляешься от задачи которую выполняешь. Да и трудоёмкость оптимизации на ассемблере очень высока. Да чего далеко ходить. Дизассемблируйте то, что у вас получилось в результате компиляции. Вот вам 100% соответствующая по скорости программа на ассемблере.
Посмотрел на примере 64-битного кода (в Visual Studio). Когда сравнивал программу на C с простейшей программой на ассемблере, последняя была в 1.5 раза медленнее. Но в коде, сгенерированном компилятором, кроме самой функции было ещё много какой-то дополнительной информации. Судя по всему, она используется для inline подстановки ассемблерных функций (!).
Действительно, когда я подставил код своей функции в неё саму на два уровня вложенности (т.е. получилось 7 копий кода), времена выполнения сравнялись. У компилятора возможностей для такой подстановки ещё больше.
При компиляции любых языков, кроме ассемблера, за оптимизацию отвечает компилятор. При программировании на ассемблере отвечает мозг человека! Вы не можете обогнать ассемблер из-за того, что ассемблер — это отображение языка процессора в человекопонятной форме. Любой другой код можно представить в виде ассемблерного кода, который будет один в один со скомпилированным результатом любого другого языка.
По результатам исследования сделаны следующие выводы, некоторые из которых оказались несколько неожиданными:

  1. Скорость работы программ на ассемблере может быть более 50% медленнее, чем программ на си/си++, скомпилированных с максимальной оптимизаций;



Вот так потом и создают принципиально новые ОС и доказывают математически существование жизни после смерти.

Это не скорость работы программ на ассемблере мендленнее (ведь всё в конце концов будет переведено в машинный код), это неумение оптимизировать вручную код на нём. Компиляторы могут читерить — частично разворачивать циклы и рекурсии, перестраивать последовательность операций для параллельного выполнения, правильно выравнивать данные. И на исходный алгоритм результат будет мало похож. И на грубину рекурсии это влияет. Компилятор заинлайнил 2 рекурсивных вызова — глубина рекурсии в 4 раза увеличилась. И производительность подскачила (чем меньше переходов, а уж тем более вызовов процедур, тем лучше). Но стек отстался прежним. Единственное приемущество, что компилятор всё это оптимизирует автоматически, может учитывать особенности конкретных моделей процессоров. А так — развернёте в ассемблере рекурсию на десяток уровней и получите совершенно другие результаты.

Получилось отличное пособие о том, как не нужно делать бенчмарки.
Плюс сложность абстрагироваться от задачи и понимать не только алгоритм, то и где и как правильно использовать регистры процессора. При современном развитии компьютеров больше похоже на мазохизм. Хотя, в некоторых случаях, может резко поднять производительность.
А что вам не понравилось? Они _могут_ быть медленнее. Если плохо оптимизированы. А могут и не быть, в противном случае.
То, что это утверждение верно для любой пары языков. Это тавтология. И на Python можно написать код, который будет быстрее кода на C++. Да даже на Bash можно. Можно и на ассемблере написать так, что он будет медленнее любого существуюшего языка. И без дополнительных условий утверждение чего-то подобного — демагогия.

Давайте на примерах? У вас в распоряжении велосипед (исправный, без подвохов), а у меня лишь баллончик с освежителем воздуха. Мы не можем друг на друга взаимодействовать (вы меня не можете переехать, я вам мешать не могу). И мы с вами участвуем в гонке.
Я утверждаю, что я вас обгоню. Причём это не зависит от дистанции, хоть тысячу киллометров. Я даже вам дам фору в пару километров, т.к. мне вас жаль. Старт и финиш у нас с вами одни.
Однако, расчет этой функции требует значительного числа рекурсивных вызовов и большинство тестируемых языков оказалось не в состоянии их поддерживать для вычислений, имеющих заметную длительность. Известно, что вычисление этой функции нельзя свести к итерации
Известно? А как быть с теоремой об удалении рекурсии?
Надо всего лишь реализовать стек и цикл с условием выхода по пустоте стека ;) Под итерациями скорее всего имеется в виду алгоритм с константной памятью.
Эта функция забавна тем, что в итеративном виде она оказывается ничуть не быстрее рекурсивного :) 11 лет назад её тоже для простых бенчмарков использовал.
Большая проблема сравнения языков программирования в том, что составители тестов не знают и половины из них. В итоге получается сравнение сферических коней в вакууме.

К примеру, вот так должен выглядеть код на Haskell (и примерно так же на Erlang)

fib :: Integer -> Integer -> Int -> Int -> Integer
fib cur prev n ref
 | n == ref = cur
 | otherwise = fib (cur + prev) cur (n+1) ref

fib' :: Int -> Integer
fib' = fib 1 1 2
main = interact $ unlines . map (show . fib'. read) .lines


Этот код тратит на вычисление 700000го числа Фибоначчи примерно столько же времени, сколько оригинальный код на вычисление 39го.
Аналогично, код на Java измеряет хтуфту. Как и большая часть бенчмарков на яве. Измерять что-либо без прогрева, не указывая какая из версий jvm и в каком режиме используется — пустая трата времени тех, кто эти результаты потом читает.
Хоть я и не знаком с Haskell, но почти уверен, что вы привели алгоритм с одним рекурсивным вызовом вместо двух.
Конечно! Потому что любой нормальный человек не будет использовать алгоритм с двумя рекурсивными вызовами там, где можно использовать один.

Я сделал и другие оптимизации. К примеру, явное указание «родных» типов вместо используемых по умолчанию «длинных» чисел, ускоряет программу в 10 раз. Но проблема в том, что так все равно никто не пишет. А раз так никто не пишет, то и показывать такой тест будет непонятно что.
А смысл? Если я правильно понимаю задумку автора, то такой идиотский алгоритм вычисления чисел Фибоначчи выбран как раз потому, что он тяжело оптимизируется компилятором/транслятором/средой исполнения. Иначе и на других более императивных языках можно было просто цикл написать и все.
П.С. Против явного указания нативных типов данных ничего не имею ,)
Для языков более высокого уровня оптимизация компилятора более важна. Haskell точно так же не может оптимизировать двойную рекурсию как и Си, но в случае Haskell относительный выигрыш от оптимизации может быть больше. Беда в том, что в реальной жизни никто не оставит двойную рекурсию в Haskell, также как и в Си, так что непонятно, что же исходный тест проверяет.
Нам был продемонстрирован изощренный способ сравнить:
1) скорость вызова функции
2) максимальную глубину стека
Потому и выбрали такой алгоритм, чтобы рекурсия ничем ни во что не разворачивалась (хотя в случае C/C++ с -O3/5 на какую-то глубину оно все же инлайнилось, это видно, в частности, по разной глубине стека -O0 vs -O3/5).
Скорость вызова сферических функций и сферическую глубину стека. Эти параметры слишком сильно зависят от сигнатары функции — количества переменных, способа их передачи. Глубина стека отлично настраивается, и никто не мешает использовать хоть всю оперативную память под стек.
Ну, функция не совсем сферическая, а вполне определенная с одним целочисленным параметром (правда, вы утверждаете, что в случае Haskell этот параметр не совсем целочисленный, а bigInt). И потом, я же не спорил с тем, что ценность данного сравнения несколько сомнительна, а просто указал на то, что в приведенной работе всюду использовался один и тот же алгоритм (неважно с какими целями), а вы его предложили поменять лишь для одного отдельного ЯП.
Посмотрел сорцы, немного смутило то, что в разных языках вычисляются разные члены последовательности.
Надеюсь, в в процессе теста это было поправлено?
fib 15

fib(32)

int k = 41;

System.out.println(fibc(40));


Ну и про то, что
Скорость работы программ на ассемблере может быть более 50% медленнее, чем программ на си/си++, скомпилированных с максимальной оптимизаций

я бы добавил «неоптимизированных» перед «программ на ассемблере» — статья это отлично показала :)
Все программы реализуют один и тот же алгоритм… Аргументы разные, так как скорости очень разные и ждать год пока бэш отсчитает 41-е число затруднительно. Если написать на ассемблере иначе, то будет другой алгоритм. Может уже есть оптимизирующие ассемблеры?
UFO just landed and posted this here
Астрологи объявили неделю бенчмарков
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
от гугла сравнение было неплохое, жаль только оно старенькое
UFO just landed and posted this here
Всё бюджетное и софт и хард.
Новый гугл немного побыстрее.
замечание по форме: что бы цифровые показатели в таблице было легче и правильнее воспринимать, их нужно
* выравнять по правому краю
* привести к единому формату (например, во второй таблице вещественные значения все отобразить с одинаковым количеством знаков после запятой)
* использовать моноширинный шрифт

а еще лично мне не нравится как представлена вторая таблица — два столбца с не очень длинными значениями, растянутые на всю ширину. Но это уже может быть вкусовщина.

Что называется, «почувствуйте разницу» jsfiddle.net/og2xt0nb/ (обрамление и прочие стили добавьте по вкусу)

Очень благодарен, но первый блин…
Пожалуйста, не учите своих студентов таким «бенчмаркам».
А можете написать поконкретнее о том, что вам кажется не так? Студент просто честно всё закодировал и измерил. Слегка обработал факты…
Студент в данном случае сделал работу хорошо, но сделал ее так, как просили вы. А вы просили что-то невнятное.
В комментариях выше уже было указано на некоторые недочеты и сомнительные моменты. В целом хочется отметить низкое качество методики. Проводить бенчмарки — мастерство, которое сильно зависит от языка и платформы. С этим тяжело справиться без специальных инструментов и знаний, особенно студенту, писавшему до этого только на Паскале.
Почему вы не почитали про методику на указанном вами benchmarksgame.alioth.debian.org? Там есть полезные источники информации. Также советую погуглить особенности бенчмарков Java-кода. Это только та информация, которой я владею, но думаю, она применима ко многим языкам, работающим под управлением виртуальных машин. Отдельный разговор про динамический языки. Даже в случае компилируемых в нативный код языков все не просто: у Haskell, например, есть проблемы с производительностью, связанные с ленивыми вычислениями.
Зачем вам тестировать глубину стека? Обычно это настраиваемый параметр. И придирка: зачем писать названия языков по-русски?
Почему «невнятное»? Поразбирался человек с разным способом выразить один алгоритм. В статье не раз написано, что ни на какую абсолютность претензий нет. Написали, что получилось. Может стоит перечитать статью?
Я читал, дело не в «абсолютности». Определитесь с целями: либо «Большое обзорное тестирование языков программирования» (что неправда), либо «Разные способы выразить один простой алгоритм». В последнем случае алгоритм подобран плохо: он слишком прост для оценки способов выражения на разных языках.
Хм… интересно, почему Вы считаете вычисление Фибонначи является репрезентативной метрикой оценки быстродействия кода, сгенерированного компилятором? Есть же «уставной» способ оценки — SPEC2000/2006.
Спасибо за работу. Несколько замечаний:

1. Бенчмарк очень своеобразный, потому что не понятно, на что тут тратится больше времени: на вычисления или на собственно рекурсивыне вызовы. Надо было выбрать что-нибудь более вычислительное, типа вычисление Быстрого Преобразования Фурье или что-нибудь с матрицами.

2. Бенчмарк неактуальный, так как таких строго вычислительно-рекурсивных задач очень мало в современном программировании. Раз в сто больше задач по общей обработке информации типа «создать массив на сто тысяч строк, отсортировать его, отфильтровать по какому-нибудь паттерну, поработать с такой же хэштаблицей из ста тысяч строк и т.п.»

3. Ну и, конечно, многие языки имеют свои супероптимальные конструкции для типичных задач, про которые сразу и не узнаешь, если быстро пробежишься по основам языка «чисто чтобы тест быстренько написать».

4. Жалко, что с тестах присутствуют совсем экзотические языки, но нет, например, таких, как Scala и Clojure (хотя они явно не для вычислений чисел Фибоначи были придуманы).
Затраты на вызов функции и величина стека. Это все, что тут измерялось.
Вы практически пересказали мою мысль, но другими словами. О том и речь, что в реальном программировании ни величина стека, ни затраты на вызов функции не являются критичными ни в малейшей мере. Но в начале статьи указано другое — что измерялась «скорость исполнения программ».
Про вызов функции можно и поспорить. Хотя ситуации, когда его скорость является критичной, встречаются крайне редко. Мне такое встретилось один раз — когда обработчик данных строился как последовательный вызов очень маленьких функций, указатели на которые были записаны в массив (строившийся после того, как стал известен формат данных). Остальные варианты реализации этой обработки были ещё хуже.
Да там был натуральный полиморфизм, да еще и времени исполнения! ) Однако, есть миллион способов избежать очень большого кол-ва очень маленьких функций. И в реальных системах, скорее наоборот, есть большая проблема огромных и очень огромных функций.
UFO just landed and posted this here
Ага. И вообще любой язык программирования потом превратится в машинные инструкции, которые будет выполнять один и тот же процессор. Так какой смысл вообще что-то сравнивать? Все равны. 8-)
UFO just landed and posted this here
Было бы странно, если бы компиляторы с разным функционалом, разной стандартной библиотекой давали одинаковый итоговый байткод.
Как-то не совсем понятно, что хотел донести автор и какие выводы из всего этого должен сделать студент и прочитавшие.

Если это попытка показать, как выглядят программы на разных языках, то задача для этого выбрана совсем уж простая. Чтобы «прочувствовать» язык, надо написать что-то покрупнее, например веб-сервис или игру. А потом сравнить, какой из языков больше подходит к какой нише (хотя это и так все знают).

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

1) Почему реализация питона только одна, если уж сравнивать на скорость, то надо было включить ещё и pypy? Он очень шустрый и довольно хорошо совместим с CPython. Например, у меня 33-е число Фибоначчи после прогрева pypy считает в 3-4 раза быстрее CPython.
2) Почему нет другого «гонщика» — luajit? У неё, например, в комплекте есть поддержка ffi, поэтому скорость на простых бенчмарках на уровне v8/java/pascal (у меня на машине у luajit и C почти одинаковое время).
3) Даже если забыть, что такую древовидную рекурсию обычно не используют в жизни, а стараются заменить её на что-то более линейное), всё равно так код не пишут. Например, хоть я и не писал на перле, но помню, что там есть такая замечательная штука, как memoize. Из таблицы видно, что перл уступает, например, питону. Но если добавить пару строк…

Но если добавить пару строк
use Memoize;

sub fib {
  my $n = shift;
  if ($n < 3) {return 1;}
  return fib($n-1) + fib($n-2);
}

memoize('fib');

print fib(33), "\n"


Результаты:
$ time perl fib.pl
3524578

real    0m3.437s
user    0m3.427s
sys     0m0.008s

$ time perl fib-memo.pl
3524578

real    0m0.028s
user    0m0.020s
sys     0m0.008s



Это быстрее, чем PyPy (0m0.453s), Luajit(0m0.063s), и С без оптимизации (0m0.040s),
C -O3 одинаково.

Т.е. прирост в скорости составил 122 раза!


Но самое главное, что все эти выводы никак не применимы в реальной жизни. Никто не бросится переписывать всё с С на перл, потому что в бенчмарке они по скорости одинаковы. А вот для научных расчётов, например, люди любят использовать питон, несмотря на его неторопливость. Весь секрет в том, что на питоне там ничего не считается, это всего лишь удобная оболочка к фортрановским и сишным библиотекам.

Сравнивать веб-серверы под нагрузкой, это одно, там хотя бы задача приближена к реальности. А в этом примере, на мой взгляд, нет ни смысла, ни пользы.
хотя это и так все знают
Очень благодарен вам за внимание к публикации. Хотя почти уверен, что не все и не всё.
Sign up to leave a comment.

Articles