4 ms·

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 pr

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)

jffry 4y ago
Indeed that's discussed in the article, under "Position heuristic" - https://death.andgravity.com/pwned#position-heuristic https://death.andgravity.com/pwned#position-heuristic
Mogzol 4y ago
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 https://death.andgravity.com/pwned#position-heuristic
- remus 4y ago
  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.
  - throwaway14356 4y ago
    could one insert empty bytes to make it evenly distributed?
- leni536 4y ago
  > 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.
  - genericlemon24 4y ago
    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 https://news.ycombinator.com/item?id=34021826
    - danielvf 4y ago
      BTW, loved the article, not sure how I missed that you tried this.
benlivengood 4y ago
With some random sampling it looks like the worst case is 5 megabytes of error on the initial seek.

jffry 4y ago

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

Mogzol 4y ago

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 https://death.andgravity.com/pwned#position-heuristic

remus 4y ago
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.
- throwaway14356 4y ago
  could one insert empty bytes to make it evenly distributed?
leni536 4y ago
> 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.
- genericlemon24 4y ago
  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 https://news.ycombinator.com/item?id=34021826
  - danielvf 4y ago
    BTW, loved the article, not sure how I missed that you tried this.

benlivengood 4y ago

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