[cfe-dev] [libc++] debug mode

[Howard Hinnant]

On Sep 18, 2011, at 11:11 PM, M.E. O'Neill wrote:

> Howard Hinnant wrote:
>>>> There isn't a lot there yet.  I've tried to get vector working (just the primary, not vector<bool> so far), and I believe I have done so.  Though I don't have tests for it yet (I've just been spot checking).  At this point I'm simply exploring whether the basic design is viable or not.
>>>> 
>>>> A major goal of the design of this debug mode is to keep the ABI stable as debug mode is turned on/off.
> 
> Sounds good, but it'd be useful to have a more detailed design document somewhere so that people can see where you're going and how.
> 
> ... and Christopher Jefferson replied:
>>> I have often seen interest on a "cheap" debugging mode, which would add checks which were possible without breaking complexity requirements, or "excessive" cost.
> 
> Without seeing Howard's design, I don't know how "excessive" the costs of his design might be, but in principle, you can do some checks like iterator invalidation very cheaply -- if you have the right design.
> 
> This may be obvious (in which case I apologize), it may even be what Howard has already done (in which case, oops, and, uh, cool), but in case it isn't, let me outline how:
> 
> - For every container, associate a 64-bit tag (a.k.a. version stamp). 
> 
> - For every iterator, also associate a 64-bit tag.
> 
> - When you create a new container, just pick a random 64-bit value.
> 
> - When you create an iterator, copy the 64-bit tag from the associated container.  This represents the container/version the iterator belongs to.   Any access via the iterator checks that the tag of the iterator matches the tag of the container.  If it doesn't, BANG!
> 
> - When iterators are invalidated, generate a new tag for container. (For speed, you could just increment it, but the important point is that the value is a new and different one)
> 
> This method is probabilistic -- there is a 1 in 18446744073709551616 chance that it won't catch an invalid access, but personally I like those odds.  It also imposes very very little in runtime overhead -- you can invalidate N iterators in O(1) time.
> 
> I've always stored the tag in the containers/iterators, but it should also work with a database-based scheme.

Thanks M.E.O.

This is an interesting approach.  But one problem with it is that it only allows the system to invalidate all iterators referring to a container.  It can't invalidate a subset of them.  And we need to be able to invalidate subsets of iterators (e.g. during vector::erase).

Or have I missed something?

Howard