4 ms·

Fair enough that perhaps you can allow M to be a function of N. It feels like this sort of model might run into other issues, though. If you treat a memory look

by oivey 3y ago

Fair enough that perhaps you can allow M to be a function of N. It feels like this sort of model might run into other issues, though. If you treat a memory look up as an operation on an infinitely long bit string that therefore takes non-constant time, then why wouldn’t you select integer addition to act on unbounded numbers and have similar asymptotic behavior? Obviously in practice M >> N, M is not a function of N, and/or M is constant, but we’re essentially discussing how to define the axioms underlying the complexity analysis.

tsimionescu 3y ago
The model is ultimately a choice, and you chose one that models important aspects of your domain. People very very often work with data that doesn't fit into the fastest available memory, so modeling that fact that memory accesses taking O(foo(N)) time makes a lot of sense if you want to compare the performance of algorithms with different amounts of memory accesses. The performance differences predicted by a model that adds this complexity compared to a model that doesn't will be better. For example, traditional complexity analysis predicts that linear search in a linked list should be about as fast as in an array up to some constant factor. If you instead model memory access as taking longer the larger the data structure you seek to access, you'll predict that linked list search is in fact worse and worse compared to array search as the size of each increases. This second prediction will more closely match the actual performance on real hardware. In contrast, people very rarely work on problems where fixed, small size integers (i32, i64) are not good enough. Those that do also typically model addition as an O(foo(N)) operation. There is of course some interesting overlap where you'd perhaps want to model the actual address calculation using large integers, but since in practice that will almost always be much faster than the actual memory access itself, it's rarely useful to account for it inatead of the memory access cost.
- oivey 3y ago
  I think we’re in agreement mostly. I was trying to make the point that the model needs to contain some practical assumptions at the level we’re discussing, or it breaks down. Both binary integer addition and binary address look ups are O(L) where L is the number of bits in the number. In practice for both, we assume L is a constant so both operations are O(1). Hardware completes the operations in essentially a single atomic step, too. Even with data that is so big you can’t fit it in local storage, you’re almost surely not going to exceed the size of a 64 bit address space. If you can’t fit in cache/RAM/HDD/cloud storage the bottleneck won’t be a binary address look up. The upper bound will be a function of the latency between the CPU and where the memory is stored (like TFA is talking about). Doing arithmetic on numbers larger than 64 bits (e.g. cryptography) is far more common than exceeding the address space of the OS / hardware / theoretical address space maximum (hundreds of terabytes up to exabytes).

by oivey 3y ago

tsimionescu 3y ago

The model is ultimately a choice, and you chose one that models important aspects of your domain. People very very often work with data that doesn't fit into the fastest available memory, so modeling that fact that memory accesses taking O(foo(N)) time makes a lot of sense if you want to compare the performance of algorithms with different amounts of memory accesses. The performance differences predicted by a model that adds this complexity compared to a model that doesn't will be better. For example, traditional complexity analysis predicts that linear search in a linked list should be about as fast as in an array up to some constant factor. If you instead model memory access as taking longer the larger the data structure you seek to access, you'll predict that linked list search is in fact worse and worse compared to array search as the size of each increases. This second prediction will more closely match the actual performance on real hardware. In contrast, people very rarely work on problems where fixed, small size integers (i32, i64) are not good enough. Those that do also typically model addition as an O(foo(N)) operation. There is of course some interesting overlap where you'd perhaps want to model the actual address calculation using large integers, but since in practice that will almost always be much faster than the actual memory access itself, it's rarely useful to account for it inatead of the memory access cost.

oivey 3y ago
I think we’re in agreement mostly. I was trying to make the point that the model needs to contain some practical assumptions at the level we’re discussing, or it breaks down. Both binary integer addition and binary address look ups are O(L) where L is the number of bits in the number. In practice for both, we assume L is a constant so both operations are O(1). Hardware completes the operations in essentially a single atomic step, too. Even with data that is so big you can’t fit it in local storage, you’re almost surely not going to exceed the size of a 64 bit address space. If you can’t fit in cache/RAM/HDD/cloud storage the bottleneck won’t be a binary address look up. The upper bound will be a function of the latency between the CPU and where the memory is stored (like TFA is talking about). Doing arithmetic on numbers larger than 64 bits (e.g. cryptography) is far more common than exceeding the address space of the OS / hardware / theoretical address space maximum (hundreds of terabytes up to exabytes).