TIL: divide by 10 with this one weird number

Running an application across two physical databases is not a straightforward thing. One of the relatively easier ways to do it involves assigning each database instance a shard number and then arranging for all your primary key IDs to end with that number. For example, shard 0 generates IDs like 1230, 40, 482340, shard 1 generates IDs like 1231, 41, 482341, and shard 2 generates IDs like 1232, 42, 482342, etc. all the way up to 9. If you want more than 10 database shards, it gets more involved.

My brain is wired oddly, so I came to wonder how you would quickly get the shard ID for an ID (e.g. shard 1 for 1231). This is really easy with decimal math; you just divide by 10. However, we run our databases on computers that can only do binary math, so its not actually simple.

But it turns out you can do it quite fast! There’s one weird number, expressed as `0x1999999A` hexadecimal, that is very close to multiplying by the fraction 1/10 (plus further binary math and register trickery). Thus you can do this in only a few instructions on Intel processors released in the past twenty years.

I’m really glad someone else figured this out.

Published by Adam Keys

Telling a joke. Typing.