"Pure doesn't support multi-threading yet..." should it ever? Why not CALM rather than threads?

[Gregory Burd]

"Pure doesn't support multi-threading yet..." - Pure FAQ, under Why not Pure?

I think given how well thought out the Pure language is that it deserves a better concurrency model than "multi-threading".  :-)  I also think that the Pure language concurrency model should take a local and distributed view of the world, it should have a single model for multi-core/multi-processor/GPGPU/FPGA/ASIC and multi-system (or distributed) computation.  I'm an Erlang programmer by day and a Haskell hack at night with a strong background in transactional databases and distributed systems and I'm personally interested in seeing Pure set a new standard for exploiting available resources when performing computation in parallel, and I think it's mathematical underpinnings and functional nature might allow that to happen.

What then, if not threads?  I'll toss out an idea for the group to consider! Consider concurrency to be the default case while infering from the code where operations cannot be concurrent and then suggest methods for coordination.  This idea isn't really mine, it's based on what I see in the Bloom Language (http://www.bloom-lang.net/) which is based on research out of UC Berkeley called CALM (http://www.bloom-lang.net/calm/ http://databeta.wordpress.com/2010/10/28/the-calm-conjecture-reasoning-about-consistency/ http://boom.cs.berkeley.edu/papers.html).

Model the dependencies between data in operations as an evolving semi-lattice where at times you are forced to converge that lattice using the most efficient and appropriate coordination method for that case.  If you are not forced to converge, don't and run as many operations in parallel as possible given your scheduling algorithm of choice.

Bloom's Bud language (which is a Ruby DSL) uses two operators to indicate concurrency for it's list datatype, one with and one without the need for synchronization.  '<=' indicates that an operation needs to take place in the current time slice within the executing block and '<~' indicates that it's okay for this operation to happen in a later time slice as long as it happens eventually.  Take a second to read a bit on it here: http://www.bloom-lang.net/features/ and see if you agree.  One really amazing statement is, "Bud includes program analysis tools that can point out precise points of order in your program: lines of code where a coordination library should be plugged in if you want to ensure distributed consistency."  A compiler that can tell you ahead of time that, based on some analysis of your code paths, your program will require coordination at a particular location and then suggest some alternative methods for that orchestration.

Let's start with an example: fib.pure

$ cat fib.pure

extern int puts(char*);

do (puts.str) (take 1000 (fibs 0L 1L)) with fibs a b = a : fibs b (a+b) & end;

$ pure --analyze-coordination fib.pure

  = puts() is a external function call in libc and is considered to have side effects requiring coordination

  ~ fibs is recursive function consuming its result

  ~ take has no side effects

Start with the question, "What here cannot be executed in parallel, what requires coordination?" then examine the points where coordination is required and choose the most salient methods for each.  If in the future new methods of coordination are perfected, say someone adds CRDTs to Pure, then the existing program could run more execute more concurrently without any code changes. The analysis is done at compile time and the choice of coordination methods can happen dynamically at run-time and be informed by the scheduler.

IMHO, it would be sad to see a Pure not do something more interesting than basic thread/mutex concurrency.  It deserves better. :)

comments?

-greg

[Albert Graef]

Hi Gregory,

and welcome to the list! :)

On 02/20/2013 05:59 PM, Gregory Burd wrote:
> IMHO, it would be sad to see a Pure not do something more interesting
> than basic thread/mutex concurrency. It deserves better. :)

That was never the plan, we certainly want to offer something much
higher-level than pthreads. The approaches that I've been considering
are parallel maps and concurrent futures. Especially the latter seems a
good fit since Pure already has lazy futures.

We've also discussed the idea to add delimited continuations as an
abstraction for coroutines. That doesn't give you real parallelism, but
is somewhat easier to implement and would still be useful for some
applications in FRP like realtime processing of event streams (e.g.,
inside Pure's Pd external).

But I'm certainly open to other suggestions. Thanks for the interesting
links, I will have a deeper look before I reply to the remainder of your
post!

Albert

--
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email: Dr.G...@t-online.de, a...@muwiinfa.geschichte.uni-mainz.de
WWW: http://www.musikinformatik.uni-mainz.de/ag

[John Cowan]

Gregory Burd scripsit:

> I think given how well thought out the Pure language is that it deserves a
> better concurrency model than "multi-threading". :-) I also think that
> the Pure language concurrency model should take a local and distributed
> view of the world, it should have a single model for
> multi-core/multi-processor/GPGPU/FPGA/ASIC and multi-system (or
> distributed) computation.

It's important not to confuse support for concurrency (conceptually
simultaneous execution) with support for parallelism (physically
simultaneous execution). Programming languages need both, but not
necessarily using a single mechanism. See
<http://recycledknowledge.blogspot.com/2012/04/concurrency-vs-parallelism.html>
for an explanation of the difference.

> What then, if not threads? I'll toss out an idea for the group to
> consider! Consider concurrency to be the default case while infering from
> the code where operations cannot be concurrent and then suggest methods for
> coordination.

Pure code that is pure can be executed concurrently, but it's difficult to
automatically determine how much concurrency and how much parallelism are
actually useful. Too much is as bad as too little, as the speedup gets
devoured by coordination costs. In principle you could add 1024 numbers
using 512 processors in just ten steps, but bus contention would kill you.

> Bloom Language (http://www.bloom-lang.net/) which is based on research out
> of UC Berkeley called CALM (http://www.bloom-lang.net/calm/
> http://databeta.wordpress.com/2010/10/28/the-calm-conjecture-reasoning-about-consistency/
> http://boom.cs.berkeley.edu/papers.html).
>
> Model the dependencies between data in operations as an evolving
> semi-lattice where at times you are forced to converge that lattice using
> the most efficient and appropriate coordination method for that case. If
> you are not forced to converge, don't and run as many operations in
> parallel as possible given your scheduling algorithm of choice.
>

--
XQuery Blueberry DOM John Cowan
Entity parser dot-com co...@ccil.org
Abstract schemata http://www.ccil.org/~cowan
XPointer errata
Infoset Unicode BOM --Richard Tobin

[Albert Graef]

On 02/27/2013 08:40 PM, John Cowan wrote:
> It's important not to confuse support for concurrency (conceptually
> simultaneous execution) with support for parallelism (physically
> simultaneous execution).

I'd consider concurrency the more general concept, and I think we should
build Pure's concurrency features on a library which abstracts away the
scheduling issues. However, that depends on the approach chosen.

> Pure code that is pure can be executed concurrently, but it's difficult to
> automatically determine how much concurrency and how much parallelism are
> actually useful. Too much is as bad as too little, as the speedup gets
> devoured by coordination costs. In principle you could add 1024 numbers
> using 512 processors in just ten steps, but bus contention would kill you.

Yep, that's the problem with purely functional code; there are way too
many opportunities to parallelize. :) Therefore I'm leaning towards an
approach that lets the user decide, like concurrent futures. But there
might still be some idiomatic constructs like map-reduce (a.k.a.
map-fold) which could benefit from auto-parallelization.

Anyway, I've put up a little roadmap at
https://bitbucket.org/purelang/pure-lang/wiki/Roadmap. Feel free to add
to this page in order to clarify existing items or add new items which
you think are important for the future development of Pure.

[Gregory Burd]

Hey John,

On Wednesday, February 27, 2013 2:40:53 PM UTC-5, John Cowan wrote:

Gregory Burd scripsit:

> I think given how well thought out the Pure language is that it deserves a
> better concurrency model than "multi-threading".  :-)  I also think that
> the Pure language concurrency model should take a local and distributed
> view of the world, it should have a single model for
> multi-core/multi-processor/GPGPU/FPGA/ASIC and multi-system (or
> distributed) computation.  

It's important not to confuse support for concurrency (conceptually
simultaneous execution) with support for parallelism (physically
simultaneous execution).  Programming languages need both, but not
necessarily using a single mechanism.  See
<http://recycledknowledge.blogspot.com/2012/04/concurrency-vs-parallelism.html>
for an explanation of the difference.

I totally agree,I think Rob Pike hits the nail on the head on this topic (https://news.ycombinator.com/item?id=3837147) and I think that message is worth repeating over and over.  I'm not new to this dance, I've been in it for over 20 years (NeXT, Sun, JavaSoft, Oracle, Sleepycat, now Basho) and I know first hand how hard this problem is.  What I see in Pure is a great foundation that could really change the way people program.  I work in Erlang these days and I really find it fascinating how and almost-functional language with system that supports soft-real time concurrency makes a huge difference.  I like Erlang and Haskell but I don't see either of those languages breaking into the mainstream for the majority of programmers.  Right now Pure feels to me like the early days of Haskell, too much attention at this point could kill it (or at least slow it down).  I think the Dart Language team wanted exposure early in the process, but they are paying for it as they quickly catch up with a level of expectation set by Java and JavaScript these days... but I digress.

Your message, "concurrency and parallelism are different" - well yeah.  :-P

 

> What then, if not threads?  I'll toss out an idea for the group to
> consider! Consider concurrency to be the default case while infering from
> the code where operations cannot be concurrent and then suggest methods for
> coordination. 

Pure code that is pure can be executed concurrently, but it's difficult to
automatically determine how much concurrency and how much parallelism are
actually useful.  Too much is as bad as too little, as the speedup gets
devoured by coordination costs.  In principle you could add 1024 numbers
using 512 processors in just ten steps, but bus contention would kill you.

That's the point of this research that I referenced.  Semi-lattices are used to govern the major datatypes as they are operated on in parallel, this is paper should answer most of your questions:

http://db.cs.berkeley.edu/papers/UCB-lattice-tr.pdf

The point is that when you have 512 processors and a nice representation of your program's execution decorated such that you know where it is side-effect free and where it isn't then you can create any number of plans that could be executed in parallel with minimal coordination, minimal bus contention.  In fact, you could have dozens of different coordination techniques (like garbage collection algorithms) known to the runtime and it could choose (or you could hint at) the most appropriate for a given execution path that requires coordination.  That's the point.

Most other languages/systems implement a particular approach ("we use actors", "we use threads/locks", "we use futures", etc.) and then the programmer is bound to that for all programs in that language.  This approach would say, "functional programs are inherently concurrent except where side effects dictate that they be coordinated by the runtime".

Did that make sense?  I hope so.

So, what I was advocating was to see if we could map the concepts into Pure and do something a bit harder but I think vastly more useful that futures or other approaches to concurrent programming.

$0.02,

-greg

[John Cowan]

Gregory Burd scripsit:

> I'm not new to this dance, I've been in it for over 20 years (NeXT,
> Sun, JavaSoft, Oracle, Sleepycat, now Basho) and I know first hand how
> hard this problem is.

Sorry, I didn't mean to try to teach you to suck eggs. There are just
so many people who are fired up by the Upcoming 16,384-Core Palmtop
Machine and how it will be a *waste*, just a criminal *waste* not to use
all cores at all times in all situations, that I have become wary (and
weary) of those who speak of This Thing Called Parallelism.

> That's the point of this research that I referenced. Semi-lattices
> are used to govern the major datatypes as they are operated on in
> parallel, this is paper should answer most of your questions:
>
> http://db.cs.berkeley.edu/papers/UCB-lattice-tr.pdf

Enqueued for reading. Right now I'm working my way through the MS stuff
on concurrent revisions and cloud types:

http://research.microsoft.com/apps/pubs/default.aspx?id=145511

http://research.microsoft.com/apps/pubs/default.aspx?id=163842

The idea of concurrent revisions is very cool: each forked thread has
its own copy of all state (implemented by copy-on-write), but when you
join a thread to you, its state overrides yours (unlike with processes
where the child thread's state is discarded). Furthermore, you can join
any thread, whether you forked it or not. An extension allows selective
merger of state between the joining and joined threads.

> In fact, you could have dozens of different coordination techniques
> (like garbage collection algorithms) known to the runtime and it
> could choose (or you could hint at) the most appropriate for a given
> execution path that requires coordination.

But then you need a rather sophisticated hint language to specify what
kind of results you want, no?

--
The Unicode Standard does not encode John Cowan
idiosyncratic, personal, novel, or private http://www.ccil.org/~cowan
use characters, nor does it encode logos
or graphics. co...@ccil.org

[Gregory Burd]

Here is another interesting article on CALM and it's application to concurrent systems. [1]

This quote: "Any code that fails CALM tests is a candidate for stronger coordination mechanisms." is very interesting to me.  In this context it seems to me that we could build into the compiler and runtime of pure an ability to identify code paths which don't meet the constraints of CALM.  In those cases you could choose from a number of generic coordination methods ranging from stop-the-world to CRDTs and including things like 2PC, PAXOS, etc.  Programmers, or the pure language runtime, could then choose a coordination method for these cases.  As the state of the art in coordination changes over time new methods could be added and existing programs would benefit without modification.  This is in contrast to other concurrency methods such as futures where you've locked programmers into a methodology where they themselves must design into their application code the method(s) for coordination.  From Wikipedia: "In computer science, future, promise, and delay refer to constructs used for synchronizing..." [2] (if you hold that to be a definitive reference on the topic) we see that futures create the potential for an asynchronous concurrent environment where shared state must be explicitly managed ("constructs used for synchronizing") in program code.  Futures are a good design, and a popular one too (see all the languages at the bottom of [2] which implement this design pattern), but if added to pure those using the pure language will have the same issues when dealing with concurrency as all those other languages mentioned.  Programmers would explicitly have to manage concurrency by learning and implementing one or more of a today's very complex designs for coordination.  That's error prone work that is all too often simply punted on by programmers due to lack of understanding, its complexity, or lack of time to "do the right thing".

If pure can break from the pack and offer a more future proof concurrency model in addition to its other advanced features I think that more people would be interested in using it for more complex systems.

just my $0.02, I'll shut up now  :-)

[1] http://queue.acm.org/detail.cfm?id=2462076

[2] http://en.wikipedia.org/wiki/Futures_and_promises