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 fa

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.