3 ms·

Nah. Sorry cache-misses don't count as part of a theoretical analysis on complexity. Why? Because you're getting into specific access pattern performance. Compl

by hacknat 10y ago

Nah. Sorry cache-misses don't count as part of a theoretical analysis on complexity. Why? Because you're getting into specific access pattern performance. Complexity is about "all things being equal". Is it the only thing you should consider? At first it should be, then if you run into a problem with a specific structure that has remarkable scale or access then go ahead and consider what the underlying hardware might be doing with the specific access patterns your structure is encountering. It's interesting to see linked-list as his example, because it is the most likely to have cache-misses as you move through it as the allocations are very fragmented. I'd be very curious to see the same chart on a warmed-up hash-table. Also, if we're considering the hardware, can we take into account pre-fetching and branch prediction? What are your numbers then? Yeah RAM is farther out then the local caches, but the CPU is also not completely ignorant of what it has to do next.

DanWaterworth 10y ago
> Sorry cache-misses don't count as part of a theoretical analysis on complexity. They don't in the random access machine model, but there are other models where cache misses do factor in.
- mmalone 10y ago
  Yes. This is what I came to say. Big-O assumes a model of computation. Typically people assume a random access machine with certain constant time operations like arithmetic. In some models arithmetic might not be O(1) (e.g., in a pure lambda calculus it's O(n)). A random access machine model makes a bunch of simplifying assumptions that don't actually hold in practice. As the article suggests, if you're writing code in industry it's not a bad idea to understand how your specific hardware differs from the model.
zeroer 10y ago
Did you read part II of the series? It's a deeper analysis than you seem to give him credit for. His argument is that in this universe, the specific laws of physics we have here enforce the property that memory access takes o(sqrt(N)) time [1] where N is the size of your data set. [1] - What's actually going on is that it takes o(N * sqrt(N)) time to touch N bits of information. Since for any particular bit, it might be very close to the processor and thus fast, but hitting N bits necessitates that most of the bits you access are far away.
- hacknat 10y ago
  I did read part II, and I think his analogy is off. Memory isn't linearly limited (it happens to be in the processor, but this isn't a given), I don't even understand why he brings circles into his conception of memory. Memory isn't linearly bound to the previous local cache. RAM isn't an order of magnitude larger than the L3 cache, it's MANY of order of magnitude larger! His analogy is just wrong. A better analogy would be library A takes X amount of time to access its books and can store 100 of them, and library B takes 10X amount of time to access its books, but it can store 1,000,000 books! Yes as we increase in memory size latency goes up, but he never proves that this is sqrt(N) (he correlates that it is). Each jump in up can be explained by cache misses in each successive local cache, but RAM can scale more than a few orders of magnitude beyond the L3 cache. He needed to keep his chart going past 1GB to see that there is actually a plateau to be hit. If he had scaled to 10GB and then to 100GB he would have seen access times be about the same that they were for 1GB.
  - zeroer 10y ago
    Re-read the "The theoretical limit" section in part II. His arguments depend on the physics in this particular universe, not how computers happen to be built.
    - hacknat 10y ago
      My response was about his math and physics: If you scale the radius of a sphere by one unit then you indeed get an order of magnitude increase in volume (bits of info), but that's not the correct model! We don't increase by on unit! RAM isn't a one unit increase in radius! It's an order of magnitude increase! If you increase the radius by an order of magnitude you get a 3 fold order of magnitude increase in memory. So you jump up in latency by one order of magnitude and you get 3 orders of magnitude of memory in return. His analysis and math are wrong.
      - Jweb_Guru 10y ago
        You clearly did not understand the linked article at all. He is referring to theoretical results on the information density of a black hole, which indeed collapses to area. In practice, the reason RAM doesn't appear to increase by three orders of magnitude is not that (it's that we don't actually build RAM in a sphere) but his point is that whether you are looking at theory or practice the square root is the correct model.

by hacknat 10y ago

DanWaterworth 10y ago

> Sorry cache-misses don't count as part of a theoretical analysis on complexity. They don't in the random access machine model, but there are other models where cache misses do factor in.

mmalone 10y ago
Yes. This is what I came to say. Big-O assumes a model of computation. Typically people assume a random access machine with certain constant time operations like arithmetic. In some models arithmetic might not be O(1) (e.g., in a pure lambda calculus it's O(n)). A random access machine model makes a bunch of simplifying assumptions that don't actually hold in practice. As the article suggests, if you're writing code in industry it's not a bad idea to understand how your specific hardware differs from the model.

zeroer 10y ago

Did you read part II of the series? It's a deeper analysis than you seem to give him credit for. His argument is that in this universe, the specific laws of physics we have here enforce the property that memory access takes o(sqrt(N)) time [1] where N is the size of your data set. [1] - What's actually going on is that it takes o(N * sqrt(N)) time to touch N bits of information. Since for any particular bit, it might be very close to the processor and thus fast, but hitting N bits necessitates that most of the bits you access are far away.

hacknat 10y ago
I did read part II, and I think his analogy is off. Memory isn't linearly limited (it happens to be in the processor, but this isn't a given), I don't even understand why he brings circles into his conception of memory. Memory isn't linearly bound to the previous local cache. RAM isn't an order of magnitude larger than the L3 cache, it's MANY of order of magnitude larger! His analogy is just wrong. A better analogy would be library A takes X amount of time to access its books and can store 100 of them, and library B takes 10X amount of time to access its books, but it can store 1,000,000 books! Yes as we increase in memory size latency goes up, but he never proves that this is sqrt(N) (he correlates that it is). Each jump in up can be explained by cache misses in each successive local cache, but RAM can scale more than a few orders of magnitude beyond the L3 cache. He needed to keep his chart going past 1GB to see that there is actually a plateau to be hit. If he had scaled to 10GB and then to 100GB he would have seen access times be about the same that they were for 1GB.
- zeroer 10y ago
  Re-read the "The theoretical limit" section in part II. His arguments depend on the physics in this particular universe, not how computers happen to be built.
  - hacknat 10y ago
    My response was about his math and physics: If you scale the radius of a sphere by one unit then you indeed get an order of magnitude increase in volume (bits of info), but that's not the correct model! We don't increase by on unit! RAM isn't a one unit increase in radius! It's an order of magnitude increase! If you increase the radius by an order of magnitude you get a 3 fold order of magnitude increase in memory. So you jump up in latency by one order of magnitude and you get 3 orders of magnitude of memory in return. His analysis and math are wrong.
    - Jweb_Guru 10y ago
      You clearly did not understand the linked article at all. He is referring to theoretical results on the information density of a black hole, which indeed collapses to area. In practice, the reason RAM doesn't appear to increase by three orders of magnitude is not that (it's that we don't actually build RAM in a sphere) but his point is that whether you are looking at theory or practice the square root is the correct model.