4 ms·

The problem is that the most used memory model for algorithms performance research is not true in the real world: O(1) memory access. In the real world memory a

The problem is that the most used memory model for algorithms performance research is not true in the real world: O(1) memory access. In the real world memory access is not a O(1) operation, it takes a different amount of time to access memory in the different levels of cache. https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

jstimpfle 7y ago
Memory access time is bounded by a constant time - given by the last level in the hierarchy (which would be the SSD or HD in this case). So, access time is indeed O(1). What's not true in the real world is that the actual value of the constant can be ignored. Memory or disk access on the one hand, and simple arithmetic operations on the other, are both O(1) but the difference is significant.
- CalChris 7y ago
  No, it isn't bounded by the access time of the last level in the hierarchy. You could miss in the TLB before you even get to the storage hierarchy. Your TLB miss may even require a page table walk with more misses. You could even get rescheduled because your quantum was exceeded. You probably think this never happened but it used to always happen. The Linux scheduler used to traverse a linked list of pages (because Linus didn't know any better). Once the number of processes being scheduled exceeded something like 64, it slowed to a crawl consuming most of the quanta just rescheduling.
  - jstimpfle 7y ago
    Yeah, there are finer points to consider to get at an actual bound, and there might be some quirks and infelicities on some platforms. But this is not about competing processes on the system. For matters of asymptotic Analysis the access time is still O(1), i.e. bounded by a constant. If it wasn't, what would it be?
mruts 7y ago
O(constant) = O(constant - 1) = O(1) They are all the same.

jstimpfle 7y ago

Memory access time is bounded by a constant time - given by the last level in the hierarchy (which would be the SSD or HD in this case). So, access time is indeed O(1). What's not true in the real world is that the actual value of the constant can be ignored. Memory or disk access on the one hand, and simple arithmetic operations on the other, are both O(1) but the difference is significant.

CalChris 7y ago
No, it isn't bounded by the access time of the last level in the hierarchy. You could miss in the TLB before you even get to the storage hierarchy. Your TLB miss may even require a page table walk with more misses. You could even get rescheduled because your quantum was exceeded. You probably think this never happened but it used to always happen. The Linux scheduler used to traverse a linked list of pages (because Linus didn't know any better). Once the number of processes being scheduled exceeded something like 64, it slowed to a crawl consuming most of the quanta just rescheduling.
- jstimpfle 7y ago
  Yeah, there are finer points to consider to get at an actual bound, and there might be some quirks and infelicities on some platforms. But this is not about competing processes on the system. For matters of asymptotic Analysis the access time is still O(1), i.e. bounded by a constant. If it wasn't, what would it be?

mruts 7y ago

O(constant) = O(constant - 1) = O(1) They are all the same.