pass-by-ref semantics for structs (was Deque impl.)

[Rainer Schuetze]

On 31.01.2013 17:17, Andrei Alexandrescu wrote:
> On 1/31/13 11:00 AM, Steven Schveighoffer wrote:
>> On Thu, 31 Jan 2013 10:40:15 -0500, Andrei Alexandrescu
>> <SeeWebsiteForEmail at erdani.org> wrote:
>>> It has a destructor.
>>
>> One which is not called if allocated on the heap.
>
> That is correct. My point was that with structs we get to implement
> full-fledged reference counting for containers.
>
> Reference counting makes a lot of sense for containers. They inherently
> own their internals, don't have cycles, and are massive enough to make
> pass by value effectively an anti-pattern (as it is for C++). At the
> same time memory reclamation is of high interest. Reference counting is
> really the sweet spot for containers.

I can understand interest in early and deterministic reclamation of 
memory, but I have some issues with reference counting. Maybe you can 
shed some light on these:

- how do you reference count immutable containers? You'll have to cast 
the payload to mutable and assume it is not in read-only memory.

- how do you do reference counting when accessing shared containers in 
multiple threads? Consider clearing the last reference to a shared 
reference counted object while another thread reads this reference. With 
usual atomic operations on the reference count only:

   1. the reading thread reads the payload pointer
   2. the writing thread reads the payload pointer, decrements the 
reference count and frees the array
   3. the reading thread increments the reference count, but accesses 
the deallocated array.

With atomic operations, I can only imagine fixing this with CAS2 
operations reading/changing both pointer and reference count at the same 
time, but even then, it is not obvious. Anyway, this operation is not 
supported by the currently popular processors.

In contrast, GC managed memory is memory- at safe in multi-threading 
environments by design.