On Wednesday, 1 October 2014 at 17:53:43 UTC, H. S. Teoh via
Digitalmars-d wrote:
>
> But Sean's idea only takes strings into account. Strings aren't the only
> allocated resource Phobos needs to deal with. So extrapolating from that
> idea, each memory management struct (or whatever other aggregate we end
> up using), say call it MMP, will have to define MMP.string, MMP.jsonNode
> (since parseJSON() need to allocate not only strings but JSON nodes),
> MMP.redBlackTreeNode, MMP.listNode, MMP.userDefinedNode, ...
>
> Nope, still don't see how this could work. Please clarify, kthx.

Assuming you're willing to take the memoryModel type as a
template argument, I imagine we could do something where the user
can specialize the memoryModel for their own types, a bit like
how information is derived for iterators in C++.  The problem is
that this still means passing the memoryModel in as a template
argument.  What I'd really want is for it to be a global, except
that templated virtuals is logically impossible.  I guess
something could maybe be sorted out via a factory design, but
that's not terribly D-like.  I'm at a loss for how to make this
memoryModel thing work the way I'd actually want it to if I were
to use it.

On Wednesday, 1 October 2014 at 18:37:50 UTC, Sean Kelly wrote:
> On Wednesday, 1 October 2014 at 17:53:43 UTC, H. S. Teoh via
> Digitalmars-d wrote:
>>
>> But Sean's idea only takes strings into account. Strings aren't the only
>> allocated resource Phobos needs to deal with. So extrapolating from that
>> idea, each memory management struct (or whatever other aggregate we end
>> up using), say call it MMP, will have to define MMP.string, MMP.jsonNode
>> (since parseJSON() need to allocate not only strings but JSON nodes),
>> MMP.redBlackTreeNode, MMP.listNode, MMP.userDefinedNode, ...
>>
>> Nope, still don't see how this could work. Please clarify, kthx.
>
> Assuming you're willing to take the memoryModel type as a
> template argument, I imagine we could do something where the user
> can specialize the memoryModel for their own types, a bit like
> how information is derived for iterators in C++.  The problem is
> that this still means passing the memoryModel in as a template
> argument.  What I'd really want is for it to be a global, except
> that templated virtuals is logically impossible.  I guess
> something could maybe be sorted out via a factory design, but
> that's not terribly D-like.  I'm at a loss for how to make this
> memoryModel thing work the way I'd actually want it to if I were
> to use it.

If you were to forget D restrictions for a moment, and consider an idealized language, how would you express this?  Maybe providing that will trigger some ideas from people beyond what we have seen so far by removing implied restrictions.

On Wednesday, 1 October 2014 at 15:48:39 UTC, Oren Tirosh wrote:
> On Tuesday, 30 September 2014 at 19:10:19 UTC, Marc Schütz wrote:
> One problem with actually implementing this is that using reference counting as a memory management policy requires extra space for the reference counter in the object, just as garbage collection requires support for scanning and identification of interior object memory range. While allocation and memory management may be quite independent in theory, practical high performance implementations tend to be intimately related.
>
>> (I'll try to make a sketch on how this can be implemented in another post.)
>
> Do elaborate!
>
>> As a conclusion, I would say that APIs should strive for the following principles, in this order:
>>
>> 1. Avoid allocation altogether, for example by laziness (ranges), or by accepting sinks.
>>
>> 2. If allocations are necessary (or desirable, to make the API more easily usable), try hard to return a unique value (this of course needs to be expressed in the return type).
>>
>> 3. If both of the above fails, only then return a GCed pointer, or alternatively provide several variants of the function (though this shouldn't be necessary often). An interesting alternative: Instead of passing a flag directly describing the policy, pass the function a type that it should wrap it's return value in.
>>
>> As for the _allocation_ strategy: It indeed needs to be configurable, but here, the same objections against a template parameter apply. As the allocator doesn't necessarily need to be part of the type, a (thread) global variable can be used to specify it. This lends itself well to idioms like
>>
>>    with(MyAllocator alloc) {
>>        // ...
>>    }
>
> Assuming there is some dependency between the allocator and the memory management policy I guess this would be initialized on thread start that cannot be modified later. All code running inside the thread would need to either match the configured policy, not handle any kind of pointers or use a limited subset of unique pointers. Another way to ensure that code can run on either RC or GC is to make certain objects (specifically, Exceptions) always allocate a reference counter, regardless of the currently configured policy.

I don't have all answers to these questions. Still, I'm convinced this is doable.

A straight-forwarding and general way to convert a unique object to a ref-counted one is to allocate new memory for it plus the reference count, move the original object into it, and release the original memory. This is safe, because there can be no external pointers to the object, as it is unique. Of course, this can be optimized if the allocator supports extending an allocation. It could then preallocate a few extra bytes at the end to make the extend operation always succeed, similar to your suggestion to always allocate a reference counter.

I think the most difficult part is to find an efficient and user-friendly way for the wrapper types to get at the allocator. Maybe the allocators should all implement an interface (a real one, not duck-typing). The wrappers (Owned, RC) can then include a pointer to the allocator (or for RC, embed it next to the reference count). This would make it possible to specify a (thread) global default allocator at runtime, which all library functions use by convention (for example let's call it `alloc`, then they would call `alloc.make!MyStruct()`). At the same time, it is safe to change the default allocator at any time, and to use different allocators in parallel in the same thread.

The alternative is obviously a template parameter to the function that returns the unique object. But this unfortunately is then not restricted to just the function, but "infects" the return type, too. And from there, it needs to spread to the RC wrapper, or any containers. Thus we'd have incompatible RC types, which I would imagine would be very inconvenient and restrictive. Besides, it would probably be too tedious to specify the allocator everywhere.

Therfore, I think the additional cost of an allocator interface pointer is worth it. For Owned!T (with T being a pointer or reference), it would just be two words, which we can return efficiently. We already have slices doing that, and AFAIK there's no significantly worse performance because of them.

On Wednesday, 1 October 2014 at 17:13:38 UTC, Andrei Alexandrescu wrote:
> On 10/1/14, 8:48 AM, Oren Tirosh wrote:
>> Bingo. Have some way to mark the function return type as a unique
>> pointer.
>
> I'm skeptical about this approach (though clearly we need to explore it for e.g. passing ownership of data across threads). For strings and other "casual" objects I think we should focus on GC/RC strategies. This is because people do things like:
>
> auto s = setExtension(s1, s2);
>
> and then attempt to use s as a regular variable (copy it etc). Making s unique would make usage quite surprising and cumbersome.

Sure? I already showed in an example how it is possible to chain calls seamlessly that return unique objects. The users would only notice it when they are trying to make a real copy (i.e. not borrowing). Do you think this happens frequently enough to be of concern?

On 10/1/14, 10:51 AM, H. S. Teoh via Digitalmars-d wrote:
> But Sean's idea only takes strings into account. Strings aren't the only
> allocated resource Phobos needs to deal with. So extrapolating from that
> idea, each memory management struct (or whatever other aggregate we end
> up using), say call it MMP, will have to define MMP.string, MMP.jsonNode
> (since parseJSON() need to allocate not only strings but JSON nodes),
> MMP.redBlackTreeNode, MMP.listNode, MMP.userDefinedNode, ...
>
> Nope, still don't see how this could work. Please clarify, kthx.

There's management for T[], pointers to structs, pointers to class objects, associative arrays, and that covers everything. -- Andrei

On 10/1/14, 1:56 PM, "Marc Schütz" <schuetzm@gmx.net>" wrote:
> On Wednesday, 1 October 2014 at 17:13:38 UTC, Andrei Alexandrescu wrote:
>> On 10/1/14, 8:48 AM, Oren Tirosh wrote:
>>> Bingo. Have some way to mark the function return type as a unique
>>> pointer.
>>
>> I'm skeptical about this approach (though clearly we need to explore
>> it for e.g. passing ownership of data across threads). For strings and
>> other "casual" objects I think we should focus on GC/RC strategies.
>> This is because people do things like:
>>
>> auto s = setExtension(s1, s2);
>>
>> and then attempt to use s as a regular variable (copy it etc). Making
>> s unique would make usage quite surprising and cumbersome.
>
> Sure? I already showed in an example how it is possible to chain calls
> seamlessly that return unique objects. The users would only notice it
> when they are trying to make a real copy (i.e. not borrowing). Do you
> think this happens frequently enough to be of concern?

I'd think so. -- Andrei

On 01/10/14 19:25, Oren T wrote:

> The idea is that the unique property is very short-lived: the caller
> immediately assigns it to a pointer of the appropriate policy: either RC
> or GC. This keeps the callee agnostic of the chosen policy and does not
> require templating multiple versions of the code. The allocator
> configured for the thread must match the generated code at the call site
> i.e. if the caller uses RC pointers the allocator must allocate space
> for the reference counter (at negative offset to keep compatibility).

Can't we do something like this, or it might be what you're proposing:

Foo foo () { return new Foo; }

@gc a = foo(); // a contains an instance of Foo allocated with the GC
@rc b = foo(); // b contains an instance of Foo allocated with the RC allocator

-- 
/Jacob Carlborg

On Thursday, 2 October 2014 at 06:29:24 UTC, Jacob Carlborg wrote:
> @gc a = foo(); // a contains an instance of Foo allocated with the GC
> @rc b = foo(); // b contains an instance of Foo allocated with the RC allocator

That would be better, but how do you deal with "bar(foo())" ? Context dependent instantiation is a semantic challenge when you also have overloading, but I guess you can get somewhere if you make whole program optimization mandatory and use a state-of-the-art constraint solver to handle the type system. Could lead you to NP-complete type resolution? But still doable (in most cases).

I think you basically have 2 realistic choices if you want easy-going syntax for the end user:

1. implement rc everywhere in standard libraries and make it possible to turn off rc in a call-chain by having compiler support (and whole program optimization). To support manual management you need some kind of protocol for traversing allocated data-structures to free them.

e.g.:

define memory strategy @malloc = some…manual…allocation…strategy…description;

auto a = bar(foo()); //  use gc or rc based on compiler flag
auto a = @rc( bar(foo()) ); // use rc in a gc context
auto a = @malloc( bar(foo()) ); // manual management (requires a protocol for traversal of recursive datastructures)


2. provide allocation strategy as a parameter

e.g.:

auto a = foo(); // alloc with gc
auto a = foo!rc(); // alloc with rc
auto a = foo!malloc(); // alloc with malloc

But going the C++ way of having explicit allocators and non-embedded reference counters (double indirectio) probably is the easier solution in terms of bringing D to completion.

How many years are you going to spend on making D ref count by default in a flawless and performant manner? Sure having RC being as easy to use as GC is a nice idea, but if it turns out to be either slower or more bug ridden than GC, then what is the point?

Note that:

1. A write to a ref-count means the 64 bytes cacheline is dirty and has to be written back to memory. So you don't write 4 bytes,  you write to 64 bytes. That's pretty expensive.

2. The memory bus is increasingly becoming the bottle neck of hardware architectures.

=> RC everywhere without heavy duty compiler/hardware support is a bad long term idea.

On 02/10/14 11:41, "Ola Fosheim Grøstad" <ola.fosheim.grostad+dlang@gmail.com>" wrote:

> That would be better, but how do you deal with "bar(foo())" ? Context
> dependent instantiation is a semantic challenge when you also have
> overloading, but I guess you can get somewhere if you make whole program
> optimization mandatory and use a state-of-the-art constraint solver to
> handle the type system. Could lead you to NP-complete type resolution?
> But still doable (in most cases).

I haven't really thought how it could be implemented but I was hoping that the caller could magically decide the allocation strategy instead of the callee. It looks like Rust is doing something like that but I haven't looked at it in detail.

-- 
/Jacob Carlborg

On Wednesday, 1 October 2014 at 15:48:39 UTC, Oren Tirosh wrote:
> On Tuesday, 30 September 2014 at 19:10:19 UTC, Marc Schütz wrote:
>> (I'll try to make a sketch on how this can be implemented in another post.)
>
> Do elaborate!

Here's an example implementation of what I have in mind (totally untested and won't compile because of `scope`):

http://wiki.dlang.org/User:Schuetzm/RC,_Owned_and_allocators

This is just a sketch to explain the general idea. Some things probably won't work as implemented, especially the disable postblit and opAssign() of Owned!T. I think it needs to implement implicit moving, otherwise one would have to call `release()` everywhere.

As in the other post, the function that produces the value returns Owned!T. The types don't require @unique however (although integration with DMD's idea of unique would still be useful).

Because of auto-borrowing via alias this, Owned!T and RC!T both can pass their payloads to functions that accept them by `scope`. The ref-count is not touched for borrowing.

Usage examples:

    Owned!string setExtension(in char[] path, in char[] ext);

    void saveFileAs(in char[] name) {
        import std.path: setExtension;
        import std.file: write;
        name.                    // scope const(char[])
            setExtension("txt"). // Owned!string
            write(data);
    }

    RC!string[] stringList;

    void addToGlobalList(scope RC!string s) {
        stringList ~= s;    // increments ref-count
    }

    RC!string foo;
    addToGlobalList(foo);   // borrowing doesn't change ref-count

    auto newFileName = "hello-world".setExtension("txt");
    auto tmp1 = newFileName;       // ERROR: cannot copy
    scope tmp2 = newFileName;      // OK, borrowing
    foo = newFileName;             // ERROR: cannot copy
    foo = newFileName.release();   // OK, move
    auto bar = newFileName.toRC(); // ditto