Container insertion and removal

[Andrei Alexandrescu]

dsimcha wrote:
> == Quote from Robert Jacques (sandford at jhu.edu)'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