5 ms·

Why would normal memory access be O(log n)? Seems to me jumping to a random address should be an O(1) operation. Would be pretty dumb if jumping to higher RAM a

Why would normal memory access be O(log n)? Seems to me jumping to a random address should be an O(1) operation. Would be pretty dumb if jumping to higher RAM addresses takes longer than jumping to lower RAM, excluding hardware things like different RAM sticks or page files.

Jaxan 3y ago
> excluding hardware things like different RAM sticks or page files. Exactly this! Also as n grows you will need bigger address busses (or have serial communication).
Athas 3y ago
It depends on your definitions and assumptions. Here 'n' is not the address, but the size of memory (or the largest possible/worst-case address). In the universe we inhabit, due to limitations on information density in a given volume[1], the worst-case random access time for a memory of size 'n' would be the cube root of 'n', because you need to transmit a signal at the speed of light between to points inside a sphere. Real computers tend not to be able to store their information in all three dimensions (I think I once saw an argument for why this is also theoretically not feasible), and in practice appear to have worst-case access times that are logarithmic. It's fundamentally for the same reason: the bigger your memory, the more distant will be the most remote (worst-case) part of it. Of course, in a single specific desktop or server computer, changing the capacity of your RAM sticks will likely not affect worst case access speeds, because the speed limit is likely based on the maximum capacity of the machine (a constant). So this kind of analysis is useful for pondering the ultimate limits of worst case memory accesses (and does also have some relevance huge computers), but in practice you will of course find that cache/locality effects are far more important for performance on real computers. [1]: Since information is energy and therefore mass, a sufficiently dense store of information would collapse into a singularity, and you better hope your pointer doesn't point into one of those.
- btdmaster 3y ago
  There was an article that mentioned that cbrt(n) is worst-case array access, not constant time. They did some benchmarks across the CPU cache/RAM/SSD boundary to show this practically. I can't seem to find it though, where was it? Edit: found it, https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
deleted 3y ago
[deleted]

Jaxan 3y ago

> excluding hardware things like different RAM sticks or page files. Exactly this! Also as n grows you will need bigger address busses (or have serial communication).

Athas 3y ago

It depends on your definitions and assumptions. Here 'n' is not the address, but the size of memory (or the largest possible/worst-case address). In the universe we inhabit, due to limitations on information density in a given volume[1], the worst-case random access time for a memory of size 'n' would be the cube root of 'n', because you need to transmit a signal at the speed of light between to points inside a sphere. Real computers tend not to be able to store their information in all three dimensions (I think I once saw an argument for why this is also theoretically not feasible), and in practice appear to have worst-case access times that are logarithmic. It's fundamentally for the same reason: the bigger your memory, the more distant will be the most remote (worst-case) part of it. Of course, in a single specific desktop or server computer, changing the capacity of your RAM sticks will likely not affect worst case access speeds, because the speed limit is likely based on the maximum capacity of the machine (a constant). So this kind of analysis is useful for pondering the ultimate limits of worst case memory accesses (and does also have some relevance huge computers), but in practice you will of course find that cache/locality effects are far more important for performance on real computers. [1]: Since information is energy and therefore mass, a sufficiently dense store of information would collapse into a singularity, and you better hope your pointer doesn't point into one of those.

btdmaster 3y ago
There was an article that mentioned that cbrt(n) is worst-case array access, not constant time. They did some benchmarks across the CPU cache/RAM/SSD boundary to show this practically. I can't seem to find it though, where was it? Edit: found it, https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

deleted 3y ago

[deleted]