8

If I have an algorithm A. and it has fewer instructions than algorithm B. but performs worse on a CPU due to poor memory coalescing (and hence, poor CPU cache performance), does that factor into the Time Complexity analysis - given that, CPUs can have different wildly different cache implementations (or no cache) such that a algorithm's effectiveness can only be adequately judged on a single given CPU?

If you don't understand the issue in question, please watch Mike Acton's CPPCon speech on youtube ("Data Oriented Design").

2 Answers 2

18

Time Complexity (Big-O notation) does not measure performance of an algorithm. Instead, it categorizes how an algorithm's resource use scales with input size. This allows us to compare two algorithms with a judgement such as “for some sufficiently big input, algorithm A will always be faster than algorithm B”. We can do this judgement without even considering concrete implementations of the algorithms. As such, Big-O is not concerned about implementation details such as caching.

However, we do assume certain implementation details when calculating Big-O. E.g. it is common to assume that each memory access has constant cost. This clearly does not hold in an environment where lookups are actually O(n) (e.g. when memory is represented as a linked list). If you want to be very precise when calculating Big-O, we must draw up a cost model that assigns a concrete cost for each operation, though this may be expressed in terms of some undetermined constants. E.g. we usually assume that a memory load has concrete running time T(n) = c for some constant c. This constant will be eliminated when simplifying to Big-O. Incidentally, caching does not change the constant-time guarantee – as long as there is some fixed upper bound for an operation, it can be considered constant. Here, this would be the cost of a read with cache miss.

This also means that Big-O is not suitable for comparing real-world performance of algorithms with known workloads. Two algorithms might be in the same complexity class, but one may outperform the other by a consistent factor of 1000. Or one algorithm might have spectacular linear complexity, but requires so much pre-processing that even an exponential algorithm is faster in practice (real example: many regex engines).

1
  • 3
    This is very true. The hardware is almost completely abstract in O() notation. Not least because hardware doesn't generalise well - memory access on most platforms has big-O type scaling but it's type-specific. At times it's not accurate to assume O(n) because even within a cache type performance can be O(n>1). EG crossing tape boundaries can mean that you go O(data volume X number of tapes) and bob help you if your tape isn't in the changing mechanism (cache lookup fail = person with trolley). Similar effects can happen on the nanoscale as things like processor locks cascade across caches.
    – Móż
    Dec 14, 2015 at 1:21
2

Time complexity is a mathematical concept that applies to a model of computation. Normally, we apply it to Turing machines, which have nothing like a cache, so most normal time complexity results are effectively assuming there are no caches.

But you can use more complex models if you want. I'm not aware of any mathematical models in common use that go as far as mimicking CPU caches, but there are certainly "register machines" that have a mathematically precise definition but unlike Turing machines have registers separate from main memory. They've been proven mathematically equivalent to Turing machines in terms of decideability, i.e. what computations they can perform, but they differ in the time complexities with which they execute those computations.

I suspect that the time complexities of a register machine will be somewhat closer to the "real-world time complexities" you get when CPU caching is involved, as registers are arguably the most primitive form of CPU caching. But how true that is will depend highly on the details of the model you choose. Figuring out what mathematical model best simulates your real-world computations is the sort of thing academic researchers are still working on.

2
  • 2
    cs.cmu.edu/~cdm/pdf/RegisterMach-6up.pdf might be a good place to start if you're curious about register machines.
    – Ixrec
    Dec 13, 2015 at 22:12
  • 5
    Actually, we usually apply it to a Random Access Machine. In a Turing Machine, accessing the nth word in memory takes n steps, whereas in a Random Access Machine, like in typical computers, it is O(1). Dec 13, 2015 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.