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.

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

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.

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

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.

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.

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

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

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.

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.