On Saturday, 20 September 2014 at 18:26:56 UTC, Ola Fosheim Grøstad wrote:
> On Saturday, 20 September 2014 at 18:18:05 UTC, Walter Bright wrote:
>>
>> Please show me the inc/dec optimized x86 code.
>
> There's no optimization of the inc/dec, you use regular inc/dec within a larger xbegin/xend block.

Actually you dont need to inc/dec if you do both in the transaction. You only need to read the refcount. If somebody else writes to the ref count the transaction fails.

So, you cannot succeed a transaction while somebody else decrease the ref count.

Sounds right?

Hi everyone. Unlurking to make my first comment here.

Here is an idea for making RC and GC coexist peacefully. I think this technique may be used to make the Throwable transition to RC while keeping full backward compatibility.

A Throwable object would have a reference counter to track the number of RC references to it. It would also have a flag indicating whether there are any outstanding GC references to the object as well. This flag may be implemented by setting the MSB of the reference counter.

RC references would be a different type from GC references. An RC reference may be converted to a GC reference by setting the MSB, indicating that there may be one or more uncounted references to the object and that it should not be destroyed until successfully reclaimed by the GC. This RC to GC conversion may happen when a reference to a Throwable leaves @nogc code and enters GC land. When a GC operation can find no more references to the Throwable it would clear the counter MSB. If the number of RC references is zero at this point the object would be immediately destroyed.

A crucial part of making this work is to ensure that RC references are *not* seen by GC scanning. This may be done by mangling the pointer value in some way. Alternatively, if mark-and-sweep is replaced with count-and-sweep the number of counted RC references may be deducted.

One way to mangle the pointer is to decrement the value to a lower memory address. Incrementing the pointer won't work because the D garbage collector must handle inner references for slices etc.  Any dereferencing of the RC reference would compensate for this offset by incrementing the field offset. An obvious piece of information to put in the location reserved by decrementing the pointer would the the reference counter itself. Conversion of RC reference to GC would require incrementing the pointer and setting the counter MSB. Converting GC reference to RC is done by just decrementing the pointer.

I'm sure there are many things I'm missing here, but could something along these line be made to work?

On 9/20/2014 11:26 AM, "Ola Fosheim Grøstad" <ola.fosheim.grostad+dlang@gmail.com>" wrote:
> On Saturday, 20 September 2014 at 18:18:05 UTC, Walter Bright wrote:
>>
>> Please show me the inc/dec optimized x86 code.
>
> There's no optimization of the inc/dec, you use regular inc/dec within a larger
> xbegin/xend block.
>
> You amortize the cost over all the lock-prefixed instructions you would
> otherwise have executed in that block. There is no locking, there is a
> transaction instead. Only if the transaction fails do you execute the locking
> fallback code.

I strongly suggest taking a look at C++ shared_ptr<T>, compile a simple example, and examine the generated code. It is NOT AT ALL as simple as emitting an inc/dec pair. I.e. what happens if an exception is thrown between the inc and the dec?

If RC was as costless and simple as you are suggesting, everyone would be doing it and would have for decades.


>> Suppose I pass a pointer to:
>>
>>    void foo(T* p);
>>
>> How do I do dataflow?
>
> You mean a separate compilation unit that the compiler don't have access to? You
> don't, obviously.

Right. "dataflow" is not the answer.


>> The question was about mixing RC'd and non-RC'd objects.
>
> Well, if you are talking about negative offset for ref counts, then people do
> it. E.g. there are examples of systems that provide C-compatible strings with
> length at offset -4 and ref count at -8.

Now embed that object as a field in some other object.


> If you need to distinguish you can either use address-space info or keep a
> negative int in the non-RC'd object.

Now add that runtime distinguishing logic to the inc/dec code.

On Saturday, 20 September 2014 at 22:07:45 UTC, Walter Bright wrote:
> On 9/20/2014 11:26 AM, "Ola Fosheim Grøstad" <ola.fosheim.grostad+dlang@gmail.com>" wrote:
>> On Saturday, 20 September 2014 at 18:18:05 UTC, Walter Bright wrote:
>>>
>>> Please show me the inc/dec optimized x86 code.
>>
>> There's no optimization of the inc/dec, you use regular inc/dec within a larger
>> xbegin/xend block.
>>
>> You amortize the cost over all the lock-prefixed instructions you would
>> otherwise have executed in that block. There is no locking, there is a
>> transaction instead. Only if the transaction fails do you execute the locking
>> fallback code.
>
> I strongly suggest taking a look at C++ shared_ptr<T>, compile a simple example, and examine the generated code. It is NOT AT ALL as simple as emitting an inc/dec pair. I.e. what happens if an exception is thrown between the inc and the dec?

C++ provides weak references. If you throw issue xabort.

Nobody have said it is free, and TSX is new tech. So what you can do, who knows?

> If RC was as costless and simple as you are suggesting, everyone would be doing it and would have for decades.

Transactions are not free.

> Now embed that object as a field in some other object.

Uhm, I referred to new-allocated objects.

> Now add that runtime distinguishing logic to the inc/dec code.

Test N flag?

On Saturday, 20 September 2014 at 16:27:33 UTC, Andrei Alexandrescu wrote:
>> I don't think ARC is needed.
>>
>> library RC + borrowing + uniqueness/moving = WIN
>
> s/WIN/Rust/

Well Rust does some things well. We are going in the same direction anyway (type qualifier, uniqueness) expect we do it in an ad hoc manner that is guaranteed to yield a C++ish result.

On Friday, 19 September 2014 at 15:32:38 UTC, Andrei Alexandrescu
wrote:
> As discussed, having exception objects being GC-allocated is clearly a large liability that we need to address. They prevent otherwise careful functions from being @nogc so they affect even apps that otherwise would be okay with a little litter here and there.
>
> The Throwable hierarchy is somewhat separate from everything else, which makes it a great starting point for investigating an automated reference count approach. Here's what I'm thinking.
>
> First, there must be some compiler flag -nogc or something, which triggers the RC exceptions. All modules of an application must be compiled with this flag if it is to work (such that one module can throw an exception caught by the other). Of course a lot of refinement needs to be added here (what happens if one tries to link modules built with and without -nogc, allowing people to detect the flag programmatically by using version(nogc) etc).
>
> If -nogc is passed, the compiler severs the inheritance relationship between Throwable and Object, making it impossible to convert a Throwable to an Object. From then henceforth, Throwable and Object form a two-rooted forest. (In all likelihood we'll later add an RCObject root that Throwable inherits.)
>
> Whenever a reference to a Throwable is copied about, passed to functions, the compiler inserts appropriately calls to e.g. incRef and decRef. (Compiler may assume they cancel each other for optimization purposes.) Implementation of these is up to the runtime library. Null checking may be left to either the compiler or the library (in the latter case, the functions must be nonmember). However it seems the compiler may have an advantage because it can elide some of these checks.
>
> Once we get this going, we should accumulate good experience that we can later apply to generalizing this approach to more objects. Also, if things go well we may as well define _always_ (whether GC or not) Throwable to be reference counted; seems like a good fit for all programs.
>
> Please chime in with thoughts.
>
>
> Andrei

I guess it is time to put isolated back on the table.

You can throw only isolated. When isolated goes out of scope
without being consumed, the island is blasted out of existence.

On Saturday, 20 September 2014 at 19:48:14 UTC, Oren Tirosh wrote:
> Hi everyone. Unlurking to make my first comment here.
>
> Here is an idea for making RC and GC coexist peacefully. I think this technique may be used to make the Throwable transition to RC while keeping full backward compatibility.
>
> A Throwable object would have a reference counter to track the number of RC references to it. It would also have a flag indicating whether there are any outstanding GC references to the object as well. This flag may be implemented by setting the MSB of the reference counter.
>

I was thinking about this recently (and also, Andrei's talk at cppcon provided some interesting data).

Most reference count are small. I think it make sense for us to propose a ref count system, that allocate on the GC heap, and that do not free when the counter saturate.

It would help to:
 - get intrusive refcount without putting too much crap into objects (it is all about cache line).
 - get a way to escape RC object to the GC heap (by saturating the refcount).

The GC is still there, but do kick in randomly, it simply act as a safety net.

Also given the type qualifier in D, the whole synchronization thing is embeded in the type, so we can be safe and fast on that one. All of this can be done as library.

On 9/20/14, 5:30 PM, deadalnix wrote:
> On Saturday, 20 September 2014 at 16:27:33 UTC, Andrei Alexandrescu wrote:
>>> I don't think ARC is needed.
>>>
>>> library RC + borrowing + uniqueness/moving = WIN
>>
>> s/WIN/Rust/
>
> Well Rust does some things well. We are going in the same direction
> anyway (type qualifier, uniqueness) expect we do it in an ad hoc manner
> that is guaranteed to yield a C++ish result.

Rust looked a lot more exciting when I didn't know much about it. -- Andrei

Andrei Alexandrescu:

> Rust looked a lot more exciting when I didn't know much about it.

I didn't remember ever seeing you excited about Rust :-) In past you (rightfully) didn't comment much about Rust. But do you have more defined ideas about it now? Do you still think D has a chance against Rust?

Bye,
bearophile

On Sunday, 21 September 2014 at 01:46:13 UTC, Andrei Alexandrescu wrote:
> Rust looked a lot more exciting when I didn't know much about it. -- Andrei

I think it is interesting that Rust is kinda converging on only having the scope semantics in the language and the rest in the library.

(of course i'm biased to notice that cuz that's what I want here too!)