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

[Steven Watanabe]

AMDG

On 09/19/2011 02:40 PM, M.E. O'Neill wrote:
> I wrote:
>>> There are details, of course, such as reference counting things so that it all cleans up nicely (i.e., you only keep as much of the invalidation log as you actually need), and handling tag collisions for record information (because you really shouldn't *ever* fail for valid code, even if it is more likely that the user will be struck by lightning while in the bathroom).  But I think those details are pretty straightforward.
> 
> and Steven Watanabe replied:
>> [ideas deleted]
> 
> I was certainly thinking more along the lines of your second idea.  The reference count is the number of direct references, either from iterators directly using that tag, or the reference from the tag's predecessor in history. (*)
> 
>> A single long-lived iterator can cause the history to accumulate indefinitely.
> 
> Yes, this is true.  But in practice it only happens if you keep doing lots of erases and you have one long-lived iterator you never actually use.  Any actual full invalidation breaks the chain.  Likewise actually using the iterator will update it.   I suspect it would be more of a problem in theory than practice.
> 

It's quite easy to have a usage pattern where
you do a lot of erases without ever invalidating
the entire vector.  That's exactly what happens
when the vector is used as a stack.  I can't
think of any obvious cases where I would have
a long-lived iterator, but it seems to me that
the cost of invalidating the iterators doesn't
really matter unless you have a significant
number of them and are operating on the container
at the same time.  Under these conditions
I wouldn't be at all surprised to find a
long-lived iterator that isn't used for a
while.

> Feel free to suggest alternative designs or variations; my preference though is for schemes where mass iterator invalidation is O(1) (and actually fairly cheap), and the common case (valid iterators) is fast.
> 

mass iterator invalidation is O(1) even if
you implement it by marking all valid iterators
as invalid.  Recall that in the standard, O(1)
means /amortized/ constant time.  The work done
invalidating the iterators can always be paired
off with the work done creating them in the
first place.

In Christ,
Steven Watanabe

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: OpenPGP digital signature
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20110919/9868b09a/attachment.sig>