Hash-rs needs cpus and algorithms!

1

At the end of the summer I set up a little site for testing out different hashing algorithms and there performance when used with Rust's HashMap:

http://cglab.ca/~abeinges/blah/hash-rs/ (only seems to render right in Firefox right now :S)

I also later tossed in some BTreeMap impls for comparison against HashMap itself.

Someone tossed me a new hashing algorithm and has been optimizing it, but we've been seeing wildly different results between our two CPUs! As such, I think this merits more data points! Anyone interested in running the benches on their machines for science?

The source is at https://github.com/Gankro/hash-rs/ and just needs you to run cargo run --release, sit back, and relax. Results will be available in index.html when the process completes. Takes about 10-20 minutes to run them all. You can also run cargo bench directly to only try out a subset of the benches (but the logs/graphs won't change).

Also feel free to send PRs to add more hashing algos or tree data structures to the pile (there's a few commented out hashers in there because they were in poor shape when I set this up)!

2 Likes
2

[Demoman] Ka-booom!

   Compiling hash-rs v0.1.0 (file:///F:/Scratch/repos/hash-rs)
src\multiply_shift.rs:83:71: 83:78 error: unresolved name `hi64mul` [E0425]
src\multiply_shift.rs:83     *result = result.wrapping_add(accum.wrapping_mul(h1).wrapping_add(hi64mul(accum, h0)));
                                                                                               ^~~~~~~
src\multiply_shift.rs:83:71: 83:78 help: run `rustc --explain E0425` to see a detailed explanation
error: aborting due to previous error
Could not compile `hash-rs`.

To learn more, run the command again with --verbose.
[master] > rustc -vV
rustc 1.6.0-nightly (1a2eaffb6 2015-10-31)
binary: rustc
commit-hash: 1a2eaffb63aefba666f55abd992c5e2900654f06
commit-date: 2015-10-31
host: i686-pc-windows-gnu
release: 1.6.0-nightly
3

Oh right, I've been viewing this hosted, but I forgot that locally you have to deal with local file access controls. You can get it to work locally with some hacky nonsense:

Othewise, feel free to grab the individual CSVs that are output.

4

@DanielKeep I'm guessing you're not running on x64? That algorithm uses some x64 asm and a 32-bit impl isn't given yet (it uses an op that isn't exposed standard by languages, but common in ISAs).

5

I'm on x64, but my Rust is 32-bit. Ah well, no science for me. :stuck_out_tongue:

6

Instructions unclear. Computer exploded.

(Running now. My fans got really loud.)

7

Someone has also suggested normalizing the vertical axes to be "per byte" to make it more clear where steady-states are reached: Scale average and latency numbers for more legible graphs. by jbapple · Pull Request #6 · Gankra/hash-rs · GitHub

Interested if people think that will make the data easier to understand.

8

My results:

https://gist.github.com/Stebalien/7197fe72bde9a0cb6bf7

OS: Linux 4.2.6
CPU: i5-2520M @ 2.50GHz
Rustc: rustc 1.6.0-nightly (9303055f3 2015-11-19)

9

A gist for you, sir! https://gist.github.com/sgrif/b0dda861f9ba4aa2d7cf

10

Okay, I did my usual benchmarking ritual:

  • quit Firefox
  • quit Emacs
  • set my CPU governor to "performance" (I'm running Fedora)

Results here: http://www.red-bean.com/jimb/hash-rs-results.zip

1 Like
11

I'm the author of the "horner" hash function you've seen in the output and that @Gankra mentioned in the original post.

It would help me understand its performance if posters would include their processor model (like "Core i7-5775C"), their operating system and version (like "Ubuntu 14.04"), and their rustc version.

12

bytes_throughput:

bytes,farm,sip,horner,xx,fnv
1,50,71,76,66,1000
2,95,133,166,133,2000
4,166,222,307,266,4000
8,275,470,615,500,2666
16,421,761,1142,941,2285
32,376,1142,2133,1684,1777
64,457,1488,3047,2909,1361
128,528,1753,4571,4413,1094
256,693,1855,5818,6243,1003
512,658,1992,7111,7211,975
1024,686,2043,8533,8126,960
2048,700,2068,8641,9022,952

bytes_time

bytes,farm,sip,horner,xx,fnv
1,20,14,13,15,1
2,21,15,12,15,1
4,24,18,13,15,1
8,29,17,13,16,3
16,38,21,14,17,7
32,85,28,15,19,18
64,140,43,21,22,47
128,242,73,28,29,117
256,369,138,44,41,255
512,777,257,72,71,525
1024,1492,501,120,126,1066
2048,2923,990,237,227,2149

mapcountdense-throughput

bytes,sip,farm,btreenew,btree,fnv,xx,horner
1,25,22,33,16,53,22,25
2,48,44,66,34,63,43,53
4,84,86,111,62,120,84,100
8,167,138,214,122,181,156,186
16,278,148,379,228,250,273,295
32,400,204,609,369,308,390,478
64,568,306,873,604,410,619,656
128,713,424,1227,933,534,923,971
256,835,528,1523,1286,582,1185,1218
512,925,613,1750,1551,610,1387,1427
1024,974,665,1856,1760,625,1506,1334
2048,985,663,1912,1779,628,1552,1490

mapcountdense-time

bytes,sip,farm,btreenew,btree,fnv,xx,horner
1,39640,44499,29628,59523,18549,43530,38625
2,41107,44880,30231,58579,31567,45958,37588
4,47416,46502,35754,63805,33313,47233,39820
8,47880,57785,37350,65247,44165,51254,42927
16,57463,107598,42154,70021,63860,58422,54089
32,79917,156556,52467,86694,103654,81907,66900
64,112595,209051,73301,105802,155734,103334,97444
128,179332,301339,104236,137144,239453,138529,131720
256,306400,484032,168041,199044,439519,215885,210170
512,552863,834451,292480,329871,838721,368908,358656
1024,1050398,1537268,551346,581441,1634037,679669,767338
2048,2076618,3084867,1070554,1150148,3253149,1318669,1373070

mapcountsparse-throughput

bytes,fnv,farm,horner,xx,btreenew,sip,btree
1,43,19,22,20,15,21,11
2,22,18,19,18,18,19,14
4,45,36,38,37,36,37,28
8,86,70,75,74,74,73,55
16,166,100,166,165,149,162,105
32,293,165,328,292,295,305,216
64,441,299,643,580,557,531,440
128,603,462,1175,1094,1113,848,851
256,736,645,2173,1968,2268,1179,1716
512,806,825,3543,3266,4141,1501,3338
1024,838,949,4981,4667,7811,1734,6486
2048,884,958,5937,6035,15671,1888,12302

mapcountsparse-time

bytes,fnv,farm,horner,xx,btreenew,sip,btree
1,23037,52353,44219,49967,63049,47495,90719
2,90881,108175,103453,106051,107042,104399,142704
4,87343,108425,103585,107176,108118,105655,142443
8,92176,114015,105545,107940,107053,108971,143286
16,95933,159784,96312,96801,107131,98561,151458
32,109018,193217,97403,109506,108247,104863,148137
64,144912,213929,99531,110323,114799,120494,145378
128,211974,276687,108895,116914,114975,150851,150252
256,347800,396651,117746,130029,112821,216959,149115
512,634788,620010,144471,156726,123633,340955,153346
1024,1219917,1077799,205526,219356,131084,590129,157877
2048,2311472,2135765,344835,339217,130673,1083435,166455

Linux _____ 4.2.0-1-amd64 #1 SMP Debian 4.2.5-1 (2015-10-27) x86_64 GNU/Linux
rustc 1.6.0-nightly (9303055f3 2015-11-19)
Intel® Core™ i5-3570 CPU @ 3.40GHz × 4
13

Rendered graphs

Raw CSV data and CPU info

14

System

Processor: Intel(R) Core(TM) i7-4790K CPU @ 4.00GHz (8 CPUs), ~4.0GHz
Operating System: Windows 10 Pro 64-bit (10.0, Build 10240) (10240.th1_st1.151104-1714)

Compiler

rustc 1.6.0-nightly (9303055f3 2015-11-19)
binary: rustc
commit-hash: 9303055f37a34adfceec1d1012b87308136295ce
commit-date: 2015-11-19
host: x86_64-pc-windows-msvc
release: 1.6.0-nightly

###bytes_throughput.csv

bytes,fnv,horner,sip,xx,farm
1,1000,142,83,90,23
2,1000,250,166,166,47
4,4000,571,285,363,88
8,4000,1000,571,727,170
16,2666,2000,1000,1333,307
32,2000,2461,1454,2000,264
64,1523,4000,1939,3368,438
128,1254,6400,2327,5565,615
256,1113,8258,2585,8000,842
512,1087,10039,2652,10448,1009
1024,1067,11130,2680,12190,1155
2048,1048,11314,2775,13044,1302

bytes_time.csv

bytes,fnv,horner,sip,xx,farm
1,1,7,12,11,42
2,2,8,12,12,42
4,1,7,14,11,45
8,2,8,14,11,47
16,6,8,16,12,52
32,16,13,22,16,121
64,42,16,33,19,146
128,102,20,55,23,208
256,230,31,99,32,304
512,471,51,193,49,507
1024,959,92,382,84,886
2048,1954,181,738,157,1572

mapcountdense-throughput.csv

bytes,btreenew,horner,btree,sip,fnv,xx,farm
1,42,38,13,31,64,29,14
2,83,79,3,58,77,55,30
4,145,151,52,105,143,114,58
8,270,281,101,204,225,208,108
16,475,458,189,361,312,369,106
32,749,784,318,547,389,541,184
64,1154,1016,566,788,522,838,297
128,1646,1437,948,1009,646,1272,449
256,2127,1777,1409,1161,701,1645,614
512,2454,2067,1904,1285,732,1926,741
1024,2709,2094,2315,1314,749,2137,831
2048,2813,2281,2598,1390,755,2238,872

mapcountdense-time.csv

bytes,btreenew,horner,btree,sip,fnv,xx,farm
1,23489,25734,75463,32247,15459,34164,67557
2,23953,25188,502853,34151,25812,35823,66506
4,27421,26320,76052,38055,27921,35022,68345
8,29553,28441,78786,39197,35502,38367,73560
16,33669,34881,84551,44290,51173,43337,149835
32,42685,40777,100374,58401,82252,59088,173302
64,55455,62958,113059,81213,122498,76294,215294
128,77756,89011,134884,126829,197887,100569,284805
256,120296,144017,181650,220375,364681,155572,416675
512,208610,247636,268835,398179,698647,265768,690014
1024,377926,488794,442109,778334,1364646,479057,1230325
2048,727635,897540,787421,1472670,2703505,914166,2342901

mapcountsparse-throughput.csv

bytes,xx,fnv,farm,sip,btreenew,btree,horner
1,25,48,13,25,18,9,32
2,25,29,17,24,21,12,27
4,49,57,35,50,41,25,55
8,101,110,67,97,83,51,112
16,201,198,67,186,165,101,222
32,357,324,144,360,327,202,432
64,687,493,256,640,651,402,816
128,1326,656,353,1050,1287,798,1545
256,2426,809,643,1494,2523,1570,2713
512,4093,900,845,1883,4754,3043,4397
1024,6199,962,1019,2275,9127,5944,6466
2048,8536,1001,1173,2455,17479,11565,8257

mapcountsparse-time.csv

bytes,xx,fnv,farm,sip,btreenew,btree,horner
1,39445,20580,73353,39341,53400,107334,31226
2,79422,66936,114604,80152,94916,155139,73171
4,80203,69654,112974,79440,96117,156402,71795
8,79004,72153,119289,81818,96341,156527,70877
16,79552,80409,236188,85772,96820,157406,71955
32,89587,98523,221026,88712,97841,158352,73916
64,93130,129778,249349,99992,98282,158830,78358
128,96504,195039,362356,121801,99387,160267,82828
256,105487,316189,397646,171307,101431,162979,94353
512,125054,568548,605301,271747,107666,168188,116435
1024,165180,1062823,1003376,450012,112174,172254,158340
2048,239899,2042295,1744532,833445,117155,177081,247977
15

And my results: rendered and raw. Machine info is included, but also:

OS X 10.11.1 (15B42)
Processor Name: Intel Core i7
Processor Speed: 2.3 GHz
Number of Processors: 1
Total Number of Cores: 4
L2 Cache (per Core): 256 KB
L3 Cache: 6 MB
Memory: 16 GB

rustc 1.6.0-dev (43b5d5e0d 2015-11-07)

16

Results for my machine

Model Name: Mac Pro
Model Identifier: MacPro6,1
Processor Name: 6-Core Intel Xeon E5
Processor Speed: 3,5 GHz
Number of Processors: 1
Total Number of Cores: 6
L2 Cache (per Core): 256 KB
L3 Cache: 12 MB

17

Here's mine:
https://gist.github.com/sumproxy/d956ed117a4a128bcf46

18

Here you go, a whole bunch of servers: GitHub - dcohenp/hash-rs-results: Test results from running hash-rs (Rust hash function benchmarking tool)

1 Like
19

Oh, my machine info:

Red Hat Linux 4.2.6 x86_64
Intel(R) Core(TM) i7-3840QM CPU @ 2.80GHz
rustc: rustc 1.6.0-nightly (7499558dd 2015-11-28)