~skeeto/public-inbox

1

https://nullprogram.com/blog/2018/07/31/

Marc Lehmann
Details
Message ID
<YSAKn560F8d4LDky@schmorp.de>
DKIM signature
missing
Download raw message
Hi!

Just notifying you that I added your 32 lowbias32 function to libecb:

   http://pod.tst.eu/http://cvs.schmorp.de/libecb/ecb.pod#BIT_MIXING_HASHING
   http://cvs.schmorp.de/libecb/ecb.h

I also added the mxing function based on Sebastiona Vigna's splitmix64, which
is also given on your page.

Unfortunately, I didn't find a reverse, so I wrote one myself (and
googling the constants afterwards, I wasn't the first to do so, I wish I
had the reverse first to google the reverse function. ehm...).

So... thanks for doing and publishing your work - libecb is not a
particulalry widely-used library, but I wanted to drop you a note that
your work is actually used (also, microsoft mimalloc uses your lowbias32
function, if you didn't already now).

And last not least, other than providing an improved 64 bit function, your
page is so useful it could only be improved by also listing the reverse
for the splitmix64 function. (hint, hint, nudge, nudge, I even quote the
salient parts here so you don't even have to look elsewhere, or, heaven
forbid, do maths:

   uint64_t unmix64 (uint64_t v)
   {
     v ^= v >> 31 ^ v >> 62; v *= 0x319642b2d24d8ec3U;
     v ^= v >> 27 ^ v >> 54; v *= 0x96de1b173f119089U;
     v ^= v >> 30 ^ v >> 60;
     return v;
   }

Finding a better 64 bit function that uses some shifts >= 32 would, of
course, be even better.

Greetings,
Marc

-- 
                The choice of a       Deliantra, the free code+content MORPG
      -----==-     _GNU_              http://www.deliantra.net
      ----==-- _       generation
      ---==---(_)__  __ ____  __      Marc Lehmann
      --==---/ / _ \/ // /\ \/ /      schmorp@schmorp.de
      -=====/_/_//_/\_,_/ /_/\_\
Details
Message ID
<20210821174945.gyeag7ltmge4iq5q@nullprogram.com>
In-Reply-To
<YSAKn560F8d4LDky@schmorp.de> (view parent)
DKIM signature
missing
Download raw message
Interesting, and thanks for the heads up, Marc! I didn't know about 
mimalloc using lowbias32. In case you hadn't noticed, I've since found 
some very slightly better 32-bit mixers. I haven't given them fancy names, 
and the statistical difference is so small that it probably makes no 
difference in practice, but they're available for use (under "more 2-round 
constants"):

https://github.com/skeeto/hash-prospector#two-round-functions

Even better, the second best I've found, which itself is also better than 
lowbias32, has an efficient inverse.

> Unfortunately, I didn't find a reverse, so I wrote one myself

Note lowbias32_r in the hash prospector README. I have a function in 
hillclimb.c to find modular multiplicative inverses, but probably the most 
convenient way these days is to use the 3-arg pow function in Python 3.8 
or later:

pow(0xbf58476d1ce4e5b9, -1, 1<<64)  # => 0x96de1b173f119089

Outside of the one obvious case, xorshift is a little trickier, but you 
can find a code description in hillclimb.c:

https://github.com/skeeto/hash-prospector/blob/master/hillclimb.c#L410

Once you have a handle on it, you can do that one in your head. Armed with 
Python for multiplicative inverse and this knowledge, you can reverse any 
basic xorshift-multiply, including splittable64, on the fly. That's why I 
haven't been too fussed with listing inverses.

> Finding a better 64 bit function that uses some shifts >= 32 would, of 
> course, be even better.

Yup, someday I'd like to figure out how to quickly and reliably evaluate 
64-bit mixers the same way I did with 32-bit so that I could find more 
options.

> your page is so useful it could only be improved by also listing the 
> reverse for the splitmix64 function.

Thanks, I've added the inverse to my article.
Reply to thread Export thread (mbox)