Repository navigation
String-based hash functions should accept numeric arrays as input #14
Description
With minimal additional code, the string-based hash functions, like cyrb53, could work with any numeric array-like input, like Uint8Array, Uint16Array, Buffer etc. Below you can find a sample script where I did this for cyrb53a. Running the script as node cyrb53a.js 0 will run a ~20sec benchmark for the original version, running node cyrb53a.js 1 will do the same for the modified version. On my system (Ubuntu 16.04, AMD Ryzen 7 1700) with Node.js v12.19 and v14.15 both versions perform about the same, i.e. the additional code does not seem to hinder V8's Turbofan from optimizing the function like the original one.
PS: Keep up the good work. This repository is a real treasure trove for hash enthusiasts :)
// ORIGINAL VERSION
const cyrb53a = function(str, seed = 0) {
let h1 = 0xdeadbeef ^ seed, h2 = 0x41c6ce57 ^ seed;
for(let i = 0, ch; i < str.length; i++) {
ch = str.charCodeAt(i);
h1 = Math.imul(h1 ^ ch, 0x85ebca77);
h2 = Math.imul(h2 ^ ch, 0xc2b2ae3d);
}
h1 ^= Math.imul(h1 ^ (h2 >>> 15), 0x735a2d97);
h2 ^= Math.imul(h2 ^ (h1 >>> 15), 0xcaf649a9);
h1 ^= h2 >>> 16; h2 ^= h1 >>> 16;
return 2097152 * (h2 >>> 0) + (h1 >>> 11);
};
// MODIFIED VERSION
const cyrb53a_1=function(x,seed=0){
var i,c,l=x.length,imul=Math.imul,h1=0xdeadbeef^seed,h2=0x41c6ce57^seed;
if (typeof(x)==="string") {
for (i=0;i<l;i++) {
c=x.charCodeAt(i);
h1=imul(h1^c,0x85ebca77);
h2=imul(h2^c,0xc2b2ae3d);
}
} else {
for (i=0;i<l;i++) {
c=x[i];
h1=imul(h1^c,0x85ebca77);
h2=imul(h2^c,0xc2b2ae3d);
}
}
h1^=imul(h1^(h2>>>15),0x735a2d97);
h2^=imul(h2^(h1>>>15),0xcaf649a9);
h1^=h2>>>16;h2^=h1>>>16;
return 2097152*(h2>>>0)+(h1>>>11);
}
// BENCHMARKING
var i,j,l,s,a,
fromCc=String.fromCharCode,
rnd=Math.random,trunc=Math.trunc,
cl=console.log,ct=console.time,cte=console.timeEnd,
f=(process.argv[2]==="1"?cyrb53a_1:cyrb53a);
// generate random string (100K)
a=new Array(l=1e5);
for (i=0;i<l;i++) a[i]=trunc(rnd()*65536);
s=fromCc.apply(String,a);
// start benchmark after 5s process relaxation
cl("benchmarking",f.name,"...");
setTimeout(()=>{
// start warmup run (10K*100K=1G)
l=1e4;
for (i=0;i<l;i++) f(s);
// start actual benchmark run (100K*100K=10G)
l=1e5;
ct(":");
for (i=0;i<l;i++) f(s);
cte(":");
},5000);
Activity
bryc commentedon Apr 13, 2023
Cool! I'm surprised the performance isn't impacted. I always just assumed doing a type check would be prohibitively expensive in a benchmark. Normally I just use arrays anyway, but when I posted to
cyrb53to SO initially, I assumed most people would want to hash strings.Keep in mind
cyrb53aisn't final yet. I've yet to wrap my head around getting SMHasher to work, and when I do I'll probably have to change things to make it pass the tests better.I've also been working on a (hopefully) faster hash called BlazeHash which reads 8 bytes at a time instead of just 1. Largely the same idea as cyrb53a.
There's also BlazeHash128 which in theory could be even faster, though it needs a lot of work. It reads 16 bytes at a time and produces a 128-bit hash. Poroblem is, 128-bit hashes are harder to test fully, so I typically just use my MurmurHash3_x86_128 port when I need large hashes, since it's quite fast already.
hjerabek commentedon Apr 14, 2023
ad cyrb53a) I've read your code comments and am aware that it is still work in progress. I'm not using it in production, I just stumbled upon it as I was interested in a hash function that makes full use of JavaScript's 52/53bit integer range.
ad performance) As much as I appreciate that someone takes the time to develop high performance hash functions in pure JavaScript, it might be more "fulfilling" for you to code and test them in C. If you take a look at, for example, the xxhash benchmarks, you will find that such performance might never be achievable with a JS solution. While Turbofan can theoretically optimize the JS function's byte code to run just as fast as a C routine, in practice this is only that case for very simple functions. In that regard I must say that your cyrb53a JS function performs very well. In the benchmark I ran (100K*100K strings) the throughput on my machine was ~0.6Gb/s. If your BlazeHash versions, for example, are as fast as you expect them to be, write them in C and check whether they can hold their own against the current "top dogs" like xxhash, murmur, city etc. as far as speed, randomness, collision resistance etc. are concerned... As you were talking about SMHasher (which is written in C afaik) you might already be doing this anyway, but at least in this repository I could only find JavaScript code...
In any case, I wish you all the best for your future work.
lnfel commentedon Apr 19, 2023
I am using it to hash url strings in my personal scraper.