Goal of SG5

[fragga...@gmail.com]

Thanks to Herb who reminded me as I may not have made it clear. The goal of an SG is to work on something with the goal of generating an initial proposal into WG21, which WG21 can then decide to take in and progress. So as we move forward, there is an expectation that SG5’s goal is to create a document that could be used as an initial submission to WG21.

Thank you.

[Niall Douglas]

Firstly Michael it was great to meet you at C++ Now and your talk was very interesting. I now feel I am in a position to comment on what minimal initial proposal this SG ought to send forth to the committee, though I am very sure this SG won't like it.

The biggest thing which strikes me about the TM proposal so far is it is far too big, complex, and riven with potential breaking changes to existing code. If I were on the core committee, I would be scared to death to admit the current proposal. I freely admit right now that my ignorance is the cause of this reaction, and I do not wish to dismiss or impune upon all the very substantial work which has gone into TM so far. Nor am I criticising nor condemning anyone on this SG, nor any of the work so far done. However, my ignorance and fear of the current TM proposal is not limited to me: after Michael's talk, I heard a number of people on the core committee informally express very similar worries to mine about the potential of the current proposal to break existing code. Whether these are unfounded or not isn't the important part: the important part is getting TM into C++, not some particular implementation of TM into C++. And right now the current proposal appears too complex to give peace of mind to a lot of folk.

So, given this, here is my alternative minimal initial proposal for TM support in C++. I stress the "initial" part: We start with this and add stuff. I can guarantee everyone on this SG will hate it, but I think it's worth bringing up for discussion as an alternative route to getting standardised TM support into the standard. Call it "TM lite" in a nod to "Concepts Lite":

// transaction context is opaque compiler-internal type

typedef void *trans_ctx;

// unwind context is opaque compiler-internal type

typedef void *unwind_ctx;

// Start a transaction. Can be called many times. Can return NULL if ENOMEM (or HTM has run out of free contexts).

trans_ctx begin_trans();

// Makes the transaction visible if possible, returning false if not possible. Deletes ctx if successful.

_Bool commit_trans(trans_ctx ctx);

// Deletes ctx

void abort_trans(trans_ctx ctx);

// Loads and stores

template<typename T> T trans_load_explicit(trans_ctx ctx, volatile T* obj, memory_order order);

template<typename T> void trans_store_explicit(trans_ctx ctx, volatile T* obj, T desired, memory_order order);

// These equal the explicit forms with order=memory_order_relaxed

template<typename T> T trans_load(trans_ctx ctx, volatile T* obj);

template<typename T> void trans_store(trans_ctx ctx, volatile T* obj, T desired);

// Exchanges ...

template<typename T> T trans_exchange_explicit(trans_ctx ctx, volatile T* obj, T desr, memory_order order);

// API continues duplicating the C11 atomic API but where non-explicit functions default to memory_order_relaxed

...

// Create a stack unwind transaction for this execution context (i.e. curly braces). Can be called many times. Can return NULL if insufficient stack space.

unwind_ctx begin_unwind_trans();

// Registers an unwind transaction to occur when the specified execution context exits.

void commit_unwind_trans(unwind_ctx ctx);

// Unregisters a previously registered unwind transaction.

void abort_unwind_trans(unwind_ctx ctx);

// Add a filtering callback. Gets called when ANY unwind passes through ctx. Callback is passed all unwinds currently in progress.

// ctx=NULL means filter is global.

void unwind_trans_filter(unwind_ctx ctx, void (*filter)(size_t no, unwind_ctx *ctxs, size_t idx, void *data), void *data);

// Loads and stores

template<typename T> T unwind_trans_load_explicit(unwind_ctx ctx, volatile T* obj, memory_order order);

template<typename T> void unwind_trans_store_explicit(unwind_ctx ctx, volatile T* obj, T desired, memory_order order);

// These equal the explicit forms with order=memory_order_relaxed

template<typename T> T unwind_trans_load(unwind_ctx ctx, volatile T* obj);

template<typename T> void unwind_trans_store(unwind_ctx ctx, volatile T* obj, T desired);

// Exchanges ...

template<typename T> T unwind_trans_exchange_explicit(unwind_ctx ctx, volatile T* obj, T desr, memory_order order);

// API continues duplicating the C11 atomic API but where non-explicit functions default to memory_order_relaxed

...

In other words, the absolute minimum C API possible for coping with TM and stack unwinding TM. On HTM capable hardware, the compiler generates the appropriate HTM instructions. Without HTM capable hardware, support is emulated. The stack unwinding stuff basically opens the existing compiler's stack unwinding machinery to programmer control. The above enables TM availability to both C and C++ code, with HTM acceleration where available, in a completely non-threatening and non-intrusive way.

I appreciate that this proposal may appear to propose undoing everything everyone on this SG has worked towards for a decade or more. I don't wish it to mean that: I wish to start from the opposite end of where TM support in compilers has traditionally began. Somewhere in between these bottom up and top down approaches will be likely something both acceptable to the core C++ committee and a good foundation version 1 of TM support used for building version 2. This post is purely to invite discussion - not as a viable actual alternative.

Niall

[Zhihao Yuan]

On Tue, May 21, 2013 at 4:35 PM, Niall Douglas <ndougl...@gmail.com> wrote:
> standardised TM support into the standard. Call it "TM lite" in a nod to
> "Concepts Lite":

You can call it "Low-level TM".

... while what we want is a language support. Some optional parts can
be implemented in libraries.

BTW, "Lite" is a missing leading postfix to me after I found "Concept-lite"
is a broken "Concept" and essentially a better "static if".

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

[Niall Douglas]

On Tuesday, May 21, 2013 4:50:47 PM UTC-4, Zhihao Yuan wrote:

On Tue, May 21, 2013 at 4:35 PM, Niall Douglas <ndougl...@gmail.com> wrote:
> standardised TM support into the standard. Call it "TM lite" in a nod to
> "Concepts Lite":

You can call it "Low-level TM".

... while what we want is a language support.  Some optional parts can
be implemented in libraries.

It's far easier to change a standard library than a standard language feature. And for good reason: libraries can be replaced without standards change.

 

BTW, "Lite" is a missing leading postfix to me after I found "Concept-lite"
is a broken "Concept" and essentially a better "static if".

We actually met at C++ Now Zhihao, though you may not remember me!

Andrew's approach to Concepts is not without its problems, as Andrew will tell you himself. But we live in a practical world: Andrew asked what's possible now rather than what's desirable (later after much lengthy debate). And if even static if isn't possible due to lack of consensus, you can see what standards formers are facing. Meanwhile, any developers using metaprogrammed libraries today waste tens of thousands of man hours, which adds up to billions of dollars of lost productivity. Andrew's proposal could halve that cost. For that alone, it is worth it.

We work with the hand we're dealt. That includes TM as well: consensus must be found, and that often means a huge amount of compromise, indeed throwing away decades of exploratory work. Such is ISO standards.

Niall

[Nevin Liber]

On 22 May 2013 10:56, Niall Douglas <ndougl...@gmail.com> wrote:

It's far easier to change a standard library than a standard language feature.

Is it?  While developers can opt to use a different library, I don't see anything about the standards process which makes changing the existing standard library any easier (let alone far easier) than a language feature.

--
 Nevin ":-)" Liber  <mailto:ne...@eviloverlord.com>  (847) 691-1404

[Zhihao Yuan]

On Wed, May 22, 2013 at 11:56 AM, Niall Douglas <ndougl...@gmail.com> wrote:
> It's far easier to change a standard library than a standard language
> feature. And for good reason: libraries can be replaced without standards
> change.

I pretty much sure you don't want to write __cxa_throw instead of
a `throw` keyword, or write a __cxa_begin_catch... __cxa_end_catch
pair instead of a `catch` block. For the same reason, begin_trans...
commit_trans... make my eyes bleeding.

> We actually met at C++ Now Zhihao, though you may not remember me!

I have to say sorry since I can't pair the people and their names unless
we meet more than... 3 times.

> Andrew's approach to Concepts is not without its problems, as Andrew will
> tell you himself. But we live in a practical world: Andrew asked what's
> possible now rather than what's desirable (later after much lengthy debate).
> And if even static if isn't possible due to lack of consensus, you can see
> what standards formers are facing. Meanwhile, any developers using
> metaprogrammed libraries today waste tens of thousands of man hours, which
> adds up to billions of dollars of lost productivity. Andrew's proposal could
> halve that cost. For that alone, it is worth it.

I suppose you know "concept-lite" only works on syntax level. It's nothing
but a set of macros which can do conjunction and disjunction. C++ has *no*
feature only works on the syntax level other than the __cplusplus macro.

> We work with the hand we're dealt. That includes TM as well: consensus must
> be found, and that often means a huge amount of compromise, indeed throwing
> away decades of exploratory work. Such is ISO standards.

If a library solution works, it's considerable; however, I want to
point out that your solution does not work -- transactions can
not be composed (one embedded into another), since the
unwind_ctx is explicit.

[Niall Douglas]

Yes it is easier, in fact considerably so. There is an additional track for library changes allowing it to evolve a lot quicker (the TR process). Boost lets you implement an alternative library and if it gains widespread acceptance then a subsequent TR can and does merge those Boost changes into the libc++. Typical times for library changes are about five years, as against more than ten years for language changes. It's also the case that changing compilers is vastly harder than changing libraries.

One of the informally discussed topics at C++ Now was that we're going to have to break existing futures and promises, because C++11 made some mistakes not obvious at the time. The fix, while difficult because of the code that may break, is doable.

Niall

[Nevin Liber]

On 22 May 2013 12:52, Niall Douglas <ndougl...@gmail.com> wrote:

One of the informally discussed topics at C++ Now was that we're going to have to break existing futures and promises, because C++11 made some mistakes not obvious at the time. The fix, while difficult because of the code that may break, is doable.

We'll see.  That particular discussion has been raging on well past the Bristol meeting, and a CD is not the same as a standard...

[Niall Douglas]

On Wednesday, May 22, 2013 12:12:00 PM UTC-4, Zhihao Yuan wrote:

On Wed, May 22, 2013 at 11:56 AM, Niall Douglas <ndougl...@gmail.com> wrote:
> It's far easier to change a standard library than a standard language
> feature. And for good reason: libraries can be replaced without standards
> change.

I pretty much sure you don't want to write __cxa_throw instead of
a `throw` keyword, or write a __cxa_begin_catch... __cxa_end_catch
pair instead of a `catch` block.  For the same reason, begin_trans...
commit_trans... make my eyes bleeding.

No one is proposing that anyone use the API I posted directly. It would almost certainly be wrapped in C++ RAII utility classes etc.

 

> Andrew's approach to Concepts is not without its problems, as Andrew will
> tell you himself. But we live in a practical world: Andrew asked what's
> possible now rather than what's desirable (later after much lengthy debate).
> And if even static if isn't possible due to lack of consensus, you can see
> what standards formers are facing. Meanwhile, any developers using
> metaprogrammed libraries today waste tens of thousands of man hours, which
> adds up to billions of dollars of lost productivity. Andrew's proposal could
> halve that cost. For that alone, it is worth it.

I suppose you know "concept-lite" only works on syntax level.  It's nothing
but a set of macros which can do conjunction and disjunction.  C++ has *no*
feature only works on the syntax level other than the __cplusplus macro.

Sure, though there is a theorem prover in there too. I don't want to get into concepts in SG5 though.

 

> We work with the hand we're dealt. That includes TM as well: consensus must
> be found, and that often means a huge amount of compromise, indeed throwing
> away decades of exploratory work. Such is ISO standards.

If a library solution works, it's considerable; however, I want to
point out that your solution does not work -- transactions can
not be composed (one embedded into another), since the
unwind_ctx is explicit.

What I proposed was literally off the cuff to test the waters. If there is significant interest from this SG, I might attempt an example implementation based on Haswell TSX and C preprocessor macro magic. You're right that composibility is essential, and I didn't complete that part.

Niall

[Zhihao Yuan]

On Wed, May 22, 2013 at 1:58 PM, Niall Douglas <ndougl...@gmail.com> wrote:
> No one is proposing that anyone use the API I posted directly. It would
> almost certainly be wrapped in C++ RAII utility classes etc.

If the things you showed are underlying APIs, then they are
already there:

http://gcc.gnu.org/wiki/TransactionalMemory?action=AttachFile&do=view&target=Intel-TM-ABI-1_1_20060506.pdf

I'd like to see the interface you want, or the users want, based
on your suspect.

> What I proposed was literally off the cuff to test the waters. If there is
> significant interest from this SG, I might attempt an example implementation
> based on Haswell TSX and C preprocessor macro magic. You're right that
> composibility is essential, and I didn't complete that part.

There is no need to test, and SG is not a river in front of you. Just FYI:
C++ does not accept macro solutions, since the need of a macro always
implies a need of a language feature.

[Ville Voutilainen]

On 22 May 2013 20:52, Niall Douglas <ndougl...@gmail.com> wrote:

Yes it is easier, in fact considerably so. There is an additional track for library changes allowing it to evolve a lot quicker (the TR process). Boost lets you implement an alternative library and if it gains widespread acceptance then a subsequent TR can and does merge those Boost changes into the libc++. Typical times for library changes are about five years, as against more than ten years for language changes. It's also the case that changing compilers is vastly harder than changing libraries.

I fail to see what's typical in these numbers, when the language changes in c++11 didn't take ten years, and
when some language changes seem well on track to happen between c++11 and c++14, while some library
changes didn't make it in that timespan, despite being in boost for over a decade.

[Jens Maurer]

Thanks for your comments.

On 05/21/2013 10:35 PM, Niall Douglas wrote:
> after Michael's talk, I
> heard a number of people on the core committee informally express
> very similar worries to mine about the potential of the current
> proposal to break existing code.

Could you clarify what you mean by "core committee"? Do you mean WG21
or do you mean the core language sub-group of WG21? Neither of which
has been exposed to TM (as a group), yet, so it's rather hard to predict
their opinions.

Then, I'm really surprised to hear that the mere presence of TM
support in the compiler would be suspect of breaking existing code.
Given our (current) choice of double-underscore keywords, is
there anything a bit more detailed (such as an example) that you
could relate?

> Whether these are unfounded or not

> isn't the important part: /the important part is getting TM into
> C++/, not some particular implementation of TM into C++. And right
> now the current proposal /appears /too complex to give peace of mind

> to a lot of folk.

Noted. Some of this might be fear of the unknown, though.

> So, given this, here is my alternative minimal *initial *proposal for

> TM support in C++. I stress the "initial" part: We start with this
> and add stuff. I can guarantee everyone on this SG will hate it, but
> I think it's worth bringing up for discussion as an alternative route
> to getting standardised TM support into the standard. Call it "TM
> lite" in a nod to "Concepts Lite":
>
> // transaction context is opaque compiler-internal type
> typedef void *trans_ctx;
> // unwind context is opaque compiler-internal type
> typedef void *unwind_ctx;
>
> // Start a transaction. Can be called many times. Can return NULL if ENOMEM (or HTM has run out of free contexts).
> trans_ctx begin_trans();
>
> // Makes the transaction visible if possible, returning false if not possible. Deletes ctx if successful.
> _Bool commit_trans(trans_ctx ctx);
>
> // Deletes ctx
> void abort_trans(trans_ctx ctx);
>
> // Loads and stores
> template<typename T> T trans_load_explicit(trans_ctx ctx, volatile T* obj, memory_order order);
> template<typename T> void trans_store_explicit(trans_ctx ctx, volatile T* obj, T desired, memory_order order);

What's the "volatile" doing here? It shouldn't be there (also below).

> // These equal the explicit forms with order=memory_order_relaxed
> template<typename T> T trans_load(trans_ctx ctx, volatile T* obj);
> template<typename T> void trans_store(trans_ctx ctx, volatile T* obj, T desired);

So, how does the memory order given here interact with 1.10? These are not atomic
variables, so they don't plug into 1.10 as-is.

> // Exchanges ...
> template<typename T> T trans_exchange_explicit(trans_ctx ctx, volatile T* obj, T desr, memory_order order);
>
> // API continues duplicating the C11 atomic API but where non-explicit functions default to memory_order_relaxed

I'd presume we'd make trans_ctx a C++ class so that we can make these member
functions, right?

> // Create a stack unwind transaction for this execution context (i.e. curly braces). Can be called many times. Can return NULL if insufficient stack space.
> unwind_ctx begin_unwind_trans();

> // Registers an unwind transaction to occur when the specified execution context exits.
> void commit_unwind_trans(unwind_ctx ctx);
>
> // Unregisters a previously registered unwind transaction.
> void abort_unwind_trans(unwind_ctx ctx);
>
> // Add a filtering callback. Gets called when ANY unwind passes through ctx. Callback is passed all unwinds currently in progress.
> // ctx=NULL means filter is global.
> void unwind_trans_filter(unwind_ctx ctx, void (*filter)(size_t no, unwind_ctx *ctxs, size_t idx, void *data), void *data);
>
> // Loads and stores
> template<typename T> T unwind_trans_load_explicit(unwind_ctx ctx, volatile T* obj, memory_order order);
> template<typename T> void unwind_trans_store_explicit(unwind_ctx ctx, volatile T* obj, T desired, memory_order order);
>
> // These equal the explicit forms with order=memory_order_relaxed
> template<typename T> T unwind_trans_load(unwind_ctx ctx, volatile T* obj);
> template<typename T> void unwind_trans_store(unwind_ctx ctx, volatile T* obj, T desired);
>
> // Exchanges ...
> template<typename T> T unwind_trans_exchange_explicit(unwind_ctx ctx, volatile T* obj, T desr, memory_order order);
>
> // API continues duplicating the C11 atomic API but where non-explicit functions default to memory_order_relaxed
> ...

I'm sorry, I don't know what this unwinding stuff is supposed to do.

> In other words, the absolute minimum C API possible for coping with
> TM and stack unwinding TM. On HTM capable hardware, the compiler
> generates the appropriate HTM instructions. Without HTM capable
> hardware, support is emulated. The stack unwinding stuff basically
> opens the existing compiler's stack unwinding machinery to programmer
> control. The above enables TM availability to both C and C++ code,
> with HTM acceleration where available, in a completely
> non-threatening and non-intrusive way.

I'm sure there are software transactional memory implementations out there
that provide an explicit function call interface similar to the one you
proposed above (minus the unwinding part).

- This not easy to use. The compiler should be able to do the instrumentation.

- This interface allows arbitrary non-transactional memory accesses between
transactional ones. As far as I understand, that's not what HTM supports,
where ALL memory accesses after "tx begin" are transactional, until "tx commit"
is reached.

Jens

[Torvald Riegel]

On Wed, 2013-05-22 at 21:58 +0200, Jens Maurer wrote:
> > In other words, the absolute minimum C API possible for coping with
> > TM and stack unwinding TM. On HTM capable hardware, the compiler
> > generates the appropriate HTM instructions. Without HTM capable
> > hardware, support is emulated. The stack unwinding stuff basically
> > opens the existing compiler's stack unwinding machinery to programmer
> > control. The above enables TM availability to both C and C++ code,
> > with HTM acceleration where available, in a completely
> > non-threatening and non-intrusive way.
>
> I'm sure there are software transactional memory implementations out there
> that provide an explicit function call interface similar to the one you
> proposed above (minus the unwinding part).
>
> - This not easy to use. The compiler should be able to do the instrumentation.
>
> - This interface allows arbitrary non-transactional memory accesses between
> transactional ones. As far as I understand, that's not what HTM supports,
> where ALL memory accesses after "tx begin" are transactional, until "tx commit"
> is reached.

This depends on the HTM, but you are right that users shouldn't expect
the HTM to support nontransactional accesses. In particular, what you
describe cannot guarantee atomicity at compile time, because users could
always use this like a relaxed transaction.

IMO, a library-interface really is a non-starter. We've discussed this
in prior threads already, so I'm not going to repeat all points raised
in that discussion. Please have a look at the archives.

[Justin Gottschlich]

I agree with Torvald. Several of us have spent quite some time (years+) exploring building an STM using a library-only approach. I personally worked with the Boost community for a few years trying to make TBoost.STM viable. If I am recalling correctly, all of the folks that I've spoken to who have spent significant time looking into this have come to the same conclusion; that is, we simply cannot support the fundamental goal of programming simplicity, which is a key tenet of TM, while still fulfilling all the necessary correctness criteria needed for transactions from such a library-only approach.

 

You may want to look at Dalessandro et al.'s TRANSACT paper from 2007 for starters (http://www.cs.rochester.edu/u/scott/papers/2007_TRANSACT_RSTM2.pdf).

 

Just to be clear, I'm not saying that you cannot build an STM from a library-only approach. Certainly that can be done.

 

Best,

Justin

 

 

 

--
You received this message because you are subscribed to the Google Groups "SG5 - Transactional Memory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tm+unsu...@isocpp.org.
To post to this group, send email to t...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/tm/?hl=en.

[Torvald Riegel]

On Wed, 2013-05-22 at 22:16 +0200, Torvald Riegel wrote:
> On Wed, 2013-05-22 at 21:58 +0200, Jens Maurer wrote:
> > > In other words, the absolute minimum C API possible for coping with
> > > TM and stack unwinding TM. On HTM capable hardware, the compiler
> > > generates the appropriate HTM instructions. Without HTM capable
> > > hardware, support is emulated. The stack unwinding stuff basically
> > > opens the existing compiler's stack unwinding machinery to programmer
> > > control. The above enables TM availability to both C and C++ code,
> > > with HTM acceleration where available, in a completely
> > > non-threatening and non-intrusive way.
> >
> > I'm sure there are software transactional memory implementations out there
> > that provide an explicit function call interface similar to the one you
> > proposed above (minus the unwinding part).
> >
> > - This not easy to use. The compiler should be able to do the instrumentation.
> >
> > - This interface allows arbitrary non-transactional memory accesses between
> > transactional ones. As far as I understand, that's not what HTM supports,
> > where ALL memory accesses after "tx begin" are transactional, until "tx commit"
> > is reached.
>
> This depends on the HTM, but you are right that users shouldn't expect
> the HTM to support nontransactional accesses. In particular, what you
> describe cannot guarantee atomicity at compile time, because users could
> always use this like a relaxed transaction.

To clarify: "you" in this sentence was meant to refer to Niall, not
Jens.

[Niall Douglas]

On Wednesday, May 22, 2013 2:37:12 PM UTC-4, Zhihao Yuan wrote:

On Wed, May 22, 2013 at 1:58 PM, Niall Douglas <ndougl...@gmail.com> wrote:
> No one is proposing that anyone use the API I posted directly. It would
> almost certainly be wrapped in C++ RAII utility classes etc.

If the things you showed are underlying APIs, then they are
already there:

  http://gcc.gnu.org/wiki/TransactionalMemory?action=AttachFile&do=view&target=Intel-TM-ABI-1_1_20060506.pdf

I'd like to see the interface you want, or the users want, based
on your suspect.

That is an interesting document, but it requires use of TLS on Linux plus a runtime. It also doesn't cope with unwind. What I proposed is literally opening up the direct programming of an aspect of how the compiler generates code e.g. like alloca(). Nothing more, as no runtime is needed.

 

There is no need to test, and SG is not a river in front of you.  Just FYI:
C++ does not accept macro solutions, since the need of a macro always
implies a need of a language feature.

 

The proposed API is intentionally C only for C <=> C++ interop. If you look into how C11 atomics are implemented, they are implemented as "magic macros" because of the need to accept arbitrary integral types. Hence the macro-like proposed API.

Niall

[Niall Douglas]

C++14 isn't released yet. My comment was based on achieved history till today. N

[Niall Douglas]

On Wednesday, May 22, 2013 3:58:05 PM UTC-4, Jens Maurer wrote:

On 05/21/2013 10:35 PM, Niall Douglas wrote:
>   after Michael's talk, I
> heard a number of people on the core committee informally express
> very similar worries to mine about the potential of the current
> proposal to break existing code.

Then, I'm really surprised to hear that the mere presence of TM
support in the compiler would be suspect of breaking existing code.
Given our (current) choice of double-underscore keywords, is
there anything a bit more detailed (such as an example) that you
could relate?

There appear to be changes to control flow, overload resolution, the type system, symbol mangling and the memory model, any one of which is enough to bring in significant hesitation. Also nothing is obvious about how TM enabled C++ interops with C other than calling C anything auto-aborts any TM. I'm not saying any of these are actually true, just it comes across initially as so.

>   Whether these are unfounded or not
> isn't the important part: /the important part is getting TM into
> C++/, not some particular implementation of TM into C++. And right
> now the current proposal /appears /too complex to give peace of mind
> to a lot of folk.

Noted.  Some of this might be fear of the unknown, though.

Absolutely.

> So, given this, here is my alternative minimal *initial *proposal for
> TM support in C++. I stress the "initial" part: We start with this
> and add stuff. I can guarantee everyone on this SG will hate it, but
> I think it's worth bringing up for discussion as an alternative route
> to getting standardised TM support into the standard. Call it "TM
> lite" in a nod to "Concepts Lite":
>
> // transaction context is opaque compiler-internal type
> typedef void *trans_ctx;
> // unwind context is opaque compiler-internal type
> typedef void *unwind_ctx;
>
> // Start a transaction. Can be called many times. Can return NULL if ENOMEM (or HTM has run out of free contexts).
> trans_ctx begin_trans();
>
> // Makes the transaction visible if possible, returning false if not possible. Deletes ctx if successful.
> _Bool commit_trans(trans_ctx ctx);
>
> // Deletes ctx
> void abort_trans(trans_ctx ctx);
>
> // Loads and stores
> template<typename T> T trans_load_explicit(trans_ctx ctx, volatile T* obj, memory_order order);
> template<typename T> void trans_store_explicit(trans_ctx ctx, volatile T* obj, T desired, memory_order order);

What's the "volatile" doing here?  It shouldn't be there (also below).

It duplicates the C11 atomic API exactly.

> // These equal the explicit forms with order=memory_order_relaxed
> template<typename T> T trans_load(trans_ctx ctx, volatile T* obj);
> template<typename T> void trans_store(trans_ctx ctx, volatile T* obj, T desired);

So, how does the memory order given here interact with 1.10?  These are not atomic
variables, so they don't plug into 1.10 as-is.

They *are* atomic variables :). Just with the non-explicit variant defaulting to relaxed.

 

> // Exchanges ...
> template<typename T> T trans_exchange_explicit(trans_ctx ctx, volatile T* obj, T desr, memory_order order);
>
> // API continues duplicating the C11 atomic API but where non-explicit functions default to memory_order_relaxed

I'd presume we'd make trans_ctx a C++ class so that we can make these member
functions, right?

Nope. trans_ctx doesn't exist except as a convenience to the programmer. The compiler simply treats them as an accumulation handle, so as you do "load, store, load" that gets tracked by the compiler as building what that transaction pseudo-handle will do on commit.

Think of the proposed API as 100% compiler intrinsics. trans_ctx only comes into being if it gets passed to a function or stored somewhere in global storage, and then it takes on the form of a pointer to a function.

 

> // Create a stack unwind transaction for this execution context (i.e. curly braces). Can be called many times. Can return NULL if insufficient stack space.
> unwind_ctx begin_unwind_trans();

> // Registers an unwind transaction to occur when the specified execution context exits.
> void commit_unwind_trans(unwind_ctx ctx);
>
> // Unregisters a previously registered unwind transaction.
> void abort_unwind_trans(unwind_ctx ctx);
>
> // Add a filtering callback. Gets called when ANY unwind passes through ctx. Callback is passed all unwinds currently in progress.
> // ctx=NULL means filter is global.
> void unwind_trans_filter(unwind_ctx ctx, void (*filter)(size_t no, unwind_ctx *ctxs, size_t idx, void *data), void *data);
>
> // Loads and stores
> template<typename T> T unwind_trans_load_explicit(unwind_ctx ctx, volatile T* obj, memory_order order);
> template<typename T> void unwind_trans_store_explicit(unwind_ctx ctx, volatile T* obj, T desired, memory_order order);
>
> // These equal the explicit forms with order=memory_order_relaxed
> template<typename T> T unwind_trans_load(unwind_ctx ctx, volatile T* obj);
> template<typename T> void unwind_trans_store(unwind_ctx ctx, volatile T* obj, T desired);
>
> // Exchanges ...
> template<typename T> T unwind_trans_exchange_explicit(unwind_ctx ctx, volatile T* obj, T desr, memory_order order);
>
> // API continues duplicating the C11 atomic API but where non-explicit functions default to memory_order_relaxed
> ...

I'm sorry, I don't know what this unwinding stuff is supposed to do.

You may remember my earlier discussion that I believe TM to be primarily a control flow issue, not a memory model issue. The ability to program the compiler's unwind machinery is absolutely essential to implementing abortable transactions of any kind.

> In other words, the absolute minimum C API possible for coping with
> TM and stack unwinding TM. On HTM capable hardware, the compiler
> generates the appropriate HTM instructions. Without HTM capable
> hardware, support is emulated. The stack unwinding stuff basically
> opens the existing compiler's stack unwinding machinery to programmer
> control. The above enables TM availability to both C and C++ code,
> with HTM acceleration where available, in a completely
> non-threatening and non-intrusive way.

I'm sure there are software transactional memory implementations out there
that provide an explicit function call interface similar to the one you
proposed above (minus the unwinding part).

My proposal is not a library. It's a C API for telling the compiler how to compile code.

 

 - This not easy to use.  The compiler should be able to do the instrumentation.

 - This interface allows arbitrary non-transactional memory accesses between
transactional ones.  As far as I understand, that's not what HTM supports,
where ALL memory accesses after "tx begin" are transactional, until "tx commit"
is reached.

 I think you misunderstood what I propose (my fault). If I do:

int dest=1, src=4, foo=5;

trans_ctx h=begin_trans();

trans_store(h, &dest, foo+trans_load(h, &src));

src=2;

foo=10;

assert(dest==1); // works

if(trans_commit(h)) // make everything written to by trans_ctx visible atomically

  assert(dest==12); // works

In other words you *cannot* interleave non-transactional and transactional accesses. trans_ctx is simply to tell the compiler to compile any code working on the trans_ctx into a separate block of code whose effects on memory are to be made visible atomically. In the above case, the direct load of foo in the trans_store() gets converted by the compiler into an implicit trans_load(h, &foo).

In other words, think of trans_ctx operations as being like a lambda. begin_trans() starts the lambda. trans_*() functions write what the lambda will do. trans_commit() calls the lambda.

I agree that use of the C11 atomics API severely limits what you can do inside a transaction e.g. no branch logic. That is deliberate: the API is intended to force programmers to work in small, chainable, unwindable atomic chunks of memory effect. As I mentioned before, no one is proposing that programmers use this API directly. And as I also mentioned before, I'm not aiming for feature parity, I want the most useful 80% of what TM can provide, which for me is mainly multi-CAS and multi-atomics.

Niall

[Niall Douglas]

I am not proposing a library interface. I am proposing a C API for programming the compiler to generate TM code. Niall

[Zhihao Yuan]

On Thu, May 23, 2013 at 12:14 PM, Niall Douglas <ndougl...@gmail.com> wrote:
> I am not proposing a library interface. I am proposing a C API for
> programming the compiler to generate TM code. Niall

Then pls contact WG14.

[Zhihao Yuan]

On Thu, May 23, 2013 at 11:41 AM, Niall Douglas <ndougl...@gmail.com> wrote:
> That is an interesting document, but it requires use of TLS on Linux plus a
> runtime. It also doesn't cope with unwind. What I proposed is literally
> opening up the direct programming of an aspect of how the compiler generates
> code e.g. like alloca(). Nothing more, as no runtime is needed.

TLS is part of C11, as _Thread_local, so it's not an issue.
Unwinding does exist in C, so C must not say anything
about it. Maybe we want a new set of __cxa_* APIs for TM,
but that's not WG14 nor WG21's job... Same as alloca(),
which is a POSIX API -- it's not our job to define it.

>> C++ does not accept macro solutions, since the need of a macro always
>> implies a need of a language feature.
>
> The proposed API is intentionally C only for C <=> C++ interop. If you look
> into how C11 atomics are implemented, they are implemented as "magic macros"
> because of the need to accept arbitrary integral types. Hence the macro-like
> proposed API.

Since you used template, C can not use the API.
Sorry I truly don't know how to give your suggestions...

Which language your API is targeting?

[Victor Luchangco]

Hi Niall,

Thanks for your feedback. I agree we need to think about what we really need to include in the proposal, and omit--at least for now--extraneous features. But it's also important to keep in mind what our goals are, so that we don't throw out features important to these goals.

I think Zhihao's initial response sums up my reaction as well:

> You can call it "Low-level TM".
>
> ... while what we want is a language support. Some optional parts can
> be implemented in libraries.

To limit the scope of this discussion, I want to clarify that I think your proposal covers only the part of the proposal related to *atomic* transactions, not relaxed ones. (Semantically, in the absence of atomic transactions, relaxed transactions are equivalent to critical sections guarded by a single global lock.) Please correct me if I am misunderstanding you on this point.

Even for atomic transactions, here is not a single goal, but among the goals are to provide a simpler, more effective mechanism than locks and atomic variables for synchronization in concurrent C++ programs and to exploit hardware features (i.e., hardware TM) we expect in some future processors. Transactional constructs in C++ are, we believe, a *means* to such goals, not the goal itself.

On May 23, 2013, at 12:13 PM, Niall Douglas wrote:

> On Wednesday, May 22, 2013 3:58:05 PM UTC-4, Jens Maurer wrote:
>
>> On 05/21/2013 10:35 PM, Niall Douglas wrote:
>> > after Michael's talk, I
>> > heard a number of people on the core committee informally express
>> > very similar worries to mine about the potential of the current
>> > proposal to break existing code.
>>
>> Then, I'm really surprised to hear that the mere presence of TM
>> support in the compiler would be suspect of breaking existing code.
>> Given our (current) choice of double-underscore keywords, is
>> there anything a bit more detailed (such as an example) that you
>> could relate?

> There appear to be changes to control flow, overload resolution, the type system, symbol mangling and the memory model, any one of which is enough to bring in significant hesitation. Also nothing is obvious about how TM enabled C++ interops with C other than calling C anything auto-aborts any TM. I'm not saying any of these are actually true, just it comes across initially as so.

It is our intention that, in the absence of transactions, there should be no change to the semantics. The memory model changes, for example, are expressed using new evaluations corresponding to the beginning and end of transactions. If there are no transactions, then none of the orderings change. (If this is not true, then there is some mistake, and we should fix it.) Similarly, overload resolution should be affected only for calls made within atomic transactions. And, although we are proposing a change to the type system, this is only to distinguish transaction-safe and transaction-unsafe functions. Code that is not transaction-aware need not concern itself with this distinction. (If anyone disagrees with these claims, please say so.)

Thanks for this clarifying example. I did not know that this was the semantics you intended--indeed, I didn't know what semantics you intended. I'm curious though about why the direct load of foo should be converted to an implicit trans_load. If so, why put the trans_load explicitly for src? Why have two ways to say the same thing? And when would such an implicit conversion take place? For example, what if there is a function call within the third argument expression to trans_store? What if that function does I/O?

As others have mentioned, many of us have thought for a long time about support for transactional constructs in concurrent programming, both semantic and linguistic issues (i.e., how to make it usable) and implementation issues, including support on systems that may or may not support hardware TM. We would have liked a solution--at least temporarily--that did not require linguistic support, but found such to be cumbersome to use, enough to discourage use and induce error when used. (See, for example, case studies done by Pankratius and Adl-Tabatabai and by Rossbach et al.)

> I agree that use of the C11 atomics API severely limits what you can do inside a transaction e.g. no branch logic. That is deliberate: the API is intended to force programmers to work in small, chainable, unwindable atomic chunks of memory effect. As I mentioned before, no one is proposing that programmers use this API directly. And as I also mentioned before, I'm not aiming for feature parity, I want the most useful 80% of what TM can provide, which for me is mainly multi-CAS and multi-atomics.

My worry is that this does not provide the "most useful 80%". In terms of mere *functionality*, it may, but the perceived value of a feature must exceed the (perceived) difficulty in learning and using it. The interface you describe seems to me to be more difficult to learn and use, and provide less functionality. It may be less difficult to implement, but I think it's worth trying. Furthermore, note that we are proposing a TS. We do not expect to get everything right the first time, and indeed, various people working on this have different ideas about what (if anything) should ultimately be included into C++ (i.e., not merely in a TS), but I think we all agree that we need more feedback from real people trying to use transactional constructs to draw any meaningful conclusions. That is why we are proposing this TS, and also guides our choices in deciding what to include.

- Victor

>
> Niall

[Michael L. Scott]

On May 22, 2013, at 3:58 PM, Jens Maurer wrote:

> Thanks for your comments.
>
> On 05/21/2013 10:35 PM, Niall Douglas wrote:
>>

>> [snip]

>>
>> In other words, the absolute minimum C API possible for coping with
>> TM and stack unwinding TM. On HTM capable hardware, the compiler
>> generates the appropriate HTM instructions. Without HTM capable
>> hardware, support is emulated. The stack unwinding stuff basically
>> opens the existing compiler's stack unwinding machinery to programmer
>> control. The above enables TM availability to both C and C++ code,
>> with HTM acceleration where available, in a completely
>> non-threatening and non-intrusive way.
>
> I'm sure there are software transactional memory implementations out there
> that provide an explicit function call interface similar to the one you
> proposed above (minus the unwinding part).
>
> - This not easy to use. The compiler should be able to do the instrumentation.
>
> - This interface allows arbitrary non-transactional memory accesses between
> transactional ones. As far as I understand, that's not what HTM supports,
> where ALL memory accesses after "tx begin" are transactional, until "tx commit"
> is reached.

Absolutely. We have a decade of experience with library-level TM implementations.
I was initially very optimistic about them. I became convinced that they're untenable.
TM is inherently a language-level mechanism. It needs non-fn-call syntax and extensive
complier support. For one example of a paper addressing these issues, see our (rather
old now) paper at TRANSACT'07: http://www.cs.rochester.edu/u/scott/papers/2007_TRANSACT_RSTM2.pdf

- Michael

[Torvald Riegel]

On Thu, 2013-05-23 at 09:13 -0700, Niall Douglas wrote:
> On Wednesday, May 22, 2013 3:58:05 PM UTC-4, Jens Maurer wrote:
> On 05/21/2013 10:35 PM, Niall Douglas wrote:
> > after Michael's talk, I
> > heard a number of people on the core committee informally
> express
> > very similar worries to mine about the potential of the
> current
> > proposal to break existing code.
>
> Then, I'm really surprised to hear that the mere presence of
> TM
> support in the compiler would be suspect of breaking existing
> code.
> Given our (current) choice of double-underscore keywords, is
> there anything a bit more detailed (such as an example) that
> you
> could relate?
>
>
> There appear to be changes to control flow

Without cancellation, there are no changes. Abort and restart is an
implementation-level thing.

> , overload resolution, the type system,

True, the transaction_safe property becomes part of types.

> symbol mangling

That's implementation-internal, so no change as far as the language is
concerned. Users don't see this.

> and the memory model,

The memory model is extended, but not changed. This doesn't even affect
how a compiler(/runtime) would implement the current memory model (note
that we don't treat atomics as transaction_safe).

> any one of which is enough to bring in significant hesitation. Also
> nothing is obvious about how TM enabled C++ interops with C other than
> calling C anything auto-aborts any TM.

I don't understand this sentence.

Atomic operations are not transaction_safe. They are supposed to be a
single atomic thing that doesn't give the guarantee of extending the
atomicity guarantee to anything else (ie, you can't just merge two
atomic accesses). Transactions do give those guarantees. It's not the
same thing.

So it's directives for the compiler expresses through a library
interface. And because it's not supposed to be a library, it must
conceptually be a language-level feature, right? So, in the end, you're
trying to express a language-level feature by telling the compiler about
it with a library-level interface?

So the compiler has to do the same that it has to do with
__transaction_atomic, just that we're requiring users to use a much less
compact interface? And we change the (language-level) semantics of the
code between begin and end? I don't see any benefit to a clean
language-level construct. This makes it harder for a compiler to figure
out when a transaction ends, and which code has to be instrumented.
It's easier for programmers to make a mistake with this interface. And
we have the same or even more changes to semantics you were worrying
about.

>
> In other words, think of trans_ctx operations as being like a lambda.
> begin_trans() starts the lambda. trans_*() functions write what the
> lambda will do. trans_commit() calls the lambda.

But you said that the compiler converts foo=10 into a trans_store(). So
there's more than just setting up a static transaction. If it really
were like a lambda, why not use a lambda right away but design a very
similar feature?

>
> I agree that use of the C11 atomics API severely limits what you can
> do inside a transaction e.g. no branch logic. That is deliberate: the
> API is intended to force programmers to work in small, chainable,
> unwindable atomic chunks of memory effect. As I mentioned before, no
> one is proposing that programmers use this API directly.

So who would be the actual target audience of this API, if it isn't C++
programmers?

> And as I also mentioned before, I'm not aiming for feature parity, I
> want the most useful 80% of what TM can provide, which for me is
> mainly multi-CAS and multi-atomics.

If that's what you're interested it, why not just work on a clean API
for atomic operations on multi-memory locations (e.g., mCAS, atomic
snapshots, ...)? Or call them static transactions, if you like (static
in the sense of which accesses and which operational semantics (from a
fixed set of semantics such as CAS)). Those could perhaps even be
considered independently of TM, although they should likely be able to
synchronize with transactions as specified by SG5. Define the precise
semantics wrt. the memory model, and propose this API to C++ SG1/SG5.

IMO, and I guess for most here, TM is about transactions that can access
any memory locations, don't have to declare which they are going to
access up-front at the start of a transaction, and allow programmers to
express any kind of operational semantics using transactions (eg, do
branch). Of course we'll have some restrictions as only allowing
transaction_safe code in atomic transactions, but the goal is to not try
to come up with a general mechanism. Which is another reason why it
will probably be cleaner as a language construct than a library.

[Zhihao Yuan]

On Fri, May 24, 2013 at 6:06 AM, Torvald Riegel <tri...@redhat.com> wrote:
>> , overload resolution, the type system,
>
> True, the transaction_safe property becomes part of types.

I don't want to repeat this, but... Please don't. Just starts
with the `txunsafe` specification, like `noexcept`.
We don't need `txunsafe( const-expr )` and
`txunsafe( expr )` in the first round. Just the keyword alone.

[Niall Douglas]

On Thursday, May 23, 2013 12:46:56 PM UTC-4, Zhihao Yuan wrote:

TLS is part of C11, as _Thread_local, so it's not an issue.
Unwinding does exist in C, so C must not say anything
about it.  Maybe we want a new set of __cxa_* APIs for TM,
but that's not WG14 nor WG21's job...  Same as alloca(),
which is a POSIX API -- it's not our job to define it.

I think you need to reread what I wrote much more closely before jumping to conclusions. Nothing I mentioned has anything to do with WG14 nor POSIX.

Niall 

[Niall Douglas]

On Thursday, May 23, 2013 2:18:00 PM UTC-4, Victor Luchangco @ Oracle wrote:

Hi Niall,

Thanks for your feedback.  I agree we need to think about what we really need to include in the proposal, and omit--at least for now--extraneous features.  But it's also important to keep in mind what our goals are, so that we don't throw out features important to these goals.

It's more observations than feedback. Full fat TM is cool and everything, but it comes across as being similarly deep as full fat Concepts. We all have bad memories of how the committee and vendors reacted to full fat Concepts.

I think what most C++ users will mostly want from TM is multi-atomics. The rest they can live without. I think you'll see that conservatism appear when you submit your TS. They'll ask "do we really need this?" to which the answer is "no". The next question will be "what from this do we actually need?" to which is the answer I think is "multi-atomics". You'll get that support and that support alone because the rest won't be absolutely necessary, and C++ TM v1.0 will be considered done.

 

To limit the scope of this discussion, I want to clarify that I think your proposal covers only the part of the proposal related to *atomic* transactions, not relaxed ones.  (Semantically, in the absence of atomic transactions, relaxed transactions are equivalent to critical sections guarded by a single global lock.)  Please correct me if I am misunderstanding you on this point.

My proposal only covers doing multiple scatter/gather atomics as a single operation, all of which is either entirely visible at once or it isn't. The traditional TM nomenclature is inapplicable here.

 

Even for atomic transactions, here is not a single goal, but among the goals are to provide a simpler, more effective mechanism than locks and atomic variables for synchronization in concurrent C++ programs and to exploit hardware features (i.e., hardware TM) we expect in some future processors.  Transactional constructs in C++ are, we believe, a *means* to such goals, not the goal itself.

Sure, and I do appreciate that. However we have twenty plus years of accumulated patterns in threading management. I think that when the time comes, TM will be seen primarily as a lock acquisition optimisation technique and a way of performing multiple atomic operations simultaneously. The rest, sadly, will be pushed to "later" and likely not as a part of ISO standards process.

In the end you have to ask, what's the least old code disturbing route? Answer: to follow the patterns of the past twenty years closely. It's different for greenfield code of course, but that's a tiny minority of development effort.

>  I think you misunderstood what I propose (my fault). If I do:
>
> int dest=1, src=4, foo=5;
> trans_ctx h=begin_trans();
> trans_store(h, &dest, foo+trans_load(h, &src));
> src=2;
> foo=10;
> assert(dest==1); // works
> if(trans_commit(h)) // make everything written to by trans_ctx visible atomically
>   assert(dest==12); // works
>
> In other words you *cannot* interleave non-transactional and transactional accesses. trans_ctx is simply to tell the compiler to compile any code working on the trans_ctx into a separate block of code whose effects on memory are to be made visible atomically. In the above case, the direct load of foo in the trans_store() gets converted by the compiler into an implicit trans_load(h, &foo).
>
> In other words, think of trans_ctx operations as being like a lambda. begin_trans() starts the lambda. trans_*() functions write what the lambda will do. trans_commit() calls the lambda.

Thanks for this clarifying example.  I did not know that this was the semantics you intended--indeed, I didn't know what semantics you intended.  I'm curious though about why the direct load of foo should be converted to an implicit trans_load.  If so, why put the trans_load explicitly for src?  Why have two ways to say the same thing?

I appreciate it isn't entirely obvious. I was coming at it from a compiler's perspective, so basically the compiler sets up an AST from the trans_store() to its dependent expression. Everything in that dependent expression must be convertible to a trans_something(). If not, the compiler errors out.

 

 And when would such an implicit conversion take place?  For example, what if there is a function call within the third argument expression to trans_store?  What if that function does I/O?

An inlineable function call is fine, iff it can be decayed into a sequence of trans_something(). Obviously i/o therefore causes a compiler error. Indeed, anything non-arithmetic causes a compiler error.

Why be so restrictive? Mainly because I suspect HTM nesting level limits will be a major factor in practice. Haswell's limit of seven nesting levels places very severe restrictions on HTM's use cases.

 

> As others have mentioned, many of us have thought for a long time about support for transactional constructs in concurrent programming, both semantic and linguistic issues (i.e., how to make it usable) and implementation issues, including support on systems that may or may not support hardware TM.  We would have liked a solution--at least temporarily--that did not require linguistic support, but found such to be cumbersome to use, enough to discourage use and induce error when used.  (See, for example, case studies done by Pankratius and Adl-Tabatabai and by Rossbach et al.) 

Please do not take anything I have said in this thread as downplaying or trivialising anyone's work in this area. My hat is off to you for the very substantial investment you all have made over many years. What I'm hopefully doing is preparing you for the arguments you will see once a TS leaves this SG: WG21 is a very conservative body. If there is a hint a controversy they will likely cherry pick as I explained at the top.

> My worry is that this does not provide the "most useful 80%".  In terms of mere *functionality*, it may, but the perceived value of a feature must exceed the (perceived) difficulty in learning and using it.  The interface you describe seems to me to be more difficult to learn and use, and provide less functionality.  It may be less difficult to implement, but I think it's worth trying.  Furthermore, note that we are proposing a TS.  We do not expect to get everything right the first time, and indeed, various people working on this have different ideas about what (if anything) should ultimately be included into C++ (i.e., not merely in a TS), but I think we all agree that we need more feedback from real people trying to use transactional constructs to draw any meaningful conclusions.  That is why we are proposing this TS, and also guides our choices in deciding what to include.

I think I covered my angle on this sentiment at the top of this post.

Niall

[Niall Douglas]

On Friday, May 24, 2013 6:06:22 AM UTC-4, Torvald Riegel wrote:

> any one of which is enough to bring in significant hesitation. Also
> nothing is obvious about how TM enabled C++ interops with C other than
> calling C anything auto-aborts any TM.

I don't understand this sentence.

Any changes to the C++ memory model need representation in C. Otherwise you break C <=> C++ interop. We've seen this necessity already in the parallel C11 and C++11 atomics API design.

Before anyone says "this SG is for C++, not C" trust me any TS you send out will have the "C compatibility" question asked of it. And correctly so.

 

> They *are* atomic variables :). Just with the non-explicit variant
> defaulting to relaxed.

I should correct an error of mine here: I meant relaxed with respect to their surrounding, non trans_ctx bretheren. Within the trans_ctx the default would of course be that trans_load()'s acquire and trans_store()'s release.

 

Atomic operations are not transaction_safe.  They are supposed to be a
single atomic thing that doesn't give the guarantee of extending the
atomicity guarantee to anything else (ie, you can't just merge two
atomic accesses).  Transactions do give those guarantees.  It's not the
same thing.

Only if you define a transaction as you (and this SG) have. I would see TM as simply a question of atomic visibility of a batch of writes: either a collection of writes become visible to other threads all at once, or they don't all at once. That definition entirely allows multiple atomic increments as part of a transaction: either all of the atomic increments increment atomically, or none do.

 

> My proposal is not a library. It's a C API for telling the compiler
> how to compile code.

So it's directives for the compiler expresses through a library
interface.  And because it's not supposed to be a library, it must
conceptually be a language-level feature, right?  So, in the end, you're
trying to express a language-level feature by telling the compiler about
it with a library-level interface?

I have to admit I'm struggling with why people are finding this hard to conceptualise.

It's very simple: compiler intrinsics, in every compiler I've yet seen, take the form of C macro API style forms. My proposed compiler programming API therefore must do the same. Hence the form I've taken.

Is it ideal? No. Is it easy to program with? No. Do either of these two concerns matter when all you want is the ability to have the compiler do multi-atomics for you? No, because only library code would ever use them.

Is anything I've proposed a language level feature? Not really, and deliberately not so because otherwise you're talking significant language changes, exactly the thing that will give people the fear I've mentioned in other posts.

 

So the compiler has to do the same that it has to do with
__transaction_atomic, just that we're requiring users to use a much less
compact interface?  And we change the (language-level) semantics of the
code between begin and end?  I don't see any benefit to a clean
language-level construct.  This makes it harder for a compiler to figure
out when a transaction ends, and which code has to be instrumented.
It's easier for programmers to make a mistake with this interface.  And
we have the same or even more changes to semantics you were worrying
about.

My argument is that changing the language scares people, and you'll see enough resistance you won't get TM into the standard. Then the vendors will go do their own proprietary thing. Then impatient people will form abstraction libraries using proprietary facilities. Then this SG and all the work done up to this point is moot.

BTW, I actually hope that doesn't happen. Hence me posting this thread. I'm trying to play devil's advocate here.

 

> In other words, think of trans_ctx operations as being like a lambda.
> begin_trans() starts the lambda. trans_*() functions write what the
> lambda will do. trans_commit() calls the lambda.

But you said that the compiler converts foo=10 into a trans_store().  So
there's more than just setting up a static transaction.  If it really
were like a lambda, why not use a lambda right away but design a very
similar feature?

C compatibility. If a C14 adds lambdas, then I'm happy with lambdas.

Why care about C compatibility? Most real world early demand for TM I suspect will be in low level threading primitive implementations, all of which are generally written in C.

 

> I agree that use of the C11 atomics API severely limits what you can
> do inside a transaction e.g. no branch logic. That is deliberate: the
> API is intended to force programmers to work in small, chainable,
> unwindable atomic chunks of memory effect. As I mentioned before, no
> one is proposing that programmers use this API directly.

So who would be the actual target audience of this API, if it isn't C++
programmers?

Anyone wanting to do multi-atomics in a compiler and vendor and architecture neutral way.

> And as I also mentioned before, I'm not aiming for feature parity, I
> want the most useful 80% of what TM can provide, which for me is
> mainly multi-CAS and multi-atomics.

If that's what you're interested it, why not just work on a clean API
for atomic operations on multi-memory locations (e.g., mCAS, atomic
snapshots, ...)?  Or call them static transactions, if you like (static
in the sense of which accesses and which operational semantics (from a
fixed set of semantics such as CAS)).  Those could perhaps even be
considered independently of TM, although they should likely be able to
synchronize with transactions as specified by SG5.  Define the precise
semantics wrt. the memory model, and propose this API to C++ SG1/SG5.

Sure, and that's exactly where I'm going in fact. What I've proposed is fairly idempotent to the draft TS being worked on by this SG. If there is buy in from this SG i.e. I'm not stepping on toes and no one is thinking I'm am cutting off their feet during the TS construction, I may well give that a go with a patch to clang to implement it.

 

IMO, and I guess for most here, TM is about transactions that can access
any memory locations, don't have to declare which they are going to
access up-front at the start of a transaction, and allow programmers to
express any kind of operational semantics using transactions (eg, do
branch).  Of course we'll have some restrictions as only allowing
transaction_safe code in atomic transactions, but the goal is to not try
to come up with a general mechanism.  Which is another reason why it
will probably be cleaner as a language construct than a library.

Sure. You guys have been at this for fifteen years or so. I think what you've achieved is amazing, but it still comes across as being full of dragons to the C++ language standard. ISO standards are supposed to standardise existing practice, not new practice, and that's the benchmark by which they are judged.

Niall

[Michael L. Scott]

On May 24, 2013, at 11:11 AM, Niall Douglas wrote:

> [snip]

>
> I think what most C++ users will mostly want from TM is
> multi-atomics. The rest they can live without. I think you'll see that
> conservatism appear when you submit your TS. They'll ask "do we really
> need this?" to which the answer is "no". The next question will be
> "what from this do we actually need?" to which is the answer I think
> is "multi-atomics". You'll get that support and that support alone
> because the rest won't be absolutely necessary, and C++ TM v1.0 will
> be considered done.

If all we really wanted were "multi-atomics," I would be inclined to go
with something much simpler than what Niall is proposing -- namely, a
library-based MCAS that doesn't even try to look like TM -- something
along the lines of

struct loc_info {
void* loc;
type_info& tp;
};
bool atomic_compare_exchange_weak_multiple(
unsigned r, loc_info[r] reads,
unsigned w, loc_info[w] writes);

This would attempt to (atomically) confirm the r reads, each of whose
values was expected to agree with *reads[i].loc for 0<=i<r, and perform
the w writes, setting each to *writes[j].loc for 0<=j<w, and return an
indication as to whether it succeeded.

Calls to atomic_compare_exchange_weak_multiple would be required to be
obstruction free, and atomic wrt each other (only).

While this does a lot less than TM does, I can definitely imagine it
being useful. It would certainly be better than nothing at all.

- Michael

[Jens Maurer]

On 05/24/2013 05:11 PM, Niall Douglas wrote:
> It's more observations than feedback. Full fat TM is cool and
> everything, but it comes across as being similarly deep as full fat
> Concepts. We all have bad memories of how the committee and vendors
> reacted to full fat Concepts.

The way this is expressed does not match my recollection of the
WG21 standards meetings where concepts were discussed.

The problems that concepts intended to solve were, I believe, widely
understood in the committee. Doug Gregor put in tremendous effort to
get the wording right (and the wording was about 10 times bigger than
what the transactional memory wording will end up being, in my
estimation), and a special sub-group of WG21's Core Working Group
invested a lot of effort to review and clean up the wording, including
having separate face-to-face meetings in between the WG21 meetings.

All poll results below are from my personal notes, not from the official
minutes. Please consult the official minutes if in doubt.

In Sophia Antipolis (June 2008), the concepts straw poll read:

straw poll: Ship a CD with concepts in core and library in San Francisco?
J16: lots/3/0
WG21: 7/0/0 unanimous

and, in fact, the vote in San Francisco (September 2008) went

Motion 10: concepts
Steve A: "it's time, vote yes"
many in favor, 1 opposed (Daveed)

Motion 11: named requirements for concepts
many in favor, 1 opposed (Daveed)


For comparison, the range-based "for" loop that we hopefully all love
by now had a lot more opposition:

Motion 12: range-based for-loop
Clark: implemented? Doug: yes, concept-gcc had it
many in favor, 3 opposed


We took out concepts in Frankfurt (July 2009) again, because we felt we
would need more time to fix up the remaining issues than what the C++11
schedule allowed for:

Motion: Remove concepts from the working draft.
Barry, Daveed seconds.
Objections: none


Nobody has picked up Doug's proposal since then.


Note that concepts were directly integrated into the C++ standard.
Nowadays, we're on a more fine-grained schedule, and TM is heading for
a TS, not the C++ standard proper, in the first round. Both facts
make me believe we'll not hit roundabout opposition in WG21.

Jens

[Jens Maurer]

On 05/24/2013 05:42 PM, Niall Douglas wrote:
> Any changes to the C++ memory model need representation in C.

Not if those changes are conditional on using syntax that doesn't
exist in C.

> Otherwise you break C <=> C++ interop.

Not really. The way C and C++ interact is that there is a common
subset of both languages that will compile with a C and C++ compiler,
with the same semantics (thereby allowing to share header files).
People targeting this common subset will have to refrain from using
certain C features, as well as refrain from using certain C++ features.
For example, C++ doesn't have _Bool, and C doesn't have templates.

> We've seen this necessity
> already in the parallel C11 and C++11 atomics API design.

The API design for atomic variables was deliberately written so
that some of the syntax for atomic variables intentionally
ended up in the common subset of C and C++. That said, C++
still has a "more natural" interface using atomic<T> in
addition to the C-like pure function call interface.

> Before anyone says "this SG is for C++, not C" trust me any TS you
> send out will have the "C compatibility" question asked of it. And
> correctly so.

Sure, and the answer is easy: There is no support for C at this time.
We welcome input from the C community interested in transactional
memory to come up with suggestions for integration. For the time
being, we're focusing on C++, because we feel we can benefit from
its expressiveness when specifying TM semantics.

Jens

[Mark Moir]

On 5/25/13 3:11 AM, Niall Douglas wrote:
>
> Why be so restrictive? Mainly because I suspect HTM nesting level limits
> will be a major factor in practice. Haswell's limit of seven nesting
> levels places very severe restrictions on HTM's use cases.

First, I don't think we should be making design decisions based on an
assumption that all implementations will use HTM, and certainly not
make significant decisions based on (perceived, see below) limitations
of a particular vendor's implementation.

That said, this is actually a non-issue, even for Haswell. The
consequence of Haswell's restriction on nesting depth is a minor
invonvenience for implementors, *not* a limitation on what can be done
in C++ transactions implemented over them.

Using the simple form of Haswell's HTM (HLE), which is used via
special forms of instructions that demarcate a critical section and
leave all details of eliding the lock to Haswell, there is a nesting
depth imposed. This makes sense, because the implementation has to
have resources to track each lock being elided, so it has to be
limited.

Using the more complex form (RTM), which any implementation of
transactional language features would, there is also a nesting depth
limitation of 7. Why? I don't know for sure, but it's a reasonable
guess that this is inherited from the simpler form as they use similar
mechanisms.

But the *only* benefit to nesting transactions using RTM is to avoid
the need to count the nesting depth. With the limitation in place,
implementations will need to maintain a local count of the nesting
level, so that they don't execute a txbegin instruction within a
hardware transaction and they don't execute txend unless it's the
outermost nesting level. This is what we've done for our Rock-based
hybrid TM implementations. The performance overhead is negligible and
it's a bit of an inconvenience for implementations, but that's all.

I probably need to convince some people of my claim that there is no
real benefit to nesting hardware transactions. This is a direct quote
from Intel's public documentation at software.intel.com/file/41604:

8.3.4 Transactional Nesting

Both HLE and RTM support nested transactional regions. However, a
transactional abort restores state to the operation that started
transactional execution: either the outermost XACQUIRE prefixed HLE
eligible instruction or the *outermost* XBEGIN instruction. The
processor treats all nested transactions as *one monolithic
transaction*.

(Emphasis added.)

Cheers

Mark

[Mark Moir]

We don't need to throw the baby out with the bath water. *If* we throw
out most of the things in the current spec, *including* the ability to
call functions from within transactions and the ability to use
exceptions *at all* within transactions (let alone allowing them to
escape), we can still have nice syntax for the simple atomic blocks that
remain, and all of the issues about what functions are transaction_safe
go away.

The static versions, along the lines Michael suggests don't require any
compiler support, but also make the programming model much harder (think
about ABA). Niall's proposal, to the extent I understand it, still
requires compiler support to translate code used in transactions, and as
others have pointed out, if we're doing that anyway, we might as well
make the syntax nice.

Another possibility (not tasteful to me, just mentioned for
completeness) is to have fixed functions like this that can express
dynamic transactions. That's vague but I have to run. Will elaborate
later if it's unclear.

Cheers

Mark




>
> - Michael
>

[Torvald Riegel]

On Fri, 2013-05-24 at 08:42 -0700, Niall Douglas wrote:
> On Friday, May 24, 2013 6:06:22 AM UTC-4, Torvald Riegel wrote:
> Atomic operations are not transaction_safe. They are supposed
> to be a
> single atomic thing that doesn't give the guarantee of
> extending the
> atomicity guarantee to anything else (ie, you can't just merge
> two
> atomic accesses). Transactions do give those guarantees.
> It's not the
> same thing.
>
>
> Only if you define a transaction as you (and this SG) have. I would
> see TM as simply a question of atomic visibility of a batch of writes:
> either a collection of writes become visible to other threads all at
> once, or they don't all at once. That definition entirely allows
> multiple atomic increments as part of a transaction: either all of the
> atomic increments increment atomically, or none do.

The point is that atomic operations as specified by C++ and C (nor the
underlying HW ops) don't allow you to make one operation on one location
simply atomic with another. And transactions, as you confirm, do allow
that.

You said that the compiler would be required to transform normal code
located between different calls to intrinsics. So you are using the
calls to demarcate a region of code, and then require the compiler to
not just replace the intrinsics calls with something else but actually
instrument all the code in between, etc. That's unlike the typical
intrinsics I'm aware of, and much more like a language feature. Just
uglier.

>
> So the compiler has to do the same that it has to do with
> __transaction_atomic, just that we're requiring users to use a
> much less
> compact interface? And we change the (language-level)
> semantics of the
> code between begin and end? I don't see any benefit to a
> clean
> language-level construct. This makes it harder for a compiler
> to figure
> out when a transaction ends, and which code has to be
> instrumented.
> It's easier for programmers to make a mistake with this
> interface. And
> we have the same or even more changes to semantics you were
> worrying
> about.
>
>
> My argument is that changing the language scares people, and you'll
> see enough resistance you won't get TM into the standard. Then the
> vendors will go do their own proprietary thing.

Actually, two vendors have already implemented the language constructs:
Intel (What-If prototypes) and GCC. And SG5's work or the predecessor
work was the blueprint for these implementations.

Do you think that vendors would prefer having to agree on one set of
intrinsics that isn't just calls but demarcates code, and thus brings in
lots of the issues a language-level construct would face, instead of
having a properly defined language-level construct right away?

> Then impatient people will form abstraction libraries using
> proprietary facilities. Then this SG and all the work done up to this
> point is moot.
>
>
> BTW, I actually hope that doesn't happen. Hence me posting this
> thread. I'm trying to play devil's advocate here.
>
> > In other words, think of trans_ctx operations as being like
> a lambda.
> > begin_trans() starts the lambda. trans_*() functions write
> what the
> > lambda will do. trans_commit() calls the lambda.
>
> But you said that the compiler converts foo=10 into a
> trans_store(). So
> there's more than just setting up a static transaction. If it
> really
> were like a lambda, why not use a lambda right away but design
> a very
> similar feature?
>
>
> C compatibility. If a C14 adds lambdas, then I'm happy with lambdas.
>
>
> Why care about C compatibility? Most real world early demand for TM I
> suspect will be in low level threading primitive implementations, all
> of which are generally written in C.

You mean like TBB, for example? :)

IMO, if what you're proposing does need custom compiler support (ie,
it's not just a library), then you'll see the same opposition from
compiler vendors as you claim will come up for a language extension.
Something isn't compiler/vendor-neutral if you require custom compiler
support. If I were you, I'd rather start with a pure library interface.

>
> IMO, and I guess for most here, TM is about transactions that
> can access
> any memory locations, don't have to declare which they are
> going to
> access up-front at the start of a transaction, and allow
> programmers to
> express any kind of operational semantics using transactions
> (eg, do
> branch). Of course we'll have some restrictions as only
> allowing
> transaction_safe code in atomic transactions, but the goal is
> to not try
> to come up with a general mechanism. Which is another reason
> why it
> will probably be cleaner as a language construct than a
> library.
>
>
> Sure. You guys have been at this for fifteen years or so. I think what
> you've achieved is amazing, but it still comes across as being full of
> dragons to the C++ language standard. ISO standards are supposed to
> standardise existing practice, not new practice, and that's the
> benchmark by which they are judged.

How do you think would your proposal score according to this benchmark?
An intrinsics-like interface with required compiler instrumentation of
normal code for static transactions doesn't seem like existing practice
to me...

[Torvald Riegel]

On Fri, 2013-05-24 at 08:11 -0700, Niall Douglas wrote:
> On Thursday, May 23, 2013 2:18:00 PM UTC-4, Victor Luchangco @ Oracle
> wrote:
> Hi Niall,
>
> Thanks for your feedback. I agree we need to think about what
> we really need to include in the proposal, and omit--at least
> for now--extraneous features. But it's also important to keep
> in mind what our goals are, so that we don't throw out
> features important to these goals.
>
>
> It's more observations than feedback. Full fat TM is cool and
> everything, but it comes across as being similarly deep as full fat
> Concepts. We all have bad memories of how the committee and vendors
> reacted to full fat Concepts.
>
>
> I think what most C++ users will mostly want from TM is multi-atomics.
> The rest they can live without. I think you'll see that conservatism
> appear when you submit your TS. They'll ask "do we really need this?"
> to which the answer is "no". The next question will be "what from this
> do we actually need?" to which is the answer I think is
> "multi-atomics".

If you haven't yet, please try building a simple concurrent operation,
say, a concurrent linked list with this kind of static transaction.
Don't cheat regarding ABA issues and such, as Mark pointed out. Are you
still convinced this is the static transactions are quite 80%?

> You'll get that support and that support alone because the rest won't
> be absolutely necessary, and C++ TM v1.0 will be considered done.
>
> To limit the scope of this discussion, I want to clarify that
> I think your proposal covers only the part of the proposal
> related to *atomic* transactions, not relaxed ones.
> (Semantically, in the absence of atomic transactions, relaxed
> transactions are equivalent to critical sections guarded by a
> single global lock.) Please correct me if I am
> misunderstanding you on this point.
>
>
> My proposal only covers doing multiple scatter/gather atomics as a
> single operation, all of which is either entirely visible at once or
> it isn't.

So which operations do you actually want?
- atomic snapshot?
- atomic updates?
- atomic snapshot and updates?
- nCAS?
- others?

What do you think is the minimal set that you want to offer? Why do you
think it will be 80% sufficient? (Actually, 80% of what?)

> The traditional TM nomenclature is inapplicable here.

If you declare up front, before starting the transaction, what the
transaction is supposed to access, then this is typically called a
static transaction.

[Michael Spear]

In the same spirit as Niall, I would like to suggest that we at least consider a different API for transactions.  I will present it as a hypothetical library API, though I do not believe that a library API is practical.  Instead, I think that the library API provides an abstraction for allowing some advanced features that I do not believe we can live without in the current specification.

Our recent discussions about the memory model seem to roughly conclude that all transactions (even atomic ones) behave as if protected by a single global lock.  Thus I claim that another model we could use is that transactions behave as if there is a single "transactional executor" and threads schedule jobs with the transactional executor.  The transactional executor either (a) acquires an internal lock, executes the job, and then releases the lock, or (b) returns an error code without changing the shared memory at all.

In this case, __transaction_atomic blocks are simply a syntactic sugar for telling the compiler to take the code block, wrap it up as a closure, and pass it to the executor.  The same is true for __transaction_relaxed, except that the closure includes an extra property (in the spirit of the older v1.1 TM specification, let's call it may_not_cancel, rather than discussing the difference between a relaxed "transaction" and a truly atomic transaction).

I think we could all imagine an API for implementing this as a library.  It would fit on half a page, in essence consisting of some tm::executor object and a method for submitting a closure or lambda or function pointer of some sort.  I hope we would all also agree that it would be difficult to actually get good performance out of this API, because we'd want implementations to elide the lock and have the executor be a concurrent object, but doing so would require instrumentation of the functions called by the closures that are passed to the executor, which returns us directly to the whole [[transaction_safe]] requirement and/or safe-by-default.

The reason I prefer this API to the current way we are thinking about TM is that I want to have a clean mechanism for setting properties of transactions, and I do not want that mechanism to entail additional language extensions.  In particular, I believe the following are necessary:

1 - the ability to dynamically set 'onCommit' handlers from within a transaction, e.g., for signalling on a condition variable at the end of some executions of an atomic transaction, or deferring fprintf-style logging until the transaction commits.

2 - the ability to dynamically set 'onAbort' handlers from within or outside of a transaction, e.g., for implementing backoff or other forms of contention management on transaction abort.

3 - the ability to 'shut off' transactions from within a transaction, or from an onAbort/onCommit handler, in order to allow assertions inside of atomic transactions.

Hopefully everyone believes these three cases are necessary.  They certainly all occurred when transactionalizing memcached, and the in-progress specification does not address them.  However, they all seem be dynamic properties -- we can't statically annotate transactions to get these effects.  Yet they all are very easy if there is a notion of a transactional executor to which I can say e.g., 'tm::set_for_running_transaction(tm::oncommit, foo())' or 'tm::set_for_next_transaction(tm::onabort, backoff())'.

I do understand that we want a minimal proposal, but since these are true user-visible API calls to the tm machinery, rather than language features, I hope we can fit them in, and I hope that thinking about TM as entailing a transactional executor object helps to convince that their addition need not complicate the presentation of these new features.

- Mike

[Niall Douglas]

On Friday, May 24, 2013 12:51:12 PM UTC-4, mlscott wrote:

On May 24, 2013, at 11:11 AM, Niall Douglas wrote:

> [snip]
>
> I think what most C++ users will mostly want from TM is
> multi-atomics. The rest they can live without. I think you'll see that
> conservatism appear when you submit your TS. They'll ask "do we really
> need this?" to which the answer is "no". The next question will be
> "what from this do we actually need?" to which is the answer I think
> is "multi-atomics". You'll get that support and that support alone
> because the rest won't be absolutely necessary, and C++ TM v1.0 will
> be considered done.

If all we really wanted were "multi-atomics," I would be inclined to go
with something much simpler than what Niall is proposing -- namely, a
library-based MCAS that doesn't even try to look like TM

What I'm proposing needs compiler support, hence it being a set of compiler intrinsics. It can't be a pure library solution unless you can guarantee HTM support being available.

Niall

[Niall Douglas]

On Friday, May 24, 2013 3:45:23 PM UTC-4, Jens Maurer wrote:

On 05/24/2013 05:11 PM, Niall Douglas wrote:
> It's more observations than feedback. Full fat TM is cool and
> everything, but it comes across as being similarly deep as full fat
> Concepts. We all have bad memories of how the committee and vendors
> reacted to full fat Concepts.

The way this is expressed does not match my recollection of the
WG21 standards meetings where concepts were discussed.

Sure. I'm coming at it from a very different perspective though: as a former SC22 mirror convenor. There was concern expressed at my national committee level that some of what was being talked about for C++0x appeared to be inappropriate for the ISO process. I remember answering that WG21 took great care to ensure vendor and implementor buy in, and that would ensure what got sent to ISO was practical and that WG21 would not therefore make the mistakes that other SC22 WGs have made in pushing too far ahead of vendors too quickly. There is always a worry that some ISO WGs go off on a "wouldn't it be nice if" form of standards making, and that this can lead to the delegitimisation of ISO on the world stage.

Perhaps "bad memories" is an inappropriate choice of term: I think absolutely everyone is agreed that we need some form of abstract base class equivalent for metaprogramming, and the overwhelming majority have settled on some form of concepts as the right way to do it. I, personally speaking, deeply disliked the full fat Concepts proposal as I think it touches and affects too much when we can make do with a far lighter set of changes given what is actually needed: ABTs for metaprogramming, so I guess the bad memories I refer to are mostly mine. I'm presently ambivalent regarding the present TM proposal. Quite frankly, I'm not yet persuaded the breadth and sweep of changes is actually necessary given the problem needing to be solved.

 

Note that concepts were directly integrated into the C++ standard.
Nowadays, we're on a more fine-grained schedule, and TM is heading for
a TS, not the C++ standard proper, in the first round.  Both facts
make me believe we'll not hit roundabout opposition in WG21.

I see no problem for a TS - indeed, that's the whole point of TSs and TCs is to publish non-binding thought proposals reflecting some form of consensus.

The problem I think will be getting widespread vendor buy in for that TS in terms of officially endorsed experimental implementations. You'll need at least three of the major C++ compiler vendors to implement it to create enough impetus to make it happen. And there I'm currently seeing some difficulties: generally less is more for the compiler vendors for obvious reasons.

Let me put this another way: OpenMP saw fairly rapid and complete adoption, with all but one of the major C/C++ compilers supporting it, because the compiler vendors buy into OpenMP. Any TM proposal needs to achieve at least the same amount of buy in across the board, and that preferably needs to happens some years before 2017.

Niall

[Niall Douglas]

On Friday, May 24, 2013 4:07:53 PM UTC-4, Mark Moir wrote:

The static versions, along the lines Michael suggests don't require any
compiler support, but also make the programming model much harder (think
about ABA).  Niall's proposal, to the extent I understand it, still
requires compiler support to translate code used in transactions, and as
others have pointed out, if we're doing that anyway, we might as well
make the syntax nice.

I think where I am going eventually in my head is that your stuff gets translated into my stuff under the bonnet. And that then lets C interop cleanly, or indeed one can use the internal compiler intrinsic API to interact with the higher level implementation on the few occasions it's needed.

In other words, I guess I'm proposing an alternative formulation of minimal TM support so we can get the ball rolling.

Niall

[Niall Douglas]

On Sunday, May 26, 2013 7:26:06 PM UTC-4, Torvald Riegel wrote:

On Fri, 2013-05-24 at 08:42 -0700, Niall Douglas wrote:
You said that the compiler would be required to transform normal code
located between different calls to intrinsics.  So you are using the
calls to demarcate a region of code, and then require the compiler to
not just replace the intrinsics calls with something else but actually
instrument all the code in between, etc.  That's unlike the typical
intrinsics I'm aware of, and much more like a language feature.  Just
uglier.

OpenMP is not dissimilar. Even vector intrinsics is not dissimilar: some vectors calls are decayed into multiple ops, especially on ARM NEON.

Do you think that vendors would prefer having to agree on one set of
intrinsics that isn't just calls but demarcates code, and thus brings in
lots of the issues a language-level construct would face, instead of
having a properly defined language-level construct right away?

I intentionally designed the intrinsics to map identically onto what the compiler does internally in terms of code generation anyway. Support for a naive implementation, theoretically speaking, ought to be trivial: the intrinsics simply override what the compiler would normally do. If HTM isn't available, the generated code segments use CAS to emulate HTM. Because you can't do much logic inside the code segments, correctly nobbling the compiler's state ought to be easy enough.

I agree that support for a non-naive implementation is no less complex than a full fat TM implementation. Generating optimised TM code is distinctly non-trivial. I completely agree that my proposal only gets buy in from anyone under the assumption that performance on non-HTM hardware will not be optimal and that that is something people will happily accept in order to get TM as soon as possible. I agree that's an unproven assumption, and one invalid at present on at least one major architecture which to my knowledge hasn't announced its intended HTM approach: ARM.

 

IMO, if what you're proposing does need custom compiler support (ie,
it's not just a library), then you'll see the same opposition from
compiler vendors as you claim will come up for a language extension.

I agree that if ARM announced their HTM plans, then it's a much easier sell: implement this proposal and save yourself having to implement twice for Intel and ARM.

(I know there are non-ARM and non-Intel architectures. However they're the only two I consider at work).

I would also point out that GCC has a nicely abstracted intrinsics API, so you can do bit scans for example using a generic intrinsic and that compiles into whatever is the right code for the architecture. What I'm proposing is simply an extension of the same idea.

 

> Sure. You guys have been at this for fifteen years or so. I think what
> you've achieved is amazing, but it still comes across as being full of
> dragons to the C++ language standard. ISO standards are supposed to
> standardise existing practice, not new practice, and that's the
> benchmark by which they are judged.

How do you think would your proposal score according to this benchmark?

Well my proposal clearly cannot affect any existing code. Any brokenness in it is contained, and therefore induced uncertainty is much lower. I agree it's pure marketing and perception of risk, but it *is* important. Anything which changes the C++ type system *has* to pass a very, very high barrier. There is also the extant problem that we keep trying to fix our existing brokenness in the type system with more typing e.g. how do we fix the lack of correct per-type alignment metadata? C++11 has a half finished implementation there, mainly because finishing it immediately might close off implementation of other important things.

And if we can't finish per-type alignment - something far smaller and less consequential than the present TM proposal - can you see where I'm coming from in terms of the risk and uncertainty perceived by those external to this SG? I know from experience ISO is usually more about uncertainty management and people management than anything else. If a large vendor gets any doubt about something, they can and will veto very quickly and once they do, a technical measure, no matter how well thought through or technically meritous or in fact unrisky, is dead.

Niall

[Niall Douglas]

On Sunday, May 26, 2013 7:41:32 PM UTC-4, Torvald Riegel wrote:

On Fri, 2013-05-24 at 08:11 -0700, Niall Douglas wrote:
> I think what most C++ users will mostly want from TM is multi-atomics.
> The rest they can live without. I think you'll see that conservatism
> appear when you submit your TS. They'll ask "do we really need this?"
> to which the answer is "no". The next question will be "what from this
> do we actually need?" to which is the answer I think is
> "multi-atomics".

If you haven't yet, please try building a simple concurrent operation,
say, a concurrent linked list with this kind of static transaction.
Don't cheat regarding ABA issues and such, as Mark pointed out.  Are you
still convinced this is the static transactions are quite 80%?

I think you misunderstand my intent. I'm not saying "this is the minimum of what we need". I'm saying "this is probably what the general body looking in from outside thinks is the minimum of what they need". Most people looking at TM get the value of multi-atomics. There is significant buy in there.

I think there is much less buy in that TM revolutionises the way that one writes code and would make all C++ programming more productive, more fun, and less buggy. I genuinely wish there were more buy in on this, because that's the true value of TM. I fear, unfortunately, we'll graft multi-atomics onto the existing pthreads primitives as an optimisation technique, and then it'll be at least another decade before anyone starts to think about the improvements on *design* that are made possible by TM.

 

So which operations do you actually want?

I think what most people want is compiler emulation of HTM on CPUs without HTM. That's *very* different to C++ TM as presently proposed: by compiler emulation of HTM, I mean quite literally that you write the Haswell TSX intrinsic functions and on non-TSX hardware the compiler generates code that acts as if TSX were present.

You may note that what I proposed goes significantly beyond that bare minimum. I tried to make it possible to implement higher order functionality.

I appreciate that in circles I don't move in the discussion may be very different. What I report above is what I'm currently seeing, that's all.

Niall

[Niall Douglas]

I know where you're coming from Mike, but I believe this SG has clearly set its focus on the memory model aspect of TM only (notwithstanding the ripples caused). I would observe that TM's biggest contribution by far is the atomicity of visibility of changes to memory: you can make many changes to memory become simultaneously visible to other threads all at once, thus eliminating a huge source of race conditions and other bugs in threaded code, plus the ability to eliminate locking constructs completely. Therefore there is no single global lock, though I understand from where you're getting the analogy.

In terms of generic transactional storage for C++, you may be interested that I submitted a GSoC project for Boost this summer which implements the first half of such a thing: an extension of Boost.ASIO adding a massive batch chainable parallel closure execution engine. The second half implements an ACID compliant data persistence engine for C++ through which I think your desired feature set would be more appropriately placed.

HTH,

Niall

[Victor Luchangco]

On May 26, 2013, at 11:08 PM, Michael Spear wrote:

> In the same spirit as Niall, I would like to suggest that we at least consider a different API for transactions. I will present it as a hypothetical library API, though I do not believe that a library API is practical. Instead, I think that the library API provides an abstraction for allowing some advanced features that I do not believe we can live without in the current specification.

What do you mean by not being able to live without these advanced features? We know that the current basic proposal does not include many features that we think will be useful, even essential, for some applications. But we don't have complete agreement about what features should be included and often also on what the exact semantics of such features would be. I'm thinking, for example, of explicit cancel (rather than just cancelling when there is an uncaught exception) and allowing certain kinds of synchronization.

> Our recent discussions about the memory model seem to roughly conclude that all transactions (even atomic ones) behave as if protected by a single global lock. Thus I claim that another model we could use is that transactions behave as if there is a single "transactional executor" and threads schedule jobs with the transactional executor. The transactional executor either (a) acquires an internal lock, executes the job, and then releases the lock, or (b) returns an error code without changing the shared memory at all.

I think it is a bad idea to describe the semantics of atomic transactions in terms of a single global lock, as I argued in a short SPAA 2008 position paper (Against Lock-Based Semantics for Transactional Memory). Among other things, it strongly suggests an implementation technique that I believe we all agree is undesirable. One of the points of providing transactional constructs in C++ is to relieve the programmer of having to think about locks.

> In this case, __transaction_atomic blocks are simply a syntactic sugar for telling the compiler to take the code block, wrap it up as a closure, and pass it to the executor. The same is true for __transaction_relaxed, except that the closure includes an extra property (in the spirit of the older v1.1 TM specification, let's call it may_not_cancel, rather than discussing the difference between a relaxed "transaction" and a truly atomic transaction).

One problem with the model of having a separate executor is that it doesn't specify which memory accesses remain data races, and which are not. In C++, this is specified (in part) by the happens-before order, and I think most of the subtlety in amending the C++ specification to accommodate atomic transactions is in changes to this order (really, the suborders that comprise it).

>
> I think we could all imagine an API for implementing this as a library. It would fit on half a page, in essence consisting of some tm::executor object and a method for submitting a closure or lambda or function pointer of some sort. I hope we would all also agree that it would be difficult to actually get good performance out of this API, because we'd want implementations to elide the lock and have the executor be a concurrent object, but doing so would require instrumentation of the functions called by the closures that are passed to the executor, which returns us directly to the whole [[transaction_safe]] requirement and/or safe-by-default.
>
> The reason I prefer this API to the current way we are thinking about TM is that I want to have a clean mechanism for setting properties of transactions, and I do not want that mechanism to entail additional language extensions. In particular, I believe the following are necessary:
> 1 - the ability to dynamically set 'onCommit' handlers from within a transaction, e.g., for signalling on a condition variable at the end of some executions of an atomic transaction, or deferring fprintf-style logging until the transaction commits.
> 2 - the ability to dynamically set 'onAbort' handlers from within or outside of a transaction, e.g., for implementing backoff or other forms of contention management on transaction abort.
> 3 - the ability to 'shut off' transactions from within a transaction, or from an onAbort/onCommit handler, in order to allow assertions inside of atomic transactions.

Again, I don't know what you mean by "necessary". If I understand correctly, Niall is arguing that we should support *less* than what we currently aim to support. You are arguing we ought to support more. I agree that commit and abort handlers would be very useful for certain kinds of programming, but I think that transactions are useful without them. (I'm not sure what you mean by "shutting off" a transaction, but it sounds suspiciously like explicit cancel, a feature I also support, but we have agreed not to include in the first version.)

> Hopefully everyone believes these three cases are necessary. They certainly all occurred when transactionalizing memcached, and the in-progress specification does not address them. However, they all seem be dynamic properties -- we can't statically annotate transactions to get these effects. Yet they all are very easy if there is a notion of a transactional executor to which I can say e.g., 'tm::set_for_running_transaction(tm::oncommit, foo())' or 'tm::set_for_next_transaction(tm::onabort, backoff())'.
>
> I do understand that we want a minimal proposal, but since these are true user-visible API calls to the tm machinery, rather than language features, I hope we can fit them in, and I hope that thinking about TM as entailing a transactional executor object helps to convince that their addition need not complicate the presentation of these new features.
>

For the basic proposal, my goal wasn't to be minimal, but rather to have a proposal that we could agree to move forward with. This means mostly leaving out controversial features, or ones whose semantics we didn't agree on, but it also means including enough that it still captures the spirit of transactions (as opposed to simply supporting multi-word atomics), so that we can get real feedback to inform further development based on writing in a "transactional style" rather then merely converting lock-based programs to use transactions. (I'm not saying that the latter isn't an important use case for transactions, but that it isn't the only one--it's not even the one I'm most interested in.) Another goal of mine was to make the proposal "extendable"--that is, that it should possible to add various features we've discussed without breaking code using only the basic proposal.

To be clear: I am interested in the features you mention above--I'm even inclined to think them "essential". But I don't think we should include them in the first version: We don't have time to work through all the issues that we would need to do before we could even get down to specifying them.

- Victor

[Torvald Riegel]

On Mon, 2013-05-27 at 10:58 -0700, Niall Douglas wrote:
> On Sunday, May 26, 2013 7:26:06 PM UTC-4, Torvald Riegel wrote:
> On Fri, 2013-05-24 at 08:42 -0700, Niall Douglas wrote:
> You said that the compiler would be required to transform
> normal code
> located between different calls to intrinsics. So you are
> using the
> calls to demarcate a region of code, and then require the
> compiler to
> not just replace the intrinsics calls with something else but
> actually
> instrument all the code in between, etc. That's unlike the
> typical
> intrinsics I'm aware of, and much more like a language
> feature. Just
> uglier.
>
>
> OpenMP is not dissimilar.

It's a language-level specification though. Sure it uses pragmas (and
some bits of library interface), but it has a grammar and bases its
rules on the constructs of the base languages.

> Even vector intrinsics is not dissimilar: some vectors calls are
> decayed into multiple ops, especially on ARM NEON.

But do they change the semantics of code between calls to the
intrinsics? Optimizing, inlining, ... a certain call is fine, even
merging stuff resulting from several intrinsics calls; but if there's no
requirement to instrument code in between, I think it's different.

>
> Do you think that vendors would prefer having to agree on one
> set of
> intrinsics that isn't just calls but demarcates code, and thus
> brings in
> lots of the issues a language-level construct would face,
> instead of
> having a properly defined language-level construct right
> away?
>
>
> I intentionally designed the intrinsics to map identically onto what
> the compiler does internally in terms of code generation anyway.

How can you predict how we want to transform the code in every future
compiler?

IOW, we generally want to have stable ABIs, but basing a feature such as
transactions on a current ABI design doesn't really seem future-proof to
me.

For example, in GCC, we can create for each transaction two code paths:
one uninstrumented version of the transaction for use with a global lock
or HTM, and one with instrumentation for the software fallback. The
compiler can try do such a transformation based on calls that demarcate
the transactional code from the nontransactional code, but this doesn't
necessarily get any easier if you don't get the nice block-scoped form
of transactions, but your begin/commit calls can be anywhere.

> Support for a naive implementation, theoretically speaking, ought to
> be trivial: the intrinsics simply override what the compiler would
> normally do. If HTM isn't available, the generated code segments use
> CAS to emulate HTM. Because you can't do much logic inside the code
> segments, correctly nobbling the compiler's state ought to be easy
> enough.
>
>
> I agree that support for a non-naive implementation is no less complex
> than a full fat TM implementation.

> Generating optimised TM code is distinctly non-trivial. I completely
> agree that my proposal only gets buy in from anyone under the
> assumption that performance on non-HTM hardware will not be optimal
> and that that is something people will happily accept in order to get
> TM as soon as possible. I agree that's an unproven assumption, and one
> invalid at present on at least one major architecture which to my
> knowledge hasn't announced its intended HTM approach: ARM.
>
> IMO, if what you're proposing does need custom compiler
> support (ie,
> it's not just a library), then you'll see the same opposition
> from
> compiler vendors as you claim will come up for a language
> extension.
>
>
> I agree that if ARM announced their HTM plans, then it's a much easier
> sell: implement this proposal and save yourself having to implement
> twice for Intel and ARM.

I don't see how this is related to whether a particular architecture has
an HTM or not. If we had HTMs with similar semantics and memory model
implications on all relevant architectures, and those HTMs would only
*never* need to fall back to software to execute transaction, then maybe
we could expose transactions more like atomics. But we don't have that.

> (I know there are non-ARM and non-Intel architectures. However they're
> the only two I consider at work).
>
>
> I would also point out that GCC has a nicely abstracted intrinsics
> API, so you can do bit scans for example using a generic intrinsic and
> that compiles into whatever is the right code for the architecture.
> What I'm proposing is simply an extension of the same idea.

What you proposed changes the semantics of code between calls to
intrinsics. This is different from replacing a call to an intrinsic
with something else. Are you disagreeing with this observation, or
where is the misunderstanding here?

>
> > Sure. You guys have been at this for fifteen years or so. I
> think what
> > you've achieved is amazing, but it still comes across as
> being full of
> > dragons to the C++ language standard. ISO standards are
> supposed to
> > standardise existing practice, not new practice, and that's
> the
> > benchmark by which they are judged.
>
> How do you think would your proposal score according to this
> benchmark?
>
>
> Well my proposal clearly cannot affect any existing code.

So you are agreeing that your proposal is not existing practice? And is
not even implemented yet or shipped to users, in contrast to (prior
revisions of) the SG5 draft?

> Any brokenness in it is contained, and therefore induced uncertainty
> is much lower.

If you're concerned about the risk of the SG5 proposal, please point out
precisely what you're worrying about.

We've been very careful to not affect nontransactional code. This also
is the case at the implementation level: GCC doesn't change any
nontransactional code when -fgnu-tm is used, for example.

> I agree it's pure marketing and perception of risk, but it *is*
> important. Anything which changes the C++ type system *has* to pass a
> very, very high barrier.

Well, to be precise, we may add a property to types that only affects
transactional code, nothing else. So if you don't use transactions, no
change.

> There is also the extant problem that we keep trying to fix our
> existing brokenness in the type system with more typing e.g. how do we
> fix the lack of correct per-type alignment metadata? C++11 has a half
> finished implementation there, mainly because finishing it immediately
> might close off implementation of other important things.
>
>
> And if we can't finish per-type alignment - something far smaller and
> less consequential than the present TM proposal - can you see where
> I'm coming from in terms of the risk and uncertainty perceived by
> those external to this SG?

I can understand that you worry about resources and such. I'm not
familiar with the per-type alignment example you bring up; any pointers
so I can try to make sense of the comparison you are attempting?

> I know from experience ISO is usually more about uncertainty
> management and people management than anything else. If a large vendor
> gets any doubt about something, they can and will veto very quickly
> and once they do, a technical measure, no matter how well thought
> through or technically meritous or in fact unrisky, is dead.

Do you have a particular large vendor in mind, or a large organization,
or is this about (fear of) FUD?

If there are concrete (technical) concerns, we surely want to discuss
them. But just stating the point that there perhaps might be somebody
who is worried and thus might try to veto and that this veto then might
be successful... how does this help us to solve the technical problems?

[Torvald Riegel]

I gave a very simple example, which can serve as a test for how useful a
mechanism is to make dealing with concurrency easier. There's nothing
unusual about wanting to access a shared data structure concurrently, or
is there? Do you have actual use cases (not mechanisms!) that you feel
are more representative of the problems that most potential users would
want to solve?

> There is significant buy in there.
>

As measured how?

>
> I think there is much less buy in that TM revolutionises the way that
> one writes code and would make all C++ programming more productive,
> more fun, and less buggy. I genuinely wish there were more buy in on
> this, because that's the true value of TM. I fear, unfortunately,
> we'll graft multi-atomics onto the existing pthreads primitives as an
> optimisation technique,

Can you be more specific? Are you thinking about lock elision?

> and then it'll be at least another decade before anyone starts to
> think about the improvements on *design* that are made possible by TM.
>
> So which operations do you actually want?
>
>
> I think what most people want is compiler emulation of HTM on CPUs
> without HTM. That's *very* different to C++ TM as presently proposed:
> by compiler emulation of HTM, I mean quite literally that you write
> the Haswell TSX intrinsic functions and on non-TSX hardware the
> compiler generates code that acts as if TSX were present.

You cannot do what TSX(/RTM) does in software only (when the former
actually runs a transaction).

To "emulate", the compiler could always choose to not run a transaction;
but that's not what you want either.

[Jens Maurer]

On 05/27/2013 07:00 PM, Niall Douglas wrote:
> The problem I think will be getting widespread vendor buy in for that
> TS in terms of officially endorsed experimental implementations.
> You'll need at least three of the major C++ compiler vendors to
> implement it to create enough impetus to make it happen.

I don't see the requirement for this number.

In the past, WG21 has been happy to vote a feature into the standard
proper if there was implementation experience from at least one vendor.
("It can be done.")

For TM, we have that with GCC, I understand.

I understand that, in your opinion, this might not be enough.

Considering history, for C++11, we have two vendors (gcc and Clang)
on the verge of having implemented all of it, and I haven't heard
any other vendor claiming "we won't implement X".
EDG says at http://www.edg.com/?location=c_lang
"...and the rest will be coming soon."

In my experience, C++ so far has not suffered from having a
language standard that nobody implements (fully), and we have
historic evidence that end-user pressure on vendors to actually
implement the standard is actually strong. That's why MSVC6 is
gone for good.

> And there
> I'm currently seeing some difficulties: generally less is more for
> the compiler vendors for obvious reasons.

If we can convince C++ end-users that transactions are cool,
vendor buy-in will be easy to achieve, since end-users will bully
their vendors into supplying the cool stuff.

We have a chunk of C++ implementers in this forum; those wouldn't
participate if they didn't see an interest from their user community.

> Let me put this another way: OpenMP saw fairly rapid and complete
> adoption, with all but one of the major C/C++ compilers supporting
> it, because the compiler vendors buy into OpenMP. Any TM proposal
> needs to achieve at least the same amount of buy in across the board,
> and that preferably needs to happens some years before 2017.

Let's hope we get something out there soon so that vendors can
actually have an informed opinion.

Jens

[Jens Maurer]

On 05/27/2013 07:58 PM, Niall Douglas wrote:
> e.g. how do we fix the lack of correct per-type
> alignment metadata? C++11 has a half finished implementation there,
> mainly because finishing it immediately might close off
> implementation of other important things.

I'm sorry, I'm not aware of any alignment issues and/or proposal
on the table of WG21 right now. Do you have a paper number for
reference?

Yes, the current alignment support in C++11 might be perceived
as incomplete. I'm sure WG21 will be happy to discuss a proposal
to fix this area, if accompanied by an analysis what's actually
considered broken, and where the end-user pain is.

Thanks,
Jens

[Niall Douglas]

Apologies, I'll have to bow out of this thread. GSoC has begun this week, and I'm mentoring two Boost GSoC projects on top of my normal 50+ hour week at BlackBerry, both of which are proving time consuming. I think though that we were beginning to stray off topic anyway onto matters not specific to the thrust of my original post, or even TM.

I hope that after all these posts that my argument has, more or less, at least been delivered, even if few would agree with it (indeed, I don't entirely agree with it, but I was partially playing a devil's advocate). My very best of wishes to SG5 and its very valuable work.

Niall