[cpp-threads] High-level concurrency issues

[Peter A. Buhr]

Note, the "subject" name change for this message.

   Date: Mon, 10 Oct 2005 20:25:06 -0700
   From: Andrei Alexandrescu <andrei at metalanguage.com>
   Reply-To: cpp-threads at decadentplace.org.uk
   Sender: Cpp-threads_decadentplace.org.uk-bounces at decadentplace.org.uk
   ...
   When they resist to "changing the language" and prefer "library-based 
   solutions", most people (some even without realizing it) are really 
   thinking "changing the syntax of the language" and prefer "solutions 
   that look like library-based". See what I mean? If you give them a 
   concurrency model wrapped in a syntax that looks like invoking functions 
   and instantiating objects, everybody will like them, even though the 
   semantics are "magic" that couldn't be achieved solely via a library.

I've answered the front part of this, but I've been struggling for the last
couple of days to understand the part above. I'll press on anyway. I'm going to
grab something from Kevlin Henney's taxonomy that appeared in a message after
this one by Andrei (I will get to Kevlin's email at some point):

  (2) Present threading to the programmer as a C++ library. This is where the
  Boost proposal and my proposal currently fit. Different as they are, they
  have more in common at this level than not.

  (3) Extend the language with new concepts and syntax. This is where Lawrence
  Crowl's ideas fit (and likewise, those not on the table: Peter Buhr's work,
  Concurrent C++, etc).

I've argued for well over a decade that a "pure" library approach cannot work.

  Peter A. Buhr and Glen Ditchfield. ``Adding Concurrency to a Programming
  Language''. In USENIX C++ Technical Conference Proceedings, pages 207-224,
  Portland, Oregon, U.S.A., August 1992. USENIX Association.

(This paper is old and not well written, but it contains the core points. Doug
Lea, I think we met at this conference! ;-)

Hans picked up on this recently and suggests that changing C++'s memory model
should be sufficient to allow construction of a pure library approach.  This
may be true (although I don't know if there is any strong proof of this).
Either way, I will argue the kind of library that can be constructed in this
context is very simple (pthread-like). The above paper points out the
limitations preventing higher-level forms of concurrency using just a library
approach with a memory model.

Now I need to digress for a moment back to the above paper, which I'll precis:

  All concurrent systems must provide three primary properties:

  thread: mechanism to sequentially execute statements, independently of and
  possibly concurrently with other threads.

  execution context: the state needed to permit independent execution,
  including a separate stack.

  mutual exclusion/synchronization (MES): mechanisms to exclusively access a
  resource and provide necessary timing relationships among threads.

These primary properties cannot be expressed in an architecture-independent way
through existing language constructs.  (Even algorithms for MES, e.g., Dekker's
algorithm, do not always work without a sufficient memory-model.)  Therefore,
any concurrency system must provide abstractions to implement these properties.
(Additional secondary properties are also important.)

A concurrent programmer needs direct or indirect mechanisms to access these
primary properties. I argue the compiler also needs to know precisely when
these primary properties occur to truly understand a program is concurrent so
it can generate safe and efficient code. The less the compiler knows, the more
dangerous and/or inefficient the code generation. Notice, a memory model does
not completely address the above properties, such as when a thread starts and
ends, etc.

How can the compiler be told know about these primary properties? One approach
is to use a library approach with "magic". (Possibly what Andrei is alluding to
above.) That is, the compiler and thread-library use some form of collusion
such as hidden syntax to convey information. For example, inheriting from the
type named "thread" or a special routine name "pthread_create" tells the
programmer and the compiler that a primary concurrency property is being
used. Interestingly, this approach causes a transition from category (2) to
category (3) in Kevlin's taxonomy because the language has been changed. That
is, every C++ compiler has to be cracked open and modified. (I believe some C
compilers do this for the pthread routines.) Furthermore, there is little
difference to the programmer or the compiler writer whether a magic type-name
is used or a proper keyword.  Therefore, it is crucial to understand where a
concurrency model lies in the taxonomy, versus pretending the language has not
been changed.

Once a decision is made to change the language, with all the associated pain,
it always better to do the change properly rather than put lip-stick on a pig.