[m-dev.] Version arrays

[Ralph Becket]

Fergus Henderson, Thursday, 22 January 2004:
> 
> 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.

Here is a more comprehensive set of results.  The first set of tests is
for repeated reversals of an array of ints, the second set is for
repeated summations of an array of ints.  Version arrays do better than
maps once 100 items or thereabouts are involved.

benchmark: 1 reversals of 100000 items
bt_array time:        810ms
map array time:       660ms  ratio: 1.23
version array time:   230ms  ratio: 2.86
ordinary array time:  100ms  ratio: 2.29

benchmark: 10 reversals of 10000 items
bt_array time:        270ms
map array time:       300ms  ratio: 0.90
version array time:   130ms  ratio: 2.30
ordinary array time:   50ms  ratio: 2.57

benchmark: 100 reversals of 1000 items
bt_array time:        190ms
map array time:       210ms  ratio: 0.91
version array time:   120ms  ratio: 1.74
ordinary array time:   50ms  ratio: 2.37

benchmark: 1000 reversals of 100 items
bt_array time:        110ms
map array time:       130ms  ratio: 0.85
version array time:   140ms  ratio: 0.93
ordinary array time:   50ms  ratio: 2.76

benchmark: 10000 reversals of 10 items
bt_array time:         60ms
map array time:        80ms  ratio: 0.75
version array time:   120ms  ratio: 0.67
ordinary array time:   50ms  ratio: 2.37

benchmark: 100000 reversals of 1 items
bt_array time:         60ms
map array time:        50ms  ratio: 1.20
version array time:   260ms  ratio: 0.20
ordinary array time:  110ms  ratio: 2.35

benchmark: 100 summations of 100000 items
bt_array time:       4730ms
map array time:      7240ms  ratio: 0.65
version array time:  2650ms  ratio: 2.73
ordinary array time: 1740ms  ratio: 1.52

benchmark: 1000 summations of 10000 items
bt_array time:       3960ms
map array time:      6090ms  ratio: 0.65
version array time:  2620ms  ratio: 2.32
ordinary array time: 1730ms  ratio: 1.51

benchmark: 10000 summations of 1000 items
bt_array time:       2510ms
map array time:      4180ms  ratio: 0.60
version array time:  2610ms  ratio: 1.60
ordinary array time: 1730ms  ratio: 1.51

benchmark: 100000 summations of 100 items
bt_array time:       1630ms
map array time:      2780ms  ratio: 0.59
version array time:  2630ms  ratio: 1.06
ordinary array time: 1720ms  ratio: 1.53

benchmark: 1000000 summations of 10 items
bt_array time:        630ms
map array time:      1620ms  ratio: 0.39
version array time:  2610ms  ratio: 0.62
ordinary array time: 1770ms  ratio: 1.47

benchmark: 10000000 summations of 1 items
bt_array time:        410ms
map array time:       560ms  ratio: 0.73
version array time:  2660ms  ratio: 0.21
ordinary array time: 1820ms  ratio: 1.46

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