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
-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
|
