News for hackers. Stuff that matters.
Re:The Billion Row Challenge (1BRC) – Step-by-Step from 71s ... by o11c on Thursday February 22, 2024 @03:35PM (#39472819)
There's a reason everybody uses hashing - if your data is trusted, it does very few operations.

Tries have to allocate, walk, and interpret multiple nodes. Perhaps not as bad as trees (though that depends on how many possible trie node representations there are, vs what the data density is at each level), but still worse than the non-colliding hash.

That said, with a finite dataset a perfect hash would probably beat a general hash though.

Re:The Billion Row Challenge (1BRC) – Step-by-Step from 71s ... by koliber on Thursday February 22, 2024 @05:24PM (#39474172)
Was the list of city names known? Could you statically pre-build the Trie structure?
Re:The Billion Row Challenge (1BRC) – Step-by-Step from 71s ... by haxen on Thursday February 22, 2024 @05:30PM (#39474229)
It was known, but the requirement was that the program keep working for an arbitrary keyset that conforms to the specified rules (up to 10,000 unique keys, each up to 100 bytes in length).