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

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

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.

Hysteresis doesn't imply adding a fixed chunk on growing, nor
removing one on shrinking. It simply implies the threshholds for
growth or shrinkage are not the same, but separated somehow so that
a requirement for 1 more slot which causes an allocation, when followed
by a requirement for 1 less slot, does NOT cause a reduction.

The idea applies no matter whether growth is a constant chunk,
or a fractional increase, or some other calculation:
arrays grow when they must, but don't
shrink until they waste a certain amount of space (which is
more than the amount wasted after an allocation).

This is what you described for the doubling routine:
if you allow 25% wastage before shrinking, and you remove
only 15% of the unused space when you do shrink, then small
vibrations don't cause either allocations or deallocations.

Anyhow, the point is not to use a naive routine where the
growth and shrinkage triggers are the same, since a loop
which adds an element and then removes one repeatedly would
cause violent and unacceptable thrashing.

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.

In my system I had:

(1) a standard strategy (chunks of 16 elements)
(2) a global variable which was initialised to the standard
strategy but which could be changed
(3) a default constructor using the global strategy
(4) a constructor accepting a strategy argument
(5) a method for changing the strategy for any individual array

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

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

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