Databases
StackOverflow2013
Postsdbo
POFast bitarray in OCaml
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFast bitarray in OCaml
    text
    copied!<p>Yet another synthetic benchmark: <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow">Sieve of Eratosthenes</a></p> <p>C++</p> <pre><code>#include &lt;vector&gt; #include &lt;cmath&gt; void find_primes(int n, std::vector&lt;int&gt;&amp; out) { std::vector&lt;bool&gt; is_prime(n + 1, true); int last = sqrt(n); for (int i = 2; i &lt;= last; ++i) { if (is_prime[i]) { for (int j = i * i; j &lt;= n; j += i) { is_prime[j] = false; } } } for (unsigned i = 2; i &lt; is_prime.size(); ++i) { if (is_prime[i]) { out.push_back(i); } } } </code></pre> <p>OCaml (using <a href="http://janestreet.github.com/" rel="nofollow">Jane Street's Core</a> and <a href="https://bitbucket.org/mmottl/res" rel="nofollow">Res</a> libraries)</p> <pre><code>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 &lt;= 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 </code></pre> <p>I was surprised that OCaml version (native) is about 13 times slower than C++. I replaced <code>Res.Bits</code> with <code>Core_extended.Bitarray</code>, but it became ~18 times slower. Why it is so slow? Doesn't OCaml provide fast operations for bit manipulation? Is there any alternative fast implementation of bit arrays?</p> <p>To be clear: I'm from C++ world and consider OCaml as a possible alternative for writing performance critical code. Actually, I'm a bit scary with such results.</p> <p><strong>EDIT:</strong></p> <p>Profiling results</p> <pre><code>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 ... </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload