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

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

On Fri, 25 Apr 2003, John Max Skaller wrote:

> Brian Hurt wrote:
> 
> > On Mon, 14 Apr 2003, John Max Skaller wrote:
> 
> > I'm not sure Hysteresis is the best algorithm.
> 
> 
> [snip]
> 
> > You preventing thrashing by letting shrinkage go longer before shrinking.  
> 
> 
> Must be some misunderstanding here.

Yes there was.  I was misunderstanding you.  My apologies.

The good news was that in the current version of Xarray in the libraries, 
every time I allocate a new array I allow the caller to pass in what 
reallocation strategy to use.  Neither of the two I have defined are what 
you are talking about- but new strategies can easily be added.

I tried to document in xarray.mli how to write a resizer function.  If the 
comments are clear, please let me know and I'll improve them.

> And the real point is: there is no single optimal
> strategy, it depends on the use to which the array
> is being put. Hence, allowing the user to specify
> the strategy allows for the user to tune performance
> in a way reasonably well separated from the
> overall program logic.

I fully agree.  I can even envision application-specific resizer 
functions, which "know" the behavior of the algorithm being used and can 
behave differently as the algorithm changes it's allocation behavior.  Or 
implements heuristics to try and predict the algorithm.  Etc.

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.


> In my system I had:
> 
> (1) a standard strategy (chunks of 16 elements)

I'm using doubling.  See above.

> (2) a global variable which was initialised to the standard
> strategy but which could be changed

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

> (3) a default constructor using the global strategy

Got it.

> (4) a constructor accepting a strategy argument

Got it.

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

> 
> In addition, my stratgies were objects which had some
> data, which could also be changed (eg: chunk strategy
> was parameterised by chunk size).

Partial evaluation takes care of this.  

> 
> The cost is a function pointer in each array,
> and some overhead calling it when necessary.
> 

Already paying it.  I call the resizer function (which tells me what size 
the array should be) every time I add or remove an element from the array.

Brian