News for hackers. Stuff that matters.

A comment on A new fast hash table in response to Google’s new fast hash table. Parent comment

Re:A new fast hash table in response to Google’s new fast ha... by timerol on Tuesday May 29, 2018 @10:03AM (#17179230)
The article in question: https://news.ycombinator.com/item?id=12383012

It's fun to think about, but the presentation played fast and loose with a few concepts. Sparked some lively discussion because of that. I really like the idea of needing to count random memory accesses as costing more than sequential accesses when analyzing algorithms in a big-O-type notation.

[ Parent | on HN ]
Re:A new fast hash table in response to Google’s new fast ha... by Ar-Curunir on Tuesday May 29, 2018 @01:46PM (#17181367)
back when HDDs were a thing, and sequential accesses were much, much faster than random accesses.

So people developed algorithms that maximised locality of reference, like B-trees. An interesting line of work in this vein is that of cache-oblivious algorithms :)

[ Parent | on HN ]