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

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

Nicolas Cannasse wrote:

 
>>- I haven't made the reallocation strategy explicit.  And I'm not sure I
>>like the shrinking strategy.
>>


I have a published article on this subject.
The gist of it is:

1) the strategy is specified by a user supplied function
with signature

	strategy: int -> int -> int -> int

The first argument is the allocation size (total slots).

The second argument is the number of used slots.

The third arguument is the desired number of used slots.

The result is the number of slots which should be present.

2) It is nice to provide a default function which has
reasonable performance. A memory efficient algorithm is:

let chunk = 16

let strategy a u d =
   if d > a - chunk then roundup(d,chunk)+chunk
   else if d < a + chunk then roundup(d,chunk)+chunk
   else u

This basically adds or removes a fixed sized block
WITH HYSTERESIS (like a thermostat).

The semantics of use are: the physical allocator does NOT
have to allocate the recommended amount. After calling
the result must satisfy

	result >= 0
	result >= d

which is also a constraint on the physical allocator.

An faster routine uses a doubling factor instead,
but HYSTERESIS is vital to prevent thrashing.


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