<div dir="ltr">Hey folk.<br><br>jch-erl 0.1 freshly baked.<br><br>NIF wrapper for Jump Consistent Hash algorithm by John Lamping and Eric Veach developed at Google, Inc. Paper: "A Fast, Minimal Memory, Consistent Hash Algorithm".<div><br></div><div><a href="http://arxiv.org/ftp/arxiv/papers/1406/1406.2294.pdf">http://arxiv.org/ftp/arxiv/papers/1406/1406.2294.pdf</a> <br><br>This implementation uses the xorshift64* pseudo-random number generator rather than the linear congruential generator in the paper as it is reasonably fast but, more importantly, memory efficient.<br><br>Usage<br><br>A single function jch:ch/2 is offered. Simply pass in a 64 bit long (or less) integer key argument followed by the desired bucket or continuum partition size. The function returns the partition allocated for the key.<br><br>Performance is very stable as bucket size increases and distribution across the ring is stable (standard deviation for a reasonable sample size is typically <2% relative to the mean).<br><br>Example<br><br>% ERL_LIBS=deps erl +sfwi 1 +scl false -pa ebin<br>Erlang R16B02 (erts-5.10.3) [source] [64-bit] [smp:8:8] [async-threads:10] [hipe] [kernel-poll:false] [dtrace]<br><br>Eshell V5.10.3  (abort with ^G)<br>1> jch:ch(1,128).<br>29<br>2> jch:ch(13,128).<br>121<br>3> jch:ch(13,128).<br>121<br>4> jch:ch(trunc(math:pow(2,64))-1,128).<br>78<br>5> jch:ch(trunc(math:pow(2,64)),128). %% off by 1 mate<br>** exception error: bad argument<br>     in function  jch:ch/2<br>        called as jch:ch(18446744073709551616,128)<br>6> %% off by 1 mate<br>6><div><br></div><div>Access times are typically sub-microsecond. Performance tests of the erlang NIF</div><div>and underlying C function are included.</div><div><br></div><div>Example performance for a space of 1 billion buckets:</div><div><br></div><div>- 1B Buckets. Hash performance.<br>ch1b N: 10 Min: -----1 Max: -----2 Median: -----1 Avg: -----1 Elapsed: 16<br>ch1b N: 100 Min: -----0 Max: -----1 Median: -----1 Avg: -----1 Elapsed: 102<br>ch1b N: 1000 Min: -----0 Max: -----9 Median: -----0 Avg: -----0 Elapsed: 1178<br>ch1b N: 10000 Min: -----0 Max: ----13 Median: -----0 Avg: -----0 Elapsed: 10146<br>ch1b N: 100000 Min: -----0 Max: ----59 Median: -----0 Avg: -----0 Elapsed: 109772<br>ch1b N: 1000000 Min: -----0 Max: ---886 Median: -----0 Avg: -----0 Elapsed: 1048561<br>ch1b N: 10000000 Min: -----0 Max: --3734 Median: -----0 Avg: -----0 Elapsed: 11757297</div><div><table class="" style="border-collapse:collapse;border-spacing:0px;color:rgb(51,51,51);font-family:Helvetica,arial,freesans,clean,sans-serif,'Segoe UI Emoji','Segoe UI Symbol';font-size:13px;line-height:18.2000007629395px;background-image:initial;background-repeat:initial"><tbody></tbody></table><br>And a sample of how keys partition over the space:</div><div><br></div><div><table class="" style="border-collapse:collapse;border-spacing:0px;color:rgb(51,51,51);font-family:Helvetica,arial,freesans,clean,sans-serif,'Segoe UI Emoji','Segoe UI Symbol';font-size:13px;line-height:18.2000007629395px;background-image:initial;background-repeat:initial"><tbody><tr><td id="LC117" class="" style="padding:0px 10px;font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;vertical-align:top;white-space:pre;overflow:visible"></td></tr></tbody></table>- 32 Buckets. 10M hashes Uniform Distribution Check.<br>312292 312457 312660 312522 313805 311987 311431 312299<br>311975 312834 312233 312125 313391 312222 312170 312389<br>311811 313134 312986 312434 312002 313060 312784 312699<br>312114 312170 312385 312721 313163 311883 313060 312802<br>oOo| Min: 311431 Max: 313805 Median: 312389 Avg: 312500 Elapsed: 15748372<br>Worst: 99.2435 Med: 99.5488 Avg: 99.5841 RSD: 0.9139</div><div><br></div><div>The RSD here is the standard deviation relative to the mean (avg) which is less than 1%</div><div>after 10M hash operations on random uniform test data. That's pretty good.</div><div><br></div><div>A pint (or fancy fizzy water, or cup of pant wetting tea...) to anyone who can strip off an order of magnitude off the max outlier latencies and explain through scheduler, gc or emulator tuning what insight I missed or runtime vagary i've yet to master. Mainly written to toy with micro-benchmarking and get practice with tuning the emulator.</div><div><br></div><div>Enjoy!<br></div></div><div><br></div><div>Cheers,</div><div><br></div><div>Darach.</div></div>