5 ms·
> in fact lots of standard big O complexity analysis assumes a von Neumann machine – O(1) random access. i don't see the logic here.
by baq 11y ago
> in fact lots of standard big O complexity analysis assumes a von Neumann machine – O(1) random access.
i don't see the logic here.
- lsd5you 11y agoMemory 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?