3 ms·
Why the string searching? One million bits is 125KB. That would fit in L2 cache. Just build a bitmap of interesting results (small enough to ship with the app),
by ryan-c 3y ago
Why the string searching? One million bits is 125KB. That would fit in L2 cache. Just build a bitmap of interesting results (small enough to ship with the app), do modulo 1000000, then do a lookup in the bit map. Could even be a byte map where the byte value indicates type of interesting number and would still fit in cache.
For sextuplets, you can just check whether the value is zero modulo 111111...
- jakey_bakey 3y agoI actually mentioned this in the article! That's a nice catch on the L2 cache reasoning and modulo idea, that saves on spenny heap allocations everywhere. I did the first sweep of optimisations to kill the super-slow regex and turn the slowest operations into a set matching operation. I considered pre-processing all the potential interesting codes, reducing everything to a simple dict/set matching, but by that point the actual operation to generate OTPs was orders of magnitude slower than everything else, so there would be negligible user-facing benefit to doing so.
- ryan-c 3y agoAre you caching a keyed HMAC context? Given the data sizes, it ought to be at least one call of the SHA transform function to set the key, and one to produce the hash. They keying operation isn't dependant on the data and its result can therefore be reused.