2 ms·
Here's the problem, the sqrt(N) assumption is based on completely random access, where most accesses bust all the caches. What will matter more, when it comes t
by falcolas 10y ago
Here's the problem, the sqrt(N) assumption is based on completely random access, where most accesses bust all the caches. What will matter more, when it comes to the cost of memory in real applications, is the actual size of your dataset in relation to the cache sizes, and whether your access is sequential across a region of memory (an array) or random (a scrambled linked list).
In practical terms, the plateaus of the stair step graphs matter more than the general trend of the line.
- AstralStorm 10y agoUnless you're concerned about worst case scenario, where the last part is definitely not a plateau ever. You can reduce it to a Turing machine fetching you data sequentially.