[m-dev.] Version arrays

[Fergus Henderson]

On 22-Jan-2004, Ralph Becket <rafe at cs.mu.OZ.AU> wrote:
> I've knocked up a quick implementation of version arrays (i.e. ground
> arrays whose "latest" version provides O(1) access and update, but
> "older" versions take O(k) time where k updates have occurred.)

Great -- we should put version arrays in the standard library.

> I've just run a benchmark test reversing 100,000 ints comparing
> map(int, int), varray(int) and array(int).  The results averaging over
> 10 iterations (starting with fresh array structures on each iteration)
> are as follows:
> 
> map array time:       455ms
> version array time:   173ms  ratio 2.63
> ordinary array time:   61ms  ratio 2.84
> 
> (The files were compiled with -O5 --transitive-intermodule-optimization.)
> 
> That's a fairly respectable speedup for version arrays.

So the test was using arrays or maps with 100,000 elements?
100,000 is a rather large collection size.
How does it compare with a collection size of 100, or 1000?

If you can get any speedup at all with collection sizes like that,
then the next experiment to try is replacing the pred_table map
(and perhaps others similar data structures) in the module_info with
version arrays.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------