Приглашаю вас в небольшое приключение выходного дня, в котором никто никому ничего не будет доказывать. Мы просто будем реализовывать один и тот же несложный алгоритм, разыскивающий простые числа в некотором диапазоне, на нескольких языках программирования: C, C++, Scheme и Python - и смотреть, что с этим кодом могут сделать современные оптимизирующие компиляторы. В процессе приключения мы увидим, что «динамический» не означает «совсем уж медленный», и посмотрим на приёмы программирования на Scheme, что, как мне кажется, можно сравнить с путешествием на экзотический остров.
Начало
Началось всё одним томным вечером, когда мне на глаза попалось видео, в котором автор сравнивал три языка программирования: Python, C и Ассемблер IA-32 - по продуктивности программиста и по эффективности полученного кода. Задача решается несложная: подсчитать количество простых чисел не больших 250000.
На мой взгляд, такая оценка - комбинация продуктивности и производительности - хорошо подходит для сравнения языков программирования. Поэтому мне стало интересно, какое место среди этих трёх языков займёт Scheme. При этом, мне хотелось проверить, насколько быстро Scheme позволит написать более сложный алгоритм, который позволит получить решение за меньшее время.
Scheme - язык с динамической типизацией, сборкой мусора, динамическими контекстами и замыканиями, от программ на котором не ожидаешь особой прыти. Ограничив перебор потенциальных делителей простыми числами, я рассчитывал получить код, работающий раз в 10 быстрее, чем программа на Python в видео. Вот asciicast реализации этой затеи.
Результат мягко говоря, удивил (уважаемый читатель, не торопись писать комментарий о sqrt(n); для большего драматического эффекта, я оставил эту деталь напоследок).
time scheme --script primes.scm
22044
real 0m1.408sТо есть, Chez Scheme успевает разобрать исходный текст, скомпилировать код (компилятор написан на Scheme) и выполнить его быстрее, чем прокрутит свои циклы полученный из исходника на C код, который даже память не трогает? «Да, ну, не может быть!» - подумал я: «Просто у автора видео медленный процессор.» Естественно, возникает желание проверить всё на одной машине, в данном случае на виртуальной в облаке Яндекс с такой вот конфигурацией.
|
|
|
|
|
|
|
|
|
|
Все исходные тексты, использованные дальше, выложены здесь
Итерация 0: Не верю!
Исходники на C и Python, взяты из ролика. Я полагаю, что все знакомы с Python и C, поэтому их можно не пояснять.
primes-0.c и primes-0.py
Hidden text
// primes-0.c
#include <stdio.h>
int is_prime(int n) {
for(int p = 2; p <= n/2; p++)
if (!(n % p))
return 0;
return 1;
}
void main() {
int n_primes = 0;
for(int n = 2; n < 250001; n++)
n_primes += is_prime(n);
printf("%d\n", n_primes);
}# primes-0.py
def is_prime(n):
for p in range(2, n//2 + 1):
if (not (n%p)):
return 0
return 1
n_primes = 0
for i in range(2, 250001):
n_primes += is_prime(i)
print(str(n_primes))Со Scheme, вероятно, знакомо меньше читателей, поэтому я буду объяснять, как устроен код.
; primes-0.scm
(define (prime? n P) (or (null? P)
(> (car P) (quotient n 2))
(and (positive? (remainder n (car P)))
(prime? n (cdr P)))))
(define primes (cons 2 '()))
(do ((n 3 (+ 2 n))
(P primes (if (not (prime? n primes)) P (begin (set-cdr! P (cons n '())) (cdr P)))))
((> n 250000) (display (length primes)) (newline)))Код primes-0.scm состоит из двух частей.
Часть первая. Процедура prime? возвращает #f (ложь), если находит простой делитель числа n в списке P. В ней использованы списки и логические конструкции Scheme.
Конструкции (or E1 ... En) и (and E1 ... En) работают по сокращённой схеме (short-circuiting). В C бы им соответствовали конструкции E1 || ... || En и E1 && ... && En.
Списки в Lisp со стародавних времён представляют cons-парами. Cons от constructor: в классическом определении символьных выражений (s-выражений), конструирование пары - единственный способ построения неатомарных значений, других конструкторов нет, отсюда и название. Пару конструирует процедура (примитивная, но обычно это не уточняют, в Scheme все процедуры равноправны) cons.
Список элементов - это пара (элемент, список остальных элементов). Из списка L можно получить новый список добавлением элемента e в голову: (cons e L). Список [1, 2, 3, 4] создаётся выражением (cons 1 (cons 2 (cons 3 (cons 4 '())))). Здесь '() - специальное атомарное значение, обозначающее пустой список.
Пары разбирают на первую и вторую компоненты процедуры car и cdr. Названия исторически связаны со способом представления пар в первой реализации Lisp на машине IBM 704. car - contents of the address part of the register, cdr - contents of the decrement part of the register. Под регистром подразумевается ячейка памяти. По одной ячейке на каждую cons-пару - Морфеус увидел бы в этом предназначение.
Если L - список, то (car L) возвращает первый элемент списка L, (cdr L) - остаток списка. Если L = [1, 2, 3, 4], то (car L) = 1 и (cdr L) = [2, 3, 4] = (cons 2 (cons 3 (cons 4 '()))).
Это понадобится чуть позже, но напишу об этом сразу. Scheme (как и многие другие диалекты Lisp) позволяет изменять значения полей cons-ячеек процедурами set-car! и set-cdr!.
Приняв во внимание вышесказанное, код prime?
; primes-0.scm
(define (prime? n P) (or (null? P)
(> (car P) (quotient n 2))
(and (positive? (remainder n (car P)))
(prime? n (cdr P)))))можно прочитать так: (prime? n P) - истина,
если
(null? P)- список закончился;или если не закончился, то если
(> (car P) (quotient n 2))- очередной простое число достаточно большое, и дальше проверять смысла нет;-
или если смысл проверять есть, то:
если
(positive? (remainder n (car P)))- текущее простое число не делитn,и тогда, если
(prime? n (cdr P))- в остатке списка простых чисел не найдётся делителя дляn.
Стандарт Scheme гарантирует, что в этом случае вызов (prime? n (cdr P)) будет хвостовым, то есть, стек кадров активации процедур не будет расти. Поэтому можно считать, что prime? - реализация цикла.
Вторая часть последовательно перебирает целые числа n от 3 до 250000 c шагом 2 и, обнаружив простое число, добавляет его в конец списка простых чисел primes. Переменная P - курсор, указывающий на этот конец. Реализован этот процесс циклом do
(do ((V1 I1 U1) ... (Vn In Un))
(C E1 ... Ek)
B1
...
Bm)Работает это так:
В области видимости
doсоздаются переменныеV1, ...,Vn. КаждаяVjинициализируется значением соответствующего выраженияIj.На каждой итерации цикла
Vjобновляется значением выраженияUj. Цикл завершается, когда выражениеСстановится истинным, перед выходом из цикла исполняются выраженияE1, ...,Ek. Значением всего выраженияdoстановится результатEk.На каждой итерации выполняются выражения в теле цикла
B1, ...,Bn.
В do в тексте primes-0.scm
(do ((n 3 (+ 2 n))
(P primes (if (not (prime? n primes)) P (begin (set-cdr! P (cons n '())) (cdr P)))))
((> n 250000) (display (length primes)) (newline)))вероятно, самым мудрёным является выражение для обновления переменной P, указывающей на последнюю cons-пару списка primes:
(if (not (prime? n primes)) P (begin (set-cdr! P (cons n '())) (cdr P)))В нём проверяется простота n. Если n не простое, то возвращается значение P без изменений. Если простое, то во второй элемент cons-пары P записывается ссылка на новую cons-пару, содержащую атомарный список [n]. Эта ссылка возвращается последним выражением блока begin - (cdr P) - и становится новым значением переменной P. Инвариант цикла: P указывает на последнюю cons-пару списка primes - сохраняется.
Посмотрим, насколько быстро это всё работает.
$ gcc primes-0.c && time ./a.out
22044
real 0m3.854sАвтор ролика грубо пошутил над питонистами, забыв о том, что они вооружены JIT-компилятором PyPy, который отлично справляется в данном случае.
$ time pypy primes-0.py
22044
real 0m4.859sScheme ...
$ time scheme --script primes-0.scm
22044
real 0m1.468s.. в 2.5 раза быстрее C. «Как же так? Не верю! Что происходит!? В Debian-версии GCC отключены какие-то оптимизации? Надо включить всё.» - вертелось у меня в голове.
$ gcc -O3 primes-0.c && time ./a.out
22044
real 0m2.769s«Да что же это такое!?» - вопрошал мой уже слегка воспалённый разум. Но раз в ход пошла агрессивная оптимизация, то, для полноты картины, нужно применить её и для программы на Scheme.
Во-первых, нужно заменить всю арифметику на арифметику с fixnum-ами. В Lisp fixnum-ами называют целые числа, работа с которыми гарантированно осуществляется напрямую, без boxing-а, то есть, не по ссылкам.
primes-fx-0.scm
Hidden text
; primes-fx-0.scm
(define (prime? n P) (or (null? P)
(fx> (car P) (fxquotient n 2))
(and (fxpositive? (fxremainder n (car P)))
(prime? n (cdr P)))))
(define primes (cons 2 '()))
(do ((n 3 (fx+ 2 n))
(P primes (if (prime? n primes) (begin (set-cdr! P (cons n '())) (cdr P)) P)))
((fx> n 250000) (display (length primes)) (newline)))Во-вторых, нужно разрешить компилятору пуститься во все тяжкие.
$ time scheme --optimize-level 3 --script primes-fx-0.scm
22044
real 0m0.538sОптимизированный код на C, не работающий с памятью, оказался в 5 раз медленней оптимизированного кода на Scheme (языке с динамической типизацией, сборкой мусора), вовсю использующим для своей работы динамическую структуру данных и с циклами в виде рекурсии!?
Вечер стремительно терял свою томность.
Итерация 1: Алгоритмизируй это!
Я был готов к тому, что алгоритмы побеждают грубую силу. Но я не ожидал такого результата (ведь, перебор шёл не до sqrt(n)). Мне захотелось выяснить, насколько компилятор Chez Scheme хорош.
Нужно реализовать похожие алгоритмы на Python, C++ и C, и сравнить.
На Python и C++ это довольно просто сделать. Списки в Python позволяют быстро добавлять элементы в конец. В стандартном C++ есть векторы с более плотной упаковкой значений в памяти и амортизированным добавлением элементов в конец (в этой части моего приключения C++ и появился по этой причине).
Код на C++ и Python должен быть понятен.
python-1.cpp и python-1.py
Hidden text
// primes-1.cpp
#include <iostream>
#include <vector>
using std::vector;
static bool is_prime(const long n, const vector<long> &P) {
for (auto p : P) {
if (p > n / 2) return true;
if (!(n % p)) return false;
}
return true;
}
int main(int argc, char *argv[]) {
if (argc < 2) {
std::cerr << "Specify limit" << std::endl;
exit(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;
}# primes-1.py
import sys
def is_prime(n, P):
for p in P:
if p > n//2: return True
if not (n%p): return False
return True
limit = int(sys.argv[1])
primes = [2]
for n in range(3, limit + 1, 2):
if is_prime(n, primes): primes.append(n)
print(len(primes))Код на Scheme отличается от primes-fx-0.scm тем, что граница поиска простых чисел считывается из командной строки выражением: (string->number (cadr (command-line))). В котором загадочной может показаться процедура cadr. Обычно её определяют так:
(define (cadr L) (car (cdr L)))cadr извлекает первую компоненту из второй cons-пары списка, то есть, второй элемент списка.
primes-1.scm
Hidden text
; primes-1.scm
(define (prime? n P)
(or (null? P)
(fx> (car P) (fxquotient n 2))
(and (fxpositive? (fxremainder n (car P)))
(prime? n (cdr P)))))
(define N (string->number (cadr (command-line))))
(define primes (cons 2 '()))
(do ((n 3 (fx+ 2 n))
(P primes (if (prime? n primes) (begin (set-cdr! P (cons n '())) (cdr P)) P)))
((fx> n N) (display (length primes)) (newline)))Программа на C - калька программы на Scheme с одним отличием. В процессе подсчёта найденных простых чисел в функции counting_free освобождается занятая память. Конкретно в этой программе освобождать память не нужно: ядро ОС освободит ресурсы завершённого процесса. Но в Python и Scheme есть сборщики мусора. В программе на C++ будет вызван деструктор вектора. Поэтому постараемся и на C быть аккуратными.
primes-1.c
Hidden text
// primes-1.c
#include <stdio.h>
#include <stdlib.h>
typedef struct cons {
long p;
struct cons *next;
} Cons;
static Cons *cons(const long v) {
Cons *const c = malloc(sizeof(Cons));
c->p = v;
c->next = NULL;
return c;
}
static int is_prime(const long n, const Cons *const list) {
const Cons *P = list;
for (const Cons *P = list; P; P = P->next) {
if (P->p > n/1) return 1;
if (n % P->p == 0) return 0;
}
return 1;
}
static long counting_free(Cons *const list) {
long n = 0;
const Cons *P = list;
while(P) {
const Cons *const next = P->next;
free((void *) P);
n++;
P = next;
}
return n;
}
int main(int argc, char *argv[]) {
if (argc < 2) {
fprintf(stderr, "Specify limit\n");
return 1;
}
const long N = atol(argv[1]);
Cons *const primes = cons(2);
Cons *P = primes;
for(long n = 3; n <= N; n += 2) {
if (is_prime(n, primes)) {
P->next = cons(n);
P = P->next;
}
}
printf("%ld\n", counting_free(primes));
return 0;
}
Запускаем наших претендентов.
$ time scheme --script primes-1.scm 250000
22044
real 0m1.156s
$ g++ primes-1.cpp && time ./a.out 250000
22044
real 0m1.231s
$ gcc primes-1.c && time ./a.out 250000
22044
real 0m0.972s
$ time pypy primes-1.py 250000
22044
real 0m0.505s«Да вы издеваетесь! PyPy!?» PyPy оказался резвее всех, завершив вычисление почти в 2 раза быстрее ближайшего конкурента. Программы на C++ и С не слишком далеко оторвались от программы на Scheme. Включение 3-го уровня оптимизации сделало программу на C++ в 2.5 раза быстрее (на самом деле, неожиданный и неприятный сюрприз), но значительно превзойти результат PyPy это не позволило. А программа на C оказалась медленней программы на Scheme.
$ gcc -O3 primes-1.c && time ./a.out 250000
22044
real 0m0.862s
$ time scheme --optimize-level 3 --script primes-1.scm 250000
22044
real 0m0.514s
$ g++ -O3 primes-1.cpp && time ./a.out 250000
22044
real 0m0.459s«Да что же это такое!?»
Итерация 2: Дединамизируй это!
Знакомые, посмотрев на безобразие, предположили, что «это» - работа с кучей, и предложили избавиться от malloc-ов. «Что же делать? Где там мой page size?» - подумал я и принялся за дело.
Первый на этой итерации вариант программы на C реализует всё тот же алгоритм, но хранит обнаруженные простые числа в массиве, размер которого увеличивается по необходимости на одну страницу памяти обращением к realloc. Единственная хитрость в коде - подсказка GCC о более вероятном значении выражения A->cursor = A->len при помощи __builtin_expect.
primes-2.c
Hidden text
// primes-2.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
typedef struct {
long *restrict buf;
long len;
long cursor;
} Array;
static Array make_array() {
const long pagelen = sysconf(_SC_PAGESIZE) / sizeof(long);
return (Array) {
.buf = malloc(pagelen * sizeof(long)),
.len = pagelen,
.cursor = 0 };
}
#define unlikely(X) __builtin_expect((X), 0)
static void push(const long val, Array *restrict const A) {
if (unlikely(A->cursor >= A->len)) {
A->len += sysconf(_SC_PAGESIZE) / sizeof(long);
A->buf = realloc(A->buf, A->len * sizeof(long));
}
A->buf[A->cursor++] = val;
}
static long counting_free(Array *restrict const A) {
free(A->buf);
A->buf = NULL;
return A->cursor;
}
static int is_prime(const long n, const Array *restrict const P) {
for (int i = 0; i < P->cursor; i++) {
const long p = P->buf[i];
if (p > n / 2) return 1;
if (n % p == 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]);
Array primes = make_array();
push(2, &primes);
for(long n = 3; n <= N; n += 2)
if (is_prime(n, &primes)) push(n, &primes);
printf("%ld\n", counting_free(&primes));
return 0;
}
Такая стратегия работы с памятью позволяет libc использовать механизм виртуальной памяти для релокации массива, чтобы избежать явного копирования данных на новое место. Вместо копирования достаточно перенастраивать таблицу трансляции виртуальных адресов процесса системным вызовом mremap. Что и происходит:
$ gcc primes-2.c && strace ./a.out 250000
...
mremap(0x7f60f2ce0000, 172032, 176128, MREMAP_MAYMOVE) = 0x7f60f2ce0000
mremap(0x7f60f2ce0000, 176128, 180224, MREMAP_MAYMOVE) = 0x7f60f2ce0000
...Снизить интенсивность запросов на выделение памяти можно и в программе на Scheme. Современные Lisp-ы (Chez Scheme не исключение), поддерживают разные виды массивов. Но в стандартной библиотеке Chez нет процедур для эффективного изменения размеров массивов: нужно вручную создавать новый массив с большим размером и копировать в него данные.
Однко можно применить чуть более сложную структуру данных: список fixnum-массивов (fxvector), где каждый вектор размером со страницу. Для каждой такой страницы нужно хранить курсор, указатель на очередной свободный элемент массива. Курсором может быть нулевой элемент вектора. Сказано - сделано.
primes-2.scm
Hidden text
; primes-2.scm
(define page-length 512)
(define (cursor P) (fxvector-ref P 0))
(define (cursor-set! P c) (fxvector-set! P 0 c))
(define (make-page n)
(let ((P (make-fxvector page-length)))
(cursor-set! P 2)
(fxvector-set! P 1 n)
P))
(define (push! n P)
(let ((A (car P))
(c (cursor (car P))))
(if (fx< c (fxvector-length A))
(begin (fxvector-set! A c n)
(cursor-set! A (fx1+ c))
P)
(begin (set-cdr! P (cons (make-page n) '()))
(cdr P)))))
(define (prime? n pages)
(let ((l (fxquotient n 2)))
(let next ((P pages))
(or (null? P)
(let ((A (car P))
(c (cursor (car P))))
(let loop ((i 1))
(if (fx< i c)
(let ((p (fxvector-ref A i)))
(or (fx> p l)
(and (fxpositive? (fxremainder n p))
(loop (fx1+ i)))))
(next (cdr P)))))))))
(define (count P)
(do ((p P (cdr p))
(S 0 (fx+ S (cursor (car p)) -1)))
((null? p) S)))
(let ((N (string->number (cadr (command-line))))
(primes (cons (make-page 2) '())))
(do ((n 3 (fx+ 2 n))
(P primes (if (prime? n primes) (push! n P) P)))
((> n N) (display (count primes)) (newline))))
Первые три процедуры в primes-2.scm задают «архитектуру» страницы.
(define (cursor P) (fxvector-ref P 0))
(define (cursor-set! P c) (fxvector-set! P 0 c))
(define (make-page n)
(let ((P (make-fxvector page-length)))
(cursor-set! P 2)
(fxvector-set! P 1 n)
P))fxvector-ref и fxvector-set! - процедуры для чтения и записи элементов вектора. Процедура make-fxvector создаёт вектор запрошенного размера, инициализируя его нулями.
Конструкция (let ((V1 E1) ... (VN EN)) B1 ... BK) используется для определения переменных в локальной для выражений тела (Bi) области видимости. По смыслу эта конструкция эквивалентна выражению
((lambda (V1 ... VN) B1 ... BK) E1 ... EN)Этот код создаёт анонимную процедуру, параметры которой названы нужным образом, и вызывает её со значениями выражений, которые связываются с соответствующими именам. В резальтате Bi выполняются с нужными значениями переменных Vi.
Процедура push! реализована бесхитростно.
(define (push! n P)
(let ((A (car P))
(c (cursor (car P))))
(if (fx< c (fxvector-length A))
(begin (fxvector-set! A c n)
(cursor-set! A (fx1+ c))
P)
(begin (set-cdr! P (cons (make-page n) '()))
(cdr P)))))Она предполагает, что P указывает на последнюю cons-пару в списке страниц с простыми числами. Если на этой странице осталось место, то на это место записывается число n и курсор сдвигается. Если места нет, создаётся новая страница, в начало которой записывается n, эта страница упаковывается в новую cons-пару, которая «подшивается» в конец списка, и ссылка на этот новый конец списка возвращается.
В процедуре prime? применён другой вариант let: (let N ((V1 E1) ... (VN EN)) B1 ... BK). По смыслу он эквивалентен выражению:
((rec N (lamda (V ...) B ...)) E ...)(rec N E) - оператор неподвижной точки, то есть, он вычисляет выражение E, в окружении, в котором E - значение переменной N.
Например (rec ones (stream-cons 1 ones) будет потоком из единиц:
> (stream->list (stream-take 10 (rec ones (stream-cons 1 ones))))
(1 1 1 1 1 1 1 1 1 1)Или, например, используя rec, можно классическим функциональным способом определить последовательность Фибоначчи
> (stream->list
(stream-take 20
(rec fibs (stream-cons 0 (stream-cons 1 (stream-map + fibs (stream-cdr fibs)))))))
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)Таким образом, выражение
((rec N (lamda (V1 ... VN) B1 ... BK)) E1 ... EN)задаёт процедуру, которая может рекурсивно вызывать себя по имени N, и применяет её к некоторым аргументам. Чувствую, что ещё один пример не помешает. Традиционный пример: факториал.
> ((rec loop (lambda (n r) (if (zero? n) r (loop (- n 1) (* n r))))) 10 1)
3628800Или, эквивалентно, в форме let:
(let loop ((n 10) (r 1)) (if (zero? n) r (loop (- n 1) (* n r))))Вместе с хвостовыми вызовами такой вариант let позволяет описывать циклы со сложной логикой работы, множественными точками передачи управления и выходами.
(define (prime? n pages)
(let ((l (fxquotient n 2)))
(let next ((P pages))
(or (null? P)
(let loop ((i 1))
(if (fx< i (cursor (car P)))
(let ((p (fxvector-ref (car P) i)))
(or (fx> p l)
(and (fxpositive? (fxremainder n p))
(loop (fx1+ i)))))
(next (cdr P))))))))В prime? два цикла: next по списку страниц с простыми числами, и loop по простым числам внутри страницы. Первый выход из next происходит, когда заканчивается список - (null? P) возвращает истину, и эта истина становится результатом внешнего or.
Если же в списке есть страницы, то с первой из них, (car P), начинает работу цикл loop. Если числа на странице закончились - условие (fx< i (cursor (car P)) стало ложным, то происходит переход на следующую итерацию цикла next с оставшимся списком страниц: (next (cdr P)). Если числа есть, тогда берётся очередное простое число p. Если оно достаточно больше, or останавливается на истинном условии (fx> p l), и эта истина возвращается из обоих циклов. В противном случае, если p делит n, циклы возвращают ложь. А если p не делит n, простота n будет протестирована на следующей итерации loop очередным делителем на текущей странице: (loop (fx1+ i)).
Остаток кода: подсчёт количества чисел, записанных в список страниц, и основной цикл программы - должны быть понятны. Основной цикл реализует ту же логику, что и в prime-1.scm.
В первый вариант prime-2.scm прокралась ошибка (для тестирования возможностей компиляторов). Вместо того, чтобы вычислить границу для перебора простых делителей как n/2, то есть (fxquotient n 2), в оптимизаторском порыве я таки посчитал её, как (isqrt n), то есть, как ceil(sqrt(n)). От этого, естественно, объём вычислений и, соответственно, время работы резко сократились.
time scheme --script primes-3.scm 250000
22044
real 0m0.100s«Ну это уже ни в какие ворота!» - подумал я, увидев это, и решил, что с realloc или GCC что-то не так. Пытаясь исключить из тормозов realloc я переписал логику primes-2.scm на C. В процессе переписывания ошибку я заметил, но не пропадать же добру. primes-21.c - калька c primes-2.scm, с одной особенностью: страницы связываются в список не через отдельные cons-пары, а через указатели next, хранящиеся на самих страницах.
primes-21.c
Hidden text
// primes-21.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define PAGE_CAPACITY 510
typedef struct page {
struct page *restrict next;
long cursor;
long numbers[PAGE_CAPACITY];
} Page;
Page *make_page(const long n) {
Page *const P = malloc(sizeof(Page));
P->next = NULL;
P->cursor = 1;
P->numbers[0] = n;
return P;
}
#define likely(X) __builtin_expect((X), 1) // __
Page *push(Page *restrict const P, const long n) {
if (likely((P->cursor < PAGE_CAPACITY))) {
P->numbers[P->cursor++] = n;
return P;
}
return P->next = make_page(n);
}
int is_prime(const Page *restrict const pages, const long n) {
const long l = n / 2;
for (const Page *restrict P = pages; P; P = P->next) {
for (int i = 0; i < P->cursor; i++) {
const long p = P->numbers[i];
if (p > l) return 1;
if (n % p == 0) return 0;
}
}
return 1;
}
long counting_free(const Page *restrict const pages) {
const Page *restrict P = pages;
long cnt = 0;
while (P) {
const Page *const next = P->next;
cnt += P->cursor;
free((void *)P);
P = next;
}
return cnt;
}
int main(int argc, char *argv[]) {
if (argc < 2) {
fprintf(stderr, "Specify limit\n");
return 1;
}
const long N = atol(argv[1]);
Page *restrict const primes = make_page(2);
Page *restrict P = primes;
for (long n = 3; n <= N; n += 2) {
if (is_prime(primes, n)) P = push(P, n);
}
printf("%ld\n", counting_free(primes));
return 0;
}
Итак, волнительный момент запуска.
$ gcc -O3 primes-2.c && time ./a.out 250000
22044
real 0m0.469s
$ gcc -O3 primes-21.c && time ./a.out 250000
22044
real 0m0.464s
$ time scheme --optimize-level 3 --script primes-2.scm 250000
22044
real 0m0.517s
«Во дела...» Код на C оказывается всего на 11% быстрее кода на Scheme. И оказывается, что работа realloc через механизмы виртуальной памяти не так уж сильно и помогает. Может быть, нужно считать больше, чтобы гарантированно выпасть из кэшей?
$ gcc -O3 primes-2.c && time ./a.out 2500000
183072
real 0m31.376s
$ gcc -O3 primes-21.c && time ./a.out 2500000
183072
real 0m31.323s
$ time scheme --optimize-level 3 --script primes-2.scm 2500000
183072
real 0m31.930s
2$ time pypy ../1/primes-1.py 2500000
183072
real 0m32.191sНемая сцена, в которой Жан-Люк Пикар молча прикладывает ладонь к лицу.
Итерация 3: Маловато будет.
Конечно, с границей для перебора делителей в n/2 много простых чисел не насчитаешь. Нужно перебирать до isqrt(n). Код программ итерации 3 только этим и отличается от кода программ итерации 2. Не буду приводить его здесь, он сохранён в gist.
С такими программами можно посчитать и до 25E+6.
$ g++ -O3 primes-3.cpp && time ./a.out 25000000
1565927
real 0m3.726s
$ gcc -O3 primes-3.c && time ./a.out 25000000
1565927
real 0m3.717s
$ gcc -O3 primes-31.c && time ./a.out 25000000
1565927
real 0m3.776s
$ time pypy primes-3.py 25000000
1565927
real 0m5.423s
$ time scheme --optimize-level 3 --script primes-3.scm 25000000
1565927
real 0m6.003s«Фьюх!..» Картина мира восстановлена. Программа на C в 1.45 раза быстрее программы на Python и в 1.6 раза быстрее программы на Scheme. Хотя, маловато, конечно, будет:
fixnum-ы в Scheme - не то же самое, что 64 битовые целые, арифметическая работа с fixnum-ами более замороченная;
структуа данных в программе на Scheme несколько сложнее;
Не полностью удовлетворённый результатом, я решил испытать Clang.
clang --version
Debian clang version 11.0.1-2
$ clang -O3 primes-3.c && time ./a.out 25000000
1565927
real 0m2.385s
$ clang -O3 primes-31.c && time ./a.out 25000000
1565927
real 0m2.388s
$ clang++ -O3 primes-3.cpp && time ./a.out 25000000
1565927
real 0m2.448s
$ clang primes-31.c && time ./a.out 25000000
1565927
real 0m4.667s
$ clang++ primes-3.cpp && time ./a.out 25000000
1565927
real 0m8.583s
$ clang primes-3.c && time ./a.out 25000000
1565927
real 0m4.590sКогда я увидел это, в глаза мне попала соринка то ли радости, то ли разочарования. Здесь требуется дальнейший анализ происходящего. Почему GCC выдаёт в 1.6 более медленный код, чем Clang? Почему неоптимизированная версия кода на C++ настолько хуже оптимизированной и при использовании Clang, и при использовании GCC? Но это требует вычитки получающегося машинного кода, на что у меня уже не оставалось времени.
Заключение
Scheme и Python языки динамические (PyPy работает только с программами, в которых он может статически вывести типы, но это программы на Python). Scheme совсем-совсем динамический, в этом языке даже нет обычных целых чисел фиксированной длинны: 32 битовых или 64 битовых. Fixnum-ы - значения в специальной кодировке, содержащей тип. Добавьте к этому сборку мусора, динамические контексты, замыкания, в которые превращается lambda, реализацию циклов (do - тоже макрос) через рекурсивные вызовы процедур (пусть и хвостовые).
С учётом этого, то, что PyPy и Chez Scheme умудряются выдавать код, который в данной конкретной числодробильной по своей природе задаче, работает всего лишь в 2.5 раза медленней, чем код, оптимизированный на 3-ем уровне системой LLVM (в которую вложено на пару порядков больше труда), удивляет.
Для себя из всего этого приключения я сделал вывод: имеет смысл писать прототипы алгоритмов на Python или Scheme, не только по той причине, что это проще и в написании, и в отладке, но и по той причине, что они позволяют получить некоторую базовую оценку производительности, к которой нужно стремиться. А то, ведь, есть риск, программируя на C++, получить, вроде как, естественную для задачи реализацию, которая будет раза в четыре медленней оптимальной.
Благодарю за внимание.
P.S. Если Вы хотите, чтобы я позапускал Ваши реализации primes на той самой виртуальной машине, чтобы можно было сравнить результаты, присылайте, пожалуйста, pull-реквесты сюда: https://github.com/mbakhterev/primes
Комментарии (71)
dikey_0ficial
03.04.2022 19:13+1интересно было бы ещё сравнить аналогичный код на го, который считается довольно быстрым языком)
vkni
03.04.2022 19:36+1Иногда есть функция divmod, то есть, вам выдаётся одновременно и остаток и частное от деления. Если сравнить частное от деления с текущим проверяемым числом, можно получить примерно тот же результат, что и с sqrt.
sibirier
03.04.2022 20:15+1Код на Lua (адаптация v31 кода)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 не проверялsibirier
03.04.2022 21:22+1С код#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 тоже относительно легко. одни плюсы.
mikhanoid Автор
03.04.2022 21:51История с виртуальной памятью не такая простая, как может показаться. Реальное выделение физической памяти непростой процесс, и он может занимать довольно много времени.
napa3um
04.04.2022 22:34+1Надо ещё отметить, что
mallocна самом деле не к операционке за памятью идёт, а откусывает её от уже выделенной процессу (где-то перед стартом функцииmainRTL себе резервирует шмоточек, и к операционке идёт лишь тогда, когда закончились эти запасы). Есть альтернативные аллокаторы с другими профилями / эвристиками распределения памяти, один из самых известных, например, - https://github.com/google/tcmalloc (а тут можно взглянуть на изощрённость подкапотной логики подобных библ).
0xd34df00d
03.04.2022 22:09+6Мм, сравнения языков, не могу пройти мимо!
Хаскель-версия с проверкой до
n / 2, написанная примерно за три минуты, с ленивыми неэффективными для кэша списками и с завязыванием узла (чистый иммутабельныйpsиспользуется внутриisPrimeпри построении себя же):{-# 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 (<= (n `div` 2)) ps main :: IO () main = do [cnt] <- getArgs print $ length $ primes $ read cntВремя работы — 0.700 с на моей машине (ghc 8.10, кодогенерирующий бекенд — LLVM 13). Для сравнения, ваша плюсовая версия — 0.94 с с gcc 11, 0.5 с с clang 13 (
-O3в обоих случаях)Та же версия, только с заменой
(n `div` 2)на(floor $ sqrt $ fromIntegral n)(ну, короче, считать до корня), и с аналогичными заменами для плюсов, на 25000000 числах — тут уже хаскель выигрывает и у gcc, и у clang.
ghc: 4.6 секунд, clang: 8.6 с, gcc: 7.7 с. Добавление-march=nativeи/или-ftree-vectorizeвлияет на плюсовые результаты в пределах погрешности.mikhanoid Автор
03.04.2022 22:20Где-нибудь можно почитать об оптимизациях, которые выполняет современный Haskell? Тут явно одним deforestation не обошлось.
0xd34df00d
03.04.2022 22:34Боюсь, что нет, даже для разработчиков ghc нет какого-то централизованного описания всех оптимизаций. А то самому было бы интересно.
mikhanoid Автор
04.04.2022 00:39+1Попробовал почитать ассемблер. Ничего на вскидку не понятно. Нужно сидеть с IDA, разбираться. Но судя по strace, Haskell делает нечто ооочень странное.
0xd34df00d
04.04.2022 16:49+2Как раз хотел пожелать удачи в соседнем комментарии — хаскель из-за ленивости (и ещё отчасти по историческим причинам) генерирует совершенно нечитабельный ассемблер. Я уже давно туда не смотрю.
vkni
04.04.2022 19:34Даже через llvm backend?
0xd34df00d
04.04.2022 20:22+1Да. LLVM соптимизирует горячие циклы и числовые операции, но calling convention, семантика ленивости и все такое остаются теми же, так как модули, собранные LLVM, должны уметь работать с модулями, собранными NCG.
Inspector-Due
05.04.2022 15:32Если я ничего не попутал, то вот мои результаты:
Первая версия (до `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++ 250000001565927 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
250000001565927 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 такой же результат)
DustCn
03.04.2022 23:27+2Вот опять статья про оптимизацию кода, и ни одного профиля приложения. Ну как так то?
mikhanoid Автор
04.04.2022 00:07+1Так код простой, и без профилей всё понятно. Разве нет?
Armleo
04.04.2022 10:59+3Нет, непонятно. Вы гадайте по кофейной гуще. Я не верю в данные результаты.
Можно на профиль посмотреть хотя бы?
mikhanoid Автор
04.04.2022 12:07+1Так разве кто запрещает? Можно конечно! Исходники все открыты.
На машине я обновил версии ПО, поэтому всё надо замерять заново. У меня нет на неделе на это времени. Sorry. В следующий раз сделаю с профилями.
Благодарю за указание на этот недочёт.
0xd34df00d
04.04.2022 16:51+3Вы гадайте по кофейной гуще. Я не верю в данные результаты.
Почему? Автор берёт, компилирует всю программу и замеряет всё время ей выполнения. Тут ИМХО нет особого пространства для недоверия.
svr_91
04.04.2022 17:10+1Тут как указывали выше вполне может быть разница из-за подхода с работой с памятью. Я видел пару раз, когда языки с gc выигрывали у языков без gc просто из-за разной механики работы с памятью. Взять другой аллокатор - и результат будет совсем иной
0xd34df00d
04.04.2022 17:46+2Так для этого достаточно показывать тайминг, опции сборки и опции запуска. Автор все это вроде делает.
Профиль может помочь разобраться, что вызывает тормоза, но на уровень доверия к цифрам он точно влиять не должен. Да и некоторые оптимизации (вроде снижения проверок от n/2 до корня) вполне себе априорно разумны и никакие не гадания на кофейной гуще.
svr_91
04.04.2022 17:55Если время работы измеряет не то, на что оно тратится, то какое тут доверие? Если мы измеряем время работы стандартного аллокатора, а не алгоритма, то зачем мы писали алгоритм?
0xd34df00d
04.04.2022 18:02+1Мы измеряем время работы не аллокатора, а всей программы целиком.
svr_91
04.04.2022 18:32На первой работе я тоже один раз услышал такую формулировку. А потом мы часть алгоритма переписали (не связано с аллокатором, там другая проблема была), и то что мы должны были исследовать до этого, внезапно оказалось бутылочным горлышком. А обнаружили бы раньше, и проблемы бы не было
0xd34df00d
04.04.2022 18:54+1Естественно, на некотором этапе профилирование оказывается полезным, чтобы понять, что делать дальше. Но некоторые оптимизации, особенно в самом начале, особенно для тривиальных алгоритмов, отлично можно делать и без прогонов профайлера.
DustCn
04.04.2022 19:04Можно, но раз уже пишешь статью, а потом оказывается что у тебя тормоза не в коде, а в syscall и непонятно что и где... Очень странно не использовать возможности профилирования, имеющиеся наверное в любом чайнике. Какую функию копирования использует программа с -О2 и с О3? В одном случае может быть вызов glibc, во втором инлайнинг оптимизированного под AVX2/512 интринсика.
Короче профиль точно не повредит.
svr_91
04.04.2022 20:19Можно, но если уже есть подозрение на настоящее бутылочное горлышко, то почему бы и не проверить?
yeputons
04.04.2022 00:19+6.. в 2.5 раза быстрее C. «Как же так? Не верю! Что происходит!? В Debian-версии GCC отключены какие-то оптимизации? Надо включить всё.» - вертелось у меня в голове.
Так у вас же исходный код на Scheme перебирает только простые делители до n/2, а не все подряд до n/2, как на остальных языках? Простых чисел до n примерно n/ln(n), у вас алгоритм на Scheme выполняет примерно в 6 раз меньше операций.
Потом, конечно, алгоритм уже везде одинаковый.
WASD1
04.04.2022 02:48+7Сначала вы сравнили алгоритмы с разной ассимптотической сложностию.
Потом, вместо того, чтобы написать эффективный алгоритм на 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, на произвольных задачах, а не только накрасивых".mikhanoid Автор
04.04.2022 07:42Задача была не написать самый быстрый алгоритм, а проверить поведение компиляторов на примерно одинаковых вычислительных нагрузках. Решето эратосфена и на Scheme, и на PyPy будет работать быстрее. Но при этом, решето и памяти потребует больше.
Да, первое решение на Scheme отличалось. Но, онять же, асимптотика асимптотикой, но есть ещё и технические детали: кэши, проверки типов в runtime, аллокация cons-ов - это тоже влияет на сложность алгоритма и поведение программы.
Потом вычисления были примерно одинаковые. И если Вы обратите внимание на числа, то перебор только простых делителей ускорил программы примерно в 10 раз. Чего я и ожидал изначально от реализации Scheme. В тексте так и написано.
Kelbon
04.04.2022 08:11Так на самом деле это код, где оптимизировать буквально некуда, никакой компилятор менять алгоритм не будет, а написаны 2 простейших цикла, которые крайне сложно как то улучшить в ассемблере
mikhanoid Автор
04.04.2022 08:32Вы невнимательно читали. Это текст не про выяснение возможностей компиляторов C и C++, в которых у меня не было сомнений (зря, как показало сравнение с Clang, и вот несколькими комментариями выше - с Haskell), а про выяснение возможностей компиляторов Python и Scheme. И это желание возникло от того, что программа на Scheme отработала быстрее программы, исполняемой простым Pyhton, в 40 раз. Я ожидал ускорения раз в 10.
Дальше вычислительные нагрузки были одинаковыми.
WASD1
04.04.2022 12:25Есть два утверждения:
1. "PyPy примерно вдвое медленнее C"
2. "На очень простом тесте, где компилятору просто негде облажаться PyPy примерно вдвое медленнее С".
Вы измерили вариант-2, но почему-то преподносите его как вариант-1. Без доказательства, что (в целом приемлемое замедление вдвое) будет сохраняться, при усложнении структуры вычислений.mikhanoid Автор
04.04.2022 13:23Собственно, поэтому и был написан вариант-2, чтобы работа с памятью на Си оказалась примерно сравнимой с тем, что делает Python. Всё же не закончилось на итерации 1.
Какой более сложный алгоритм удовлетворил бы Вас? Только без больших входных данных.
WASD1
04.04.2022 15:00Какой более сложный алгоритм удовлетворил бы Вас? Только без больших входных данных.
Э... даже теряюсь как объяснить, что по 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 "увеличение времени работы".
Можно также посмотреть на наличие/отсутствие корреляции.
mikhanoid Автор
04.04.2022 15:17Вы описали полноценную научную работу, а не развлечение выходного дня. За научную работу можно было бы взяться, но где потом такое публиковать? Я же всё делал just for fun, а не для глубоких результатов. Специально написал, что никого ни в чём не собираюсь убеждать.
Благодарю за идею с advent of code.
WASD1
04.04.2022 17:32Как написавший большой коммент, не мог пройти момо и не написать код.
Оказалось, что хранение списков, а также map, filter и lambda (избыточные в коде, но всё-же) не вызывают видимого увеличения времени работы.
Да не смотрел что будет с кодом, насыщенным try-except
ПС
Правда моя оценка (ещё более простого кода, чем у вас) C-perf / PyPy-perf = 3.5.Так что по прошествии суток, я бы сказал, что оценка замедления PyPy относительно C, как x2 - x4 (если не делать жуктих perf-ошибок) имеет право на жизнь.
0xd34df00d
04.04.2022 16:52Ваша статья напомнила мне, когда я пол-года назад разбирался с Haskell (хороший своеобразный, но уж слишком академический язык) — так и подмывало написать статью типа "как ведёт себя Haskell, на произвольных задачах, а не только на красивых".
Было бы, кстати, очень интересно, потому что в моём опыте он нормально себя ведёт и на произвольных задачах. В худшем случае придётся использовать
ST, и вы всё равно ничего не теряете по сравнению с более привычными языками.WASD1
04.04.2022 17:29+1В принципе прошло 3 месяца всего можно ещё собраться с мыслями.
Но если совсем тезисно, то критика звучала бы так (хорошее вы и без меня знаете), возможно немного сумбурно:
Статьи от сообщества про Хаскель: они явно демонстрируют best case, создавая завышенные ожидания.
200 часов явно недостаточно, в смысле instrument-mastery и чувствую себя довольно неуклюже, пытаясь решить какие-то реальные проблемы (конечно если решать на Хаскель только каждую 10-ую задачу будет ок).
Хаскель требует отдельного instrument-mastery, best-practics... о чём, к стати в статьях не говорится.
Не по-порядку но важно: язык очень сильно смещает акцент с "алгоритмов" на "структуры данных" (не знаю как это правильно описать). Сюда же: буквально у каждой строчки кода есть "законченное состояние", это прикольно и хорошо.
Вообще есть ощущение, что "если писать всё в манаде State - то нафига Хаскель", а если писать всё по-возможности чисто и функционально, то какая-нибудь внезапная не стоящая внимания деталь может потребовать вторые (а затем и третьи) 90% работы от тебя, на вроде бы пустом месте.
Вообще менять программу "чуть-чуть" очень легко и приятно, намного лучше чем, в ООП, но вот менять программу "средне" (я пытался сформулировать, лучшее что получилось - если приходится менять структуры данных) намного-намного больше работы, чем в ООП.
// Дальше обещанная критика "хорошие" вещи вы наверное знаете лучше меня.
Внезапно Хасель довольно многословен, ОСОБЕННО, если решать несвойственные ему задачи (State и аналоги просто ужасна как и массивы, может с непривычки).
Да и вообще весь синтаксис выглядит довольно неудачным (хороший он только в "подогнанных" учебных примерах), - тут много частных кэйсов можно и нужно приводить.
Хаскель требует повышенной ментальной нагрузки (помним про "всего лишь / целых" 200 часов опыта): через 3 часа я чувствую себя уставшим, голова не соображает...
Функции надо делать очень очень маленькими, соответственно и слоёв абстракций больше (Кажется не только по предыдущей причине, но и по какому-то внутреннему свойству языка). То есть "единицы кода" надо дробить мельче, чем ты к этому привык - мне не кажется, что это хорошо: 400 строк кода идеально раздробить на 20 функций по 20 строк, а на Хаскеле это будет 150 функций по 3 строчки.
-
Скомпилировалось-работает: оно в жизни совсем не так, как в статьях в интернете. От серьёзных ошибок (на каждой итерации вы приближаетесь к завершению) оно вас не защищает, а те ошибки от которых защищает - это обычно не слишком серьёзные низкоуровневые ошибки, неприятные, но быстро находимые\устроняемые. Самое полезное где "скомпилировалось-работает" пригодилось это рефакторинг, чуть более сложный, чем автоматический.
Да сюда не относится C/C++ UB - отсутствие такого поведения это, конечно же, благо.
vkni
04.04.2022 19:33+3через 3 часа я чувствую себя уставшим, голова не соображает...
У-ууу, это вы ещё на Питоне не писали... :-)
WASD1
05.04.2022 16:44+1К стати хочу задать вам вопрос.
Прикинул вчера, очень грубо "ощущений от Хаскеля" получается на 3 статьи ("ощущения" растянуть на 3 статьи - это явно перебор).Как по-вашему, учитывая целевую аудиторию (целевая аудитория - как раз "я два года назад, когда увидел статьи с какими-то непонятными рассуждениями про Хаскель, ФП-подход...") лучше писать:
- терпимо по краткости но без примеров кода?
- разбить на 3 раздела: "совсем общее [подход сообщества]" "общее" "частное но важное"
- разбить на 3 раздела: "понравилось" "не понравилось" "особенности: не плохо\не хорошо"
?
-
noolo
04.04.2022 10:09+3Добрый день. Спасибо за статью.
На итерации 0, в коде на C++ и Python идёт итерация по всем числам [2; 250000] с последующей их проверкой на простоту. В Вашем коде на Scheme вы выкинули из данного интервала все четные числа.mikhanoid Автор
04.04.2022 12:22-1Да, так и есть. Идея была в том, чтобы посмотреть, насколько дольше я буду писать более тонкий алгоритм, и насколько, в итоге, он окажется быстрее. За дополнительные 30 секунд работы, я выиграл в 2 раза в скорости.
Итерация 0 - это вместо введения. Объяснение, почему я вообще принялся, условно, Python с C++ сравнивать. Обычно это считается абсурдным занятием.
Butterfly_M
04.04.2022 14:39+2"На это зрелище смотреть никто не мог без слез"... Нет, ребята. Я уж как-нибудь продолжу на С++ работать. Ни в жисть не поверю, что его можно побить, когда он работает с большими блоками памяти. Да, вот прикол. В библиотеке кмпилятора от M$ есть одна простая функция- StrToD()- список аргументов не помню, но это неважно. Берет указатель на текстовую строку, возвращает число в двоичном формате и указатель на следующий за числом символ. Очевидна идея испльзовать такую полезную функцию для обработки больших текстовых строк с сотнями тысяч или миллионами чисел, разделенных там пробелом, запятой или чем-то подобным. Ну картируем текстовый файл и движемся в цикле, выдирая из него число за числом. Опаньки- тормозня страшная. Что такое? Идем отлаживать, благо исходный код имеется. Ну и что- казалось бы, все должно работать так. Ищем первый символ принадлежащий числу, затем идем дальше пока не встретим символ, числу не принадлежащий. преобразуем байты числа в его двоичное представление и возвращаем результат. А это умники что сделали- каждый раз при вызове функция сканирует строку целиком, пока не встретит нуль-терминатор. Зачем??? Ясно что если в строке записан миллион чисел, то тормоза неизбежны. Ну что, написал для забавы процедуру на ассемблере. Потом не раз ее корректировал, напарываясь на всяки экзотические строковые представления. Осталось еще на 64 бита ассемблере накатать.
mapron
04.04.2022 18:53from_chars сравните с актуальным MSVC
en.cppreference.com/w/cpp/utility/from_chars
эта функция сразу знает размер, никакой лишней работы.
notsomeone12469
04.04.2022 15:13+2Сравнение получилось странное, потому что самая медленная часть получившегося кода у всех компиляторов - инструкция деления. Её производительность не сильно зависит от того, кто её скомпилировал. На моём процессоре под g++ если использовать профилировщик, останавливающий последнюю программу 100 раз в секунду, то 89% остановок попадают на инструкцию сразу после деления (у остановки небольшая погрешность, конечно). У других программ делений выполняется ровно столько же, поэтому можно вычесть что-нибудь, и разница в производительности сразу станет заметнее.
У меня программа от clang++ работает с той же скоростью, что и от g++. Когда я нашёл причину этого несоответствия, моей радости не было предела: похоже, это очередная победа AMD над Intel! Машинный код от g++ (и от pypy3) выполняет честное 64-битное деление, а clang++ сначала проверяет, влезает ли делитель в 32 бита, и выполняет 32-битное деление, если это возможно (а тут числа маленькие и это возможно всегда). Видимо, мой процессор интеллектуально анализирует делитель и автоматически выбирает самый быстрый алгоритм для каждой ситуации. Clang, похоже, знает это и не вставляет ненужную проверку при использовании -march=znver1.
C++ без оптимизации работает очень плохо, потому что с -O0 компиляторы сохраняют результаты всех операций на стек, а операторы инкремента, разыменования и сравнения итераторов вызываются на каждой итерации как полноценные функции.
fiego
04.04.2022 16:31Взял за основу 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.Вопрос быстродействия очень сложный и делать далеко идущие выводы, отталкиваясь от небольшого числа частных случаев, надо осторожно. Нужно реально проверять разные архитектуры, версии процессоров, понимать где бутылочные горлышки, от чего тормозит память или ломается предсказатель ветвлений и тому подобное.
Ktator
04.04.2022 17:56+1А что насчёт ключа
-march? Кажется, без него что clang что gcc почти не используют богатство SSE и AVX.mikhanoid Автор
04.04.2022 19:56Выше уже писали, что основное время процессор выполняет целочисленное деление, поэтому, вроде как, большой разницы нет.
$ 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
mafia8
05.04.2022 11:18+1PHP:
<? 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 секунд.
Kelbon
А можно вектор зарезервить?
vector<long> primes = {2}; for(long n = 3; n <= limit; n += 2) { if (is_prime(n, primes)) { primes.push_back(n); } }mikhanoid Автор
Можно, наверное. Но резервить сразу под все значения, вроде как, не спортивно. А небольшой резерв не особо изменит общую картину, потому что размер буфера наращивается по экспоненте.
Да и идея была в том, что программы на Python и C++ примерно одинаковые по структуре.
Kelbon
эм, ну придётся допустим 2 раза перекладывать, это и есть основное что выполняет эта программа в итоге. В питоне и прочих языках это не вектор, а какая то мапа в которой нет реаллокации при вставке
mikhanoid Автор
Если посмотреть через strace, то видно, что тоже не происходит копирования. C++ версия тоже работает через remap-ы.
Kelbon
может всё таки попробуете добавить резерв или заменить vector на std::deque, а не говорить про какие то ремапы?
sibirier
добавление резервирования почти нужного количества памяти для сокращения большого кол-ва реаллокаций (осталась одна(?)) почти не повлияла на результат. всё-таки push_back выполняется сильно меньше раз, чем вычисление простоты числа или корня. да и вектор не дурак, он, вроде как, выделяет не по одному дополнительному элементу, а раза в 2 больше каждый раз (это неточно, лучше проверить). то есть реаллокации не сильно влияют на скорость
даже выделение памяти с запасом не оказывает заметного влияния на результат.
все утверждения приведены после анализа результатов тестов.
добавлял вот такой код.
mikhanoid Автор
Я не против потестить предлагаемые варианты на той же машине в выходные, но на переписывание у меня пока нет времени. Могу завести хранилище под эту задачу на GitHub, чтобы Вы могли добавить туда интересующий Вас код.
svr_91
Если не хочется именно резервировать, можно попробовать поиспользовать разные аллокаторы (tcmalloc, jemalloc, etc). По сути это будет в каком-то смысле эквивалентно сборщику мусора в языках со сборокой мусора
mikhanoid Автор
Вы можете отправить pull-запрос с интересующим Вас кодом вот сюда: https://github.com/mbakhterev/primes
napa3um
Разница в скорости, по сути, вытекает именно из разницы в работе с динамическими структурами. GC позволяет откладывать все те вещи, которые в безколлекторных языках приходится производить на каждой итерации. Ну или руками придётся написать аналогичный механизм оптимального (отложенного и/или наоборот «предфечащего») управления ресурсами. Максимальной оптимизацией тут, действительно, станет резервирование сразу всей необходимой памяти (или хотя бы большими кусками, не реалоцируемыми максимально долго). Компиляторы функциональных языков благодаря имутабельности обрабатываемых структур данных и большему контролю потока вычислений потенциально могут произвести эту максимальную оптимизацию вплоть до статичного «многоэтажного» распределения памяти, когда переменные каждого последующего этапа алгоритма кладутся на память предыдущего вообще без вызова функций GC/аллокатора (компилятор уже точно знает, что через данную ячейку памяти связаны читатель с писателем уже нового поколения, а старые уже точно не оживут). Не знаю, делают ли реальные компиляторы так, но чисто теоретически не видится особых препятствий к этому :).
vkni
Есть ещё такая оптимизация как "partial evaluation", то есть, какой-нибудь Stalin или MLton в теории может вообще всё предвычислить.
napa3um
Слышал где-то байку про оптимизирующий компилятор Фортрана, которому, мол, скормили жирные исходники какого-то алгоритма решения какой-то сложной комбинаторной/геометрической задачи или типа того, он их ворочал-ворочал пару часов, и в итоге скомпилировал-оптимизировал в машинный код, эквивалентный коду
print 42(или типа того, где 42 - это уже окончательное решение задачи). :)Kelbon
Как может быть неспортивно просто выделить память под N элементов когда нужно N элементов...
mikhanoid Автор
Задача в том, чтобы сравнить поведение компиляторах и runtime на примерно одинаковой вычислительной нагрузке. Если в программе на Python весь массив сразу целиком не выделяется, и на Scheme не выделяется, и на C не выделяется, то почему он должен выделяться в программе на C++? Тогда уж надо писать такую версию кода на всех языках.
Да и потом, в C++, по сравнению с другими версиями, память выделяется более эффективно, размер массива растёт по экспоненте. То есть, требуется меньше этих самых реаллокаций.
Kelbon
... То есть то что может НЕ потребоваться реаллокация это вы игнорируете? С чего вы взяли, что все языки используют тупо динамический массив внутри?
mikhanoid Автор
Смотрел, как код на Python, Scheme и С++ выполняется, через strace. В коде на Си и так всё очевидно.