4 ms·

For the problem mentioned in the post (determining whether a given password is valid), how about using a Trie[0]? Wouldn't this work perfectly in this situation

• salmonellaeater 12y ago
  The author's point about memory access being non-constant still holds for a trie. Nodes that have been recently accessed will still be in cache and will load faster. The quest for a sublinear algorithm is futile in the face of caching. The solution is similar to the solution to branch-based timing attacks: don't branch, in code or in data. Every comparison must follow the same code path and the same memory path, and that means reading every element of the data structure every time you search.