RFC: naming for FrontTransversal and Transversal ranges

[Robert Jacques]

On Fri, 01 May 2009 14:03:44 -0400, Rainer Deyke <rainerd at eldwood.com>  
wrote:

> Robert Jacques wrote:
>> On Thu, 30 Apr 2009 23:18:13 -0400, Rainer Deyke <rainerd at eldwood.com>
>> wrote:
>>>   - It uses an extra heap allocation per instance.
>>
>> And during a deep copy, you're often making a lot of heap copies. (N vs
>> N+1 when N>>1)
>
> In the case of dynamic arrays, N = 1 (or possibly 0 if the small array
> optimization is used).  In the case of static arrays, N = 0.  Either
> way, the extra level of indirection is significant.
>

In the case of dynamic arrays, it's a struct. So no extra heap allocation  
is done. Same goes with heaps. Your argument only applies to object based  
containers, like trees, which generally contain lots of child objects.,  
i.e. N heap allocations.

>>>   - It allocates an extra reference to a virtual function table per
>>> instance.
>>
>> Huh? Isn't that part of the extra heap allocation?
>
> Extra allocations: 1.
>
> Extra memory usage: 2 words (virtual function table pointer, local
> pointer) plus heap overhead for one allocation.

Nope. Most of the time, the extra memory usage is 0. Remember, the GC uses  
large blocks with power of 2 sizes. Unless you happen to push across a  
boundry, the extra 2 words don't matter.

>> Also, a really important question is: is it possible to implement are
>> shared, lock-free containers as value types?
>
>
> Is it possible to implement them as reference types?

Yes. See java.util.concurrent for examples. In fact, all of the algorithms  
I've read explicitly don't support copying, which is why I'm asking.

> Why would the
> issues different between reference types and value types?

A value type has to support copying. Reference types don't. Perhaps I  
should have said value semantics / reference semantics instead.

> A reference
> type is just a reference wrapper around a value type.

Precisely, so it's always passed by reference and doesn't need to support  
copying.