Re: [Ocaml-lib-devel] Array interface

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

First off, an apology.  I was grumpy this morning about things completely 
irrelevent to the list- and thus responded a lot more hotly than was 
called for.  Sorry.  And thank you for being rational enough not to flame 
in return.

Unless I'm missing something (which is possible), there are three possible
implementations of Dynarray that I can see working:

1) Have the internal array be a 'a option array, and not a 'a array as it 
is currently.  This means we are going through at least one, maybe 2 
references for every element, need it or not.  If I understand things 
correctly, in this case a dynarray of booleans takes up 3 words per entry, 
and retrieving on takes two or three dereferences.

2) Use the null value kludge.  I agree that this is far from optimal- but 
it allows me to avoid options were not needed, and still write in Ocaml.

3) Write in C, leaving floats unboxed.  Actually, thinking about it, we 
could do this in C even keeping floats unboxed- if we don't allocate the 
array until the first element is added (and we know what type it is).

I'm not opposed to option 3.  Heck, I'd even support an implemention 
along those lines.  I'm just unlikely to write it anytime soon.

On Sat, 21 Jun 2003, John Max Skaller wrote:

> There is no need to do that. The proposal is
> to make an array of ints. And cast input values,
> all of which are boxed, to int. And cast
> values being fetched into single values,
> all of which are boxed.
> 

This won't work- it'll cause the GC to screw up.  Since they're int's (the 
low bits are set), the GC won't follow any references.  If the last 
reference to an object is in a Dynarray.t, the GC will think there aren't 
*any* references to the object at all, and collect the object.  Then, when 
the reference is fished out of the int it was stored in and returned, 
all sorts of chaos will happen.

Is there any sort of documentation kicking around about Obj?
> > But one of the reasons I'm contributing to ExtLib is that I want to do 
> > some programming in *Ocaml*.  But I'm willing to take it under advisement, 
> > and put it on my to do list.  Just don't hold your breath.
> 
> 
> I agree, it would be nice to do everything in Ocaml.
> 
> But this is a fundamental data type it seems we cannot do
> in Ocaml.
> 

Actually, we can do it.  Just have the inner array be a 'a option array 
instead of just a 'a array.

> The null value is not acceptable at all. Just suppose
> that you wanted to use a Dynarray.t to implement
> some part of another polymorphic container ..
> then you would have to pass the null value to IT too.
> So the null value 'permeates' any data structure
> you use it in. For example a list which automagically
> converts to an array to improve performance.

Yep.  

> 
> So if it is necessary to do a C implementation,
> then do one, because it will make Ocaml
> programming so much easier.
> 
> I need a dynamic array. I'm using lists far too often.
> I can implement it in Ocaml easily as an array ref,
> but I'd have to copy the array on *every* append
> operation.

So take the time to write one.  Write it once, write it correct, and 
submit the code.

WRT to unboxed floats, I myself wouldn't be horrified.  The only data 
structure in which floats are unboxed (to my knowledge) is arrays.  If the 
data size is that important, use arrays.  Actually, as on average about 
1/2 of the dynarray is allocated by unused, I could make the argument that 
keeping floats in dynarrays unboxed actually uses less memory.

> You have my sympathy. I have recently been blasting the
> committee about the mess. But I'm on it, I'm entitled :-)

I've been trying to keep the amount of C++ discussions on the Ocaml lists 
to an absolute minimum.  As they are off topic.

Brian