if d.length = Array.length d.values then begin
d.values <- Array.(append d.values (make (length d.values) x))
end;
if d.length = Array.length d.values then begin
let new_array = Array.make (Array.length d.values * 2) x in
Array.blit d.values 0 new_array 0 (Array.length d.values);
d.values <- new_array
end;
New results for the previously slowest cases:
-- 25_000_000 elements --
list: 0.977002 sec
list: 0.963903 sec
list: 0.950473 sec
dynarray: 1.476165 sec
dynarray: 1.281724 sec
dynarray: 1.343222 sec
my dynarray: 0.872558 sec
my dynarray: 0.755902 sec
my dynarray: 0.753746 sec
-- 50_000_000 elements --
list: 1.914777 sec
list: 1.886989 sec
list: 1.542614 sec
dynarray: 2.922376 sec
dynarray: 2.783559 sec
dynarray: 2.537473 sec
my dynarray: 1.725873 sec
my dynarray: 1.545252 sec
my dynarray: 1.515591 sec
-- 75_000_000 elements --
list: 2.827154 sec
list: 2.835789 sec
list: 2.318733 sec
dynarray: 4.354404 sec
dynarray: 4.150271 sec
dynarray: 3.781488 sec
my dynarray: 1.887360 sec
my dynarray: 1.929286 sec
my dynarray: 1.814873 sec
Also, other ways of organizing dynamic not-quite-an-array-but-not-quite-a-linked-list data structures exist. It could be a dynamic array (or linked list) of dynamic arrays to eliminate repeated copying of the oldest elements.
It can't be otherwise if you're just assuming a straightforward compilation model where your written roughly reflects the assembly code that's generated. This just isn't the case with better compilers though.
For instance, Haskell can often perform rewrites or fusion passes that entirely eliminates the loop and all intermediate data structures, effectively giving a near-infinite speedup compared to alternatives. You typically can't perform such optimizations when side-effects are in the middle of the computation, for numerous reasons.
(You are right on the general hand-waving level that such optimizations are sometimes possible. But there are no fuseable intermediate data structures in this particular problem.)
Also, List.map is not optimised in Ocaml. It uses a naive implementation and not a tail call. You have to use rev_map to get good perf.
The exact wording in the article is "let's say you're iterating over some structure and collecting your results in a sequence". You are interpreting a lot into this. Also, your description is of a map (reversed, and expressed as a fold). Anyway, where is your benchmark?
> Also, List.map is not optimised in Ocaml. It uses a naive implementation and not a tail call.
You are again contradicting yourself. Previously you were praising OCaml's optimization capabilities and now you are questioning them. Specifically in a case where there is a magic optimization that is explicitly motivated by List.map: https://ocaml.org/manual/5.2/tail_mod_cons.html . A magic optimization implemented using, guess what, mutation.
It will do a good job, yes. Will it do the best possible job compared to some other algorithm or data structure? It can't. Not in general.
And maybe not in the specific case either:
> The first paragraph refers to the specific case my comment quotes just before: data structure traversal and storage of elements in a set.
So, this: https://ocaml.org/play#code=bW9kdWxlIE15X2R5bmFycmF5ID0gc3Ry...
A simple dynamic array implementation (my_dynarray) beats a list over a wide range of lengths. But not at all lengths! OCaml's built-in Dynarray is not competitive, but that's because it wants to make certain strong guarantees.To be clear, I agree with your general point that we can do just fine writing nice clean pure functional OCaml code for most of our code and can hand-optimize where needed. But your very specific claims rub me the wrong way.