BitArray veloce in OCaml

Question

Ancora un altro benchmark sintetico: Sieve of Eratosthenes

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 (utilizzando Jane Street's Core e Res librerie)

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 

sono rimasto sorpreso che la versione OCaml (nativo) è circa 13 volte più lento del C++. Ho sostituito Res.Bits con Core_extended.Bitarray, ma è diventato ~ 18 volte più lento. Perché è così lento? OCaml non fornisce operazioni veloci per la manipolazione dei bit? Esiste un'implementazione alternativa alternativa dei bit array?

Per essere chiari: sono del mondo C++ e considero OCaml come una possibile alternativa per scrivere codice critico delle prestazioni. In realtà, sono un po 'spaventoso con questi risultati.

EDIT:

Profiling risultati

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 
... 

Answer 1

Hai provato a utilizzare la semplice infrastruttura dati prima di saltare su quelli sofisticati?

Sulla mia macchina, il seguente codice è solo 4x più lento della versione C++ (si noti che ho apportato le modifiche minime per utilizzare una matrice come cache e un elenco per accumulare risultati; è possibile utilizzare l'array get/set zucchero sintattico):

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 

(4x più lento: ci vogliono 4s per calcolare i primi 10_000_000 numeri primi, contro 1s per g ++ -O1 o -O2 sul vostro codice)

Rendendosi conto che l'efficienza del vostro la soluzione bitvector probabilmente proviene dal layout della memoria economica, ho cambiato il codice per utilizzare stringhe invece di array:

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 

Questo prende ora solo 2s, il che lo rende più lento di 2x soluzione vostro C++.

Answer 2

Non capita spesso utile confrontare micro-benchmark in questo modo, ma la conclusione di base è probabilmente corretto. Questo è un caso in cui OCaml è in netto svantaggio. C++ può accedere a una rappresentazione più o meno ideale (vettore di numeri interi macchina). OCaml può fare un vettore, ma non può ottenere direttamente gli interi della macchina. Quindi OCaml deve usare div e mod dove C++ può usare shift e mask.

Ho riprodotto questo test (utilizzando una libreria di bit vettoriale diversa) e ho scoperto che il tempo apprezzabile in OCaml è stato dedicato alla costruzione del risultato, che non è un array di bit. Quindi il test potrebbe non misurare esattamente quello che pensi.

Aggiornamento

Ho provato alcuni test rapidi di imballaggio 32 booleani in un 63-bit int. Sembra che le cose vadano più velocemente, ma solo un po '. Non è un test perfetto, ma suggerisce che è giusto che l'effetto di non-potenza-2 sia minore.

Answer 3

Sembra che Jeffrey Scofield abbia ragione. Il peggioramento delle prestazioni è dovuto alle operazioni div e mod.

I prototyped piccolo Bitarray modulo

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 

Esso utilizza stringa come matrice di byte (8 bit per char). Inizialmente ho usato x/8 e x mod 8 per l'estrazione dei bit. Era 10 volte più lento del codice C++. Poi li ho sostituiti con x lsr 3 e x land 7. Ora, è solo 4x più lento del C++.

Answer 4

Assicurati di installare Core includendo il file .cmx (.cmxa non è sufficiente!), Altrimenti l'inlining tra moduli non funzionerà. Il tuo profilo suggerisce che alcune chiamate potrebbero non essere state sottolineate, il che spiegherebbe una drastica perdita di efficienza.

Purtroppo lo strumento di packaging Oasis, utilizzato da molti progetti OCaml, attualmente presenta un bug che impedisce l'installazione del file .cmx. Anche il pacchetto Core è interessato da questo problema, probabilmente a prescindere dal gestore di pacchetti (Opam, Godi) che usi.