3 ms·

Even a statically-allocated C array doesn't "really" have constant-time lookup with respect to size; the more elements it has the greater the rate of cache miss

Even a statically-allocated C array doesn't "really" have constant-time lookup with respect to size; the more elements it has the greater the rate of cache misses and page faults on lookups becomes (I'm pretty sure this can be proven true of all data structures). Moreover the possibility of cache misses and page faults means that while lookups take a fixed number of CPU cycles on average, any single lookup might take between <1 and thousands of cycles. If you truly need your data accesses to take a fixed number of CPU cycles, you have to handwrite assembly and put everything in registers. And even that doesn't account for instruction reordering and the possibility of interrupts or context switches. I would assume the reason the Scala website calls Vector log(n) element lookup "effectively constant" is because in real-world use (as opposed to hypothetical ideal Von Neumann machines), the slowdown of the lookup algorithm with respect to n is nil, in relation to the decrease in cache and allocation efficiency with respect to n. If you're creating some sort of ultra-fine-grained real-time system where everything needs to take a fixed number of clock cycles, Scala would be a pretty terrible tool for the job. For that sort of thing you'd want MISRA C or assembly running on bare metal, or a FPGA or ASIC.

arnioxux 9y ago
There's an interesting argument based on physics on why memory access is O(sqrt(N)): http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-part-i http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-p... Relevant quote: > The amount of information that can fit within a sphere with radius r can be calculated using the Bekenstein bound, which says that the amount of information that can be contained by a sphere is directly proportional to the radius and mass: N ∝ r·m. So how massive can a sphere get? Well, what is the most dense thing in existence? A black hole! It turns out that the mass of a black hole is directly proportional to its radius: m ∝ r. This means that the amount of information that can fit inside a sphere of radius r is N ∝ r². And so we come to the conclusion that the amount of information contained in a sphere is bounded by the area of that sphere - not the volume! > In short: if you try to squeeze too much L1 cache onto your CPU it will eventually collapse into a black hole, and that would make it awkward to get the results of the computation back to the user. But honestly I find all of these arguments equally pedantic. People often forget Big Oh is a tool just like any other tool. It's useful for estimating number of X, whether X is cpu instructions, cache miss, disk read or whatever. When it stops being a good estimate (whether it's because your real world N is too small for growth rate to dominate, or stuff you're counting are not unit-cost comparable, or you're not even counting the right things in the first place), just stop using it and count cycles on a benchmark instead.
- deepsun 9y ago
  You're comparing radius (in Bekenstein bound) and event horizon (in black hole). Event horizon is a pretty different beast than radius. If we define "density" of a black holes using event horizon instead of radius (black holes don't have real radius), then supermassive black holes are actually pretty "light". A black hole of the mass of our universe would have "density" of the universe, which is mostly empty.
  - arnioxux 9y ago
    Not my article and I don't know any theoretical physics. In case that point happens to be false, I think his other argument still works: - "data centers ... are spread out on the two-dimensional surface of the earth" - if we tightly pack these data centers on the surface it will form a circle with area O(N) so distance to furthest data center is O(sqrt(N)). (sky scraper height is negligible) Anyway, it's more of an interesting thought experiment than of any practical use. Nobody sane would estimate cost of generic "information retrieval" that mixes cost of ram/disk/network.
- edejong 9y ago
  Thanks, enjoyed reading that. I thought in similar lines, but never wrote it down.
saurik 9y ago
The concept of "constant time" doesn't mean "always the same number of instructions, a value we can exactly predict": it means essentially "there exists some X such that for all accesses of items in a structure of size N at any index it will always take time less than X, independent of N". For "linear time" we would say "there exists some X such that for all accesses of items in a structure of size N at any index it will always take time less than X multiplied by the value N". So "O(Q)" means "there exists some X such that for all accesses of items in a structure of size N at any index it will always take time less than X multiplied by the expression Q, which is expressed in terms of N". O(1) is "constant time", and does not mean things take one instruction: it means the expression does not depend on N. There is no O(1000): that is the same as O(1); and if an operation takes randomly either 10 or 1000 cycles, it still is O(1) as X is 1000: both 10 and 1000 are bounded by 1000 multiplied by 1. Time complexity is thereby a measure of how scalable something is, not how long it will take. An operation that is linear might beat one that is logarithmic at small values of N, but eventually you will have an input large enough that the logarithmic one is not just faster but will always be faster as the constant multipliers can no longer compensate the bounds for the one underlying expression being swamped by the other one. The constant time constraint is true for simple memory access on a computer running a single process (which I only add as a constraint as the entire theoretically framework breaks otherwise), even if some accesses take a thousand times longer than other ones: there is a slowest possible time past which it will not be slower. No matter how large the array gets, it isn't going to get slower, even though it is super fast for extremely small arrays that fit entirely in some small amount of cache. Of course, it might not be true if memory is backed by a file and that file is on network storage, and the remote file is stored in a linked list ;P, but that isn't the situation with cache: the controller doesn't even keep a resizable data structure for cache lookups. If you plotted a graph of the pefromance of lookups vs. the size of the array, once you got noticeably past the size of the cache the line would stop growing, and the entire thing would fit under a flat line at some constant X. There is a fiction here, and that is that we can think about these issues at all in the world of a computer, which has a limited amount of storage (which means there exists some I past which it is no longer possible to even access elements as we cannot allocate an array that large); but it isn't due to cache misses and has nothing to do with the kind of predictable real-time constraints you describe: those are constant multipliers on the complexity. That is when you enter the world of physics, which is arguably more interesting.

arnioxux 9y ago

There's an interesting argument based on physics on why memory access is O(sqrt(N)): http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-part-i http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-p... Relevant quote: > The amount of information that can fit within a sphere with radius r can be calculated using the Bekenstein bound, which says that the amount of information that can be contained by a sphere is directly proportional to the radius and mass: N ∝ r·m. So how massive can a sphere get? Well, what is the most dense thing in existence? A black hole! It turns out that the mass of a black hole is directly proportional to its radius: m ∝ r. This means that the amount of information that can fit inside a sphere of radius r is N ∝ r². And so we come to the conclusion that the amount of information contained in a sphere is bounded by the area of that sphere - not the volume! > In short: if you try to squeeze too much L1 cache onto your CPU it will eventually collapse into a black hole, and that would make it awkward to get the results of the computation back to the user. But honestly I find all of these arguments equally pedantic. People often forget Big Oh is a tool just like any other tool. It's useful for estimating number of X, whether X is cpu instructions, cache miss, disk read or whatever. When it stops being a good estimate (whether it's because your real world N is too small for growth rate to dominate, or stuff you're counting are not unit-cost comparable, or you're not even counting the right things in the first place), just stop using it and count cycles on a benchmark instead.

deepsun 9y ago
You're comparing radius (in Bekenstein bound) and event horizon (in black hole). Event horizon is a pretty different beast than radius. If we define "density" of a black holes using event horizon instead of radius (black holes don't have real radius), then supermassive black holes are actually pretty "light". A black hole of the mass of our universe would have "density" of the universe, which is mostly empty.
- arnioxux 9y ago
  Not my article and I don't know any theoretical physics. In case that point happens to be false, I think his other argument still works: - "data centers ... are spread out on the two-dimensional surface of the earth" - if we tightly pack these data centers on the surface it will form a circle with area O(N) so distance to furthest data center is O(sqrt(N)). (sky scraper height is negligible) Anyway, it's more of an interesting thought experiment than of any practical use. Nobody sane would estimate cost of generic "information retrieval" that mixes cost of ram/disk/network.
edejong 9y ago
Thanks, enjoyed reading that. I thought in similar lines, but never wrote it down.

saurik 9y ago

The concept of "constant time" doesn't mean "always the same number of instructions, a value we can exactly predict": it means essentially "there exists some X such that for all accesses of items in a structure of size N at any index it will always take time less than X, independent of N". For "linear time" we would say "there exists some X such that for all accesses of items in a structure of size N at any index it will always take time less than X multiplied by the value N". So "O(Q)" means "there exists some X such that for all accesses of items in a structure of size N at any index it will always take time less than X multiplied by the expression Q, which is expressed in terms of N". O(1) is "constant time", and does not mean things take one instruction: it means the expression does not depend on N. There is no O(1000): that is the same as O(1); and if an operation takes randomly either 10 or 1000 cycles, it still is O(1) as X is 1000: both 10 and 1000 are bounded by 1000 multiplied by 1. Time complexity is thereby a measure of how scalable something is, not how long it will take. An operation that is linear might beat one that is logarithmic at small values of N, but eventually you will have an input large enough that the logarithmic one is not just faster but will always be faster as the constant multipliers can no longer compensate the bounds for the one underlying expression being swamped by the other one. The constant time constraint is true for simple memory access on a computer running a single process (which I only add as a constraint as the entire theoretically framework breaks otherwise), even if some accesses take a thousand times longer than other ones: there is a slowest possible time past which it will not be slower. No matter how large the array gets, it isn't going to get slower, even though it is super fast for extremely small arrays that fit entirely in some small amount of cache. Of course, it might not be true if memory is backed by a file and that file is on network storage, and the remote file is stored in a linked list ;P, but that isn't the situation with cache: the controller doesn't even keep a resizable data structure for cache lookups. If you plotted a graph of the pefromance of lookups vs. the size of the array, once you got noticeably past the size of the cache the line would stop growing, and the entire thing would fit under a flat line at some constant X. There is a fiction here, and that is that we can think about these issues at all in the world of a computer, which has a limited amount of storage (which means there exists some I past which it is no longer possible to even access elements as we cannot allocate an array that large); but it isn't due to cache misses and has nothing to do with the kind of predictable real-time constraints you describe: those are constant multipliers on the complexity. That is when you enter the world of physics, which is arguably more interesting.