== Quote from Robert Jacques ([email protected])'s article > > The mutation index has been used in Tango forever, and I think was in > > Doug Lea's original container implementations. I'm pretty sure it is > > sound in single-threaded uses. > No it's not. version tags + integer overflow = bug. Doug Lea knew about > the problem and but thought it would never happen in real code. And Bill > Gates thought no one will need more than 640k of ram. They both have been > proven wrong.
Using a 32-bit version tag probably could lead to overflow in some corner cases, but in the 64-bit case it can be shown that this is absurdly unlikely. Assume that an increment operation takes about 1 clock cycle (in reality it's more) and that most CPUs are 10 GHz (to make things future-proof in case people figure out how to get the clock speed race going again). This means that a version tag could, at most, increment at about 10^10 ticks per second. A 64-bit unsigned int goes up to about 1.8x10^19. This means that, even if our program does nothing but update the version counter in an empty for loop, it will take 1.8x10^19 / 10^10 = 1.8x10^9 seconds to overflow. There are about 3.15x10^7 seconds in a year. Therefore, even under very pessimistic assumptions the fastest you could overflow a 64-bit unsigned int by incrementing it starting at zero is in about half a century.
