Locks Aren't Slow; Lock Contention Is

I just ran across this gem of a sentence:

> I know teams which spent weeks fine-tuning a lock-free algorithm, subjecting it to a battery of tests, only to discover hidden deadlock bugs several months later.

How exactly can you deadlock in a lock-free algorithm?