빠른 bitarray

Question

또 다른 합성 벤치 마크 : 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의 (사용 Jane Street's Core 및 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의 버전 (기본)에 놀랐다 C++보다 약 13 배 느리다. 나는 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 
... 

Answer 1

정교한 데이터 구조로 점프하기 전에 간단한 데이터 구조를 먼저 사용해 보셨습니까?

내 컴퓨터에서 다음 코드는 C++ 버전보다 4 배 속도가 느립니다 (배열을 캐시로 사용하기위한 최소한의 변경 사항과 결과를 누적하는 목록을 사용하므로 어레이 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 최초의 소수를 계산하기 4S, 대 실현 1S 코드에 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 

이 지금 당신의 C++ 솔루션보다 느린 배 만드는, 단 2 초 걸립니다.

Answer 2

결과. 이것은 OCaml이 뚜렷한 단점이있는 경우입니다. C++은 다소 이상적인 표현 (기계 정수의 벡터)에 액세스 할 수 있습니다. OCaml은 벡터를 만들 수 있지만 기계 정수를 직접 얻을 수는 없습니다. 그래서 OCaml은 div와 mod를 사용해야합니다. C++은 shift와 mask를 사용할 수 있습니다.

이 테스트를 (다른 비트 벡터 라이브러리를 사용하여) 재현 한 결과 비트 배열이 아닌 결과를 생성하는 데 OCaml의 상당한 시간이 소비되었음을 알게되었습니다. 따라서 테스트는 정확하게는입니다.

업데이트 저는 63 비트 INT에 32 부울 포장 몇 가지 빠른 테스트를 시도했다. 일이 더 빨라지지만, 조금만하는 것처럼 보입니다. 완벽한 테스트는 아니지만 2의 비 파워 (non-power-of-2) 효과가 작다는 것은 gasche가 옳다고 제안합니다.

Answer 3

제프리 스코필드가 맞는 것 같습니다. 이러한 끔찍한 성능 저하는 div 및 mod 작업으로 인한 것입니다.

는 I 그것은 바이트 어레이와 같은 문자열 (문자 당 8 비트)를 사용하여 작은 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 

시제품. 처음에는 비트 추출을 위해 x/8과 x mod 8을 사용했습니다. 그것은 C++ 코드보다 10 배 느립니다. 그런 다음 나는 x lsr 3과 x land 7으로 바꿨다. 이제 C++보다 4 배나 느립니다.

Answer 4

.cmx 파일 (.cmxa가 충분하지 않습니다!)을 포함하여 Core를 설치해야합니다. 그렇지 않으면 모듈 간 인라이닝이 작동하지 않습니다. 귀하의 프로필은 특정 통화가 인라인되지 않았을 수 있음을 보여 주며 이는 효율성의 극적인 저하를 설명합니다.

많은 OCaml 프로젝트에서 사용하는 Oasis 패키징 도구에는 현재 .cmx 파일을 설치할 수없는 버그가 있습니다. 핵심 패키지는 또한이 문제의 영향을받습니다. 아마도 어떤 패키지 관리자 (Opam, Godi)와 관계없이 사용하면됩니다.