Why is a Compare-And-Swap operation limited by Amdahl's law?

Question

Martin Thompson asserts that a STM that relies on a ref that relies on CAS will ultimately be limited by Amdahl's law. Amdahl's law being that the maximum performance of a parallel program is limited by the sequential (non-parallel) part of the program. Is Martin Thompson saying that CAS is by its nature non-parallel?

Answer 1

I would think that's exactly his point. The swap must come after the results of the compare are known, so ultimately you cannot run any faster than "compare, then swap, then next compare, then next swap, the next compare, ...".

Of course, in most realistic cases, you won't get anywhere close to reaching that limit -- and you would be unbelievably thrilled with the performance if you did. It's kind of like saying that cars can never go faster than the speed of light. It's almost undoubtedly true, but car manufacturers needn't worry about it.