Schnelle BitArray in OCaml

Question

Noch ein weiterer synthetischer Benchmark: 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 (mit Jane Street's Core und Res Bibliotheken)

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 

Ich war überrascht, dass OCaml-Version (nativ) ist etwa 13 mal langsamer als C++. Ich ersetzte Res.Bits durch Core_extended.Bitarray, aber es wurde ~ 18 mal langsamer. Warum ist es so langsam? Bietet OCaml keine schnellen Operationen für die Bit-Manipulation? Gibt es alternative schnelle Implementierung von Bit-Arrays?

Um es klar zu sagen: Ich komme aus der C++ Welt und halte OCaml für eine mögliche Alternative zum Schreiben von leistungskritischem Code. Eigentlich bin ich mit solchen Ergebnissen etwas unheimlich.

EDIT:

Profilierungsergebnisse

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

Haben Sie versucht, zuerst eine einfache Datenstruktur zu verwenden, bevor Sie auf die ausgereiften springen?

Auf meinem Computer ist der folgende Code nur 4x langsamer als Sie C++ - Version (beachten Sie, dass ich die minimalen Änderungen ein Array als Cache verwendet, und eine Liste, um Ergebnisse zu sammeln; Sie könnten das Array Get/Set verwenden syntaktischer Zucker):

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 langsamer: es nimmt 4s die 10_000_000 ersten Primzahlen, gegen 1s für g ++ -O1 oder -O2 auf Ihrem Code)

Erkenntnis zu berechnen, dass die Effizienz Ihrer Bitvector Lösung wahrscheinlich kommt aus dem wirtschaftlichen Speicher Layout, änderte ich den Code, umzu verwendenStrings anstelle von Arrays:

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 

Das dauert jetzt nur 2s, das macht es 2x langsamer als C++ Lösung.

Answer 2

Es ist nicht oft nützlich, Mikro-Benchmarks wie diese zu vergleichen, aber die grundlegende Schlussfolgerung ist wahrscheinlich richtig. Dies ist ein Fall, in dem OCaml eindeutig benachteiligt ist. C++ kann auf eine mehr oder weniger ideale Darstellung (Vektor von Maschinen-Ganzzahlen) zugreifen. OCaml kann einen Vektor erzeugen, kann aber nicht direkt auf die Maschinen-Ganzzahlen zugreifen. Also muss OCaml div und mod verwenden, wobei C++ Shift und Maske verwenden kann.

Ich reproduziert diesen Test (mit einer anderen Bit-Vektor-Bibliothek) und festgestellt, dass erhebliche Zeit in OCaml wurde das Konstruieren des Ergebnisses, die kein bisschen Array ist. So könnte der Test nicht genau was Sie denken.

aktualisieren

habe ich versucht, ein paar schnelle Tests 32 booleans in einen int 63-Bit-Verpackung. Es scheint die Dinge schneller laufen zu lassen, aber nur ein bisschen. Es ist kein perfekter Test, aber es deutet darauf hin, dass Gasche richtig ist, dass der Nicht-Power-of-2 Effekt gering ist.

Answer 3

Es scheint Jeffrey Scofield hat Recht. Eine solche Verschlechterung der Leistung ist auf die Operationen div und mod zurückzuführen.

I prototypisiert kleine Bitarray Modul

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 

Es verwendet Zeichenfolge als Byte-Array (8 Bits pro Zeichen). Anfangs habe ich x/8 und x mod 8 für Bit-Extraktion verwendet. Es war 10x langsamer als C++ - Code. Dann habe ich sie durch x lsr 3 und x land 7 ersetzt. Jetzt ist es nur 4x langsamer als C++.

Answer 4

Bitte stellen Sie sicher, dass Sie Core einschließlich der .cmx-Datei installieren (.cmxa ist nicht genug!), Sonst funktioniert das Modul-übergreifende Inlining nicht. Ihr Profil weist darauf hin, dass bestimmte Anrufe möglicherweise nicht in die Warteschlange gestellt wurden, was einen dramatischen Effizienzverlust erklären würde.

Leider enthält das Oasis-Paketierungstool, das in vielen OCaml-Projekten verwendet wird, derzeit einen Fehler, der die Installation der .cmx-Datei verhindert. Das Core-Paket ist ebenfalls von diesem Problem betroffen, wahrscheinlich unabhängig davon, welchen Paketmanager (Opam, Godi) Sie verwenden.