-
Notifications
You must be signed in to change notification settings - Fork 41
Hashing Comparison ~30% speedup
Jeremy edited this page Jun 29, 2019
·
2 revisions
Changing from std::unordered_map to robin_hood_hashing
--------------------------------------------------------------------------------------- benchmark: 6 tests --------------------------------------------------------------------------------------
Name (time in ms) Min Max Mean StdDev Median IQR Outliers OPS
Rounds Iterations
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_bad_convex_hull 3.1802 (1.0) 5.4155 (1.0) 3.7996 (1.0) 0.4428 (1.0) 3.5658 (1.0) 0.7449 (1.0) 49;1 263.1840 (1.0)
168 1
test_building2 5.3337 (1.68) 8.1387 (1.50) 6.5479 (1.72) 0.5568 (1.26) 6.5675 (1.84) 0.7695 (1.03) 51;1 152.7203 (0.58)
145 1
test_building1 5.3412 (1.68) 7.6504 (1.41) 6.1408 (1.62) 0.4819 (1.09) 6.2471 (1.75) 0.8273 (1.11) 58;0 162.8440 (0.62)
146 1
test_100k_array_alpha 291.4291 (91.64) 298.4004 (55.10) 296.2097 (77.96) 2.8412 (6.42) 297.6569 (83.47) 3.2006 (4.30) 1;0 3.3760 (0.01)
5 1
test_100k_array_lmax 292.9778 (92.12) 300.1430 (55.42) 296.8278 (78.12) 2.7852 (6.29) 297.8121 (83.52) 3.9510 (5.30) 2;0 3.3690 (0.01)
5 1
test_100k_array_xyThresh 294.5387 (92.62) 306.8192 (56.66) 297.8394 (78.39) 5.0901 (11.50) 295.4963 (82.87) 4.1581 (5.58) 1;1 3.3575 (0.01)
5 1
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------- benchmark: 6 tests ---------------------------------------------------------------------------------------
Name (time in ms) Min Max Mean StdDev Median IQR Outliers OPS
Rounds Iterations
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_bad_convex_hull 2.1653 (1.0) 4.3560 (1.0) 2.4845 (1.0) 0.3919 (1.0) 2.2890 (1.0) 0.4116 (1.0) 34;13 402.4974 (1.0) 187 1
test_building1 4.0478 (1.87) 8.1608 (1.87) 4.9352 (1.99) 0.7231 (1.85) 4.8205 (2.11) 0.8186 (1.99) 43;10 202.6243 (0.50) 194 1
test_building2 4.5203 (2.09) 7.0760 (1.62) 5.2760 (2.12) 0.5016 (1.28) 5.3163 (2.32) 0.7607 (1.85) 56;2 189.5387 (0.47) 171 1
test_100k_array_lmax 181.0951 (83.63) 209.4799 (48.09) 192.2597 (77.38) 12.0026 (30.63) 187.0803 (81.73) 21.6419 (52.59) 2;0 5.2013 (0.01) 6 1
test_100k_array_xyThresh 183.0285 (84.53) 214.6098 (49.27) 193.5033 (77.88) 12.3156 (31.43) 187.5635 (81.94) 16.2370 (39.45) 1;0 5.1679 (0.01) 6 1
test_100k_array_alpha 185.7237 (85.77) 202.3285 (46.45) 194.2747 (78.20) 7.4459 (19.00) 195.0935 (85.23) 13.3503 (32.44) 2;0 5.1474 (0.01) 6 1
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Name (time in ms) Min Max Mean StdDev Median IQR Outliers OPS Rounds Iterations
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_bad_convex_hull 1.6997 (1.0) 2.7975 (1.0) 1.9016 (1.0) 0.1460 (1.0) 1.8739 (1.0) 0.1274 (1.0) 87;31 525.8757 (1.0) 450 1
test_building1 2.9304 (1.72) 4.1872 (1.50) 3.7078 (1.95) 0.3039 (2.08) 3.8240 (2.04) 0.4747 (3.73) 89;0 269.6992 (0.51) 251 1
test_building2 3.4998 (2.06) 4.8985 (1.75) 4.0559 (2.13) 0.3782 (2.59) 3.8950 (2.08) 0.7627 (5.99) 84;0 246.5531 (0.47) 211 1
test_100k_array_alpha 136.9144 (80.55) 167.7396 (59.96) 147.2006 (77.41) 10.5345 (72.14) 144.4434 (77.08) 1.2493 (9.81) 1;2 6.7934 (0.01) 6 1
test_100k_array_lmax 140.2724 (82.53) 160.4533 (57.36) 152.0597 (79.96) 8.1297 (55.67) 155.1628 (82.80) 14.4464 (113.44) 3;0 6.5764 (0.01) 7 1
test_100k_array_xyThresh 156.1592 (91.88) 173.9203 (62.17) 162.2376 (85.32) 6.2423 (42.75) 161.0981 (85.97) 8.0497 (63.21) 1;0 6.1638 (0.01) 7 1
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Name (time in ms) Min Max Mean StdDev Median IQR Outliers OPS Rounds Iterations
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_bad_convex_hull 1.0386 (1.0) 1.5172 (1.0) 1.0580 (1.0) 0.0371 (1.00) 1.0469 (1.0) 0.0065 (1.0) 79;161 945.1568 (1.0) 911 1
test_building1 2.1693 (2.09) 2.6308 (1.73) 2.1942 (2.07) 0.0370 (1.0) 2.1791 (2.08) 0.0361 (5.52) 29;9 455.7510 (0.48) 372 1
test_building2 2.5231 (2.43) 3.1893 (2.10) 2.5550 (2.41) 0.0595 (1.61) 2.5337 (2.42) 0.0405 (6.18) 19;14 391.3969 (0.41) 380 1
test_100k_array_alpha 129.4591 (124.65) 166.7643 (109.92) 143.4697 (135.60) 14.6116 (394.68) 140.6254 (134.33) 25.0568 (>1000.0) 2;0 6.9701 (0.01) 8 1
test_100k_array_xyThresh 129.6079 (124.79) 132.6770 (87.45) 131.1479 (123.96) 0.8368 (22.60) 131.1477 (125.27) 0.3939 (60.20) 2;2 7.6250 (0.01) 8 1
test_100k_array_lmax 130.6483 (125.79) 133.1601 (87.77) 131.8334 (124.60) 0.7583 (20.48) 131.9258 (126.02) 0.8784 (134.25) 2;0 7.5853 (0.01) 8 1
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------