A bunch of minor comments:
- I don't think we're losing much (if anything) to using for loops instead
of array blits. We're moving whole words which are word aligned by
definition, which is generally fast in general. Memory bandwidth
dominates. I just used the array functions because I could.
- Are floats unboxed or boxed? I thought boxed. Note: in this case boxed
floats are not the memory hog they might otherwise be, because of the
unused elements in the array. The arrays are probably on average 5/8th to
3/4th full. Assuming 3/4th full (assuming the array has been mostly
growing, and that it is on average halfway between just having been
expanded (50% full) and needing to be expanded again (100% full)), an
array of n unboxed floats would take up 2*n*4/3 or 8/3 words per float.
Meanwhile, with boxed floats, it would take 2*n + n*4/3 or 10/3 words per
float, meaning the boxed version is only 25% more memory usage than the
If the dynarray has mostly shrinking, it's on average halfway between
having just been shrunk (25% full) and just about to be shrunk (12.5%
full), meaning it's on average 3/16th full. At this point unboxing floats
takes up 2*n*16/3 or 32/2 words per float. Boxing the floats, on the
other hand, takes up 2*n + n*16/3 or 22/3 words per float, or 68.75% the
memory unboxing floats would take. So it can even save a signifigant
amount of memory to not unbox floats.
- the problem of the array being mutated behind enum's back is a general
problem with imperitive programming. It's known as a "bug". Note that my
implementation may have had other problems, I didn't think about the
enumerations that much. I'd say leave the problem children out for now,
and if there's demand for them later, we'll add them then. Fight feeping
- Is there a reason you split off conservative_exponential_resizer from
the normal exponential_resizer? I didn't think the extra couple of
branchs were that bad, especially considering that normally you don't even
reach them, and of the times you do you are hard limited to O(log N)
iterations of either loop. Especially considering you are calling resizer
less often. The default definately should be the conservative one.
Correctness over small gains in speed.
- delete has a bug if you're not deleting the last element and not
reallocating the array- the last element doesn't get nulled out. It
should be (about line 194):
end else begin
if idx = d.len then
(* erase for GC *)
iset d.arr idx (Obj.magic 0)
for i = idx to d.len - 1 do
iset d.arr i (iget d.arr (i+1));
iset d.arr d.len (Obj.magic 0) (* <-- !!! *)
- in to_array, can we replace the for loop with just:
Array.init d.len (fun i -> iget d.arr i)
? This allocates a closure, which is it's only downside.
- of_array: do we want to call resizer to see what size to make the
original array? For example, if we're using step_resizer, and the array
length is not a multiple of the step, the next time we do much of anything
with the array we're reallocating the array. Also, this means we don't
have any space initially for inserting. But this will make of_array more
complicated, we can't just use idup.
On Wed, 25 Jun 2003, Nicolas Cannasse wrote:
> This new version of Dynarray is far better that the previous ones (including
> the one I posted) :
> - using a raw ocaml block with a polymorphic type
> - doing unchecked field access (since we're checking -by hand-)
> - no problems with floats (but they are unboxed)
> - testing for resizing only when removing an element or when not enough
> space for adding.
> - correct a lot of bugs (including a infinite loop in exp_resizer when
> having a length of 0 !)
> Right now, I think the code is quite stable, although I can I have made some
> mistake here and there.
> Notice that I have removed a couple of *enum* functions since they need a
> little bit rethinking because the array can be muted after the enum is
> created : the ones currently defined are ok.
> Comments/bugs report (of course) apprecied.
> Nicolas Cannasse