Hacker News Reader

Comment by danielvf | Hacker News Reader

If we are really going all out for performance optimization...

In theory, hashes are going to be very evenly distributed. With a file of that size you could probably land within 1% of the correct location just by seeking to byte offset percentage given by the first bytes of the hash...

(It's a fun article)

View on HN

They did mention they tried that, and got similar results to the binary search they were already doing: https://death.andgravity.com/pwned#position-heuristic

> We can do this once, and then binary search a safety interval around that position. Alas, this only gets rid of the fast jumps at the beginning of the binary search, and for some reason, it ends up being slightly slower than binary search alone.

I don't get why you can't do this at each step.

You can, see the next paragraph, "also narrow down around the estimated position iteratively..."

I gave up because I was too lazy to think how to do the "precompute the maximum +/- error bounds" jiggawatts mentions in https://news.ycombinator.com/item?id=34021826

BTW, loved the article, not sure how I missed that you tried this.

I assume this doesn't improve perf much because you pretty quickly zoom in on a slice of hashes that are not evenly distributed. 37GB feels like a lot of hashes but it's pretty small compared to the space of all hashes, I suspect this approach would be more effective if we were searching over a much bigger chunk of data.

could one insert empty bytes to make it evenly distributed?

Indeed that's discussed in the article, under "Position heuristic" - https://death.andgravity.com/pwned#position-heuristic

With some random sampling it looks like the worst case is 5 megabytes of error on the initial seek.

Reply on news.ycombinator.com