19 ms·

Academic computer science tends to model a 'computer' as a simplified pointer-machine with O(1) memory access everywhere. In reality computers actually have a

Academic computer science tends to model a 'computer' as a simplified pointer-machine with O(1) memory access everywhere. In reality computers actually have a memory hierarchy and no memory access is ever O(1). In RAM it only looks like constant access, because the memory address search is hardware optimized. Many programming languages are heavily inspired by this academic pointer chasing and so their performance is pretty terrible, no matter how clever typing systems or compiler optimizations you add. It's all crap once you scale to a decent size of data and beyond one machine. The only thing that performs and transparently scales beyond one cpu are 1. array languages and 2. sql databases. Both of these actually understand things such as linear memory access, data-parallelism, the fact that cpus have caches and that 'memory' is a hierarchy of cache levels, RAM, disk, etc.

jltsiren 5y ago
Academic computer science uses many different models for analyzing computational complexity. Most of them are not taught at undergraduate level, because students generally expect to graduate without spending 10+ years at college. Computer science is a wide and diverse field, and it's impossible to teach everything every CS graduate should know in any reasonable time. The random access model is usually taught first, because it works reasonably well in most situations. A slight variation of it, the cell-probe model, tends to be more useful for proving lower bounds. In that model, all computation is free and only memory accesses count. A more practical variant of the cell-probe model is often called the external memory model. The computer is assumed to have M words of fast memory and an unlimited amount of slow memory that is accessed in blocks of B words. Computation is still free, and parameters M and B are both known to the algorithm. This model is useful in situations where accesses to one level of memory hierarchy dominate the running time. The cache-oblivious model can be useful in situations where many levels of memory hierarchy matter. It can be understood as the external memory model with unknown values of M and B. Another useful technique is parameterizing the complexity in terms of key operations. If operation X takes t_X time, we can then say than an algorithm takes O(|P| t_X log n) time with pattern P and problem size n.
jhgb 5y ago
> with O(1) memory access everywhere Isn't that technically correct? The access time is bounded by a constant, hence the 1 -- unless there's a tape in your memory hiearchy. (That you always strive for a better constant is of course another matter.)
- snidane 5y ago
  It can't be O(1) because to just search for a memory location you need at least a binary search. Since memory lookup is implemented in hardware it is treated as constant access. Of course this is all obscured by magnitudes of the memory hierarchy. For real systems such as databases, it is a better idea to treat random memory access as O(log n), which then justifies doing batch lookups and libear scans. All of this O(1) RAM access makes people confused and they never start thinking beyond the simple undergrad abstraction of a single cpu with a single layer of RAM.

jltsiren 5y ago

Academic computer science uses many different models for analyzing computational complexity. Most of them are not taught at undergraduate level, because students generally expect to graduate without spending 10+ years at college. Computer science is a wide and diverse field, and it's impossible to teach everything every CS graduate should know in any reasonable time. The random access model is usually taught first, because it works reasonably well in most situations. A slight variation of it, the cell-probe model, tends to be more useful for proving lower bounds. In that model, all computation is free and only memory accesses count. A more practical variant of the cell-probe model is often called the external memory model. The computer is assumed to have M words of fast memory and an unlimited amount of slow memory that is accessed in blocks of B words. Computation is still free, and parameters M and B are both known to the algorithm. This model is useful in situations where accesses to one level of memory hierarchy dominate the running time. The cache-oblivious model can be useful in situations where many levels of memory hierarchy matter. It can be understood as the external memory model with unknown values of M and B. Another useful technique is parameterizing the complexity in terms of key operations. If operation X takes t_X time, we can then say than an algorithm takes O(|P| t_X log n) time with pattern P and problem size n.

jhgb 5y ago

> with O(1) memory access everywhere Isn't that technically correct? The access time is bounded by a constant, hence the 1 -- unless there's a tape in your memory hiearchy. (That you always strive for a better constant is of course another matter.)

snidane 5y ago
It can't be O(1) because to just search for a memory location you need at least a binary search. Since memory lookup is implemented in hardware it is treated as constant access. Of course this is all obscured by magnitudes of the memory hierarchy. For real systems such as databases, it is a better idea to treat random memory access as O(log n), which then justifies doing batch lookups and libear scans. All of this O(1) RAM access makes people confused and they never start thinking beyond the simple undergrad abstraction of a single cpu with a single layer of RAM.