[m-dev.] Version arrays

[Ralph Becket]

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

The nice thing about version arrays is that you don't need to muck about
with funny insts and modes.

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.

I plan to try out version hash tables against maps in the near future.

One interesting idea would be version stores.  I haven't quite worked
out the details in my head, but my intuition suggests version stores
might be a real improvement over the big-pile-o-maps that we use in, for
instance, the compiler.

-- Ralph
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------