Быстрый битрейр в OCaml
Еще один синтетический тест: Сито Эратосфена
C ++
#include <vector>
#include <cmath>
void find_primes(int n, std::vector<int>& out)
{
std::vector<bool> is_prime(n + 1, true);
int last = sqrt(n);
for (int i = 2; i <= last; ++i)
{
if (is_prime[i])
{
for (int j = i * i; j <= n; j += i)
{
is_prime[j] = false;
}
}
}
for (unsigned i = 2; i < is_prime.size(); ++i)
{
if (is_prime[i])
{
out.push_back(i);
}
}
}
OCaml (используя Ядро Стрит Ядро а также Res библиотеки)
open Core.Std
module Bits = Res.Bits
module Vect = Res.Array
let find_primes n =
let is_prime = Bits.make (n + 1) true in
let last = float n |! sqrt |! Float.iround_exn ~dir:`Zero in
for i = 2 to last do
if not (Bits.get is_prime i) then () else begin
let j = ref (i * i) in
while !j <= n; do
Bits.set is_prime !j false;
j := !j + i;
done;
end;
done;
let ar = Vect.empty () in
for i = 2 to n do
if Bits.get is_prime i then Vect.add_one ar i else ()
done;
ar
Я был удивлен, что версия OCaml (нативная) примерно в 13 раз медленнее, чем C ++. Я заменил Res.Bits с Core_extended.Bitarray, но это стало ~ 18 раз медленнее. Почему это так медленно? Разве OCaml не обеспечивает быстрых операций для битовых манипуляций? Есть ли альтернатива быстрой реализации битовых массивов?
Чтобы было ясно: я из мира C ++ и рассматриваю OCaml как возможную альтернативу для написания кода, критичного к производительности. На самом деле, мне немного страшно с такими результатами.
РЕДАКТИРОВАТЬ:
Результаты профилирования
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
50.81 1.26 1.26 camlRes__pos_1113
9.72 1.50 0.24 camlRes__unsafe_get_1117
6.68 1.66 0.17 camlRes__unsafe_set_1122
6.28 1.82 0.16 camlNopres_impl__set_1054
6.07 1.97 0.15 camlNopres_impl__get_1051
5.47 2.10 0.14 47786824 0.00 0.00 caml_apply3
3.64 2.19 0.09 22106943 0.00 0.00 caml_apply2
2.43 2.25 0.06 817003 0.00 0.00 caml_oldify_one
2.02 2.30 0.05 1 50.00 265.14 camlPrimes__find_primes_64139
1.21 2.33 0.03 camlRes__unsafe_get_1041
...
Решение
Вы пробовали использовать простую структуру данных, прежде чем переходить к сложным?
На моей машине следующий код работает только в 4 раза медленнее, чем ваша версия C ++ (обратите внимание, что я внес минимальные изменения, чтобы использовать массив в качестве кэша и список для накопления результатов; вы можете использовать массив get / set синтаксический сахар):
let find_primes n =
let is_prime = Array.make (n + 1) true in
let last = int_of_float (sqrt (float n)) in
for i = 2 to last do
if not (Array.get is_prime i) then () else begin
let j = ref (i * i) in
while !j <= n; do
Array.set is_prime !j false;
j := !j + i;
done;
end;
done;
let ar = ref [] in
for i = 2 to n do
if Array.get is_prime i then ar := i :: !ar else ()
done;
ar
(В 4 раза медленнее: для вычисления первых 10_000_000 простых чисел требуется 4 с против 1 с
для g ++ -O1 или -O2 в вашем коде)
Понимая, что эффективность вашего решения bitvector, вероятно,
исходит из экономичной памяти, я изменил код для использования
строки вместо массивов:
let find_primes n =
let is_prime = String.make (n + 1) '0' in
let last = int_of_float (sqrt (float n)) in
for i = 2 to last do
if not (String.get is_prime i = '0') then () else begin
let j = ref (i * i) in
while !j <= n; do
String.set is_prime !j '1';
j := !j + i;
done;
end;
done;
let ar = ref [] in
for i = 2 to n do
if String.get is_prime i = '0' then ar := i :: !ar else ()
done;
ar
Теперь это занимает всего 2 секунды, что делает его в 2 раза медленнее, чем ваш C ++
решение.
Другие решения
Кажется, Джеффри Скофилд прав. Такое ужасное снижение производительности связано с div а также mod операции.
Я прототип маленького Bitarray модуль
module Bitarray = struct
type t = { len : int; buf : string }
let create len x =
let init = (if x = true then '\255' else '\000') in
let buf = String.make (len / 8 + 1) init in
{ len = len; buf = buf }
let get t i =
let ch = int_of_char (t.buf.[i lsr 3]) in
let mask = 1 lsl (i land 7) in
(ch land mask) <> 0
let set t i b =
let index = i lsr 3 in
let ch = int_of_char (t.buf.[index]) in
let mask = 1 lsl (i land 7) in
let new_ch = if b then (ch lor mask) else (ch land lnot mask) in
t.buf.[index] <- char_of_int new_ch
end
Он использует строку как байтовый массив (8 бит на символ). Изначально я использовал x / 8 а также x mod 8 для извлечения бит. Это было в 10 раз медленнее, чем код C ++. Затем я заменил их x lsr 3 а также x land 7, Теперь он всего в 4 раза медленнее, чем C ++.
Часто сравнивать микропроцессоры не очень полезно, но основной вывод, вероятно, правильный. Это тот случай, когда OCaml имеет явный недостаток. C ++ может получить доступ к более или менее идеальному представлению (вектор машинных целых чисел). OCaml может создать вектор, но не может получить целые числа машины напрямую. Поэтому OCaml должен использовать div и mod, где C ++ может использовать shift и mask.
Я воспроизвел этот тест (используя другую библиотеку битовых векторов) и обнаружил, что значительное время в OCaml было потрачено на создание результата, а не массива битов. Таким образом, тест может не измерять именно так что ты думаешь.
Обновить
Я попробовал несколько быстрых тестов, упаковывающих 32 логических значения в 63-битное целое. Кажется, что это заставляет дела идти быстрее, но только немного. Это не идеальный тест, но он предполагает, что Гаш прав, что эффект не-степени-2 незначителен.
Пожалуйста, убедитесь, что вы устанавливаете Core, включая файл .cmx (недостаточно .cmxa!), Иначе межмодульное встраивание не будет работать. Ваш профиль предполагает, что некоторые звонки не были встроены, что может объяснить резкую потерю эффективности.
К сожалению, в инструменте упаковки Oasis, который используется во многих проектах OCaml, в настоящее время есть ошибка, которая не позволяет ему установить файл .cmx. Пакет Core также подвержен этой проблеме, возможно, независимо от того, какой менеджер пакетов (Opam, Godi) вы используете.