[m-dev.] Updated version hash table benchmarks
Ralph Becket
rafe at cs.mu.OZ.AU
Wed Feb 11 11:27:51 AEDT 2004
I've run some longer tests on different hash table implementations,
examining
- occupancy rates above 50% with no hash table resizing;
- occupancy rates below 50% with no hash table resizing;
- occupancy rates below 50% with hash table resizing starting from a
tiny (8 bucket) starting point.
In each case the performance of map is compared with...
- vopen_hash_table which uses open addressing with each bucket being a
map to resolve collisions.
- vclosed_hash_table which uses closed addressing with each bucket
holding at most one key/value pair. vclosed_hash_table uses separate
key and value varrays and and a vbitmap to record occupancy.
- vclosed_hash_table2 which is a rewrite of vclosed_hash_table that uses
a single varray with each bucket item being either empty or a
key-value pair.
- hash_table which is the unique version of the vclosed_hash_table
implementation.
The tests were compiled and run on ceres in hlc.gc grade with -O5
--intermodule-optimization --transitive-intermodule-optimization.
I'm tempted to draw the following tentative conclusions:
(1) open hash table performance is superior when lookup failures are
expected to be common, with maps bringing up the rear;
(2) the second closed hash table implementation is superior to the
version using separate arrays for keys, values and occupancy flags;
(3) even when hash tables have to be resized, they are preferable
(modulo (1)) to maps when the number of data exceeds 1000 or so;
(4) for small data sets of the order of 100 items or so, maps are really
hard to beat;
(5) version hash table performance makes it an attractive data
structure.
-- Ralph
Hash table performance with =< 50% occupancy
--------------------------------------------
Benchmark conducted with
vopen_hash_table initially sized at 2 * expected_occupants,
vclosed_hash_table initially sized at 2 ^ (1 + ceil(log2(expected_occupants))),
vclosed_hash_table2 initially sized at 2 ^ (1 + ceil(log2(expected_occupants))),
hash_table initially sized at 2 ^ (1 + ceil(log2(expected_occupants))).
(read 45392 words from /usr/share/dict/words)
benchmark: 100 x creating and populating with 45392 words...
map: 35620ms
vopen_hash_table: 16520ms map ratio 2.15617
vclosed_hash_table: 23540ms map ratio 1.51317
vclosed_hash_table2: 15740ms map ratio 2.26302
hash_table: 16800ms map ratio 2.12024
benchmark: 100 x searching for 45392 words when populated with 45392...
map: 49140ms
vopen_hash_table: 28300ms map ratio 1.7364
vclosed_hash_table: 29940ms map ratio 1.64128
vclosed_hash_table2: 22400ms map ratio 2.19375
hash_table: 22640ms map ratio 2.17049
benchmark: 100 x searching each key when populated with 45392...
map: 49450ms
vopen_hash_table: 28550ms map ratio 1.73205
vclosed_hash_table: 30540ms map ratio 1.61919
vclosed_hash_table2: 22450ms map ratio 2.20267
hash_table: 22670ms map ratio 2.1813
benchmark: 200 x creating and populating with 22696 words...
map: 36890ms
vopen_hash_table: 22220ms map ratio 1.66022
vclosed_hash_table: 25900ms map ratio 1.42432
vclosed_hash_table2: 13900ms map ratio 2.65396
hash_table: 16510ms map ratio 2.2344
benchmark: 200 x searching for 45392 words when populated with 22696...
map: 48690ms
vopen_hash_table: 28550ms map ratio 1.70543
vclosed_hash_table: 37920ms map ratio 1.28402
vclosed_hash_table2: 27840ms map ratio 1.74892
hash_table: 26570ms map ratio 1.83252
benchmark: 200 x searching each key when populated with 22696...
map: 41890ms
vopen_hash_table: 26080ms map ratio 1.60621
vclosed_hash_table: 28310ms map ratio 1.47969
vclosed_hash_table2: 20800ms map ratio 2.01394
hash_table: 22090ms map ratio 1.89633
benchmark: 400 x creating and populating with 11348 words...
map: 32320ms
vopen_hash_table: 20890ms map ratio 1.54715
vclosed_hash_table: 23480ms map ratio 1.37649
vclosed_hash_table2: 13340ms map ratio 2.42279
hash_table: 16280ms map ratio 1.98526
benchmark: 400 x searching for 45392 words when populated with 11348...
map: 40690ms
vopen_hash_table: 22220ms map ratio 1.83123
vclosed_hash_table: 36500ms map ratio 1.11479
vclosed_hash_table2: 30440ms map ratio 1.33673
hash_table: 27130ms map ratio 1.49982
benchmark: 400 x searching each key when populated with 11348...
map: 24140ms
vopen_hash_table: 14780ms map ratio 1.63329
vclosed_hash_table: 21530ms map ratio 1.12123
vclosed_hash_table2: 14280ms map ratio 1.69048
hash_table: 14630ms map ratio 1.65003
benchmark: 800 x creating and populating with 5674 words...
map: 17040ms
vopen_hash_table: 11040ms map ratio 1.54348
vclosed_hash_table: 13020ms map ratio 1.30876
vclosed_hash_table2: 8710ms map ratio 1.95637
hash_table: 9590ms map ratio 1.77685
benchmark: 800 x searching for 45392 words when populated with 5674...
map: 57320ms
vopen_hash_table: 30190ms map ratio 1.89864
vclosed_hash_table: 52350ms map ratio 1.09494
vclosed_hash_table2: 48640ms map ratio 1.17845
hash_table: 41600ms map ratio 1.37788
benchmark: 800 x searching each key when populated with 5674...
map: 22830ms
vopen_hash_table: 14720ms map ratio 1.55095
vclosed_hash_table: 18500ms map ratio 1.23405
vclosed_hash_table2: 14070ms map ratio 1.6226
hash_table: 13880ms map ratio 1.64481
benchmark: 1600 x creating and populating with 2837 words...
map: 16210ms
vopen_hash_table: 11600ms map ratio 1.39741
vclosed_hash_table: 12740ms map ratio 1.27237
vclosed_hash_table2: 8680ms map ratio 1.86751
hash_table: 9400ms map ratio 1.72447
benchmark: 1600 x searching for 45392 words when populated with 2837...
map: 87760ms
vopen_hash_table: 45650ms map ratio 1.92245
vclosed_hash_table: 88630ms map ratio 0.990184
vclosed_hash_table2: 83760ms map ratio 1.04776
hash_table: 70970ms map ratio 1.23658
benchmark: 1600 x searching each key when populated with 2837...
map: 21880ms
vopen_hash_table: 15140ms map ratio 1.44518
vclosed_hash_table: 18370ms map ratio 1.19107
vclosed_hash_table2: 14460ms map ratio 1.51314
hash_table: 13960ms map ratio 1.56734
benchmark: 3200 x creating and populating with 1419 words...
map: 15210ms
vopen_hash_table: 11830ms map ratio 1.28571
vclosed_hash_table: 12550ms map ratio 1.21195
vclosed_hash_table2: 8390ms map ratio 1.81287
hash_table: 9220ms map ratio 1.64967
benchmark: 3200 x searching for 45392 words when populated with 1419...
map: 140410ms
vopen_hash_table: 71820ms map ratio 1.95503
vclosed_hash_table: 155610ms map ratio 0.90232
vclosed_hash_table2: 144920ms map ratio 0.968879
hash_table: 125760ms map ratio 1.11649
benchmark: 3200 x searching each key when populated with 1419...
map: 17860ms
vopen_hash_table: 13010ms map ratio 1.37279
vclosed_hash_table: 16540ms map ratio 1.07981
vclosed_hash_table2: 13030ms map ratio 1.37068
hash_table: 12500ms map ratio 1.4288
benchmark: 6400 x creating and populating with 710 words...
map: 11790ms
vopen_hash_table: 9990ms map ratio 1.18018
vclosed_hash_table: 11020ms map ratio 1.06987
vclosed_hash_table2: 7470ms map ratio 1.57831
hash_table: 7980ms map ratio 1.47744
benchmark: 6400 x searching for 45392 words when populated with 710...
map: 238980ms
vopen_hash_table: 125170ms map ratio 1.90924
vclosed_hash_table: 294300ms map ratio 0.812029
vclosed_hash_table2: 272500ms map ratio 0.876991
hash_table: 236310ms map ratio 1.0113
benchmark: 6400 x searching each key when populated with 710...
map: 15340ms
vopen_hash_table: 12540ms map ratio 1.22329
vclosed_hash_table: 16060ms map ratio 0.955168
vclosed_hash_table2: 12510ms map ratio 1.22622
hash_table: 12110ms map ratio 1.26672
benchmark: 12800 x creating and populating with 355 words...
map: 10300ms
vopen_hash_table: 9860ms map ratio 1.04462
vclosed_hash_table: 10930ms map ratio 0.94236
vclosed_hash_table2: 7300ms map ratio 1.41096
hash_table: 7960ms map ratio 1.29397
benchmark: 12800 x searching for 45392 words when populated with 355...
map: 411880ms
vopen_hash_table: 231300ms map ratio 1.78072
vclosed_hash_table: 570560ms map ratio 0.721887
vclosed_hash_table2: 528310ms map ratio 0.779618
hash_table: 459120ms map ratio 0.897108
benchmark: 12800 x searching each key when populated with 355...
map: 13220ms
vopen_hash_table: 12160ms map ratio 1.08717
vclosed_hash_table: 15910ms map ratio 0.830924
vclosed_hash_table2: 12170ms map ratio 1.08628
hash_table: 11860ms map ratio 1.11467
Hash table performance with >= 50% occupancy
--------------------------------------------
Benchmark conducted with
vopen_hash_table initially sized at 110% expected_occupants,
vclosed_hash_table initially sized at 2 ^ ceil(log2(expected_occupants)),
vclosed_hash_table2 initially sized at 2 ^ ceil(log2(expected_occupants)),
hash_table initially sized at 2 ^ ceil(log2(expected_occupants)).
(read 45392 words from /usr/share/dict/words)
benchmark: 100 x creating and populating with 45392 words...
map: 35340ms
vopen_hash_table: 13490ms map ratio 2.61972
vclosed_hash_table: 18280ms map ratio 1.93326
vclosed_hash_table2: 10850ms map ratio 3.25714
hash_table: 11010ms map ratio 3.20981
benchmark: 100 x searching for 45392 words when populated with 45392...
map: 31370ms
vopen_hash_table: 14130ms map ratio 2.2201
vclosed_hash_table: 25330ms map ratio 1.23845
vclosed_hash_table2: 17930ms map ratio 1.74958
hash_table: 17090ms map ratio 1.83558
benchmark: 100 x searching each key when populated with 45392...
map: 29540ms
vopen_hash_table: 13500ms map ratio 2.18815
vclosed_hash_table: 24790ms map ratio 1.19161
vclosed_hash_table2: 17980ms map ratio 1.64294
hash_table: 17040ms map ratio 1.73357
benchmark: 200 x creating and populating with 22696 words...
map: 21000ms
vopen_hash_table: 9230ms map ratio 2.27519
vclosed_hash_table: 16190ms map ratio 1.2971
vclosed_hash_table2: 9650ms map ratio 2.17617
hash_table: 10000ms map ratio 2.1
benchmark: 200 x searching for 45392 words when populated with 22696...
map: 32180ms
vopen_hash_table: 15400ms map ratio 2.08961
vclosed_hash_table: 30820ms map ratio 1.04413
vclosed_hash_table2: 26990ms map ratio 1.19229
hash_table: 22940ms map ratio 1.40279
benchmark: 200 x searching each key when populated with 22696...
map: 25700ms
vopen_hash_table: 12410ms map ratio 2.07091
vclosed_hash_table: 22580ms map ratio 1.13818
vclosed_hash_table2: 16590ms map ratio 1.54913
hash_table: 15660ms map ratio 1.64112
benchmark: 400 x creating and populating with 11348 words...
map: 18210ms
vopen_hash_table: 8450ms map ratio 2.15503
vclosed_hash_table: 14320ms map ratio 1.27165
vclosed_hash_table2: 8970ms map ratio 2.0301
hash_table: 9140ms map ratio 1.99234
benchmark: 400 x searching for 45392 words when populated with 11348...
map: 39580ms
vopen_hash_table: 19700ms map ratio 2.00914
vclosed_hash_table: 42510ms map ratio 0.931075
vclosed_hash_table2: 41800ms map ratio 0.94689
hash_table: 33830ms map ratio 1.16997
benchmark: 400 x searching each key when populated with 11348...
map: 22980ms
vopen_hash_table: 11550ms map ratio 1.98961
vclosed_hash_table: 19810ms map ratio 1.16002
vclosed_hash_table2: 15170ms map ratio 1.51483
hash_table: 14320ms map ratio 1.60475
benchmark: 800 x creating and populating with 5674 words...
map: 16290ms
vopen_hash_table: 8040ms map ratio 2.02612
vclosed_hash_table: 12120ms map ratio 1.34406
vclosed_hash_table2: 8420ms map ratio 1.93468
hash_table: 8650ms map ratio 1.88324
benchmark: 800 x searching for 45392 words when populated with 5674...
map: 55200ms
vopen_hash_table: 28130ms map ratio 1.96232
vclosed_hash_table: 68630ms map ratio 0.804313
vclosed_hash_table2: 66470ms map ratio 0.83045
hash_table: 55680ms map ratio 0.991379
benchmark: 800 x searching each key when populated with 5674...
map: 21140ms
vopen_hash_table: 11070ms map ratio 1.90967
vclosed_hash_table: 17900ms map ratio 1.18101
vclosed_hash_table2: 14360ms map ratio 1.47214
hash_table: 13780ms map ratio 1.53411
benchmark: 1600 x creating and populating with 2837 words...
map: 14820ms
vopen_hash_table: 7960ms map ratio 1.86181
vclosed_hash_table: 11690ms map ratio 1.26775
vclosed_hash_table2: 8220ms map ratio 1.80292
hash_table: 8600ms map ratio 1.72326
benchmark: 1600 x searching for 45392 words when populated with 2837...
map: 84800ms
vopen_hash_table: 44800ms map ratio 1.89286
vclosed_hash_table: 119080ms map ratio 0.712126
vclosed_hash_table2: 111330ms map ratio 0.761699
hash_table: 97000ms map ratio 0.874227
benchmark: 1600 x searching each key when populated with 2837...
map: 19640ms
vopen_hash_table: 10950ms map ratio 1.79361
vclosed_hash_table: 17340ms map ratio 1.13264
vclosed_hash_table2: 14100ms map ratio 1.39291
hash_table: 13520ms map ratio 1.45266
benchmark: 3200 x creating and populating with 1419 words...
map: 13370ms
vopen_hash_table: 7930ms map ratio 1.686
vclosed_hash_table: 11390ms map ratio 1.17384
vclosed_hash_table2: 8040ms map ratio 1.66294
hash_table: 8340ms map ratio 1.60312
benchmark: 3200 x searching for 45392 words when populated with 1419...
map: 139610ms
vopen_hash_table: 74260ms map ratio 1.88002
vclosed_hash_table: 213970ms map ratio 0.652475
vclosed_hash_table2: 194560ms map ratio 0.717568
hash_table: 172070ms map ratio 0.811356
benchmark: 3200 x searching each key when populated with 1419...
map: 17780ms
vopen_hash_table: 10800ms map ratio 1.6463
vclosed_hash_table: 16830ms map ratio 1.05645
vclosed_hash_table2: 13610ms map ratio 1.30639
hash_table: 12940ms map ratio 1.37403
benchmark: 6400 x creating and populating with 710 words...
map: 11720ms
vopen_hash_table: 7740ms map ratio 1.51421
vclosed_hash_table: 11090ms map ratio 1.05681
vclosed_hash_table2: 7720ms map ratio 1.51813
hash_table: 8130ms map ratio 1.44157
benchmark: 6400 x searching for 45392 words when populated with 710...
map: 237320ms
vopen_hash_table: 128850ms map ratio 1.84183
vclosed_hash_table: 400000ms map ratio 0.5933
vclosed_hash_table2: 355480ms map ratio 0.667604
hash_table: 321180ms map ratio 0.7389
benchmark: 6400 x searching each key when populated with 710...
map: 15270ms
vopen_hash_table: 10200ms map ratio 1.49706
vclosed_hash_table: 16290ms map ratio 0.937385
vclosed_hash_table2: 12830ms map ratio 1.19018
hash_table: 12450ms map ratio 1.22651
benchmark: 12800 x creating and populating with 355 words...
map: 10220ms
vopen_hash_table: 7500ms map ratio 1.36267
vclosed_hash_table: 10910ms map ratio 0.936755
vclosed_hash_table2: 7540ms map ratio 1.35544
hash_table: 7940ms map ratio 1.28715
benchmark: 12800 x searching for 45392 words when populated with 355...
map: 406410ms
vopen_hash_table: 241170ms map ratio 1.68516
vclosed_hash_table: 786340ms map ratio 0.516838
vclosed_hash_table2: 691230ms map ratio 0.587952
hash_table: 630880ms map ratio 0.644195
benchmark: 12800 x searching each key when populated with 355...
map: 13190ms
vopen_hash_table: 9720ms map ratio 1.357
vclosed_hash_table: 15900ms map ratio 0.82956
vclosed_hash_table2: 12450ms map ratio 1.05944
hash_table: 12180ms map ratio 1.08292
benchmark: 25600 x creating and populating with 178 words...
map: 14180ms
vopen_hash_table: 9660ms map ratio 1.46791
vclosed_hash_table: 13550ms map ratio 1.04649
vclosed_hash_table2: 8850ms map ratio 1.60226
hash_table: 9740ms map ratio 1.45585
benchmark: 25600 x searching for 45392 words when populated with 178...
map: 715640ms
vopen_hash_table: 476500ms map ratio 1.50187
vclosed_hash_table: 1596600ms map ratio 0.448227
vclosed_hash_table2: 1464670ms map ratio 0.488602
hash_table: 1259680ms map ratio 0.568113
benchmark: 25600 x searching each key when populated with 178...
map: 13930ms
vopen_hash_table: 12020ms map ratio 1.1589
vclosed_hash_table: 19180ms map ratio 0.726277
vclosed_hash_table2: 14550ms map ratio 0.957388
hash_table: 14320ms map ratio 0.972765
Growing hash table performance with =< 50% occupancy
----------------------------------------------------
Benchmark conducted with hash tables starting off with 8 buckets
and resizing at 50% occupancy.
(read 45392 words from /usr/share/dict/words)
benchmark: 100 x creating and populating with 45392 words...
map: 35300ms
vopen_hash_table: 24640ms map ratio 1.432612
vclosed_hash_table: 46450ms map ratio 0.759962
vclosed_hash_table2: 39570ms map ratio 0.892093
hash_table: 40110ms map ratio 0.880083
benchmark: 100 x searching for 45392 words when populated with 45392...
map: 51930ms
vopen_hash_table: 47700ms map ratio 1.088677
vclosed_hash_table: 60320ms map ratio 0.860911
vclosed_hash_table2: 52450ms map ratio 0.990086
hash_table: 41030ms map ratio 1.265653
benchmark: 100 x searching each key when populated with 45392...
map: 46000ms
vopen_hash_table: 47230ms map ratio 0.973958
vclosed_hash_table: 54700ms map ratio 0.840954
vclosed_hash_table2: 46130ms map ratio 0.997182
hash_table: 41030ms map ratio 1.121128
benchmark: 200 x creating and populating with 22696 words...
map: 31760ms
vopen_hash_table: 33680ms map ratio 0.942995
vclosed_hash_table: 59270ms map ratio 0.535861
vclosed_hash_table2: 48910ms map ratio 0.649363
hash_table: 52440ms map ratio 0.605652
benchmark: 200 x searching for 45392 words when populated with 22696...
map: 65140ms
vopen_hash_table: 56550ms map ratio 1.151898
vclosed_hash_table: 77300ms map ratio 0.842693
vclosed_hash_table2: 66250ms map ratio 0.983246
hash_table: 61570ms map ratio 1.057982
benchmark: 200 x searching each key when populated with 22696...
map: 56320ms
vopen_hash_table: 53650ms map ratio 1.049766
vclosed_hash_table: 70760ms map ratio 0.795933
vclosed_hash_table2: 58630ms map ratio 0.960601
hash_table: 57170ms map ratio 0.985132
benchmark: 400 x creating and populating with 11348 words...
map: 41630ms
vopen_hash_table: 46620ms map ratio 0.892967
vclosed_hash_table: 74400ms map ratio 0.559549
vclosed_hash_table2: 50360ms map ratio 0.826652
hash_table: 55850ms map ratio 0.745394
benchmark: 400 x searching for 45392 words when populated with 11348...
map: 76220ms
vopen_hash_table: 65670ms map ratio 1.160649
vclosed_hash_table: 95820ms map ratio 0.795452
vclosed_hash_table2: 83360ms map ratio 0.914348
hash_table: 73410ms map ratio 1.038278
benchmark: 400 x searching each key when populated with 11348...
map: 51360ms
vopen_hash_table: 57800ms map ratio 0.888583
vclosed_hash_table: 80420ms map ratio 0.638652
vclosed_hash_table2: 29130ms map ratio 1.763105
hash_table: 27960ms map ratio 1.836880
benchmark: 800 x creating and populating with 5674 words...
map: 16370ms
vopen_hash_table: 20080ms map ratio 0.815248
vclosed_hash_table: 32030ms map ratio 0.511099
vclosed_hash_table2: 22990ms map ratio 0.712061
hash_table: 23690ms map ratio 0.691022
benchmark: 800 x searching for 45392 words when populated with 5674...
map: 78550ms
vopen_hash_table: 41830ms map ratio 1.877818
vclosed_hash_table: 71450ms map ratio 1.099369
vclosed_hash_table2: 63960ms map ratio 1.228108
hash_table: 56140ms map ratio 1.399174
benchmark: 800 x searching each key when populated with 5674...
map: 25830ms
vopen_hash_table: 25530ms map ratio 1.011750
vclosed_hash_table: 37800ms map ratio 0.683342
vclosed_hash_table2: 28930ms map ratio 0.892849
hash_table: 28340ms map ratio 0.911436
benchmark: 1600 x creating and populating with 2837 words...
map: 16200ms
vopen_hash_table: 21550ms map ratio 0.751752
vclosed_hash_table: 32230ms map ratio 0.502653
vclosed_hash_table2: 22890ms map ratio 0.707745
hash_table: 23740ms map ratio 0.682406
benchmark: 1600 x searching for 45392 words when populated with 2837...
map: 126450ms
vopen_hash_table: 58190ms map ratio 2.173034
vclosed_hash_table: 107940ms map ratio 1.171483
vclosed_hash_table2: 98720ms map ratio 1.280893
hash_table: 85670ms map ratio 1.476007
benchmark: 1600 x searching each key when populated with 2837...
map: 24220ms
vopen_hash_table: 25700ms map ratio 0.942415
vclosed_hash_table: 37930ms map ratio 0.638554
vclosed_hash_table2: 28780ms map ratio 0.841562
hash_table: 28540ms map ratio 0.848639
benchmark: 3200 x creating and populating with 1419 words...
map: 15090ms
vopen_hash_table: 21520ms map ratio 0.701222
vclosed_hash_table: 31910ms map ratio 0.472909
vclosed_hash_table2: 22400ms map ratio 0.673675
hash_table: 23380ms map ratio 0.645439
benchmark: 3200 x searching for 45392 words when populated with 1419...
map: 210660ms
vopen_hash_table: 84750ms map ratio 2.485646
vclosed_hash_table: 172260ms map ratio 1.222918
vclosed_hash_table2: 158750ms map ratio 1.326990
hash_table: 139320ms map ratio 1.512055
benchmark: 3200 x searching each key when populated with 1419...
map: 19980ms
vopen_hash_table: 21920ms map ratio 0.911500
vclosed_hash_table: 33770ms map ratio 0.591661
vclosed_hash_table2: 25300ms map ratio 0.789732
hash_table: 25220ms map ratio 0.792237
benchmark: 6400 x creating and populating with 710 words...
map: 11700ms
vopen_hash_table: 18060ms map ratio 0.647860
vclosed_hash_table: 28440ms map ratio 0.411413
vclosed_hash_table2: 19720ms map ratio 0.593327
hash_table: 20600ms map ratio 0.567982
benchmark: 6400 x searching for 45392 words when populated with 710...
map: 365470ms
vopen_hash_table: 139450ms map ratio 2.620784
vclosed_hash_table: 307740ms map ratio 1.187593
vclosed_hash_table2: 287570ms map ratio 1.270890
hash_table: 250170ms map ratio 1.460885
benchmark: 6400 x searching each key when populated with 710...
map: 17320ms
vopen_hash_table: 20800ms map ratio 0.832700
vclosed_hash_table: 33300ms map ratio 0.520135
vclosed_hash_table2: 24710ms map ratio 0.700943
hash_table: 24660ms map ratio 0.702364
benchmark: 12800 x creating and populating with 355 words...
map: 10260ms
vopen_hash_table: 17420ms map ratio 0.589002
vclosed_hash_table: 28130ms map ratio 0.364758
vclosed_hash_table2: 19400ms map ratio 0.528890
hash_table: 20420ms map ratio 0.502473
benchmark: 12800 x searching for 45392 words when populated with 355...
map: 631990ms
vopen_hash_table: 251880ms map ratio 2.509086
vclosed_hash_table: 580460ms map ratio 1.088774
vclosed_hash_table2: 547270ms map ratio 1.154804
hash_table: 474740ms map ratio 1.331233
benchmark: 12800 x searching each key when populated with 355...
map: 14810ms
vopen_hash_table: 19700ms map ratio 0.751789
vclosed_hash_table: 32770ms map ratio 0.451954
vclosed_hash_table2: 24240ms map ratio 0.610990
hash_table: 24310ms map ratio 0.609230
benchmark: 25600 x creating and populating with 178 words...
map: 8780ms
vopen_hash_table: 16790ms map ratio 0.522959
vclosed_hash_table: 27990ms map ratio 0.313708
vclosed_hash_table2: 19420ms map ratio 0.452139
hash_table: 20370ms map ratio 0.431054
benchmark: 25600 x searching for 45392 words when populated with 178...
map: 1088250ms
vopen_hash_table: 482000ms map ratio 2.257777
vclosed_hash_table: 1128560ms map ratio 0.964282
vclosed_hash_table2: 1065160ms map ratio 1.021677
hash_table: 926970ms map ratio 1.173986
benchmark: 25600 x searching each key when populated with 178...
map: 12820ms
vopen_hash_table: 19130ms map ratio 0.670169
vclosed_hash_table: 32850ms map ratio 0.390277
vclosed_hash_table2: 24330ms map ratio 0.526941
hash_table: 24350ms map ratio 0.526508
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------
More information about the developers
mailing list