On Friday, 1 February 2013 at 19:10:26 UTC, Rainer Schuetze wrote:
>
>
> On 01.02.2013 09:06, Dmitry Olshansky wrote:
>> 01-Feb-2013 00:32, Rainer Schuetze пишет:
>>>
>>>
>>> - 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.
>>
>> Containers of immutables can have ref-count easily.
>> And I'd say fully immutable containers are rare case and can rely on GC.
>
> Do you want different implementations of the containers depending on the mutable/immutable/shared modifier? Would that be possible?

You can only do that on the qualifier of the *parameters*, not the container itself.

This is not possible because an S "is a" const(S). If the implementation of an S was different from a const(S), then you'd violate that. At best, a const(S) is an S with restricted possibilities, bot not *different* possibilities.

01-Feb-2013 23:10, Rainer Schuetze пишет:
>
>
> On 01.02.2013 09:06, Dmitry Olshansky wrote:
>> 01-Feb-2013 00:32, Rainer Schuetze пишет:
>>>
>>>
>>> - 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.
>>
>> Containers of immutables can have ref-count easily.
>> And I'd say fully immutable containers are rare case and can rely on GC.
>
> Do you want different implementations of the containers depending on the
> mutable/immutable/shared modifier? Would that be possible?
>

In fact I do ;) It's possible base on element type not the whole container itself.

>>
>>>
>>> - how do you do reference counting when accessing shared containers in
>>> multiple threads?
>>
>> Atomic Inc/Dec.
>>
>
> Not good enough as shown in the discussion with Steven.
>
>>> 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.
>>
>> Can't happen as reading thread got to have a reference and so does the
>> writing thread, then refcount >= 2.
>
> Can happen with a single shared reference accessed from two threads.

You mean shared reference to shared ref-counter object?
Awful and BTW impossible in D as you'd have to cast your way into it :)


-- 
Dmitry Olshansky

On Fri, 01 Feb 2013 14:03:51 -0500, Rainer Schuetze <r.sagitario@gmx.de> wrote:
>
> The problem is to make it atomic without expensive locks. Lacking the CAS2 operation (that does a CAS on two arbitrary memory locations simultaneously), my first thought was that it is not possible.

I don't think expensive locks are an issue here.  Having an expensive lock to copy a pointer from a shared location into a thread-local location is worth having an expensive lock, and may even be necessary.

Once you have the thread-local copy of the reference, incrementing and decrementing the reference count can be done via CAS.

-Steve

On 01.02.2013 20:18, monarch_dodra wrote:
> On Friday, 1 February 2013 at 19:10:26 UTC, Rainer Schuetze wrote:
>>
>>
>> On 01.02.2013 09:06, Dmitry Olshansky wrote:
>>> 01-Feb-2013 00:32, Rainer Schuetze пишет:
>>>>
>>>>
>>>> - 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.
>>>
>>> Containers of immutables can have ref-count easily.
>>> And I'd say fully immutable containers are rare case and can rely on GC.
>>
>> Do you want different implementations of the containers depending on
>> the mutable/immutable/shared modifier? Would that be possible?
>
> You can only do that on the qualifier of the *parameters*, not the
> container itself.

Ok, but that won't help changing reference count semantics, because the type of the elements are irrelevant here. It's about the container itself.

>
> This is not possible because an S "is a" const(S). If the implementation
> of an S was different from a const(S), then you'd violate that. At best,
> a const(S) is an S with restricted possibilities, bot not *different*
> possibilities.

I guess you would have to convert it to a different type, but it can be an efficient operation transferring the payload unmodified. Also, when converting to shared, you might even be able to verify that there are no other references left (that must be non-sharing).

On 01.02.2013 20:36, Dmitry Olshansky wrote:
> 01-Feb-2013 23:10, Rainer Schuetze пишет:
>>>> 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.
>>>
>>> Can't happen as reading thread got to have a reference and so does the
>>> writing thread, then refcount >= 2.
>>
>> Can happen with a single shared reference accessed from two threads.
>
> You mean shared reference to shared ref-counter object?
> Awful and BTW impossible in D as you'd have to cast your way into it :)
>

Maybe I'm coding too much C++, but isn't this what the "shared" modifier is all about?

On 01.02.2013 21:02, Steven Schveighoffer wrote:
> On Fri, 01 Feb 2013 14:03:51 -0500, Rainer Schuetze <r.sagitario@gmx.de>
> wrote:
>>
>> The problem is to make it atomic without expensive locks. Lacking the
>> CAS2 operation (that does a CAS on two arbitrary memory locations
>> simultaneously), my first thought was that it is not possible.
>
> I don't think expensive locks are an issue here.  Having an expensive
> lock to copy a pointer from a shared location into a thread-local
> location is worth having an expensive lock, and may even be necessary.
>

It depends on the application. At work we put a lot of effort into transferring data lock-free from/to a low latency thread processing audio. No blocking is allowed in this thread. (You cannot guarantee this with D at the moment, but IMO it only takes a few tweaks to the runtime.)

> Once you have the thread-local copy of the reference, incrementing and
> decrementing the reference count can be done via CAS.

Yes. My proposed code is only slightly more complex than atomic increments/decrements, but should also work for shared(Container).