On 31.01.2013 21:55, Rainer Schuetze wrote:
>
>
> On 31.01.2013 21:48, Steven Schveighoffer wrote:
>> On Thu, 31 Jan 2013 15:32:23 -0500, Rainer Schuetze <r.sagitario@gmx.de>
>> wrote:
>>
>>> - 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.
>>
>> The reference count part is not immutable.
>>
>> e.g.:
>>
>> struct refcountstruct
>> {
>>     int count;
>>     immutable(containerimpl) impl;
>> }
>
> What about immutable(refcountstruct)? Maybe only implicitely as field of
> an immutable class.
>

That would probably be better immutable(refcountstruct*) as field of the immutable container struct.

On Thu, 31 Jan 2013 15:55:11 -0500, Rainer Schuetze <r.sagitario@gmx.de> wrote:

>
>
> On 31.01.2013 21:48, Steven Schveighoffer wrote:
>> On Thu, 31 Jan 2013 15:32:23 -0500, Rainer Schuetze <r.sagitario@gmx.de>
>> wrote:
>>
>>> - 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.
>>
>> The reference count part is not immutable.
>>
>> e.g.:
>>
>> struct refcountstruct
>> {
>>     int count;
>>     immutable(containerimpl) impl;
>> }
>
> What about immutable(refcountstruct)? Maybe only implicitely as field of an immutable class.

You wouldn't be able to do that.  The reference count needs to be tail-immutable, meaning the reference count is not immutable, but the data it protects is.

Anticipating your answer, no, there isn't a good way to do this at the moment, it's something D definitely lacks.

>
>>
>>>
>>> - 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.
>>
>> I would be concerned if a thread can get ahold of a reference counted
>> pointer without having the counter incremented already on its behalf.
>>
>
> You have to read the pointer to increment the counter to get hold of the reference.

Right, but where do you get the original pointer from?  Wouldn't that reference have incremented the count?

-Steve

On 31.01.2013 22:37, Steven Schveighoffer wrote:
> On Thu, 31 Jan 2013 15:55:11 -0500, Rainer Schuetze <r.sagitario@gmx.de>
> wrote:
>>
>>>
>>>>
>>>> - 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.
>>>
>>> I would be concerned if a thread can get ahold of a reference counted
>>> pointer without having the counter incremented already on its behalf.
>>>
>>
>> You have to read the pointer to increment the counter to get hold of
>> the reference.
>
> Right, but where do you get the original pointer from?  Wouldn't that
> reference have incremented the count?
>

Any reference that is accessible from multiple threads, e.g. a global shared variable.

shared(Container) allObjects;

Without any thread having a reference to it, the payload's reference count is 1. The reading thread above increments the counter when making a local copy, but the writing thread decrements the counter when assigning Container.init. If both run concurrently, with the sequence 1 to 3 above, trouble is inevitable.

On Thu, 31 Jan 2013 17:31:38 -0500, Rainer Schuetze <r.sagitario@gmx.de> wrote:

> Any reference that is accessible from multiple threads, e.g. a global shared variable.
>
> shared(Container) allObjects;
>
> Without any thread having a reference to it, the payload's reference count is 1. The reading thread above increments the counter when making a local copy, but the writing thread decrements the counter when assigning Container.init. If both run concurrently, with the sequence 1 to 3 above, trouble is inevitable.

Right, but isn't that an issue with having ANY shared variable that isn't protected by a lock?

I was thinking you had passed the pointer in via a message or something.

-Steve

On Thu, 31 Jan 2013 17:37:39 -0500, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> On Thu, 31 Jan 2013 17:31:38 -0500, Rainer Schuetze <r.sagitario@gmx.de> wrote:
>
>> Any reference that is accessible from multiple threads, e.g. a global shared variable.
>>
>> shared(Container) allObjects;
>>
>> Without any thread having a reference to it, the payload's reference count is 1. The reading thread above increments the counter when making a local copy, but the writing thread decrements the counter when assigning Container.init. If both run concurrently, with the sequence 1 to 3 above, trouble is inevitable.
>
> Right, but isn't that an issue with having ANY shared variable that isn't protected by a lock?
>
> I was thinking you had passed the pointer in via a message or something.

BTW, couldn't we solve this with a function that increments the retain count, and then returns a pointer to the object?  Such a method would have to be atomic on shared instances.

-Steve

On 31.01.2013 23:37, Steven Schveighoffer wrote:
> On Thu, 31 Jan 2013 17:31:38 -0500, Rainer Schuetze <r.sagitario@gmx.de>
> wrote:
>
>> Any reference that is accessible from multiple threads, e.g. a global
>> shared variable.
>>
>> shared(Container) allObjects;
>>
>> Without any thread having a reference to it, the payload's reference
>> count is 1. The reading thread above increments the counter when
>> making a local copy, but the writing thread decrements the counter
>> when assigning Container.init. If both run concurrently, with the
>> sequence 1 to 3 above, trouble is inevitable.
>
> Right, but isn't that an issue with having ANY shared variable that
> isn't protected by a lock?

True, as soon as you start mutating the variable. In case of simple reference/pointer without reference count, the change is atomic though (depending on the CPU or the implementation of "shared") and the reader thread just gets the old or the new pointer, but never an invalid pointer.

My main point actually was that a lot of people seem to think that reference counting with atomic incrementing/decrementing the counter (like it is used in COM) is thread safe in general. I think they are wrong.

>
> I was thinking you had passed the pointer in via a message or something.
>

I agree, message passing should not have this issue. It needs that single reference being accessed from different threads.

01-Feb-2013 00:32, 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@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.

Containers of immutables can have ref-count easily.
And I'd say fully immutable containers are rare case and can rely on GC.

>
> - how do you do reference counting when accessing shared containers in
> multiple threads?

Atomic Inc/Dec.

> 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.

>
> 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-@safe in multi-threading
> environments by design.


-- 
Dmitry Olshansky

Whilst we're talking about containers and refcounted, I've been encountering on and off a very strange bug with Array and RefCounted.

It is creating stack overflows, and I'm *certain* is creating problems when trying to nest connectors. I also think it is the "tip" of a more serious bug.

Could anybody with the required skills try to investigate this one?

http://d.puremagic.com/issues/show_bug.cgi?id=9438

On 01.02.2013 00:14, Steven Schveighoffer wrote:
> On Thu, 31 Jan 2013 17:37:39 -0500, Steven Schveighoffer
> <schveiguy@yahoo.com> wrote:
>
>> On Thu, 31 Jan 2013 17:31:38 -0500, Rainer Schuetze
>> <r.sagitario@gmx.de> wrote:
>>
>>> Any reference that is accessible from multiple threads, e.g. a global
>>> shared variable.
>>>
>>> shared(Container) allObjects;
>>>
>>> Without any thread having a reference to it, the payload's reference
>>> count is 1. The reading thread above increments the counter when
>>> making a local copy, but the writing thread decrements the counter
>>> when assigning Container.init. If both run concurrently, with the
>>> sequence 1 to 3 above, trouble is inevitable.
>>
>> Right, but isn't that an issue with having ANY shared variable that
>> isn't protected by a lock?
>>
>> I was thinking you had passed the pointer in via a message or something.
>
> BTW, couldn't we solve this with a function that increments the retain
> count, and then returns a pointer to the object?  Such a method would
> have to be atomic on shared instances.

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.

Considering it again, I guess it can be done by not using atomic increment/decrement, but splitting up the operations. The main idea is to no longer touch the data after the reference count has become 0 once:

// CAS returns *var before operation, only modifies if *var == expected
size_t CAS(size_t* var, size_t expected, size_t newval);

struct PayLoad(T)
{
	T* array;
	size_t size;
	size_t refCount;

	PayLoad!T* ref()
	{
		size_t cnt = refCount;
		while(cnt)
		{
			int old = CAS(&refCount, cnt, cnt+1);
			if(old == cnt)
				return this;
			cnt = refCount;
		}
		// in the rare case the payload has become invalid,
		// return a new empty object to avoid having to
		// check for null (could also be null if the container
		// always checks its payload pointer)
		return new PayLoad!T;
	}
	void deref()
	{
		size_t cnt, old;
		do
		{
			assert(refCount);
			cnt = refCount;
			old = CAS(&refCount, cnt, cnt-1);
		}
		while(old != cnt);
		if(refCount == 0)
			free(array);		
	}
}

struct Container(T)
{
	PayLoad!T* payload;

	this()	// I know this doesn't work, but would be convenient
	{
		payload = new Payload!T;
	}
	this(this)
	{
		payload = payload.ref();
	}
	~this()
	{
		payload.deref();
	}
        void opAssign(typeof(this) rhs)
	{
		if(rhs.payload !is payload)
		{
			payload.deref();
			payload = rhs.payload.ref();
		}
	}
}

PayLoad!T will still have to be garbage collected, though.

BTW: Maybe I am misunderstanding it, but according to http://dlang.org/operatoroverloading.html overloading opAssign on the same type as in "void opAssign(typeof(this) rhs)" is not allowed. Is this correct? You find it in phobos as well.

Another BTW: the links to anchors on the same page are broken as they don't include the html file.

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?

>
>>
>> - 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.