Re: [boost] lifetime of ranges vs. iterators

From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-09-01 13:53:56

> I wouldn't know how to address this issue without some real-life use
> cases, though.  This has all become a bit too abstract a discussion for
> me, and Generic Programming is supposed to be driven by concrete
> examples.

Isn't my problem concrete enough? I need a stackable difference_range without exponential storage bloat. How should I implement it?

I am not sure that you appreciate the problem: 

Let's consider two implementations of a forward difference_iterator.

A) Implemented with iterators alone, it contains 4 iterators:

- the iterator to the range being traversed (mutable)
- the iterator to the range being removed (mutable)
- the end iterator to the range being traversed (constant, common)
- the end iterator to the range being removed (constant, common)

Total size: 4*sizeof(ptr)

B) Implemented with iterators + indirection to common data:

- the iterator to the range being traversed (mutable)
- the iterator to the range being removed (mutable)
- a reference to the range

Total size: 3*sizeof(ptr)

Now we stack these things, creating difference_range( difference_range, difference_range ) and so on. The iterators of the outermost difference_range then have these sizes:

A) 1st Level: 4*sizeof(ptr)
   2nd Level: 4*(4*sizeof(ptr))
   Nth Level: (4^N)*sizeof(ptr)

B) 1st Level: 3*sizeof(ptr)
   2nd Level: 2*(3*sizeof(ptr))+1*sizeof(ptr)=7*sizeof(ptr)
   3rd Level: 2*(7*sizeof(ptr))+1*sizeof(ptr)=15*sizeof(ptr)
   4th Level: 2*(15*sizeof(ptr))+1*sizeof(ptr)=31*sizeof(ptr)
   Nth Level: (2^(N+1)-1)*sizeof(ptr)

Extra factor of storage required by A over B: 4^N / (2^(N+1)-1) >= 4^N / (2^(N+1)) = 2^N / 2.

So any implementation that even temporarily expands iterators to their original size, like Giovanni's implementation, will need vastly more storage. IMO, relying on the compiler to fix this is hazardous. Non-optimized code should be a constant factor slower than optimized code, and need a constant factor more memory, not exponentially slower and exponentially more memory.

> I think you're being at least very hasty.  If you do something that slows 
> down operation on pairs of pointers, you won't be doing anyone favors.

My proposal is not slowing down operations on pairs of pointers at all. All I am asking for is that range adaptors guarantee that their input ranges stay valid, e.g., are stored inside the range adaptor. Naive iterators are stored as they are passed in, for example as iterator_range, so storage and access is as efficient as ever. Iterators don't _have_ to contain indirections, they merely _can_ contain indirections because I want to guarantee the existence of the underlying range. Current implementations in RangeEx don't guarantee that.

Arno

--
Dr. Arno Schoedl · aschoedl_at_[hidden] 
Technical Director 
 
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany 
http://www.think-cell.com · phone [phone] · toll-free (US) [phone]
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229