4 ms·
Memory lookup can be considered O(log(m)) where m is the amount of memory you are using. e.g. If the addressable memory space exceeds the word size then it woul
by lsd5you 11y ago
Memory lookup can be considered O(log(m)) where m is the amount of memory you are using. e.g. If the addressable memory space exceeds the word size then it would take two cycles to do a load from memory.
In practice memory lookup is O(1) but there is hard limit to the amount that can be used. Except of course this is not true - there are costs to using more memory - because of the cache hierarchy.
- adrianN 11y agoIn practice, whether memory lookup is constant time or log time depends on your access pattern. The TLB makes random lookups more expensive. See for example https://people.mpi-inf.mpg.de/~tojot/papers/TowardBetterComputationModelsForModernMachines.pdf https://people.mpi-inf.mpg.de/~tojot/papers/TowardBetterComp...
- kragen 11y agoIf we're really going to talk about memories of over 2⁶⁴ bytes, in the limit it's O(m^⅓) if you're talking about latency, because larger memories need to be physically further away, on average.
- lsd5you 11y agoGood point! Do we need to qualify this with saying over 2^64 bytes? What is the mose memory you can get in a machine with current hardware and constant latency? Just goes to show how much more important the space effect is vs. the addressing effect. No doubt if we tried to have 2^64 bytes of memory we would end up with another layer of cache or 2.
- kragen 11y agoThe most memory I've seen on a machine with current hardware and constant latency is 512 kilobytes, like in some of the Atmel ARM SAM D1 chips. Above that, you start getting into off-chip buses‚ which generally have substantially higher latency, even before you get to the extra latencies added by DRAM chips.
- repsilat 11y agoThe newest physics is even more pessimistic, putting it at O(m^½) because of the holographic principle. Essentially, the theory goes that the amount of data you can cram into a spherical volume of space scales in proportion to its surface area, IIRC with a density on the order of bits per Planck area. https://en.wikipedia.org/wiki/Bekenstein_bound https://en.wikipedia.org/wiki/Bekenstein_bound https://en.wikipedia.org/wiki/Holographic_principle#Limit_on_information_density https://en.wikipedia.org/wiki/Holographic_principle#Limit_on...
- kragen 11y agoI don't understand the Bekenstein bound well enough to comment very intelligently, but isn't that a bound on the information content of your CPU rather than its information throughput or latency?