4 ms·
Careful here. Let's take a simple example of allocation-heavy vs. allocation-light code in OCaml: open Batteries let bench name fn = let tstart = Unix
by rbehrends 9y ago
Careful here. Let's take a simple example of allocation-heavy vs. allocation-light code in OCaml:
open Batteries
let bench name fn =
let tstart = Unix.gettimeofday () in
let result = fn () in
let tend = Unix.gettimeofday () in
Printf.printf "%-20s %.3f seconds\n" name (tend -. tstart);
result
let iterations = 100000
let count = 1000
let insert_list_test () =
let result = ref 0 in
for i = 1 to iterations do
let work = ref [] in
for j = 1 to count do
work := j :: !work
done;
work := List.rev !work;
result := !result + List.length !work
done;
!result
let insert_list_test_rec () =
let rec build_list i n acc =
if i > n then acc
else build_list (i+1) n (i :: acc)
in
Enum.map
(fun _ -> build_list 1 count [] |> List.rev |> List.length)
(1--iterations)
|> Enum.fold (+) 0
let insert_dynarray_test () =
let result = ref 0 in
for i = 1 to iterations do
let work = DynArray.create () in
for j = 1 to count do
DynArray.add work j
done;
result := !result + DynArray.length work
done;
!result
let main () =
let x1 = bench "linked lists" insert_list_test in
let x2 = bench "linked lists (rec)" insert_list_test_rec in
let x3 = bench "dynamic arrays" insert_dynarray_test in
assert (x1 = x2 && x2 = x3)
let () = main ()
As it turns out, this gives us the following results on my laptop, give or take a few hundreds of seconds:
linked lists 0.648 seconds
linked lists (rec) 0.657 seconds
dynamic arrays 1.295 seconds
The reason that the linked list implementation (functional or imperative) is faster is that OCaml's GC uses a bump allocator for young objects, with allocations being inlined by the compiler; this essentially makes the linked list implementation behave like an arena allocator and is faster than the dynamic array version (which has to resize and copy the underlying array several times), despite having to do a gratuitous list reversal and doing an O(n) length calculation. (Note that this is not specific to OCaml: Most JVM GCs do the same thing.)
The problem that Go has here that it's GC is neither generational nor compacting, so it can't do that, so there's a fairly high constant overhead per allocation, whereas OCaml's or the JVM's temporary allocations are only marginally more expensive than alloca().
Note that there can be good engineering reasons to have a non-generational, non-compacting GC (for starters, compacting GCs make C interoperability more difficult). So, yes, if you have such a GC, you do have to watch out for avoiding extraneous allocations.
- panic 9y agoHow do the results change if you use DynArray.make and pass the count instead of DynArray.create? I think the comment you're replying to was talking about preallocated static arrays, not dynamically resizing ones.
- rbehrends 9y agoIt's still marginally slower at 760 milliseconds, give or take (I suspect that's because major heap allocations are generally more expensive than nursery allocations). That said, in that case I could also use `List.init` and be even faster. The problem is that often you don't know exactly how much memory you'll preallocate. This is where in (say) C++, you'll resort to an arena or pool allocator; a GC with a bump allocator will give you what is essentially a smart arena allocator by default for your temporary allocations.
- junke 9y agoYou didn't test with a static array, though: let insert_array_test () = let result = ref 0 in for i = 1 to iterations do let work = Array.make count 0 in for j = 1 to count do Array.set work (j - 1) j done; result := !result + Array.length work done; !result I have the following numbers: # main ();; linked lists 2.983 seconds linked lists (rec) 2.827 seconds dynamic arrays 5.152 seconds static arrays 1.718 seconds
- rbehrends 9y agoYes, I was assuming a case where you don't know exactly how much memory you know ahead of time. If you have predictable requirements, you can just use stack allocations. For example, note how the `ref 0` in the code does not actually incur overhead; the compiler does escape analysis and will stuff the counter in a register or stack location.
- ska 9y agoAll valid points, but typically even the best case gc perf will still be far more expensive than avoiding heap allocations entirely. When I was writing numeric stuff in common lisp, the performance critical stuff all ended up looking pretty c-like, and as far as I can see it's similar in OCaml (for really high performance stuff). It's not a bad trade off, especially for anything following the 80:20 heuristic. That way 80% of your code can be written more expressively and less error prone.