Re: [Ocaml-lib-devel] Dynarray (good one)

[Brian H. <bri...@ql...>]

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
unboxed version.

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 
creaturitist!

- 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)
		else
			for i = idx to d.len - 1 do
				iset d.arr i (iget d.arr (i+1));
			done;
			iset d.arr d.len (Obj.magic 0) (* <-- !!! *)
	end


- 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.

Brian


On Wed, 25 Jun 2003, Nicolas Cannasse wrote:

> Hi,
> 
> 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
>