because memory access performance is not O(1) but depends on the size of what's in memory (https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html). Every byte used makes the whole thing slower.
because memory access performance is not O(1) but depends on the size of what's in memory (https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html). Every byte used makes the whole thing slower.
I am not following, isn't this just a graph that shows that how fast operations happen is largely dependent on the odds that it is in cache at various levels (CPU/Ram/Disk)?
The memory operation itself is O(1), around 100 ns, where at a certain point we are doing full ram fetches each time because the odds of it being in CPU cache are low?
Typically O notation is an upper bound, and it holds well there.
That said, due to cache hits, the lower bound is much lower than that.
You see similar performance degradation if you iterate in a double sided array the in the wrong index first.
RAM is always storing something, it’s just sometimes zeros or garbage. Nothing in how DRAM timings work is sensitive to what bits are encoded in each cell.
> Every byte used makes the whole thing slower.
This is an incorrect conclusion to make from the link you posted in the context of this discussion. That post is a very long-winded way of saying that the average speed of addressing N elements depends on N and the size of the caches, which isn't news to anyone. Key word: addressing.
Memory access performance depends on the _maximum size of memory you need to address_. You can clearly see it in the graph of that article where L1, L2, L3 and RAM are no longer enough to fit the linked list. However while the working set fits in them the performance scales much better. So as long as you give priority to the working set, you can fill the rest of the biggest memory with whatever you want without affecting performance.
why is it not O(1)? It has to service within a deadline time, so it is still constant.