ram_bench

Code is here: https://github.com/emilk/ram_bench/blob/master/list_traversa... The author makes 2 allocations: Node* memory = (Node*)malloc(N * sizeof(Node)); Node** nodes = (Node**)malloc(N * sizeof(Node*)); Of those, only the first one (memory) is actually used during measurement, The seconds one (nodes) is just there to help shuffle the linked list, and is freeded before the actual test: free(nodes); // Free up unused memory before meassuring: // Do the actual measurements: Int start = clock(); ... Since the linked list is shuffeled, the nodes will be linked in a random order. However, since the total memory is contigous, that is the only factor (instead of having every node be a separate allocation, which could allow the system to put every node on a separate page)

> Radix sort is theoretically O(N), Nothing theoretical about it: Sorting a list of all IP addresses can absolutely and trivially be done in O(N) > in reality you can't do better than O(log N) You can't traverse the list once in <N so the complexity of any sort must be ≥N. > but memory access is logarithmic No it's not, but it's also irrelevant: A radix sort doesn't need any reads if the values are unique and dense (such as the case IP addresses, permutation arrays, and so on). > Edit: I misremembered, memory access is actually O(sqrt(N)): https://github.com/emilk/ram_bench It's not that either. The author ran out of memory; They ran a program that needs 10GB of ram on a machine with only 8GB of ram in it. If you give that program enough memory (I have around 105gb free) it produces a silly graph that looks nothing like O(√N): https://im

Radix sort is theoretically O(N), but memory access is logarithmic so in reality you can't do better than O(log N) no matter what algorithm you use. Only constant factors matter at that point. Edit: I misremembered, memory access is actually O(sqrt(N)): https://github.com/emilk/ram_bench

There is the idea that you should treat memory access as an O(N^.5) operation: https://github.com/emilk/ram_bench I am not sure if any serious academic work has been built on this model, but it's a nice short hand.

Remember it takes 100ns to get a value from main memory (after you miss all the caches). With random-access data structures the total size tells you the speed. Here's a test to see how your CPU does: https://github.com/emilk/ram_bench