www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - On heap segregation, GC optimization and nogc relaxing

reply "deadalnix" <deadalnix gmail.com> writes:
Hi all,

I want to get back on the subject of ownership, lifetime and 
propose some solution, but before, propose to state the problem 
in a way that haven't seen before (even if I have no doubt some 
have came to the same conclusion in the past).

The problem at hand is double: memory management and thread 
safety. Number one has been a hot topic for ages, and number 2 
has become very over the past years, to the widespreading of 
multicores CPU.

The problem at hand here is ownership of data. There are 3 roads 
you can go about it:
  - immutability and GC. Effectively, these 2 technique allow you 
to get rid of ownership. There are advantages and drawbacks i'm 
going to discuss later.
  - Being unsafe and rely on convention. This is the C++ road (and 
a possible road in D). It allow to implement almost any wanted 
scheme, but come at great cost for the developer.
  - Annotations. This is the Rust road. It also come a great cost 
for the developer, as some schemes may be non trivial to express 
granted the type system, but, contrary to the C++ road, is safe.

These approach all have some very nice things going on for them, 
but also some killer scenarios.

Immutability+GC allow to have safety while keeping interfaces 
simple. That is of great value. It also come with some nice 
goodies, in the sense that is it easy and safe to shared data 
without bookkeeping, allowing one to fit more in cache, and 
reduce the amount of garbage created. Most text processing apps 
fall into this category and this is why D is that good at them. 
Another big goodies is that many lock free algorithm become 
possible. Once you remove the need for bookkeeping of ownership 
many operations can be implemented in an atomic manner. 
Additionally, it is possible to implement various GC optimization 
on immutable heap, which make the GC generally more efficient. 
But the cost is also real. For some use case, this mean having a 
large amount of garbage generated (Carmack wrote a piece on 
haskell were he mention the disastrous effect that having a 
framebuffer immutable would have: you'd have to clone it 
everytime you draw in it, which is a no go). GC also tend to 
cause unpredictable runtime characteristics, which programs with 
real time constraint can have hard time to deal with.

Relying on convention has the advantage that any scheme can be 
implemented without constraint, while keeping interface simple. 
The obvious drawback is that it is time consuming and error 
prone. It also make a lot of things unclear, and dev choose the 
better safe than sorry road. That mean excessive copying to make 
sure one own the data, which is wasteful (in term of work for the 
copy itself, garbage generation and cache pressure). If this must 
be an option locally for system code, it doesn't seems like this 
is the right option at program scale and we do it in C++ simply 
because we have to.

Finally, annotations are a great way to combine safety and speed, 
but generally come at a great cost when implenting uncommon 
ownership strategies where you ends up having to express complex 
lifetime and ownership relations.

Ideally, we want to map with what the hardware does. So what does 
the hardware do ?

Multicore CPU have various cores, each of them having layers of 
cache. Cache is organized in cache line and each cache line can 
be in various modes. Actual system are quite complex and deal 
with problems we are not very interesting here (like writeback) 
but the general idea is that every cache line is owned with 
different modes.

Either the cache line is owned by a single core and can be 
written to, or the cache line shared by several cores, each of 
them having a local copy of the line, but none of them can write 
to. There is an internal bus where cores can exchange cache line 
with each other and messages to acquire cache line in read or 
read/write mode. That mean CPU are good at thread local 
read/write, shared immutable and transfer of ownership from one 
core to the other. They are bad at shared writable data (as 
effectively, the cache line will have to bounce back and forth 
between cores, and all memory access will need to be serialized 
instead of performed out of order).

In that world, D has a bizaro position were it use a combination 
of annotations (immutable, shared) and GC. Ultimately, this is a 
good solution. Using annotation for common cases, fallback on 
GC/unsafe code when these annotations fall short.

Before going into why it is fallign short, a digression on GC and 
the benefits of segregating the heap. In D, the heap is almost 
segregated in 3 groups: thread local, shared and immutable. These 
group are very interesting for the GC:
  - Thread local heap can be collected while disturbing only one 
thread. It should be possible to use different strategy in 
different threads.
  - Immutable heap can be collected 100% concurrently without any 
synchronization with the program.
  - Shared heap is the only one that require disturbing the whole 
program, but as a matter of good practice, this heap should be 
small anyway.

Various ML family languages (like OCaml) have adopted segregated 
heap strategy and get great benefice out of it. For instance, 
OCaml's GC is known to outperform Java's in most scenarios.

We are sitting on a huge GC goldmine here, but 3 things prevent 
us to exploit it:
  - Exceptions. They can bubble from one thread to the other and 
create implicit sharing.
  - Uniqueness (as it is defined now) as it allow for unique 
object to be merged with any heap.
  - message passing. Ownership transfert is not possible and so 
unsafe casting ensue.

  * It has to be noted that delegate allow as well for this kind 
of stunt, but this is recognized as a bug by now and hopefully it 
is gonna be fixed.

D has a type qualifier system for which we pay a big price. 
Getting everything const correct is difficult. We'd want to get 
the most bang for the buck. One of the bang we are not far to be 
able to get is segregating the heap. That mean shitty GC and 
unsafe code.

Let's present a concrete exemple using ownership:
pure Object foo() { ... }
immutable o = foo();

This is valid code. However, foo can do arbitrary manipulation to 
come up with the object. These include various allocations. These 
allocation are mutable into foo, which makes it impossible to 
allocate them on the immutable heap (as a GC relying on this 
immutability could mess up things pretty bad). They also cannot 
be allocated on the TL heap as once promoted to immutable, the 
data become shared as well.

On the other hand, ownership means that the compiler can know 
when things go out of scope and free them explicitly. Which is a 
plus as generating less garbage is always a way to improve 
garbage collection. The most efficient work there is is the one 
that do not need to be done.

I'd argue for the introduction of a basic ownership system. 
Something much simpler than rust's, that do not cover all uses 
cases. But the good thing is that we can fallback on GC or unsafe 
code when the system show its limits. That mean we rely less on 
the GC, while being able to provide a better GC.

We already pay a cost at interface with type qualifier, let's 
make the best of it ! I'm proposing to introduce a new type 
qualifier for owned data.

Now it means that throw statement expect a owned(Throwable), that 
pure function that currently return an implicitly unique object 
will return owned(Object) and that message passing will accept to 
pass around owned stuff.

The GC heap can be segregated into island. We currently have 3 
types of islands : Thread local, shared and immutable. These are 
builtin island with special characteristics in the language. The 
new qualifier introduce a new type of island, the owned island.

owned island can only refers to other owned island and to 
immutable. they can be merged in any other island at any time 
(that is why they can't refers to TL or shared).

owned(T) can be passed around as function parameter or returned, 
or stored as fields. When doing so they are consumed. When an 
owned is not consumed and goes out of scope, the whole island is 
freed.

That means that owned(T) can implicitly decay into T, 
immutable(T), shared(T) at any time. When doing so, a call to the 
runtime is done to merge the owned island to the corresponding 
island. It is passed around as owned, then the ownership is 
transferred and all local references to the island are 
invalidated (using them is an error).

On an implementation level, a call to a pure function that return 
an owned could look like this :

{
   IslandID __saved = gc_switch_new_island();
   scope(exit) gc_restore_island(__saved);

   call_pure_function();
}

This allow us to rely much less on the GC and allow for a better 
GC implementation.

 nogc . Remember ? It was in the title. What does a  nogc 
function look like ? a no gc function o not produce any garbage 
or trigger the collection cycle. there is no reason per se to 
prevent the  nogc code to allocate on the GC as long as you know 
it won't produce garbage. That mean the only operation you need 
to ban are the one that merge the owned things into TL, shared or 
immutable heap.

This solves the problem of the  nogc + Exception. As Exception 
are isolated, they can be allocated, throw and catched into  nogc 
code without generating garbage. They can safely bubble out of 
the  nogc section of the code and still be safe.

The same way, it open the door for a LOT of code that is not 
 nogc to be. If the code allocate memory in an owned island and 
return it, then it is now up to the caller to decide whether is 
want's it garbage collected or keep it as owned (and/or make it 
reference counted for instance).

The solution of passing a policy at compile for allocation is 
close to what C++'s stdlib is doing, and even if the proposed 
approach by Andrei is better, I don't think this is a good one. 
The proposed approach allow for a lot of code to be marked as 
 nogc and allow for the caller to decide. That is ultimately what 
we want libraries to look like.
Nov 11 2014
next sibling parent "Orvid King" <blah38621 gmail.com> writes:
On Wednesday, 12 November 2014 at 02:34:55 UTC, deadalnix wrote:
 Hi all,

 I want to get back on the subject of ownership, lifetime and 
 propose some solution, but before, propose to state the problem 
 in a way that haven't seen before (even if I have no doubt some 
 have came to the same conclusion in the past).

 The problem at hand is double: memory management and thread 
 safety. Number one has been a hot topic for ages, and number 2 
 has become very over the past years, to the widespreading of 
 multicores CPU.

 The problem at hand here is ownership of data. There are 3 
 roads you can go about it:
  - immutability and GC. Effectively, these 2 technique allow 
 you to get rid of ownership. There are advantages and drawbacks 
 i'm going to discuss later.
  - Being unsafe and rely on convention. This is the C++ road 
 (and a possible road in D). It allow to implement almost any 
 wanted scheme, but come at great cost for the developer.
  - Annotations. This is the Rust road. It also come a great 
 cost for the developer, as some schemes may be non trivial to 
 express granted the type system, but, contrary to the C++ road, 
 is safe.

 These approach all have some very nice things going on for 
 them, but also some killer scenarios.

 Immutability+GC allow to have safety while keeping interfaces 
 simple. That is of great value. It also come with some nice 
 goodies, in the sense that is it easy and safe to shared data 
 without bookkeeping, allowing one to fit more in cache, and 
 reduce the amount of garbage created. Most text processing apps 
 fall into this category and this is why D is that good at them. 
 Another big goodies is that many lock free algorithm become 
 possible. Once you remove the need for bookkeeping of ownership 
 many operations can be implemented in an atomic manner. 
 Additionally, it is possible to implement various GC 
 optimization on immutable heap, which make the GC generally 
 more efficient. But the cost is also real. For some use case, 
 this mean having a large amount of garbage generated (Carmack 
 wrote a piece on haskell were he mention the disastrous effect 
 that having a framebuffer immutable would have: you'd have to 
 clone it everytime you draw in it, which is a no go). GC also 
 tend to cause unpredictable runtime characteristics, which 
 programs with real time constraint can have hard time to deal 
 with.

 Relying on convention has the advantage that any scheme can be 
 implemented without constraint, while keeping interface simple. 
 The obvious drawback is that it is time consuming and error 
 prone. It also make a lot of things unclear, and dev choose the 
 better safe than sorry road. That mean excessive copying to 
 make sure one own the data, which is wasteful (in term of work 
 for the copy itself, garbage generation and cache pressure). If 
 this must be an option locally for system code, it doesn't 
 seems like this is the right option at program scale and we do 
 it in C++ simply because we have to.

 Finally, annotations are a great way to combine safety and 
 speed, but generally come at a great cost when implenting 
 uncommon ownership strategies where you ends up having to 
 express complex lifetime and ownership relations.

 Ideally, we want to map with what the hardware does. So what 
 does the hardware do ?

 Multicore CPU have various cores, each of them having layers of 
 cache. Cache is organized in cache line and each cache line can 
 be in various modes. Actual system are quite complex and deal 
 with problems we are not very interesting here (like writeback) 
 but the general idea is that every cache line is owned with 
 different modes.

 Either the cache line is owned by a single core and can be 
 written to, or the cache line shared by several cores, each of 
 them having a local copy of the line, but none of them can 
 write to. There is an internal bus where cores can exchange 
 cache line with each other and messages to acquire cache line 
 in read or read/write mode. That mean CPU are good at thread 
 local read/write, shared immutable and transfer of ownership 
 from one core to the other. They are bad at shared writable 
 data (as effectively, the cache line will have to bounce back 
 and forth between cores, and all memory access will need to be 
 serialized instead of performed out of order).

 In that world, D has a bizaro position were it use a 
 combination of annotations (immutable, shared) and GC. 
 Ultimately, this is a good solution. Using annotation for 
 common cases, fallback on GC/unsafe code when these annotations 
 fall short.

 Before going into why it is fallign short, a digression on GC 
 and the benefits of segregating the heap. In D, the heap is 
 almost segregated in 3 groups: thread local, shared and 
 immutable. These group are very interesting for the GC:
  - Thread local heap can be collected while disturbing only one 
 thread. It should be possible to use different strategy in 
 different threads.
  - Immutable heap can be collected 100% concurrently without 
 any synchronization with the program.
  - Shared heap is the only one that require disturbing the 
 whole program, but as a matter of good practice, this heap 
 should be small anyway.

 Various ML family languages (like OCaml) have adopted 
 segregated heap strategy and get great benefice out of it. For 
 instance, OCaml's GC is known to outperform Java's in most 
 scenarios.

 We are sitting on a huge GC goldmine here, but 3 things prevent 
 us to exploit it:
  - Exceptions. They can bubble from one thread to the other and 
 create implicit sharing.
  - Uniqueness (as it is defined now) as it allow for unique 
 object to be merged with any heap.
  - message passing. Ownership transfert is not possible and so 
 unsafe casting ensue.

  * It has to be noted that delegate allow as well for this kind 
 of stunt, but this is recognized as a bug by now and hopefully 
 it is gonna be fixed.

 D has a type qualifier system for which we pay a big price. 
 Getting everything const correct is difficult. We'd want to get 
 the most bang for the buck. One of the bang we are not far to 
 be able to get is segregating the heap. That mean shitty GC and 
 unsafe code.

 Let's present a concrete exemple using ownership:
 pure Object foo() { ... }
 immutable o = foo();

 This is valid code. However, foo can do arbitrary manipulation 
 to come up with the object. These include various allocations. 
 These allocation are mutable into foo, which makes it 
 impossible to allocate them on the immutable heap (as a GC 
 relying on this immutability could mess up things pretty bad). 
 They also cannot be allocated on the TL heap as once promoted 
 to immutable, the data become shared as well.

 On the other hand, ownership means that the compiler can know 
 when things go out of scope and free them explicitly. Which is 
 a plus as generating less garbage is always a way to improve 
 garbage collection. The most efficient work there is is the one 
 that do not need to be done.

 I'd argue for the introduction of a basic ownership system. 
 Something much simpler than rust's, that do not cover all uses 
 cases. But the good thing is that we can fallback on GC or 
 unsafe code when the system show its limits. That mean we rely 
 less on the GC, while being able to provide a better GC.

 We already pay a cost at interface with type qualifier, let's 
 make the best of it ! I'm proposing to introduce a new type 
 qualifier for owned data.

 Now it means that throw statement expect a owned(Throwable), 
 that pure function that currently return an implicitly unique 
 object will return owned(Object) and that message passing will 
 accept to pass around owned stuff.

 The GC heap can be segregated into island. We currently have 3 
 types of islands : Thread local, shared and immutable. These 
 are builtin island with special characteristics in the 
 language. The new qualifier introduce a new type of island, the 
 owned island.

 owned island can only refers to other owned island and to 
 immutable. they can be merged in any other island at any time 
 (that is why they can't refers to TL or shared).

 owned(T) can be passed around as function parameter or 
 returned, or stored as fields. When doing so they are consumed. 
 When an owned is not consumed and goes out of scope, the whole 
 island is freed.

 That means that owned(T) can implicitly decay into T, 
 immutable(T), shared(T) at any time. When doing so, a call to 
 the runtime is done to merge the owned island to the 
 corresponding island. It is passed around as owned, then the 
 ownership is transferred and all local references to the island 
 are invalidated (using them is an error).

 On an implementation level, a call to a pure function that 
 return an owned could look like this :

 {
   IslandID __saved = gc_switch_new_island();
   scope(exit) gc_restore_island(__saved);

   call_pure_function();
 }

 This allow us to rely much less on the GC and allow for a 
 better GC implementation.

  nogc . Remember ? It was in the title. What does a  nogc 
 function look like ? a no gc function o not produce any garbage 
 or trigger the collection cycle. there is no reason per se to 
 prevent the  nogc code to allocate on the GC as long as you 
 know it won't produce garbage. That mean the only operation you 
 need to ban are the one that merge the owned things into TL, 
 shared or immutable heap.

 This solves the problem of the  nogc + Exception. As Exception 
 are isolated, they can be allocated, throw and catched into 
  nogc code without generating garbage. They can safely bubble 
 out of the  nogc section of the code and still be safe.

 The same way, it open the door for a LOT of code that is not 
  nogc to be. If the code allocate memory in an owned island and 
 return it, then it is now up to the caller to decide whether is 
 want's it garbage collected or keep it as owned (and/or make it 
 reference counted for instance).

 The solution of passing a policy at compile for allocation is 
 close to what C++'s stdlib is doing, and even if the proposed 
 approach by Andrei is better, I don't think this is a good one. 
 The proposed approach allow for a lot of code to be marked as 
  nogc and allow for the caller to decide. That is ultimately 
 what we want libraries to look like.
I think a combination of the C++'s standard library's approach and Rust's approach would actually be the best possible. If we were to follow C++'s strategy, I think it would be important to make sure that it wouldn't require specifically adding template parameters and constraints, and instead allow the use of a concept-like system. I think that being able to default the allocator parameter to the GC, provided the current method is not nogc, would also be a good idea. I think that if C++'s approach were taken it would also be very beneficial to allow a syntax such as `auto obj = new MyClass() with allocator`, and `delete obj with allocator`. I do think that the definition of nogc would have to be slightly expanded though, so mean that any values that are allocated with a given allocator are also freed with the given allocator before returning. To connect back with your proposal and allow even more to be nogc, an owned(MyClass, allocator) object would be allowable to be returned in an nogc function. This would allow transfer of the ownership of the data and responsibility of deletion to the caller, provided that the caller is nogc. If the caller is nogc and fails to free the memory, DMD should produce an error. If the caller is not nogc, then DMD would say nothing, and assume that the allocator used to allocate the object will do the cleanup. This would allow far more situations to be accounted for by the allocation system without needing a GC, while still allowing programs that want to to use the GC. nogc would simply mean that no garbage is produced, it would not make a guarantee of what allocator was used to perform the allocation. nogc would also mean that no allocators, other than the ones passed in by the user, would be used to perform the allocations. This allows the current definition of nogc to still be present, while opening the scope of nogc up for use in a much larger variety of situations.
Nov 11 2014
prev sibling next sibling parent reply Rikki Cattermole <alphaglosined gmail.com> writes:
On 12/11/2014 3:34 p.m., deadalnix wrote:
 Hi all,

 I want to get back on the subject of ownership, lifetime and propose
 some solution, but before, propose to state the problem in a way that
 haven't seen before (even if I have no doubt some have came to the same
 conclusion in the past).

 The problem at hand is double: memory management and thread safety.
 Number one has been a hot topic for ages, and number 2 has become very
 over the past years, to the widespreading of multicores CPU.

 The problem at hand here is ownership of data. There are 3 roads you can
 go about it:
   - immutability and GC. Effectively, these 2 technique allow you to get
 rid of ownership. There are advantages and drawbacks i'm going to
 discuss later.
   - Being unsafe and rely on convention. This is the C++ road (and a
 possible road in D). It allow to implement almost any wanted scheme, but
 come at great cost for the developer.
   - Annotations. This is the Rust road. It also come a great cost for
 the developer, as some schemes may be non trivial to express granted the
 type system, but, contrary to the C++ road, is safe.

 These approach all have some very nice things going on for them, but
 also some killer scenarios.

 Immutability+GC allow to have safety while keeping interfaces simple.
 That is of great value. It also come with some nice goodies, in the
 sense that is it easy and safe to shared data without bookkeeping,
 allowing one to fit more in cache, and reduce the amount of garbage
 created. Most text processing apps fall into this category and this is
 why D is that good at them. Another big goodies is that many lock free
 algorithm become possible. Once you remove the need for bookkeeping of
 ownership many operations can be implemented in an atomic manner.
 Additionally, it is possible to implement various GC optimization on
 immutable heap, which make the GC generally more efficient. But the cost
 is also real. For some use case, this mean having a large amount of
 garbage generated (Carmack wrote a piece on haskell were he mention the
 disastrous effect that having a framebuffer immutable would have: you'd
 have to clone it everytime you draw in it, which is a no go). GC also
 tend to cause unpredictable runtime characteristics, which programs with
 real time constraint can have hard time to deal with.

 Relying on convention has the advantage that any scheme can be
 implemented without constraint, while keeping interface simple. The
 obvious drawback is that it is time consuming and error prone. It also
 make a lot of things unclear, and dev choose the better safe than sorry
 road. That mean excessive copying to make sure one own the data, which
 is wasteful (in term of work for the copy itself, garbage generation and
 cache pressure). If this must be an option locally for system code, it
 doesn't seems like this is the right option at program scale and we do
 it in C++ simply because we have to.

 Finally, annotations are a great way to combine safety and speed, but
 generally come at a great cost when implenting uncommon ownership
 strategies where you ends up having to express complex lifetime and
 ownership relations.

 Ideally, we want to map with what the hardware does. So what does the
 hardware do ?

 Multicore CPU have various cores, each of them having layers of cache.
 Cache is organized in cache line and each cache line can be in various
 modes. Actual system are quite complex and deal with problems we are not
 very interesting here (like writeback) but the general idea is that
 every cache line is owned with different modes.

 Either the cache line is owned by a single core and can be written to,
 or the cache line shared by several cores, each of them having a local
 copy of the line, but none of them can write to. There is an internal
 bus where cores can exchange cache line with each other and messages to
 acquire cache line in read or read/write mode. That mean CPU are good at
 thread local read/write, shared immutable and transfer of ownership from
 one core to the other. They are bad at shared writable data (as
 effectively, the cache line will have to bounce back and forth between
 cores, and all memory access will need to be serialized instead of
 performed out of order).

 In that world, D has a bizaro position were it use a combination of
 annotations (immutable, shared) and GC. Ultimately, this is a good
 solution. Using annotation for common cases, fallback on GC/unsafe code
 when these annotations fall short.

 Before going into why it is fallign short, a digression on GC and the
 benefits of segregating the heap. In D, the heap is almost segregated in
 3 groups: thread local, shared and immutable. These group are very
 interesting for the GC:
   - Thread local heap can be collected while disturbing only one thread.
 It should be possible to use different strategy in different threads.
   - Immutable heap can be collected 100% concurrently without any
 synchronization with the program.
   - Shared heap is the only one that require disturbing the whole
 program, but as a matter of good practice, this heap should be small
 anyway.

 Various ML family languages (like OCaml) have adopted segregated heap
 strategy and get great benefice out of it. For instance, OCaml's GC is
 known to outperform Java's in most scenarios.

 We are sitting on a huge GC goldmine here, but 3 things prevent us to
 exploit it:
   - Exceptions. They can bubble from one thread to the other and create
 implicit sharing.
   - Uniqueness (as it is defined now) as it allow for unique object to
 be merged with any heap.
   - message passing. Ownership transfert is not possible and so unsafe
 casting ensue.

   * It has to be noted that delegate allow as well for this kind of
 stunt, but this is recognized as a bug by now and hopefully it is gonna
 be fixed.

 D has a type qualifier system for which we pay a big price. Getting
 everything const correct is difficult. We'd want to get the most bang
 for the buck. One of the bang we are not far to be able to get is
 segregating the heap. That mean shitty GC and unsafe code.

 Let's present a concrete exemple using ownership:
 pure Object foo() { ... }
 immutable o = foo();

 This is valid code. However, foo can do arbitrary manipulation to come
 up with the object. These include various allocations. These allocation
 are mutable into foo, which makes it impossible to allocate them on the
 immutable heap (as a GC relying on this immutability could mess up
 things pretty bad). They also cannot be allocated on the TL heap as once
 promoted to immutable, the data become shared as well.

 On the other hand, ownership means that the compiler can know when
 things go out of scope and free them explicitly. Which is a plus as
 generating less garbage is always a way to improve garbage collection.
 The most efficient work there is is the one that do not need to be done.

 I'd argue for the introduction of a basic ownership system. Something
 much simpler than rust's, that do not cover all uses cases. But the good
 thing is that we can fallback on GC or unsafe code when the system show
 its limits. That mean we rely less on the GC, while being able to
 provide a better GC.

 We already pay a cost at interface with type qualifier, let's make the
 best of it ! I'm proposing to introduce a new type qualifier for owned
 data.

 Now it means that throw statement expect a owned(Throwable), that pure
 function that currently return an implicitly unique object will return
 owned(Object) and that message passing will accept to pass around owned
 stuff.

 The GC heap can be segregated into island. We currently have 3 types of
 islands : Thread local, shared and immutable. These are builtin island
 with special characteristics in the language. The new qualifier
 introduce a new type of island, the owned island.

 owned island can only refers to other owned island and to immutable.
 they can be merged in any other island at any time (that is why they
 can't refers to TL or shared).

 owned(T) can be passed around as function parameter or returned, or
 stored as fields. When doing so they are consumed. When an owned is not
 consumed and goes out of scope, the whole island is freed.

 That means that owned(T) can implicitly decay into T, immutable(T),
 shared(T) at any time. When doing so, a call to the runtime is done to
 merge the owned island to the corresponding island. It is passed around
 as owned, then the ownership is transferred and all local references to
 the island are invalidated (using them is an error).

 On an implementation level, a call to a pure function that return an
 owned could look like this :

 {
    IslandID __saved = gc_switch_new_island();
    scope(exit) gc_restore_island(__saved);

    call_pure_function();
 }

 This allow us to rely much less on the GC and allow for a better GC
 implementation.

  nogc . Remember ? It was in the title. What does a  nogc function look
 like ? a no gc function o not produce any garbage or trigger the
 collection cycle. there is no reason per se to prevent the  nogc code to
 allocate on the GC as long as you know it won't produce garbage. That
 mean the only operation you need to ban are the one that merge the owned
 things into TL, shared or immutable heap.

 This solves the problem of the  nogc + Exception. As Exception are
 isolated, they can be allocated, throw and catched into  nogc code
 without generating garbage. They can safely bubble out of the  nogc
 section of the code and still be safe.

 The same way, it open the door for a LOT of code that is not  nogc to
 be. If the code allocate memory in an owned island and return it, then
 it is now up to the caller to decide whether is want's it garbage
 collected or keep it as owned (and/or make it reference counted for
 instance).

 The solution of passing a policy at compile for allocation is close to
 what C++'s stdlib is doing, and even if the proposed approach by Andrei
 is better, I don't think this is a good one. The proposed approach allow
 for a lot of code to be marked as  nogc and allow for the caller to
 decide. That is ultimately what we want libraries to look like.
Humm. import std.stdio; struct TypeOwnerShip(T) { T value; alias value this; this(T)(T value) { this.value = value; } // implict casts to immutable, shared? // on cast to immutable, shared change islands } T owned(T)(T value) { return TypeOwnerShip!T(value); } class Bar { int x; this(int x) pure { this.x = x; } } Bar foo() pure { return owned(new Bar(5)); } struct IslandAllocationStrategy { this(ubyte v = 0) { } void opWithIn() { writeln("opWithIn"); // thread local overriding } void opWithOut() { import std.stdio; writeln("opWithOut"); // reset thread local overriding } } property IslandAllocationStrategy island() { return IslandAllocationStrategy(); } void main() { writeln("start"); with(island) { opWithIn; writeln("{"); Bar myValue = foo(); writeln(myValue.x); writeln("}"); opWithOut; } writeln("end"); } I feel like I've suggested this, just without the CS theory.
Nov 11 2014
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Wednesday, 12 November 2014 at 03:13:20 UTC, Rikki Cattermole 
wrote:
 [...]
yes and no. The ideas is similar, but it is not doable at library level if we want to get safety and the full benefit out of it, as it would require for the compiler to introduce some call to the runtime at strategic places and it does interact with nogc.
Nov 11 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Wednesday, 12 November 2014 at 06:48:47 UTC, deadalnix wrote:
 On Wednesday, 12 November 2014 at 03:13:20 UTC, Rikki 
 Cattermole wrote:
 [...]
yes and no. The ideas is similar, but it is not doable at library level if we want to get safety and the full benefit out of it, as it would require for the compiler to introduce some call to the runtime at strategic places and it does interact with nogc.
I'm not sure. A library implementation may be feasible. For invalidation, the objects can be returned to their init state. This is "safe", but maybe not ideal, as a compiler error might indeed be better. Even implicit conversion to shared & immutable will be possible with multiple alias this, though it's worth discussing whether an explicit conversion isn't preferable. As for nogc, I see it as a clutch that's needed while no "real" solution is available, and as a tool for aiding transition once we have one. That said, some compiler support will definitely be necessary.
Nov 12 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Wednesday, 12 November 2014 at 12:57:58 UTC, Marc Schütz wrote:
 On Wednesday, 12 November 2014 at 06:48:47 UTC, deadalnix wrote:
 On Wednesday, 12 November 2014 at 03:13:20 UTC, Rikki 
 Cattermole wrote:
 [...]
yes and no. The ideas is similar, but it is not doable at library level if we want to get safety and the full benefit out of it, as it would require for the compiler to introduce some call to the runtime at strategic places and it does interact with nogc.
I'm not sure. A library implementation may be feasible. For invalidation, the objects can be returned to their init state. This is "safe", but maybe not ideal, as a compiler error might indeed be better. Even implicit conversion to shared & immutable will be possible with multiple alias this, though it's worth discussing whether an explicit conversion isn't preferable. As for nogc, I see it as a clutch that's needed while no "real" solution is available, and as a tool for aiding transition once we have one. That said, some compiler support will definitely be necessary.
I now remember that I played around with a related idea when Andrei suggested his template solution (but without the islands part): http://wiki.dlang.org/User:Schuetzm/RC,_Owned_and_allocators The important part is that owning, RC and GC types all need to know the allocators they belong to. In my example I need that to allow Owned types to be converted to RC types. In your proposal, something similar will ultimately be needed for merging the islands into specific heaps. The nice thing is that this scheme also allows for switching allocators on the fly at runtime, without template bloat, at the cost of virtual calls for using the allocators (which is probably an acceptable compromise for an inherently expensive thing like allocation).
Nov 13 2014
parent "deadalnix" <deadalnix gmail.com> writes:
On Thursday, 13 November 2014 at 14:26:44 UTC, Marc Schütz wrote:
 The important part is that owning, RC and GC types all need to 
 know the allocators they belong to. In my example I need that 
 to allow Owned types to be converted to RC types. In your 
 proposal, something similar will ultimately be needed for 
 merging the islands into specific heaps. The nice thing is that 
 this scheme also allows for switching allocators on the fly at 
 runtime, without template bloat, at the cost of virtual calls 
 for using the allocators (which is probably an acceptable 
 compromise for an inherently expensive thing like allocation).
If you have a owned type, you don't need a builtin RC type. As long as the wrapper that implement the RC own the RCed object, everything is safe. Also, this construct as the nice side effect that a single reference count can own a whole island instead of tracking all objects RC one by one.
Nov 13 2014
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 11/11/2014 6:34 PM, deadalnix wrote:
 [...]
Thanks for an excellent summary of the problem. I can't just read your solution and know it works, it'll take some time.
Nov 11 2014
parent "deadalnix" <deadalnix gmail.com> writes:
On Wednesday, 12 November 2014 at 06:16:34 UTC, Walter Bright 
wrote:
 On 11/11/2014 6:34 PM, deadalnix wrote:
 [...]
Thanks for an excellent summary of the problem. I can't just read your solution and know it works, it'll take some time.
That is quite difficult to explain with drawing. Maybe I can discuss that with Andrei when he has some time with a whiteboard around.
Nov 11 2014
prev sibling next sibling parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Wednesday, 12 November 2014 at 02:34:55 UTC, deadalnix wrote:
 The problem at hand here is ownership of data.
"ownership of data" is one possible solution, but not the problem. We are facing 2 problems: 1. A performance problem: Concurrency in writes (multiple writers, one writer, periodical locking during clean up etc). 2. A structural problem: Releasing resources correctly. I suggest that the ownership focus is on the latter, to support solid non-GC implementations. Then rely on conventions for multi-threading.
  - Being unsafe and rely on convention. This is the C++ road 
 (and a possible road in D). It allow to implement almost any 
 wanted scheme, but come at great cost for the developer.
All performant solutions are going to be "unsafe" in the sense that you need to select a duplication/locking level that are optimal for the characteristics of the actual application. Copying data when you have no writers is too inefficient in real applications. Hardware support for transactional memory is going to be the easy approach for speeding up locking.
  - Annotations. This is the Rust road. It also come a great
I think Rust's approach would favour a STM approach where you create thread local copies for processing then merge the result back into the "shared" memory.
 Immutability+GC allow to have safety while keeping interfaces 
 simple. That is of great value. It also come with some nice 
 goodies, in the sense that is it easy and safe to shared data 
 without bookkeeping, allowing one to fit more in cache, and 
 reduce the amount of garbage created.
How does GC fit more data in the cache? A GC usually has overhead and would typically generate more cache-misses due to unreachable in-cache ("hot") memory not being available for reallocation.
 Relying on convention has the advantage that any scheme can be 
 implemented without constraint, while keeping interface simple. 
 The obvious drawback is that it is time consuming and error 
 prone. It also make a lot of things unclear, and dev choose the 
 better safe than sorry road. That mean excessive copying to 
 make sure one own the data, which is wasteful (in term of work 
 for the copy itself, garbage generation and cache pressure). If 
 this must be an option locally for system code, it doesn't 
 seems like this is the right option at program scale and we do 
 it in C++ simply because we have to.

 Finally, annotations are a great way to combine safety and 
 speed, but generally come at a great cost when implenting 
 uncommon ownership strategies where you ends up having to 
 express complex lifetime and ownership relations.
The core problem is that if you are unhappy with single-threaded applications then you are looking for high throughput using multi-threading. And in that case sacrificing performance by not using the optimal strategy becomes problematic. The optimal strategy is entirely dependent on the application and the dataset. Therefore you need to support multiple approaches: - per data structure GC - thread local GC - lock annotations of types or variables - speculative lock optimisations (transactional memory) And in the future you also will need to support the integration of GPU/Co-processors into mainstream CPUs. Metal and OpenCL is only a beginning…
 Ideally, we want to map with what the hardware does. So what 
 does the hardware do ?
That changes over time. The current focus in upcoming hardware is on: 1. Heterogenous architecture with high performance co-processors 2. Hardware support for transactional memory Intel CPUs might have buffered transactional memory within 5 years.
 from one core to the other. They are bad at shared writable 
 data (as effectively, the cache line will have to bounce back 
 and forth between cores, and all memory access will need to be 
 serialized instead of performed out of order).
This will vary a lot. On x86 you can write to a whole cache line (buffered) without reading it first and it uses a convenient cache coherency protocol (so that reads/write ops are in order). This is not true for all CPUs. I agree with others that say that a heterogeneous approach, like C++, is the better alternative. If parity with C++ is important then D needs to look closer at OpenMP, but that probably goes beyond what D can achieve in terms of implementation. Some observations: 1. If you are not to rely on conventions for sync'ing threads then you need a pretty extensive framework if you want good performance. 2. Safety will harm performance. 3. Safety with high performance levels requires a very complicated static analysis that will probably not work very well for larger programs. 4. For most applications performance will come through co-processors (GPGPU etc). 5. If hardware progresses faster than compiler development, then you will never reach the performance frontier… I think D needs to cut down on implementation complexity and ensure that the implementation time can catch up with hardware developments. The way to do it is: 1. Accept that generally performant multi-threaded code is unsafe and application/hardware optimized. 2. Focus on making nogc single-threaded code robust and fast. And I agree that ownership is key. 3. Use semantic analysis to automatically generate a tailored runtime with application-optimized allocators.
Nov 12 2014
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Wednesday, 12 November 2014 at 08:38:14 UTC, Ola Fosheim 
Grøstad wrote:
 That changes over time. The current focus in upcoming hardware 
 is on:

 1. Heterogenous architecture with high performance co-processors

 2. Hardware support for transactional memory

 Intel CPUs might have buffered transactional memory within 5 
 years.
I'm sorry to be blunt, but there is nothing actionable in your comment. You are just throwing more and more into the pot until nobody know what there is in. But ultimately, the crux of the problem is the thing quoted above. 1. No that do not change that much over time. The implementations details are changing, recent schemes become more complex to accommodate heterogeneous chips, but it is irrelevant here. What I've mentioned is true for all of them, and has been for at least 2 decades by now. There is no sign that this is gonna change. 2. The transactional memory thing is completely orthogonal to the subject at hand so, as the details of implementation of modern chip, this doesn't belong here. In addition, the whole CPU industry is backpedaling on the transactional memory concept. That is awesome on the paper, but it didn't worked. There is only 2 way to achieve good design. You remove useless things until there is obviously nothing wrong, or you add more and more until there is nothing obviously wrong. I won't follow you down the second road, so please stay on track.
Nov 12 2014
next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Wednesday, 12 November 2014 at 08:55:30 UTC, deadalnix wrote:
 I'm sorry to be blunt, but there is nothing actionable in your 
 comment. You are just throwing more and more into the pot until 
 nobody know what there is in. But ultimately, the crux of the 
 problem is the thing quoted above.
My point is that you are making too many assumptions about both applications and hardware.
  2. The transactional memory thing is completely orthogonal to 
 the subject at hand so, as the details of implementation of 
 modern chip, this doesn't belong here. In addition, the whole 
 CPU industry is backpedaling on the transactional memory 
 concept. That is awesome on the paper, but it didn't worked.
STM is used quite a bit. Hardware backed TM is used by IBM. For many computationally intensive applications high levels of parallelism is achieved using speculative computation. TM supports that.
 There is only 2 way to achieve good design. You remove useless 
 things until there is obviously nothing wrong, or you add more 
 and more until there is nothing obviously wrong. I won't follow 
 you down the second road, so please stay on track.
Good design is achieved by understanding different patterns of concurrency in applications and how it can reach peak performance in the environment (hardware). If D is locked to a narrow memory model then you can only reach high performance on a subset of applications. If D wants to support system level programming then it needs to taken an open approach to the memory model.
Nov 12 2014
prev sibling parent reply "Paulo Pinto" <pjmlp progtools.org> writes:
On Wednesday, 12 November 2014 at 08:55:30 UTC, deadalnix wrote:
 On Wednesday, 12 November 2014 at 08:38:14 UTC, Ola Fosheim
In addition, the whole
 CPU industry is backpedaling on the transactional memory 
 concept. That is awesome on the paper, but it didn't worked.
Given the support on Haskell, Clojure and C++ I am not sure if they are really backpedaling on it. The Haskell bugs are supposed to have been fixed in the next generation. And there is PowerPC A2 as well. Not that I have any use for it, though. -- Paulo
Nov 12 2014
parent reply "ponce" <contact gam3sfrommars.fr> writes:
On Wednesday, 12 November 2014 at 09:56:57 UTC, Paulo  Pinto 
wrote:
 On Wednesday, 12 November 2014 at 08:55:30 UTC, deadalnix wrote:
 On Wednesday, 12 November 2014 at 08:38:14 UTC, Ola Fosheim
In addition, the whole
 CPU industry is backpedaling on the transactional memory 
 concept. That is awesome on the paper, but it didn't worked.
Given the support on Haskell, Clojure and C++ I am not sure if they are really backpedaling on it. The Haskell bugs are supposed to have been fixed in the next generation. And there is PowerPC A2 as well. Not that I have any use for it, though. -- Paulo
I actually tested Haswell HLE and was underwhelmed (not the full STM, was just trying to get more out of some locks). The trouble with STM is that to be applicable, you need to have huge contention (else it wouldn't be a bottleneck) and a small task to do. And this use case is already well served with spinlock-guarded locks which already allows to stay in user space most of the time. That, added with the usual restrictions and gotchas for lockfree, makes it something not very life-changing at least in my limited experience.
Nov 12 2014
parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Wednesday, 12 November 2014 at 11:08:41 UTC, ponce wrote:
 I actually tested Haswell HLE and was underwhelmed (not the 
 full STM, was just trying to get more out of some locks).
STM = software based transactional memory (without hardware support) Haswell does not have buffered transactions so you wait for the commit, but there are presentations out where Intel has put buffered transactions at around 2017… (but I would expect a delay).
Nov 12 2014
parent reply "ponce" <contact gam3sfrommars.fr> writes:
On Wednesday, 12 November 2014 at 11:19:59 UTC, Ola Fosheim 
Grøstad wrote:
 STM = software based transactional memory (without hardware 
 support)
I was meaning HTM instead, good catch.
 Haswell does not have buffered transactions so you wait for the 
 commit, but there are presentations out where Intel has put 
 buffered transactions at around 2017… (but I would expect a 
 delay).
I wasn't arguing of the current performance (which is not impressive). My point is that transactional memory has limited applicability, since locks already fits the bill well. And I'd argue the same with most lockfree structures actually.
Nov 12 2014
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Wednesday, 12 November 2014 at 11:51:11 UTC, ponce wrote:
 Haswell does not have buffered transactions so you wait for 
 the commit, but there are presentations out where Intel has 
 put buffered transactions at around 2017… (but I would expect 
 a delay).
I wasn't arguing of the current performance (which is not impressive). My point is that transactional memory has limited applicability, since locks already fits the bill well.
Yes, Intel style HTM is only an optimization for high contention where you already have locking code in place, since you need to take a lock as a fallback anyway. But useful for database-like situations where you might have 7 readers traversing and 1 writer updating a leaf node. It is of course difficult to say how it will perform in 2./3. generation implementations or if the overall hardware architecture will change radically (as we see in Phi and Parallella). I can easily imagine that the on-die architecture will change radically, within a decade, with the current x86 architecture remaining at a coordination level. This is the direction Phi seems to be going. In that case, maybe the performance of the x86 will be less critical (if it spends most time waiting and buffering is done in hardware).
 And I'd argue the same with most lockfree structures actually.
I think in general that you need to create application specific data-structures to get performance and convenience. (I seldom reuse lists and graph-like data structures for this reason, it is just easier to create them from scratch.) I also agree that you usually can get away with regular locks and very simple lockfree structures where performance matters (such as a lockfree stack where only one thread removes nodes). Where performance truly matters you probably need to split up the dataset based on the actual computations and run over the data in a batch-like SIMD way anyway. (E.g. physics simulation).
Nov 12 2014
prev sibling next sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Wednesday, 12 November 2014 at 02:34:55 UTC, deadalnix wrote:
 Before going into why it is fallign short, a digression on GC 
 and the benefits of segregating the heap. In D, the heap is 
 almost segregated in 3 groups: thread local, shared and 
 immutable. These group are very interesting for the GC:
  - Thread local heap can be collected while disturbing only one 
 thread. It should be possible to use different strategy in 
 different threads.
  - Immutable heap can be collected 100% concurrently without 
 any synchronization with the program.
  - Shared heap is the only one that require disturbing the 
 whole program, but as a matter of good practice, this heap 
 should be small anyway.
All this is unfortunately only true if there are no references between heaps, i.e. if the heaps are indeed "islands". Otherwise, there need to be at least write barriers.
 I'd argue for the introduction of a basic ownership system. 
 Something much simpler than rust's, that do not cover all uses 
 cases. But the good thing is that we can fallback on GC or 
 unsafe code when the system show its limits. That mean we rely 
 less on the GC, while being able to provide a better GC.

 We already pay a cost at interface with type qualifier, let's 
 make the best of it ! I'm proposing to introduce a new type 
 qualifier for owned data.

 Now it means that throw statement expect a owned(Throwable), 
 that pure function that currently return an implicitly unique 
 object will return owned(Object) and that message passing will 
 accept to pass around owned stuff.

 The GC heap can be segregated into island. We currently have 3 
 types of islands : Thread local, shared and immutable. These 
 are builtin island with special characteristics in the 
 language. The new qualifier introduce a new type of island, the 
 owned island.

 owned island can only refers to other owned island and to 
 immutable. they can be merged in any other island at any time 
 (that is why they can't refers to TL or shared).

 owned(T) can be passed around as function parameter or 
 returned, or stored as fields. When doing so they are consumed. 
 When an owned is not consumed and goes out of scope, the whole 
 island is freed.

 That means that owned(T) can implicitly decay into T, 
 immutable(T), shared(T) at any time. When doing so, a call to 
 the runtime is done to merge the owned island to the 
 corresponding island. It is passed around as owned, then the 
 ownership is transferred and all local references to the island 
 are invalidated (using them is an error).

 On an implementation level, a call to a pure function that 
 return an owned could look like this :

 {
   IslandID __saved = gc_switch_new_island();
   scope(exit) gc_restore_island(__saved);

   call_pure_function();
 }
This is nice. Instead of calling fixed helpers in Druntime, it can also make an indirect call to allow for pluggable (and runtime switchable) allocators.
 The solution of passing a policy at compile for allocation is 
 close to what C++'s stdlib is doing, and even if the proposed 
 approach by Andrei is better, I don't think this is a good one. 
 The proposed approach allow for a lot of code to be marked as 
  nogc and allow for the caller to decide. That is ultimately 
 what we want libraries to look like.
+1 Andrei's approach mixes up memory allocation and memory management. Library functions shouldn't know about the latter. This proposal is clearly better and cleaner in this respect.
Nov 12 2014
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Wednesday, 12 November 2014 at 12:49:41 UTC, Marc Schütz wrote:
 All this is unfortunately only true if there are no references 
 between heaps, i.e. if the heaps are indeed "islands". 
 Otherwise, there need to be at least write barriers.
Yes, that is exactly why I'm listing the case where these can be created in safe code and propose a solution to plug the hole (and which brings other benefits along the road).
Nov 12 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Wednesday, 12 November 2014 at 21:15:05 UTC, deadalnix wrote:
 On Wednesday, 12 November 2014 at 12:49:41 UTC, Marc Schütz 
 wrote:
 All this is unfortunately only true if there are no references 
 between heaps, i.e. if the heaps are indeed "islands". 
 Otherwise, there need to be at least write barriers.
Yes, that is exactly why I'm listing the case where these can be created in safe code and propose a solution to plug the hole (and which brings other benefits along the road).
Hmm... I can't find that in what you wrote. To clarify: I'm talking about the fact that, for example, a thread-local heap can contain references into the immutable and shared heaps. Therefore, the immutable heap can _not_ be collected without disturbing any threads, because any TL heaps (and stacks!) can potentially have references to it. They either need to be stopped, or write barriers need to be utilized when references to immutable data are changed.
Nov 13 2014
next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Thursday, 13 November 2014 at 10:10:34 UTC, Marc Schütz wrote:
 potentially have references to it. They either need to be 
 stopped, or write barriers need to be utilized when references 
 to immutable data are changed.
I sometimes wonder if the very pragmatic and brutal option of just having GC on the main thread and prevent all escapes of objects from the main thread without explicit ownership transfer would solve D's GC performance related problems. It would work for real time applications and it would work for people who use D in a scripty fashion (but not for vibe.d).
Nov 13 2014
prev sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Thursday, 13 November 2014 at 10:10:34 UTC, Marc Schütz wrote:
 On Wednesday, 12 November 2014 at 21:15:05 UTC, deadalnix wrote:
 On Wednesday, 12 November 2014 at 12:49:41 UTC, Marc Schütz 
 wrote:
 All this is unfortunately only true if there are no 
 references between heaps, i.e. if the heaps are indeed 
 "islands". Otherwise, there need to be at least write 
 barriers.
Yes, that is exactly why I'm listing the case where these can be created in safe code and propose a solution to plug the hole (and which brings other benefits along the road).
Hmm... I can't find that in what you wrote. To clarify: I'm talking about the fact that, for example, a thread-local heap can contain references into the immutable and shared heaps. Therefore, the immutable heap can _not_ be collected without disturbing any threads, because any TL heaps (and stacks!) can potentially have references to it. They either need to be stopped, or write barriers need to be utilized when references to immutable data are changed.
You need a set of root from the TL heap. The trick being to consider everything that is allocated AFTER you get the roots as automatically alive (you'll collect this in the next collection cycle). That way, new allocated chunk that have reference in the TL heap will be kept alive, even if you don't know about the roots. You'll find plenty of information about the details if look into GC for ML family languages.
Nov 13 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Thursday, 13 November 2014 at 22:12:22 UTC, deadalnix wrote:
 You need a set of root from the TL heap. The trick being to
 consider everything that is allocated AFTER you get the roots as
 automatically alive (you'll collect this in the next collection
 cycle).

 That way, new allocated chunk that have reference in the TL heap
 will be kept alive, even if you don't know about the roots.

 You'll find plenty of information about the details if look into
 GC for ML family languages.
Consider this: auto i = new immutable(int); immutable(int)* a, b; b = i; // GC kicks in here, scans `a` (== null) a = b; b = null; // GC goes on, scans `b` (== null) // => whoops, no reference to *i Here, a and b are on the stack or in registers. They could also be on the TL heap.
Nov 14 2014
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Friday, 14 November 2014 at 11:46:51 UTC, Marc Schütz wrote:
 On Thursday, 13 November 2014 at 22:12:22 UTC, deadalnix wrote:
 You need a set of root from the TL heap. The trick being to
 consider everything that is allocated AFTER you get the roots 
 as
 automatically alive (you'll collect this in the next collection
 cycle).

 That way, new allocated chunk that have reference in the TL 
 heap
 will be kept alive, even if you don't know about the roots.

 You'll find plenty of information about the details if look 
 into
 GC for ML family languages.
Consider this: auto i = new immutable(int); immutable(int)* a, b; b = i; // GC kicks in here, scans `a` (== null) a = b; b = null; // GC goes on, scans `b` (== null) // => whoops, no reference to *i Here, a and b are on the stack or in registers. They could also be on the TL heap.
That is a well covered subject and told you what to google for as well as the basic approach. Your example here simply told me you haven't done your homework before posting. Please go look into scientific documentation about GC for ML languages.
Nov 14 2014
next sibling parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Friday, 14 November 2014 at 21:59:47 UTC, deadalnix wrote:
 That is a well covered subject and told you what to google for 
 as
 well as the basic approach. Your example here simply told me you
 haven't done your homework before posting.

 Please go look into scientific documentation about GC for ML
 languages.
It would help if you post links to articles. ML is geared towards functional programming which have different behaviour from system level imperative programming, so I am not sure if ML is the best starting point. From https://ocaml.org/learn/tutorials/garbage_collection.html : «OCaml's garbage collector has two heaps, the minor heap and the major heap. This recognises a general principle: Most objects are small and allocated frequently and then immediately freed. These objects go into the minor heap first, which is GCed frequently. Only some objects are long lasting. These objects get promoted from the minor heap to the major heap after some time, and the major heap is only collected infrequently. The OCaml GC is synchronous. It doesn't run in a separate thread, and it can only get called during an allocation request.» Nothing about segregation here. The older MLkit which uses a regional allocator is interesting, but probably not what you are talking about.
Nov 14 2014
parent reply "deadalnix" <deadalnix gmail.com> writes:
ML is interesting because it emphasis immutability. For
performance reasons, a part of it is in effect mutable and thread
local. Some ML implementations are very interesting for us.

But let's get back to D. To make the example simpler, let's get
rid of shared (in effect, the same thing can be achieve with
write barrier on shared and do not fundamentally affect the way
it works).

So we have a TL GC that run on a regular basis.When doing so, it
also collect the pointers to the immutable heap and give the to
the immutable GC as roots.

Now the immutable GC works from these roots, but will consider
everything allocated after it get its root as alive.

This is working because the new root to the immutable heap that
can appear in the TL heap can come from:
   - new allocations.
   - from read in immutable heap.
   - other thread (and it will be a root from their scan).

Let's get rid of #3 by making std.concurency aware of the GC
system. An exchange from a non scanned thread to a scanned one
will register a root.

We get rid of #1 by choosing that all allocation done after
getting the roots are considered alive.

We get rid of #2 by recurrence. Reading from the immutable heap
require a reference to the immutable heap. Ultimately, you end up
with a root in #1 or #2 scenario, that will be considered alive.
As the chain of reference is immutable, the one you read will
ultimately be scanned.

The idea is based on Doligez-Leroy's GC, but using TL heap as the
small object and immutable heap as the shared. Note that this GC
is done for ML, where most things are immutable and this is why
it works well (only require write barriers). This strategy would
be a disaster in java for instance, or for us to use the small
object strategy for TL.
http://gallium.inria.fr/~xleroy/publi/concurrent-gc.pdf
http://www.cs.tau.ac.il/~msagiv/courses/mm/doligez.ppt
Nov 14 2014
parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Saturday, 15 November 2014 at 00:16:22 UTC, deadalnix wrote:
 The idea is based on Doligez-Leroy's GC, but using TL heap as 
 the
 small object and immutable heap as the shared. Note that this GC
 is done for ML, where most things are immutable and this is why
 it works well (only require write barriers). This strategy would
 be a disaster in java for instance, or for us to use the small
 object strategy for TL.
 http://gallium.inria.fr/~xleroy/publi/concurrent-gc.pdf
 http://www.cs.tau.ac.il/~msagiv/courses/mm/doligez.ppt
Thanks for the link! I agree ML has some interesting work done for it, but they make some assumptions: 1. low portion of mutable objects 2. small heap fits in per-core-cache (<256KiB on Haswell). So the small heap is basically a region allocator that caches allocations that are likely to die, cutting down on the more costly effort to update the big heap. But I am not sure if that fits system level programming, that is more typical for functional programming…
Nov 15 2014
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Saturday, 15 November 2014 at 12:52:33 UTC, Ola Fosheim 
Grøstad wrote:
 Thanks for the link! I agree ML has some interesting work done 
 for it, but they make some assumptions:

 1. low portion of mutable objects

 2. small heap fits in per-core-cache (<256KiB on Haswell).

 So the small heap is basically a region allocator that caches 
 allocations that are likely to die, cutting down on the more 
 costly effort to update the big heap. But I am not sure if that 
 fits system level programming, that is more typical for 
 functional programming…
The small heap do not apply for us. We can't reproduce that part of the GC in D. However, the big heap part of the strategy would fit D's immutable heap very nicely.
Nov 15 2014
parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Saturday, 15 November 2014 at 20:13:47 UTC, deadalnix wrote:
 On Saturday, 15 November 2014 at 12:52:33 UTC, Ola Fosheim 
 Grøstad wrote:
 Thanks for the link! I agree ML has some interesting work done 
 for it, but they make some assumptions:

 1. low portion of mutable objects

 2. small heap fits in per-core-cache (<256KiB on Haswell).

 So the small heap is basically a region allocator that caches 
 allocations that are likely to die, cutting down on the more 
 costly effort to update the big heap. But I am not sure if 
 that fits system level programming, that is more typical for 
 functional programming…
The small heap do not apply for us. We can't reproduce that part of the GC in D. However, the big heap part of the strategy would fit D's immutable heap very nicely.
Maybe, but immutable in ML means that two different immutable objects are 100% indistinguishable if they have the same value. Quite often you have a cluster of objects (that could be an isolate) that are periodically immutable. I assume what is most interesting is whether it is immutable between two collections, and not whether it is mutable throughout the lifespan? There are two points in the powerpoint that sticks out though: * «trade collection “quality” for level of synchronization - allow large amounts of floating garbage» * «trade collection “simplicity” for level of synchronization - complicated algorithm (not to mention correctness proof)» And also this: «Root enumeration * Raise a flag to signal beginning of marking * shade globals * ask mutators to shade roots * wait until all mutators answered * meanwhile - start scanning and marking» Does this mean that you need all threads (which I presume are the mutators) to be in an eventloop in order to collect? Online version of the slides: http://s0.docspal.com/files/processed/64/6863864-yusxlrni/doligez.pdf
Nov 18 2014
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Tuesday, 18 November 2014 at 20:34:01 UTC, Ola Fosheim Grøstad
wrote:
 Does this mean that you need all threads (which I presume are 
 the mutators) to be in an eventloop in order to collect?
What you need is for each thread to provide you a list of roots. You can start tracing while having an incomplete list of roots, so the level of concurrency allowed is high. As for the immutability thing, here is how it goes. When you compile to native, you can either do write barrier all the time, via writing point using a function call in the runtime. The second option is to not do it and use memory protection to trap write. Option 1 is usually preferred by VM that can swicth implementation of methods when collecting, so you pay a moderate cost and only when you collect. But if you compile AOT, you always pay that price and it is not very interesting. Optin 2 is WAY more expensive and will trap even write to value, not only pointers. If it expensive, it is only expensive when it traps. That mean it is a very interesting choice for code compiled ahead of time and manipulating immutable data. This is very interesting in the case of ML, where the compiler sometime choses to mutate, but only as an optimization, and very rarely on object that reach the big heap, as if the object is long lived enough to reach that heap, most likely the compiler can't prove it is unique and thus mutable. The same strategy seems like the obvious winner for D's immutable heap as well as part of the shared heap that do not contain mutable pointers.
Nov 18 2014
parent "Guillaume Chatelet" <chatelet.guillaume gmail.com> writes:
What would be the next step to keep this effort going forward ?
A POC implementation would be a lot of work but it would also
help people detect corner cases or unsuspected interaction with
some features of the language.
Nov 21 2014
prev sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Friday, 14 November 2014 at 21:59:47 UTC, deadalnix wrote:
 On Friday, 14 November 2014 at 11:46:51 UTC, Marc Schütz wrote:
 That is a well covered subject and told you what to google for 
 as
 well as the basic approach. Your example here simply told me you
 haven't done your homework before posting.
Ok, you caught me there :-P To my excuse, I did do some (too) superficial research, but even found statements like some ML languages not supporting multithreading, but no details about GC techniques used. But your explanation makes it clear, and this indeed a very clever idea.
Nov 16 2014
parent "Paulo Pinto" <pjmlp progtools.org> writes:
On Sunday, 16 November 2014 at 10:21:53 UTC, Marc Schütz wrote:
 On Friday, 14 November 2014 at 21:59:47 UTC, deadalnix wrote:
 On Friday, 14 November 2014 at 11:46:51 UTC, Marc Schütz wrote:
 That is a well covered subject and told you what to google for 
 as
 well as the basic approach. Your example here simply told me 
 you
 haven't done your homework before posting.
Ok, you caught me there :-P To my excuse, I did do some (too) superficial research, but even found statements like some ML languages not supporting multithreading, but no details about GC techniques used. But your explanation makes it clear, and this indeed a very clever idea.
If you mean OCaml, the runtime is being made multi-thread. http://www.ocamlpro.com/blog/2013/07/01/monthly-06.html
Nov 17 2014
prev sibling next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
12-Nov-2014 05:34, deadalnix пишет:
 Hi all,

 I want to get back on the subject of ownership, lifetime and propose
 some solution, but before, propose to state the problem in a way that
 haven't seen before (even if I have no doubt some have came to the same
 conclusion in the past).
[snip nice summary]
 In that world, D has a bizaro position were it use a combination of
 annotations (immutable, shared) and GC. Ultimately, this is a good
 solution. Using annotation for common cases, fallback on GC/unsafe code
 when these annotations fall short.
Aye.
 Before going into why it is fallign short, a digression on GC and the
 benefits of segregating the heap. In D, the heap is almost segregated in
 3 groups: thread local, shared and immutable. These group are very
 interesting for the GC:
   - Thread local heap can be collected while disturbing only one thread.
 It should be possible to use different strategy in different threads.
   - Immutable heap can be collected 100% concurrently without any
 synchronization with the program.
   - Shared heap is the only one that require disturbing the whole
 program, but as a matter of good practice, this heap should be small
 anyway.

 Various ML family languages (like OCaml) have adopted segregated heap
 strategy and get great benefice out of it. For instance, OCaml's GC is
 known to outperform Java's in most scenarios.
+1000 We should take advantage of segregated heap to make all complexity of shared/immutable/TL finally pay off.
 I'd argue for the introduction of a basic ownership system. Something
 much simpler than rust's, that do not cover all uses cases. But the good
 thing is that we can fallback on GC or unsafe code when the system show
 its limits. That mean we rely less on the GC, while being able to
 provide a better GC.

 We already pay a cost at interface with type qualifier, let's make the
 best of it ! I'm proposing to introduce a new type qualifier for owned
 data.

 Now it means that throw statement expect a owned(Throwable), that pure
 function that currently return an implicitly unique object will return
 owned(Object) and that message passing will accept to pass around owned
 stuff.

 The GC heap can be segregated into island. We currently have 3 types of
 islands : Thread local, shared and immutable. These are builtin island
 with special characteristics in the language. The new qualifier
 introduce a new type of island, the owned island.
Seems sane. owned(Exception) would be implicitly assumed i.e.: catch(Exception e){ ... } would be seen by compiler as: catch(owned(Exception) e){ ... } What happens if I throw l-value exception? Do I need to cast or assumeOwned it? It's easy to see how it goes with r-values, such as new Exception(...), since they are "unique expressions" whatever that means ;)
 owned island can only refers to other owned island and to immutable.
 they can be merged in any other island at any time (that is why they
 can't refers to TL or shared).

 owned(T) can be passed around as function parameter or returned, or
 stored as fields. When doing so they are consumed. When an owned is not
 consumed and goes out of scope, the whole island is freed.

 That means that owned(T) can implicitly decay into T, immutable(T),
 shared(T) at any time. When doing so, a call to the runtime is done to
 merge the owned island to the corresponding island. It is passed around
 as owned, then the ownership is transferred and all local references to
 the island are invalidated (using them is an error).

 On an implementation level, a call to a pure function that return an
 owned could look like this :

 {
    IslandID __saved = gc_switch_new_island();
    scope(exit) gc_restore_island(__saved);

    call_pure_function();
 }

 This allow us to rely much less on the GC and allow for a better GC
 implementation.
I take it that owned(T) is implicitly deduced by compiler in case of pure functions? Also it seem templates should not take owned(T) into consideration and let it decay... How does owned compose with other qualifiers?
  nogc . Remember ? It was in the title. What does a  nogc function look
 like ? a no gc function o not produce any garbage or trigger the
 collection cycle. there is no reason per se to prevent the  nogc code to
 allocate on the GC as long as you know it won't produce garbage. That
 mean the only operation you need to ban are the one that merge the owned
 things into TL, shared or immutable heap.

 This solves the problem of the  nogc + Exception. As Exception are
 isolated, they can be allocated, throw and catched into  nogc code
 without generating garbage. They can safely bubble out of the  nogc
 section of the code and still be safe.
Seems absolutely cool. But doesn't allocating exception touches heap anyway? I take it that if I don't save exception explicitly anywhere the owned island is destroyed at catch scope?
 The same way, it open the door for a LOT of code that is not  nogc to
 be. If the code allocate memory in an owned island and return it, then
 it is now up to the caller to decide whether is want's it garbage
 collected or keep it as owned (and/or make it reference counted for
 instance).

 The solution of passing a policy at compile for allocation is close to
 what C++'s stdlib is doing, and even if the proposed approach by Andrei
 is better, I don't think this is a good one. The proposed approach allow
 for a lot of code to be marked as  nogc and allow for the caller to
 decide. That is ultimately what we want libraries to look like.
I'm not sure I get all details but I like your proposal MUCH better then forcibly introducing ref-counting. -- Dmitry Olshansky
Nov 12 2014
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Wednesday, 12 November 2014 at 20:36:32 UTC, Dmitry Olshansky 
wrote:
 Seems sane. owned(Exception) would be implicitly assumed i.e.:
 catch(Exception e){ ... }

 would be seen by compiler as:
 catch(owned(Exception) e){ ... }

 What happens if I throw l-value exception? Do I need to cast or 
 assumeOwned it?

 It's easy to see how it goes with r-values, such as new 
 Exception(...), since they are "unique expressions" whatever 
 that means ;)
Yes, the unsafe road must always be open, we are a system programming language :)
 I take it that owned(T) is implicitly deduced by compiler in 
 case of pure functions? Also it seem templates should not take 
 owned(T) into consideration and let it decay... How does owned 
 compose with other qualifiers?
You mean what is I have an owned field into an object ? In the case you pass the owned where a TL, shared or immutable is expected, the island is merged so the question do not make sense. An owned field in an object is interpreted as follow: - immutable => immutable - shared => owned (and can be touched only if the shared object is synchronized, which allow to hide a whole hierarchy behind a mutex. That is another selling point but I don't wanted to get into all the details as the post was already quite big). - const => const owned (essentially unusable - except via burrowing if we ever want to go that road one day).
 Seems absolutely cool. But doesn't allocating exception touches 
 heap anyway? I take it that if I don't save exception 
 explicitly anywhere the owned island is destroyed at catch 
 scope?
Yes it touches the heap. But as long as things are owned, they'll be freed automatically when going out of scope. That means, with that definition of things, what is forbidden in nogc code is to consume the owned in such a fashion that its island is merged into TL, shared or immutable heap. If you don't do this, then your isolated will be freed when going out of scope and the GC won't need to kick in/no garbage will be produced. Doing so allow for relaxing the constraint in nogc and allow for the same library code to be used with or without GC.
Nov 12 2014
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
13-Nov-2014 00:27, deadalnix пишет:
 On Wednesday, 12 November 2014 at 20:36:32 UTC, Dmitry Olshansky wrote:
 Seems sane. owned(Exception) would be implicitly assumed i.e.:
 catch(Exception e){ ... }

 would be seen by compiler as:
 catch(owned(Exception) e){ ... }

 What happens if I throw l-value exception? Do I need to cast or
 assumeOwned it?

 It's easy to see how it goes with r-values, such as new
 Exception(...), since they are "unique expressions" whatever that
 means ;)
Yes, the unsafe road must always be open, we are a system programming language :)
 I take it that owned(T) is implicitly deduced by compiler in case of
 pure functions? Also it seem templates should not take owned(T) into
 consideration and let it decay... How does owned compose with other
 qualifiers?
You mean what is I have an owned field into an object ? In the case you pass the owned where a TL, shared or immutable is expected, the island is merged so the question do not make sense.
Sorry, forgot to reply. Here is the case I wanted to check: try{ ... } catch(owned(Exception) e){ foo(e); } void foo(T)(T arg){ // what would this print? Exception or owned(Exception) // do we bloat a bit more on qualifiers? pragma(msg, T); }
 An owned field in an object is interpreted as follow:
   - immutable => immutable
   - shared => owned (and can be touched only if the shared object is
 synchronized, which allow to hide a whole hierarchy behind a mutex. That
 is another selling point but I don't wanted to get into all the details
 as the post was already quite big).
   - const => const owned (essentially unusable - except via burrowing if
 we ever want to go that road one day).
Thanks, looks sane.
 Seems absolutely cool. But doesn't allocating exception touches heap
 anyway? I take it that if I don't save exception explicitly anywhere
 the owned island is destroyed at catch scope?
Yes it touches the heap. But as long as things are owned, they'll be freed automatically when going out of scope. That means, with that definition of things, what is forbidden in nogc code is to consume the owned in such a fashion that its island is merged into TL, shared or immutable heap. If you don't do this, then your isolated will be freed when going out of scope and the GC won't need to kick in/no garbage will be produced. Doing so allow for relaxing the constraint in nogc and allow for the same library code to be used with or without GC.
-- Dmitry Olshansky
Nov 14 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Friday, 14 November 2014 at 19:02:52 UTC, Dmitry Olshansky 
wrote:
 Here is the case I wanted to check:

 try{
 	...
 }
 catch(owned(Exception) e){
 	foo(e);
 }

 void foo(T)(T arg){
 	// what would this print? Exception or owned(Exception)
 	// do we bloat a bit more on qualifiers?
 	pragma(msg, T);
 }
It needs to be `owned(Exception)`, otherwise, how could the compiler know how to treat it correctly? But declaring foo() in that way would be unhelpful, because it would move the exception on calling the function, which is usually not desired. What you want here, instead, is borrowing: void foo(T)(scope(T) arg) { pragma(msg, T); }
Nov 14 2014
parent "deadalnix" <deadalnix gmail.com> writes:
On Friday, 14 November 2014 at 20:22:13 UTC, Marc Schütz wrote:
 It needs to be `owned(Exception)`, otherwise, how could the 
 compiler know how to treat it correctly? But declaring foo() in 
 that way would be unhelpful, because it would move the 
 exception on calling the function, which is usually not 
 desired. What you want here, instead, is borrowing:

     void foo(T)(scope(T) arg) {
         pragma(msg, T);
     }
That is a very good question. I do think this should show the type of T, without owned qualifier.
Nov 14 2014
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 11/11/2014 6:34 PM, deadalnix wrote:
 On an implementation level, a call to a pure function that return an owned
could
 look like this :

 {
    IslandID __saved = gc_switch_new_island();
    scope(exit) gc_restore_island(__saved);

    call_pure_function();
 }

 This allow us to rely much less on the GC and allow for a better GC
implementation.
If that wrapper is automatically generated by the compiler, so the user doesn't have to mess with it, it could be workable.
Nov 13 2014
parent "deadalnix" <deadalnix gmail.com> writes:
On Friday, 14 November 2014 at 01:05:13 UTC, Walter Bright wrote:
 On 11/11/2014 6:34 PM, deadalnix wrote:
 On an implementation level, a call to a pure function that 
 return an owned could
 look like this :

 {
   IslandID __saved = gc_switch_new_island();
   scope(exit) gc_restore_island(__saved);

   call_pure_function();
 }

 This allow us to rely much less on the GC and allow for a 
 better GC implementation.
If that wrapper is automatically generated by the compiler, so the user doesn't have to mess with it, it could be workable.
Yes, that is the intention. It means that my proposal does increase moderately the complexity of the language, but increase the complexity of the runtime (most specifically the GC) significantly.
Nov 13 2014
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Nice article.

Some observations:

1. I don't understand the difference between 'unique', 'owned' and 'isolated'. 
(Some other systems use 'isolated'.) Is there a difference?

2. I suspect that 'owned' does not need to be a type qualifier - it can be a 
storage class much like 'ref' is. This makes for a much simpler implementation.

3. Taking it a step further, I suspect that 'owned' can be implemented as a 
library type, ala owned!T, with only a smidgen of compiler help.
Nov 17 2014
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Monday, 17 November 2014 at 08:04:44 UTC, Walter Bright wrote:
 Nice article.

 Some observations:

 1. I don't understand the difference between 'unique', 'owned' 
 and 'isolated'. (Some other systems use 'isolated'.) Is there a 
 difference?

 2. I suspect that 'owned' does not need to be a type qualifier 
 - it can be a storage class much like 'ref' is. This makes for 
 a much simpler implementation.

 3. Taking it a step further, I suspect that 'owned' can be 
 implemented as a library type, ala owned!T, with only a smidgen 
 of compiler help.
Ok, I'm gonna respond in reverse order, so I can use one answer as a starting point for the next one. 3. This is not doable as a library type. The proposal interact with nogc, pure function and exception handling. There is no way to make it safe as a librayr type as well, consider: static A statica; class A { void foo() { statica = this; } } owned!A owneda = ... owneda.foo(); We want the compiler to be able to determine what is owned as much as possible and insert the right runtime magic calls to make that work. 2. I'm not sure if that is enough to make it work. It is worth investigating. It is gonna be much more limited than what I have in mind. How do you see this working with fields in struct/classes for instance ? 1. owned is simply a refined version of isolated. The reserach team comming up with isolated did it for concurrency reasons, and it is useful for this, but my proposal include a memory management aspect, that isolated lacks. So I figured out I'd come up with a better name. It is different from unique in the sense that there can be multiple references to the owned object. For instance: class A { A next; } pure auto foo() { auto a1 = new A(); auto a2 = new A(); a1.next = a2; a2.next = a1; return a1; } Here the returned reference is owned. But it is not unique (a2 also have a reference to that object). Owned indicate that you enter into a new island. Everything reached transitively from there is assumed to be in the same island unless you cross a new owned or immutable reference. That means code like: owned(A) bar() { auto a = foo(); auto next = a.next; // At this point, we have 2 local reference to the island. // Returning is an operation that consume. It would invalidate all local reference to that island. That is ok here as we are returning and not using them anyway. return a.next; } is valid. The type system here is not checking that a reference to an object is unique, but that who owns the island is know (and the island only has one owner at a time). It is a more generic and more powerful construct, and I don't think it come at extra complexity for the user compared to unique. However, it definitively means more work on our side.
Nov 17 2014
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 11/17/2014 1:57 PM, deadalnix wrote:
 2. I'm not sure if that is enough to make it work. It is worth
 investigating. It is gonna be much more limited than what I have
 in mind.
There was a lot of skepticism initially when I proposed that ref be a storage class rather than a type constructor, but it turned out that the problems were resolvable and the end design was an unqualified win. So I think we can do this - at a minimum we need to exhaust the possibility.
Nov 17 2014
parent "deadalnix" <deadalnix gmail.com> writes:
On Tuesday, 18 November 2014 at 02:39:48 UTC, Walter Bright wrote:
 On 11/17/2014 1:57 PM, deadalnix wrote:
 2. I'm not sure if that is enough to make it work. It is worth
 investigating. It is gonna be much more limited than what I 
 have
 in mind.
There was a lot of skepticism initially when I proposed that ref be a storage class rather than a type constructor, but it turned out that the problems were resolvable and the end design was an unqualified win. So I think we can do this - at a minimum we need to exhaust the possibility.
ref only make sense at interface boundary. That is not the same thing.
Nov 17 2014
prev sibling parent reply "Dicebot" <public dicebot.lv> writes:
Finally got a look at your proposal. While I do agree with many 
initial statements and, specifically, proposal for heap 
segregation, proposed semantics of `owned` does leave me 
skeptical. It is effectively a more refined/mature approach to 
"cooking of immutables" concept and Marc proposal, while being 
more complicated semantic-wise, allows for much more than that.
Dec 04 2014
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Thursday, 4 December 2014 at 14:23:13 UTC, Dicebot wrote:
 Finally got a look at your proposal. While I do agree with many 
 initial statements and, specifically, proposal for heap 
 segregation, proposed semantics of `owned` does leave me 
 skeptical. It is effectively a more refined/mature approach to 
 "cooking of immutables" concept and Marc proposal, while being 
 more complicated semantic-wise, allows for much more than that.
I don't think this is solving the same problem as Marc's proposal so I'm not sure how comparing them make sense. Marc's proposal is about manipulating data without having ownership. This defines ownership. This proposal add some complexity, but I do think this is a winner. Right now we have various type qualifier (mutable, const, immutable, shared, const shared, inout, inout shared). This come at a cost, and, ultimately, as the proposal interact with this, you want to compare the total complexity with the total benefit. In one case, you have 7 qualifier. You get a mostly safe language out of them. With he proposal, you have 8 qualifiers. You get a safe language out of it + many opportunities to optimize + added expressiveness (ie interaction of GC and no gc code, ownership transfers, safe reference counting, extension of possibilities in nogc code in a similar fashion as weakly pure allow for extra expressiveness in pure code). If you allow me for a non politically correct metaphor, would you buy a 1$ condom with an hole in it or a 1.14$ one that do not ?
Dec 04 2014
parent "Dicebot" <public dicebot.lv> writes:
On Thursday, 4 December 2014 at 23:22:04 UTC, deadalnix wrote:
 I don't think this is solving the same problem as Marc's 
 proposal so I'm not sure how comparing them make sense. Marc's 
 proposal is about manipulating data without having ownership. 
 This defines ownership.
Indeed. But both combined add too much complexity to be feasible and thus we need to decide what problems are more important to solve. I think one from Marc has wider application while elements of yours can be more suitable as hidden implementation detail. Though now there is also DIP69 and I need to seriously shake them all through my head before having any true opinion :P
 This proposal add some complexity, but I do think this is a 
 winner. Right now we have various type qualifier (mutable, 
 const, immutable, shared, const shared, inout, inout shared). 
 This come at a cost, and, ultimately, as the proposal interact 
 with this, you want to compare the total complexity with the 
 total benefit.
I respectfully can't agree that shared qualifier truly exists in current language implementation. Thus perspective is a bit different. Also const/inout don't actually tell anything about how underlying data is managed and serve as secondary utility qualifiers.
Dec 05 2014