dsimcha wrote:
== 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.
Yah, there are many similar assessments that at least for a couple of
centuries going we can assume that 64-bit counters never overflow and
64-bit virtual address space is sparse. First time I saw this was when I
read about the Opal OS:
http://www.cs.washington.edu/homes/levy/opal/sigops92.ps
Andrei
