On Thu, Jun 27, 2013 at 12:43:54AM +0200, Adam D. Ruppe wrote:
> So to try some ideas, I started implementing a simple container with replaceable allocators: a singly linked list.
> 
> All was going kinda well until I realized the forward range it offers to iterate its contents makes it possible to escape a reference to a freed node.
[...]
> (though if the payload is a reference type, does the container take ownership of it? How do we indicate that? Perhaps more interestingly, how do we indicate the /lack/ of ownership at the transfer point?)

Maybe a type distinction akin to C++'s auto_ptr might help? Say we introduce OwnedRef!T vs. plain old T*. So something returning OwnedRef!T will need to assume ownership of the object, whereas something returning T* would just be returning a reference, but the container continues to hold ownership over the object.


> This is all fairly easy if we just decide "we're going to do this with GC" or "we're going to do this C style" and do the whole program like that, libraries and all. But trying to mix and match just gets more complicated the more I think about it :( It makes the question of "allocators" look trivial.

Heh. Yeah, I'm started to wonder if it even makes sense to try to mix-n-match GC-based and non-GC-based allocators. It seems that maybe we just have to settle for the fact of life that a GC-based object is fundamentally incompatible with a pool-allocated object, and both are also fundamentally incompatible with malloc-allocated objects, 'cos you need the code to be aware in each instance of what needs to be done to cleanup, etc..


T

-- 
GEEK = Gatherer of Extremely Enlightening Knowledge

On Wednesday, 26 June 2013 at 23:02:47 UTC, H. S. Teoh wrote:
> Maybe a type distinction akin to C++'s auto_ptr might help?

Yeah, that's what I'm thinking, but I don't really like it. Perhaps I'm trying too hard to cover everything, and should be happier with just doing what C++ does. Full memory safety is prolly out the window anyway.

In std.typecons, there's a Unique!T, but it doesn't look complete. A lot of the code is commented out, maybe it was started back in the days of bug city.

> Yeah, I'm started to wonder if it even makes sense to try to mix-n-match GC-based and non-GC-based allocators.

It might not be so bad if we modified D to add a lent storage class, or something, similar to some discussions about scope in the past.

These would be values you may work with, but never keep; assigning them to anything is not allowed and you may only pass them to a function or return them from a function if that is also marked lent. Any regular reference would be implicitly usable as lent.

int* ptr;

void bar(int* a) {
  foo(a); // ok
}

int* foo(lent int* a) {
   bar(a); // error, cannot call bar with lent pointer
   ptr = a; // error, cannot assign lent value to non-lent field
   foo2(a); // ok
   foo(foo2(a)); // ok
   return a; // error, cannot return a lent value
}

lent int* foo2(lent int* a) {
   return a; // ok
}

foo(ptr); // ok (if foo actually compiled)

And finally, if you take the address of a lent reference, that itself is lent; &(lent int*) == lent int**.


Then, if possible, it would be cool if:

lent int* a;
{
  int* b;
  a = b;
}


That was an error, because a outlived b. But since you can't store a anywhere, the only time this would happen would be something like here. And hell maybe we could hammer around that by making lent variables head const and say they must be initialized at declaration, so "lent int* a;" is illegal as well as "a = b;". But we wouldn't want it transitively const, because then:

void fillBuffer(lent char[] buffer) {}

would be disallowed and that is something I would definitely want.



Part of me thinks pure might help with this too.... but eh maybe not because even a pure function could in theory escape a reference via its other parameters.



But with this kind of thing, we could do a nicer pointer type that does:

lent T getThis() { return _this; }
alias getThis this;

and thus implicitly convert our inner pointer to something we can use on the outside world with some confidence that they won't sneak away any references to it. If combined with @disabling the address of operator on the container itself, we could really lock down ownership.

On Wednesday, 26 June 2013 at 23:59:01 UTC, Adam D. Ruppe wrote:
> On Wednesday, 26 June 2013 at 23:02:47 UTC, H. S. Teoh wrote:
>> Maybe a type distinction akin to C++'s auto_ptr might help?
>
> It might not be so bad if we modified D to add a lent storage class, or something, similar to some discussions about scope in the past.
>
> These would be values you may work with, but never keep; assigning them to anything is not allowed and you may only pass them to a function or return them from a function if that is also marked lent. Any regular reference would be implicitly usable as lent.

Something along those lines would probably be a good solution.

It seems that we're working with three types of objects:

1. Objects that are "owned" by a scope (can be stack-allocated)
2. Objects that are "owned" by a another object (C/C++-like memory management)
3. Objects that have no single "owner" (GC memory management)

The first two would probably operate under semantics like "lent" or "scope", although I'd like to propose an extension to the rules: it should be possible to store a weak reference to these types (or at least to #2) once we have weak reference support.

The third type seems to be pretty much solved, seeing as we have a (mostly) working GC.

Something like this might be a nice way to implement it:

class Thing {}

void doSomething(scope Thing t); //Takes #1, #2, or #3 by reference
void doSomethingElse(owned Thing t); //Takes only #2 or #3

void main() {
  scope Thing t1; //stack-allocated
  doSomething(t1);
  owned Thing t2 = new Thing; //heap-allocated but freed at end of scope
  doSomething(t2);
}

On Tuesday, 25 June 2013 at 22:22:09 UTC, cybervadim wrote:
> I know Andrey mentioned he was going to work on Allocators a year ago. In DConf 2013 he described the problems he needs to solve with Allocators. But I wonder if I am missing the discussion around that - I tried searching this forum, found a few threads that was not actually a brain storm for Allocators design.
>
> Please point me in the right direction
> or
> is there a reason it is not discussed
> or
> should we open the discussion?
>
>
> The easiest approach for Allocators design I can imagine would be to let user specify which Allocator operator new should get the memory from (introducing a new keyword allocator). This gives a total control, but assumes user knows what he is doing.
>
> Example:
>
> CustomAllocator ca;
> allocator(ca) {
>   auto a = new A; // operator new will use ScopeAllocator::malloc()
>   auto b = new B;
>
>   free(a); // that should call ScopeAllocator::free()
>   // if free() is missing for allocated area, it is a user responsibility to make sure custom Allocator can handle that
> }
>
> By default allocator is the druntime using GC, free(a) does nothing for it.
>
>
> if some library defines its allocator (e.g. specialized container), there should be ability to:
> 1. override allocator
> 2. get access to the allocator used
>
> I understand that I spent 5 mins thinking about the way Allocators may look.
> My point is - if somebody is working on it, can you please share your ideas?

Old but perhaps relevant?

http://www.linkedin.com/news?viewArticle=&articleID=-1&gid=86782&type=member&item=253295471&articleURL=http%3A%2F%2Fwww%2Eallendowney%2Ecom%2Fss08%2Fhandouts%2Fberger02reconsidering%2Epdf&urlhash=96TJ&goback=%2Egmr_86782%2Egde_86782_member_253295471

(It's an academic article about memory allocation from 2002)

Am Thu, 27 Jun 2013 01:59:00 +0200
schrieb "Adam D. Ruppe" <destructionator@gmail.com>:

> void fillBuffer(lent char[] buffer) {}
> 
> would be disallowed and that is something I would definitely want.

Isn't that what scope is for?

-- 
Marco

On Friday, 28 June 2013 at 07:07:39 UTC, Marco Leise wrote:
> Am Thu, 27 Jun 2013 01:59:00 +0200
> schrieb "Adam D. Ruppe" <destructionator@gmail.com>:
>
>> void fillBuffer(lent char[] buffer) {}
>> 
>> would be disallowed and that is something I would definitely want.
>
> Isn't that what scope is for?

Reading dlang.org makes you guess so but official position is that 'scope' does not exist, so it is hard to say what it is really for.

On Thursday, 27 June 2013 at 22:50:47 UTC, John Colvin wrote:
> Old but perhaps relevant?
>
> http://www.linkedin.com/news?viewArticle=&articleID=-1&gid=86782&type=member&item=253295471&articleURL=http%3A%2F%2Fwww%2Eallendowney%2Ecom%2Fss08%2Fhandouts%2Fberger02reconsidering%2Epdf&urlhash=96TJ&goback=%2Egmr_86782%2Egde_86782_member_253295471
>
> (It's an academic article about memory allocation from 2002)

Interesting paper. Still concurrency isn't really addressed, which is a problem to be future proof.

On Friday, 28 June 2013 at 07:07:39 UTC, Marco Leise wrote:
> Isn't that what scope is for?

I don't really know. In practice, it does something else (usually nothing, but suppresses heap closure allocation on delegates). The DIPs relating to it all talk about returning refs from functions and I'm not sure if they relate to the built ins or not- I don't think it would quite work for what I have in mind.

On Friday, 28 June 2013 at 11:55:46 UTC, Adam D. Ruppe wrote:
> On Friday, 28 June 2013 at 07:07:39 UTC, Marco Leise wrote:
>> Isn't that what scope is for?
>
> I don't really know. In practice, it does something else (usually nothing, but suppresses heap closure allocation on delegates). The DIPs relating to it all talk about returning refs from functions and I'm not sure if they relate to the built ins or not- I don't think it would quite work for what I have in mind.

It is no-op keyword in current implementation for everything but delegates. DIP speculation was based on http://dlang.org/attribute.html#scope and "Parameter Storage Classes" in http://dlang.org/function.html but that info is obviously outdated.

On Friday, 28 June 2013 at 10:57:45 UTC, deadalnix wrote:
> On Thursday, 27 June 2013 at 22:50:47 UTC, John Colvin wrote:
>> Old but perhaps relevant?
>>
>> http://www.linkedin.com/news?viewArticle=&articleID=-1&gid=86782&type=member&item=253295471&articleURL=http%3A%2F%2Fwww%2Eallendowney%2Ecom%2Fss08%2Fhandouts%2Fberger02reconsidering%2Epdf&urlhash=96TJ&goback=%2Egmr_86782%2Egde_86782_member_253295471
>>
>> (It's an academic article about memory allocation from 2002)
>
> Interesting paper. Still concurrency isn't really addressed, which is a problem to be future proof.

http://en.wikipedia.org/wiki/Hoard_memory_allocator