News for hackers. Stuff that matters.
Re:A new fast hash table in response to Google’s new fast ha... by MaxBarraclough on Tuesday May 29, 2018 @09:08AM (#17178769)
> even if you don't buy that it clearly can't be less than O(N^1/3)

Maybe I'm missing something, but why's that?

To the rest of your comment: all good points.

Re:A new fast hash table in response to Google’s new fast ha... by voidmain on Tuesday May 29, 2018 @09:18AM (#17178851)
Well, if with your best technology you can pack B bits of information in 1 m^3 of space, and you need to store N bits of information, you are going to need (N/B) m^3 of space to store it. And then the speed of light limits you to around (N/B)^(1/3)/c seconds of latency to get to the farthest bits.

(This ultimately violates the Bekenstein bound - as your server cube grows it will eventually collapse into a black hole - but this is not really a concern with forseeable technology! More practically, though, Earth's gravity makes it hard to build very high in the air, which limits you to O(N^1/2), and things like cooling and maintenance access probably impose a limit somewhere in between.)

Re:A new fast hash table in response to Google’s new fast ha... by MaxBarraclough on Tuesday May 29, 2018 @09:35AM (#17179000)
Makes sense, thanks.
Re:A new fast hash table in response to Google’s new fast ha... by adrianN on Tuesday May 29, 2018 @09:19AM (#17178861)
Imagine your bits stored in a sphere around your CPU. Take into account the time light needs to reach the bit you want to touch.