Get the latest tech news

The RAM Myth

The RAM myth is a belief that modern computer memory resembles perfect random-access memory. Cache is seen as an optimization for small data: if it fits in L2, it’s going to be processed faster; if it doesn’t, there’s nothing we can do. Most likely, you believe that code like this is the fastest way to shard data (I’m using Python as pseudocode; pretend I used your favorite low-level language): groups = [[] for _ in range(n_groups)] for element in elements: groups[element.group].append(element) Indeed, it’s linear (i.e. asymptotically optimal), and we have to access random indices anyway, so cache isn’t going to help us in any case. In reality, when the number of groups is high, this is leaving a lot of performance on the table, and certain asymptotically slower algorithms can perform sharding significantly faster. They are mostly used by on-disk databases, but, surprisingly, they are useful even for in-RAM data.

If the index is random, we can have our cake and eat it too: estimate the size of each bucket as len(elements) / 256 and reserve that much space. One simple micro-optimization is to allocate once and split the returned memory into chunks instead of invoking malloc(or creating vectors) multiple times. Switching to the straightforward algorithm on small inputs increases performance, as the effects of 𝒪(nlog⁡n) code are more pronounced there.

Get the Android app