Re: [Ocaml-lib-devel] Xarray : resizeable arrays (first cut)

[John M. S. <sk...@oz...>]

Brian Hurt wrote:


> The doubling algorithm is the overall generally best algorithm that I can
> think of.  Basically, adding and subtracting elements is O(1)- making the 
> construction and use of large xarrays not implausible.


By best you mean 'fastest'. This is clearly not the only requirement.
For example it would be a disaster on a prime number generator
in which minimisation of storage use is more important. Here the time
to copy is irrelevant compared to the time computing primes, where the
need to fit large numbers in storage is dominant.

Obviously, doubling is less efficient speed wise than tripling.
My experiments showed that, as you claim, a factor of 2 is close
to optimal: multiplying by 10 is faster, but not much. OTOH a factor
of 1.8 begins to slow the system down... on the tests I ran anyhow.


> Hmm.  Could be done with a reference.  But this is a very non-ML sort of 
> concept.


I agree: loss of reentrancy .. BUT provided the store is atomic
it only affects performance not semantics if the variable is
changed at random even by multiple threads. Setting a strategy
for a whole program depending on what phase of execution it is up
to is fairly useful.

 
>>(5) a method for changing the strategy for any individual array
>>
> 
> I only allow new strategies on allocating new arrays.  This include 
> 'implicit' allocations like of_enum and copy.  Although I suppose this 
> could be added.


It can also be left out until someone needs it (if unsure

of utility LEAVE IT OUT :-)

-------------------------------------------------------- 
one thing I found: I needed 3 arguments not 2:


current slots, current used slots, required size


Conceptually, the reason is: the ideal size
may be influenced by the allocated size for example:

Double when necessary, only shrink if the desired size
is zero.

The extra argument is necessary for asymmetric growth/shrinkage
algorithms, so I recommend you add it: at present you cannot
take 'unused space' into account since it cannot be computed.

-- 
John Max Skaller, mailto:sk...@oz...
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850