Комментарии 82
А можно вектор зарезервить?
vector<long> primes = {2}; for(long n = 3; n <= limit; n += 2) { if (is_prime(n, primes)) { primes.push_back(n); } }
Можно, наверное. Но резервить сразу под все значения, вроде как, не спортивно. А небольшой резерв не особо изменит общую картину, потому что размер буфера наращивается по экспоненте.
Да и идея была в том, что программы на Python и C++ примерно одинаковые по структуре.
эм, ну придётся допустим 2 раза перекладывать, это и есть основное что выполняет эта программа в итоге. В питоне и прочих языках это не вектор, а какая то мапа в которой нет реаллокации при вставке
Если посмотреть через strace, то видно, что тоже не происходит копирования. C++ версия тоже работает через remap-ы.
может всё таки попробуете добавить резерв или заменить vector на std::deque, а не говорить про какие то ремапы?
даже выделение памяти с запасом не оказывает заметного влияния на результат.
все утверждения приведены после анализа результатов тестов.
добавлял вот такой код.
primes.reserve(ceil(limit/log(limit))*1.1);Я не против потестить предлагаемые варианты на той же машине в выходные, но на переписывание у меня пока нет времени. Могу завести хранилище под эту задачу на GitHub, чтобы Вы могли добавить туда интересующий Вас код.
Вы можете отправить pull-запрос с интересующим Вас кодом вот сюда: https://github.com/mbakhterev/primes
Разница в скорости, по сути, вытекает именно из разницы в работе с динамическими структурами. GC позволяет откладывать все те вещи, которые в безколлекторных языках приходится производить на каждой итерации. Ну или руками придётся написать аналогичный механизм оптимального (отложенного и/или наоборот «предфечащего») управления ресурсами. Максимальной оптимизацией тут, действительно, станет резервирование сразу всей необходимой памяти (или хотя бы большими кусками, не реалоцируемыми максимально долго). Компиляторы функциональных языков благодаря имутабельности обрабатываемых структур данных и большему контролю потока вычислений потенциально могут произвести эту максимальную оптимизацию вплоть до статичного «многоэтажного» распределения памяти, когда переменные каждого последующего этапа алгоритма кладутся на память предыдущего вообще без вызова функций GC/аллокатора (компилятор уже точно знает, что через данную ячейку памяти связаны читатель с писателем уже нового поколения, а старые уже точно не оживут). Не знаю, делают ли реальные компиляторы так, но чисто теоретически не видится особых препятствий к этому :).
Есть ещё такая оптимизация как "partial evaluation", то есть, какой-нибудь Stalin или MLton в теории может вообще всё предвычислить.
Слышал где-то байку про оптимизирующий компилятор Фортрана, которому, мол, скормили жирные исходники какого-то алгоритма решения какой-то сложной комбинаторной/геометрической задачи или типа того, он их ворочал-ворочал пару часов, и в итоге скомпилировал-оптимизировал в машинный код, эквивалентный коду print 42 (или типа того, где 42 - это уже окончательное решение задачи). :)
Как может быть неспортивно просто выделить память под N элементов когда нужно N элементов...
Задача в том, чтобы сравнить поведение компиляторах и runtime на примерно одинаковой вычислительной нагрузке. Если в программе на Python весь массив сразу целиком не выделяется, и на Scheme не выделяется, и на C не выделяется, то почему он должен выделяться в программе на C++? Тогда уж надо писать такую версию кода на всех языках.
Да и потом, в C++, по сравнению с другими версиями, память выделяется более эффективно, размер массива растёт по экспоненте. То есть, требуется меньше этих самых реаллокаций.
Иногда есть функция divmod, то есть, вам выдаётся одновременно и остаток и частное от деления. Если сравнить частное от деления с текущим проверяемым числом, можно получить примерно тот же результат, что и с sqrt.
local args = {...}
if #args==0 then
print("Specify limit")
return
end
function isqrt(x)
local q = 1
while q <= x do
q = q*4
end
local r = 0
while (q > 1) do
q = q/4
local t = x - r - q
r = r/2
if (t >= 0) then
x = t
r = r+ q
end
end
return r
end
sqrt = args[2]=="std" and function(x) return math.ceil(math.sqrt(x)) end or isqrt
function is_prime(n, P)
local l = sqrt(n)
for _,p in ipairs(P) do
if (p > l) then return true end
if ((n % p)==0) then return false end
end
return true
end
local limit = tonumber(args[1])
local primes = {2}
for n = 3, limit, 2 do
if is_prime(n, primes) then
table.insert(primes, n)
end
end
print(#primes)
запускал через luajit, максимальное 5000000. со стандартным sqrt и округлением получил среднее значение 0.985с, с приведенным тут isqrt 1.15с.
сами по себе эти числа ничего не значат без сравнения с кодом из статьи. обычная версия на плюсах выдавала больше 3 секунд, оптимизированная (-Ofast -march=native -ftree-vectorize) версия на плюсах выдала в среднем 1.275с, с такими же ключами скомпилированная С версия выдаёт в среднем 1.285с.
вычисление N первых простых чисел (что почти такая же задача, как тут. граница тут задаётся другим критерием) уже обсуждал на хабре в контексте сравнения ЯП, там LuaJIT тоже показал очень хорошие результаты (а на некотором железе в 2 раза лучше, чем С или С++ версии). тоже динамически типизированный ЯП, тоже со сборкой мусора, динамическими контекстами и замыканиями
update: компилировал gcc/g++ 5.4 версии, clang не проверял
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <math.h>
inline int is_prime(const long n, const long* array, size_t len) {
const long l = ceil(sqrt(n));
for (size_t i = 0; i < len; i++) {
if (array[i] > l) return 1;
if (n % array[i] == 0) return 0;
}
return 1;
}
int main(int argc, char *argv[]) {
if (argc < 2) {
fprintf(stderr, "Specify limit\n");
return 1;
}
const long N = atol(argv[1]);
long* array = malloc(sizeof(long)*ceil(N/log(N))*1.1);
array[0]=2;
size_t count = 1;
for (long n = 3; n <= N; n += 2) {
if (is_prime(n, array, count)){
array[count++] = n;
}
}
printf("%ld\n", count);
return 0;
}написал код на С без всяких лишних манипуляций. просто массив с достаточным кол-вом места с запасом. результат: 1.21с в среднем, с указанными выше флагами компиляции. то есть это предел кодогенерации GCC при текущем описанном алгоритме. эффективнее = сильно усложнять код (если есть как можно ускорить). при этом luajit со стандартными функциями (да, понимаю, что для тестов в статье использовался одинаковый функционал. но в реальном коде никто не будет писать свои неэффективные функции, когда есть эффективные стандартные) выдаёт результат лучше (меньше времени) для конкретно такой задачи. да, что-то сверхсложное и суперхайлоад я б не стал писать на lua+luajit, но проекты среднего размера — почему бы и нет, он достаточно неплохо оптимизирует и lua очень прост в освоении и писать бинарные модули к lua тоже относительно легко. одни плюсы.
История с виртуальной памятью не такая простая, как может показаться. Реальное выделение физической памяти непростой процесс, и он может занимать довольно много времени.
Надо ещё отметить, что malloc на самом деле не к операционке за памятью идёт, а откусывает её от уже выделенной процессу (где-то перед стартом функции main RTL себе резервирует шмоточек, и к операционке идёт лишь тогда, когда закончились эти запасы). Есть альтернативные аллокаторы с другими профилями / эвристиками распределения памяти, один из самых известных, например, - https://github.com/google/tcmalloc (а тут можно взглянуть на изощрённость подкапотной логики подобных библ).
Где-нибудь можно почитать об оптимизациях, которые выполняет современный Haskell? Тут явно одним deforestation не обошлось.
Если я ничего не попутал, то вот мои результаты:
Первая версия (до `n / 2`):
C++ (clang): 0.295 с
C++ (gcc): 0.938 с
GHC (llvm): 0.521 с
GHC: 1.138 с
Вторая версия (до корня):
C++ (clang): 2.397 с
C++ (gcc): 6.784 с
GHC (llvm): 3.526 с
GHC: 8.408 с
Тесты запускал пару раз, брал минимальный результат (хотя, во всех тестах разница во времени была минимальна)
Тут только один вывод: используйте GHC с LLVM!
И один вопрос! Как там получилось, что у меня версия на clang быстрее, чем на GHC?
На всякий случай покажу код и команды, которые были во время теста, может, я что-то недоглядел.
Hidden text
Для C++:
#include <iostream>
#include <vector>
using std::vector;
template <typename integer>
integer isqrt(integer x) {
integer q = 1;
while (q <= x)
q <<= 2;
integer r = 0;
while (q > 1) {
q >>= 2;
integer t = x - r - q;
r >>= 1;
if (t >= 0) {
x = t;
r += q;
}
}
return r;
}
static bool is_prime(const long n, const vector<long> &P) {
long l = isqrt<long>(n);
for (auto p : P) {
if (p > l) return true;
if (!(n % p)) return false;
}
return true;
}
int main(int argc, char *argv[]) {
if (argc < 2) {
std::cerr << "Specify limit" << std::endl;
return 1;
}
const unsigned long limit = std::stol(argv[1]);
vector<long> primes = {2};
for(long n = 3; n <= limit; n += 2) {
if (is_prime(n, primes)) {
primes.push_back(n);
}
}
std::cout << primes.size() << std::endl;
return 0;
}
Команда, которой компилировал: clang++ primes.cpp -O3 -o primes-clang++
Результат выполнения: time ./primes-clang++ 25000000
1565927
real 0m2.394s
user 0m2.391s
sys 0m0.004sТеперь Haskell
{-# OPTIONS_GHC -O2 -fllvm #-}
module Main where
import System.Environment
primes :: Int -> [Int]
primes n = ps
where
ps = 2 : [ n | n <- [3, 5 .. n], isPrime n ]
isPrime n = all (\p -> n `rem` p /= 0) $ takeWhile (<= (floor $ sqrt $ fromIntegral n)) ps
main :: IO ()
main = do
[cnt] <- getArgs
print $ length $ primes $ read cnt
Команда, которой компилировал: ghc WithLLVM.hs
Время выполнения: time ./WithLLVM 25000000
1565927
real 0m3.520s
user 0m3.476s
sys 0m0.044sЯ думаю, что это у меня проблема во время компиляции хаскельного кода:
[1 of 1] Compiling Main ( WithLLVM.hs, WithLLVM.o )
You are using an unsupported version of LLVM!
Currently only 9 to 13 is supported. System LLVM version: 13.0.1
We will try though...
Linking WithLLVM ...Почему-то 13.0.1 уже не нравится :(
GHC версии 8.10.7 (хотя, это особо не влияет. На новом 9.2.2 такой же результат)
Вот опять статья про оптимизацию кода, и ни одного профиля приложения. Ну как так то?
Так код простой, и без профилей всё понятно. Разве нет?
Нет, непонятно. Вы гадайте по кофейной гуще. Я не верю в данные результаты.
Можно на профиль посмотреть хотя бы?
И это не учитовая тот факт, что у вас два разных алгоритма...
Так разве кто запрещает? Можно конечно! Исходники все открыты.
На машине я обновил версии ПО, поэтому всё надо замерять заново. У меня нет на неделе на это времени. Sorry. В следующий раз сделаю с профилями.
Благодарю за указание на этот недочёт.
Тут как указывали выше вполне может быть разница из-за подхода с работой с памятью. Я видел пару раз, когда языки с gc выигрывали у языков без gc просто из-за разной механики работы с памятью. Взять другой аллокатор - и результат будет совсем иной
Если время работы измеряет не то, на что оно тратится, то какое тут доверие? Если мы измеряем время работы стандартного аллокатора, а не алгоритма, то зачем мы писали алгоритм?
На первой работе я тоже один раз услышал такую формулировку. А потом мы часть алгоритма переписали (не связано с аллокатором, там другая проблема была), и то что мы должны были исследовать до этого, внезапно оказалось бутылочным горлышком. А обнаружили бы раньше, и проблемы бы не было
Можно, но раз уже пишешь статью, а потом оказывается что у тебя тормоза не в коде, а в syscall и непонятно что и где... Очень странно не использовать возможности профилирования, имеющиеся наверное в любом чайнике. Какую функию копирования использует программа с -О2 и с О3? В одном случае может быть вызов glibc, во втором инлайнинг оптимизированного под AVX2/512 интринсика.
Короче профиль точно не повредит.
Можно, но если уже есть подозрение на настоящее бутылочное горлышко, то почему бы и не проверить?
.. в 2.5 раза быстрее C. «Как же так? Не верю! Что происходит!? В Debian-версии GCC отключены какие-то оптимизации? Надо включить всё.» - вертелось у меня в голове.
Так у вас же исходный код на Scheme перебирает только простые делители до n/2, а не все подряд до n/2, как на остальных языках? Простых чисел до n примерно n/ln(n), у вас алгоритм на Scheme выполняет примерно в 6 раз меньше операций.
Потом, конечно, алгоритм уже везде одинаковый.
Сначала вы сравнили алгоритмы с разной ассимптотической сложностию.
Потом, вместо того, чтобы написать эффективный алгоритм на C - вы стали вкорячивать в решение на C плохую реализацию Scheme.
Потом вывод "есть смысл сперва делать MVP на высокоуровневом языке" - разумеется да, но вот угадывать "во сколько раз C будет быстрее" по мне так дело неблагодарное.
Уверен, что способов "схватить замедление вдвое на банальной операции" в том же PyPy масса. И это без привлечения памяти, а с памятью (и неудачной раскладке по кэшам) - можно во сколько угодно раз замедлится "почти" на пустом месте.
Ну и по поводу Scheme, ведь сравнение могло бы выглядеть и так:
C, решение 1
сложность(грубо) N^2 / log(N)
Время = 2 сек.
// был не прав по поводу оптимизации "проверяем все меньшие" vs "проверяем меньшие до sqrt(N)" - там ассимптоты очень похожи.
Scheme, решение 1
сложность N^2 / log(n)^2
время: 1 сек
С, лучшее решение (решето эратосфена):
сложность N*log(N)
время: 0.005 сек
Scheme, лучшее решение... хД
ПС
Ваша статья напомнила мне, когда я пол-года назад разбирался с Haskell (хороший своеобразный, но уж слишком академический язык) - так и подмывало написать статью типа "как ведёт себя Haskell, на произвольных задачах, а не только на красивых".
Задача была не написать самый быстрый алгоритм, а проверить поведение компиляторов на примерно одинаковых вычислительных нагрузках. Решето эратосфена и на Scheme, и на PyPy будет работать быстрее. Но при этом, решето и памяти потребует больше.
Да, первое решение на Scheme отличалось. Но, онять же, асимптотика асимптотикой, но есть ещё и технические детали: кэши, проверки типов в runtime, аллокация cons-ов - это тоже влияет на сложность алгоритма и поведение программы.
Потом вычисления были примерно одинаковые. И если Вы обратите внимание на числа, то перебор только простых делителей ускорил программы примерно в 10 раз. Чего я и ожидал изначально от реализации Scheme. В тексте так и написано.
Так на самом деле это код, где оптимизировать буквально некуда, никакой компилятор менять алгоритм не будет, а написаны 2 простейших цикла, которые крайне сложно как то улучшить в ассемблере
Вы невнимательно читали. Это текст не про выяснение возможностей компиляторов C и C++, в которых у меня не было сомнений (зря, как показало сравнение с Clang, и вот несколькими комментариями выше - с Haskell), а про выяснение возможностей компиляторов Python и Scheme. И это желание возникло от того, что программа на Scheme отработала быстрее программы, исполняемой простым Pyhton, в 40 раз. Я ожидал ускорения раз в 10.
Дальше вычислительные нагрузки были одинаковыми.
Есть два утверждения:
1. "PyPy примерно вдвое медленнее C"
2. "На очень простом тесте, где компилятору просто негде облажаться PyPy примерно вдвое медленнее С".
Вы измерили вариант-2, но почему-то преподносите его как вариант-1. Без доказательства, что (в целом приемлемое замедление вдвое) будет сохраняться, при усложнении структуры вычислений.
Собственно, поэтому и был написан вариант-2, чтобы работа с памятью на Си оказалась примерно сравнимой с тем, что делает Python. Всё же не закончилось на итерации 1.
Какой более сложный алгоритм удовлетворил бы Вас? Только без больших входных данных.
Какой более сложный алгоритм удовлетворил бы Вас? Только без больших входных данных.
Э... даже теряюсь как объяснить, что по 1й точке поведение ф-ии не измеряется.
Какой 1 тест оставить в SPEC чтобы он всех устроил (спойлер - заранее непонятно на каком сценарии какой компилятор и где просядет, поэтому добавляют разные, принципиально разные, кэйсы).
Собственно именно поэтому подход "одного ЧЯ-теста" изначально неверный и вопрос "найдите мне серебрянную пулю" некорректный.
Собственно, поэтому и был написан вариант-2, чтобы работа с памятью на
Си оказалась примерно сравнимой с тем, что делает Python.
Но вы же просто сильнее исследовали одну точку, вместо того, чтобы по бОльшему количеству точек хотя бы прикинуть общую картину.
Вообще я бы пошёл или "методом белого ящика" или "методом чёрного ящика".
Методом Б.Я. я бы проверил кэйсы-кандидаты на отсутствие оптимизаций в PyPy (список не исчерпывающий, есть ещё много чего, но боюсь что-то "тяжёлое" типа лямбд \ декораторов... PyPy просто не компилит):
- map -> list / list -> map
- hashmap / tree
- list of objects(PyPy) vs list of structures (C) - "боксинг\анбоксинг в PyPy нет, но вдруг что вылезет".
- встроенные генераторы / генераторы + yeild
// кто представляет устройство Python + PyPy лучше меня добавьте других кандидатов, подозреваю, что сходу много чего пропустил.
Методом Ч.Я. я бы проверял так:
Взять условный "adventofcode за любой год" (он мне нравится по ряду причин - на нём я проверял Haskell, и планирую Rust) или любой другой набор не слишком примитивных, но и не сложных тестов.
Реализовать всё, отписаться о результатах.
Среднее "усложнение написание" vs "увеличение времени работы".
Можно также посмотреть на наличие/отсутствие корреляции.
Вы описали полноценную научную работу, а не развлечение выходного дня. За научную работу можно было бы взяться, но где потом такое публиковать? Я же всё делал just for fun, а не для глубоких результатов. Специально написал, что никого ни в чём не собираюсь убеждать.
Благодарю за идею с advent of code.
Как написавший большой коммент, не мог пройти момо и не написать код.
Оказалось, что хранение списков, а также map, filter и lambda (избыточные в коде, но всё-же) не вызывают видимого увеличения времени работы.
Да не смотрел что будет с кодом, насыщенным try-except
ПС
Правда моя оценка (ещё более простого кода, чем у вас) C-perf / PyPy-perf = 3.5.
Так что по прошествии суток, я бы сказал, что оценка замедления PyPy относительно C, как x2 - x4 (если не делать жуктих perf-ошибок) имеет право на жизнь.
В принципе прошло 3 месяца всего можно ещё собраться с мыслями.
Но если совсем тезисно, то критика звучала бы так (хорошее вы и без меня знаете), возможно немного сумбурно:
Статьи от сообщества про Хаскель: они явно демонстрируют best case, создавая завышенные ожидания.
200 часов явно недостаточно, в смысле instrument-mastery и чувствую себя довольно неуклюже, пытаясь решить какие-то реальные проблемы (конечно если решать на Хаскель только каждую 10-ую задачу будет ок).
Хаскель требует отдельного instrument-mastery, best-practics... о чём, к стати в статьях не говорится.
Не по-порядку но важно: язык очень сильно смещает акцент с "алгоритмов" на "структуры данных" (не знаю как это правильно описать). Сюда же: буквально у каждой строчки кода есть "законченное состояние", это прикольно и хорошо.
Вообще есть ощущение, что "если писать всё в манаде State - то нафига Хаскель", а если писать всё по-возможности чисто и функционально, то какая-нибудь внезапная не стоящая внимания деталь может потребовать вторые (а затем и третьи) 90% работы от тебя, на вроде бы пустом месте.
Вообще менять программу "чуть-чуть" очень легко и приятно, намного лучше чем, в ООП, но вот менять программу "средне" (я пытался сформулировать, лучшее что получилось - если приходится менять структуры данных) намного-намного больше работы, чем в ООП.
// Дальше обещанная критика "хорошие" вещи вы наверное знаете лучше меня.
Внезапно Хасель довольно многословен, ОСОБЕННО, если решать несвойственные ему задачи (State и аналоги просто ужасна как и массивы, может с непривычки).
Да и вообще весь синтаксис выглядит довольно неудачным (хороший он только в "подогнанных" учебных примерах), - тут много частных кэйсов можно и нужно приводить.
Хаскель требует повышенной ментальной нагрузки (помним про "всего лишь / целых" 200 часов опыта): через 3 часа я чувствую себя уставшим, голова не соображает...
Функции надо делать очень очень маленькими, соответственно и слоёв абстракций больше (Кажется не только по предыдущей причине, но и по какому-то внутреннему свойству языка). То есть "единицы кода" надо дробить мельче, чем ты к этому привык - мне не кажется, что это хорошо: 400 строк кода идеально раздробить на 20 функций по 20 строк, а на Хаскеле это будет 150 функций по 3 строчки.
Скомпилировалось-работает: оно в жизни совсем не так, как в статьях в интернете. От серьёзных ошибок (на каждой итерации вы приближаетесь к завершению) оно вас не защищает, а те ошибки от которых защищает - это обычно не слишком серьёзные низкоуровневые ошибки, неприятные, но быстро находимые\устроняемые. Самое полезное где "скомпилировалось-работает" пригодилось это рефакторинг, чуть более сложный, чем автоматический.
Да сюда не относится C/C++ UB - отсутствие такого поведения это, конечно же, благо.
через 3 часа я чувствую себя уставшим, голова не соображает...
У-ууу, это вы ещё на Питоне не писали... :-)
Я лично куда быстрее выматываюсь на каком-нибудь питоне. Кроме шуток, как тут рядом написали.
Я не шутил. Как я много где писал, у каждого из нас в голове есть собственный QC отдел для кода. Этот отдел QC позволяет выпускать только код, который с нашей точки зрения "безошибочный". На этом ломаются все исследования "зависимости числа ошибок в программах от языка".
Очевидно, что для достижения того же уровня ошибок на Питоне и на Хаскеле, с программой на Питоне придётся кратно больше работать мозгами. А на Хаскеле основную часть ошибок уберёт typechecker.
Основная доля ошибок в программах - это ошибки в алгоритмах, в логике, в моделях обрабатываемых явлений. Ошибки в типах, конечно, бывают, но они редки, сразу себя проявляют и легко исправимы.
На Python исправление ошибок кратно сложнее не будет. У Haskell недостаточно мощная система типов, чтобы выявлять алгоритмические ошибки. А если бы она была достаточно мощной, то не факт, что для её использования требовалось бы меньше интеллектуальных усилий. Даже для доказательства простейших свойств программ, вроде `reverse . reverse = id`, в продвинутых системах типов приходится попотеть (буквально).
Основная доля ошибок в программах - это ошибки в алгоритмах, в логике, в моделях обрабатываемых явлений.
Если вы используете так называемый "type driven development", то ошибки в типах вам показывают на ошибки в логике. Грубо говоря, вы закладываете какие-то инварианты в типы, вводя по новому типу на каждый чих.
Например, сейчас я пишу на Камле анализатор (в рамках обучения), в стиле nanopass. И там я каждый промежуточный язык описываю своим AST, стараясь вводить типы даже очень избыточно. Например, в 3-адресном коде у меня есть atomic_expression и complex_expression как два разных типа. А просто выражение описываетсяtype expression = Complex of complex_expression | Atomic of atomic_expression
В большинстве случаев выразительности системы
не хватит для описания инвариантов. Писал я компиляторы на Си, на Lisp, на Python, на Coq и на Haskell. Могу сравнивать. Haskell ничего полезного, сокращающего сложность, в процесс разработки по моим ощущениям не привносит. Типы работают в мелких искусственных примерах, но в реальных задачах эффект от них незначителен. Не с типами основные ошибки связаны. Тот же nanopass прекрасно работает и без типов.
Даже для доказательства простейших свойств программ, вроде `reverse . reverse = id`, в продвинутых системах типов приходится попотеть (буквально).
В программах на Питоне, в основном, ошибки сидят в ветках, которые не выполняются. То есть, во всяких обработчиках исключений, буквально из 2х строк - логики там почти никакой нет, но ошибки встречаются.
Это известная страшилка. Но на практике такое редко встречается. Ветка в коде появляется, потому что (сюрприз-сюрприз) обнаруживаются триггерирующие её данные, а не наоборот. А то, что в коде обрабатываются все конструкторы, не означает ни того, что вычисление реально пойдёт по некой конкретной ветке, она может быть мёртвой, ни того, что ветка запрограммирована правильно.
Да и потом, известно же, что типы покрывают 15% багов в JS (язык с весьма своеобразной семантикой, в "нормальных" языках такого бардака со значениями нет). 15% - это совсем не большая часть ошибок, и это не самые сложные ошибки.
К стати хочу задать вам вопрос.
Прикинул вчера, очень грубо "ощущений от Хаскеля" получается на 3 статьи ("ощущения" растянуть на 3 статьи - это явно перебор).
Как по-вашему, учитывая целевую аудиторию (целевая аудитория - как раз "я два года назад, когда увидел статьи с какими-то непонятными рассуждениями про Хаскель, ФП-подход...") лучше писать:
- терпимо по краткости но без примеров кода?
- разбить на 3 раздела: "совсем общее [подход сообщества]" "общее" "частное но важное"
- разбить на 3 раздела: "понравилось" "не понравилось" "особенности: не плохо\не хорошо"
?
Добрый день. Спасибо за статью.
На итерации 0, в коде на C++ и Python идёт итерация по всем числам [2; 250000] с последующей их проверкой на простоту. В Вашем коде на Scheme вы выкинули из данного интервала все четные числа.
Да, так и есть. Идея была в том, чтобы посмотреть, насколько дольше я буду писать более тонкий алгоритм, и насколько, в итоге, он окажется быстрее. За дополнительные 30 секунд работы, я выиграл в 2 раза в скорости.
Итерация 0 - это вместо введения. Объяснение, почему я вообще принялся, условно, Python с C++ сравнивать. Обычно это считается абсурдным занятием.
"На это зрелище смотреть никто не мог без слез"... Нет, ребята. Я уж как-нибудь продолжу на С++ работать. Ни в жисть не поверю, что его можно побить, когда он работает с большими блоками памяти. Да, вот прикол. В библиотеке кмпилятора от M$ есть одна простая функция- StrToD()- список аргументов не помню, но это неважно. Берет указатель на текстовую строку, возвращает число в двоичном формате и указатель на следующий за числом символ. Очевидна идея испльзовать такую полезную функцию для обработки больших текстовых строк с сотнями тысяч или миллионами чисел, разделенных там пробелом, запятой или чем-то подобным. Ну картируем текстовый файл и движемся в цикле, выдирая из него число за числом. Опаньки- тормозня страшная. Что такое? Идем отлаживать, благо исходный код имеется. Ну и что- казалось бы, все должно работать так. Ищем первый символ принадлежащий числу, затем идем дальше пока не встретим символ, числу не принадлежащий. преобразуем байты числа в его двоичное представление и возвращаем результат. А это умники что сделали- каждый раз при вызове функция сканирует строку целиком, пока не встретит нуль-терминатор. Зачем??? Ясно что если в строке записан миллион чисел, то тормоза неизбежны. Ну что, написал для забавы процедуру на ассемблере. Потом не раз ее корректировал, напарываясь на всяки экзотические строковые представления. Осталось еще на 64 бита ассемблере накатать.
en.cppreference.com/w/cpp/utility/from_chars
эта функция сразу знает размер, никакой лишней работы.
Сравнение получилось странное, потому что самая медленная часть получившегося кода у всех компиляторов - инструкция деления. Её производительность не сильно зависит от того, кто её скомпилировал. На моём процессоре под g++ если использовать профилировщик, останавливающий последнюю программу 100 раз в секунду, то 89% остановок попадают на инструкцию сразу после деления (у остановки небольшая погрешность, конечно). У других программ делений выполняется ровно столько же, поэтому можно вычесть что-нибудь, и разница в производительности сразу станет заметнее.
У меня программа от clang++ работает с той же скоростью, что и от g++. Когда я нашёл причину этого несоответствия, моей радости не было предела: похоже, это очередная победа AMD над Intel! Машинный код от g++ (и от pypy3) выполняет честное 64-битное деление, а clang++ сначала проверяет, влезает ли делитель в 32 бита, и выполняет 32-битное деление, если это возможно (а тут числа маленькие и это возможно всегда). Видимо, мой процессор интеллектуально анализирует делитель и автоматически выбирает самый быстрый алгоритм для каждой ситуации. Clang, похоже, знает это и не вставляет ненужную проверку при использовании -march=znver1.
C++ без оптимизации работает очень плохо, потому что с -O0 компиляторы сохраняют результаты всех операций на стек, а операторы инкремента, разыменования и сравнения итераторов вызываются на каждой итерации как полноценные функции.
Взял за основу primes-3.cpp, немного потестировал его под WSL/Ubuntu 20.04.
isqrtvssqrtf- 10% разницы в пользуsqrtf(для всей программы)clang++ -march=tigerlake vs no -march
1.5sec vs 2.4sec (версия с isqrt)
g++(v10.3) vsclang++(v10) примерно одинаково без указания-march, но при указании,g++десятой версии как будто ничего не знает про архитектуру и быстродействие его результата практически не меняется. Возможно, вg++11й версии это исправили, нет под рукой чтобы проверить.Процессор для опытов -- Intel Core i7
1165G7. Возможно, на дескптопном или серверном или просто другой модели процессора ситуация будет иной. Надо проверять. На каком-нибудь микроконтроллереisqrtможет оказаться производительнее, чемsqrtf.Вопрос быстродействия очень сложный и делать далеко идущие выводы, отталкиваясь от небольшого числа частных случаев, надо осторожно. Нужно реально проверять разные архитектуры, версии процессоров, понимать где бутылочные горлышки, от чего тормозит память или ломается предсказатель ветвлений и тому подобное.
-march? Кажется, без него что clang что gcc почти не используют богатство SSE и AVX.Выше уже писали, что основное время процессор выполняет целочисленное деление, поэтому, вроде как, большой разницы нет.
$ clang -O3 primes-3.c && time ./a.out 25000000
1565927
real 0m2.362s
$ clang -O3 primes-3.c && time ./a.out 25000000
1565927
real 0m2.362s
$ gcc -O3 primes-3.c && time ./a.out 25000000
1565927
real 0m3.757s
$ gcc -march=native -mtune=native -O3 primes-3.c && time ./a.out 25000000
1565927
real 0m3.790sА распараллелить это целочисленное деление же можно с помощью SSE/AVX.
В SIMD нет инструкции целочисленного деления.
Векторизовать его может только ICC со встроенной в компилятор библиотекой интринсиковых трюков (SVML), да и то для простых чисел ещё нужно убрать выход из цикла на каждой итерации.
Поэтому простые числа - плохой тест на оптимизацию кода компилятором, сложно на нём развернуться. В "жизни" не так часто бывает, чтобы всё упиралось в какую-то одну операцию.
<?
ini_set('max_execution_time',0);
error_reporting(E_ALL | E_STRICT);
function is_prime($n) {
for($p=2;$p<=$n/2;$p++) {
if($n%$p==0)
return 0;
}
return 1;
}
$time=time();
$n_primes=0;
for($n=2;$n<250001;$n++)
$n_primes+=is_prime($n);
echo $n_primes;
echo '<br>';
echo time()-$time;
PHP 8.1.4. x64. 55 секунд.
Мы просто будем реализовывать один и тот же несложный алгоритм, разыскивающий простые числа в некотором диапазоне, на нескольких языках программирования: C, C++, Scheme и Python — и смотреть, что с этим кодом могут сделать современные оптимизирующие компиляторы.
В середине 80-х прошлого столетия у всех на слуху был PL/1 и не просто PL/1, а оптимизирующий PL/1. Особенности его применения я тогда изложил в книге "Комплексирование программ в ОС ЕС":
Москва, Финансы и статистика, 1986. 133 с.
Книга посвящена проблеме организации связей между программами, написанными на различных языках программирования. Рассмотрены общие соглашения о связях и особые соглашения, принятые в различных трансляторах. Основное внимание уделено теоретическим и практическим аспектам связи программ, написанных на разных языках (Ассемблере, Фортране, ПЛ/1) с учетом специфики транслятора ПЛ/1, уровня F и оптимизирующего транслятора ПЛ/1.
Удивительное приключение в стране оптимизирующих компиляторов