[m-rev.] for review: Add barriers (for concurrency) to the standard library

[Paul Bone]

For review by anyone

Branches: master

---

Add barriers (for concurrency) to the standard library

Mission Critical IT has maintained a library of code for concurrent
programming.  We're happy to contribute this upstream to the Mercury
project starting with this module implementing barriers.

library/thread.barrier.m:
    Add the new module implementing barriers.

library/thread.m:
library/library.m:
    Add new module.

NEWS:
    Announce the new module.
---
 NEWS                     |   8 +++-
 library/library.m        |   3 +-
 library/thread.barrier.m | 122 +++++++++++++++++++++++++++++++++++++++++++++++
 library/thread.m         |   8 ++--
 4 files changed, 135 insertions(+), 6 deletions(-)
 create mode 100644 library/thread.barrier.m

diff --git a/NEWS b/NEWS
index 5c79e34..45c8c50 100644
--- a/NEWS
+++ b/NEWS
@@ -15,8 +15,12 @@ Changes to the Mercury standard library:
 * io.print and string_writer.print now print arbitrary precision integers
   in their decimal form instead of printing their underlying representation.
 
-* We have added a module for discrete interval encoding trees,
-  which are a highly efficient set implementation for fat sets.
+* We have added a module for discrete interval encoding trees, which are a
+  highly efficient set implementation for fat sets.  This module is a
+  contribution from Yes Logic Pty. Ltd.
+
+* We have added a module that implements barriers for concurrent
+  programming.  This module is a contribution from Mission Critical IT.
 
 Changes to the extras distribution:
 
diff --git a/library/library.m b/library/library.m
index 59daa61..e490443 100644
--- a/library/library.m
+++ b/library/library.m
@@ -1,7 +1,7 @@
 %---------------------------------------------------------------------------%
 % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
 %---------------------------------------------------------------------------%
-% Copyright (C) 1993-2007, 2009-2012 The University of Melbourne.
+% Copyright (C) 1993-2007, 2009-2014 The University of Melbourne.
 % This file may only be copied under the terms of the GNU Library General
 % Public License - see the file COPYING.LIB in the Mercury distribution.
 %---------------------------------------------------------------------------%
@@ -299,6 +299,7 @@ mercury_std_library_module("term_to_xml").
 mercury_std_library_module("test_bitset").
 mercury_std_library_module("time").
 mercury_std_library_module("thread").
+mercury_std_library_module("thread.barrier").
 mercury_std_library_module("thread.channel").
 mercury_std_library_module("thread.mvar").
 mercury_std_library_module("thread.semaphore").
diff --git a/library/thread.barrier.m b/library/thread.barrier.m
new file mode 100644
index 0000000..430872d
--- /dev/null
+++ b/library/thread.barrier.m
@@ -0,0 +1,122 @@
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2005, 2014 Mission Critical IT.
+% Copyright (C) 2014 The Mercury team.
+% This file may only be copied under the terms of the GNU Library General
+% Public License - see the file COPYING.LIB in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File: thread.barrier.m
+% Original author: Peter Ross
+% Stability: new
+%
+% This module provides a barrier implementation.
+%
+% A barrier is a position in a program that any thread (of N threads) must
+% be suspended at until all the other threads (of N) reach the same
+% position.
+%
+% Barriers are represented by calls to barrier/3 (defined below).  Different
+% code locations can belong to the same conceptual barrier using values of
+% type barrier.  The same code location can also be used by multiple
+% barriers by supplying different values.
+%
+% TODO:
+%
+%   In some grades it may be possible to improve performance by writing
+%   this natively rather than using mvar.
+%
+%   A semaphore may be better for the "go" signal than an mvar.
+%
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- module thread.barrier.
+
+:- interface.
+
+:- import_module io.
+
+:- type barrier.
+
+    % init(N, Barrier, !IO)
+    %
+    % Create a barrier for N threads.
+    %
+:- pred init(int::in, barrier::out, io::di, io::uo) is det.
+
+    % barrier(Barrier, !IO)
+    %
+    % Indicate that the current thread has reached the barrier.
+    %
+:- pred barrier(barrier::in, io::di, io::uo) is det.
+
+    % release_barrier(Barrier, !IO)
+    %
+    % Release all the threads waiting at the barrier regardless
+    % of whether or not N threads have arrived at the barrier.
+    %
+:- pred release_barrier(barrier::in, io::di, io::uo) is det.
+
+%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module int.
+:- import_module require.
+:- import_module string.
+:- import_module thread.mvar.
+:- import_module unit.
+
+%------------------------------------------------------------------------------%
+
+:- type barrier
+    --->    barrier(
+                % How many threads we are still waiting on?
+                b_waiting_for   :: mvar(int),
+
+                % Can we go yet?
+                b_go            :: mvar(unit)
+            ).
+
+%------------------------------------------------------------------------------%
+
+init(N, barrier(WaitingOn, Go), !IO) :-
+    init(WaitingOn, !IO),
+    init(Go, !IO),
+    put(WaitingOn, N, !IO).
+
+%------------------------------------------------------------------------------%
+
+barrier(barrier(WaitingOn, Go), !IO) :-
+    take(WaitingOn, N, !IO),
+    StillWaitingFor = N - 1,
+
+    ( StillWaitingFor > 0 ->
+        % There are still outstanding threads.
+        
+        % Unlock the counter
+        put(WaitingOn, StillWaitingFor, !IO),
+
+        % Wait on the barrier then unlock another thread.
+        take(Go, _, !IO),
+        put(Go, unit, !IO)
+    ; StillWaitingFor = 0 ->
+        % The last thread at the barrier, so signal that we can go.
+        put(Go, unit, !IO),
+        put(WaitingOn, StillWaitingFor, !IO)
+    ;
+        unexpected($pred,
+            "Too many threads called barrier/3 on this barrier.")
+    ).
+
+release_barrier(barrier(WaitingOn, Go), !IO) :-
+    % Allow all the threads at the barrier to go.
+    put(Go, unit, !IO),
+    take(WaitingOn, N, !IO),
+    put(WaitingOn, N - 1, !IO).
+
+%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
diff --git a/library/thread.m b/library/thread.m
index 30ff338..9d282f3 100644
--- a/library/thread.m
+++ b/library/thread.m
@@ -1,7 +1,8 @@
 %-----------------------------------------------------------------------------%
 % vim: ft=mercury ts=4 sw=4 et
 %-----------------------------------------------------------------------------%
-% Copyright (C) 2000-2001,2003-2004, 2006-2008, 2010-2011 The University of Melbourne.
+% Copyright (C) 2000-2001, 2003-2004, 2006-2008, 2010-2011, 2014 The
+% University of Melbourne.
 % This file may only be copied under the terms of the GNU Library General
 % Public License - see the file COPYING.LIB in the Mercury distribution.
 %-----------------------------------------------------------------------------%
@@ -12,9 +13,9 @@
 %
 % This module defines the Mercury concurrency interface.
 %
-% The term `concurrency' here refers to threads, not necessarily to parallel
+% The term `concurrency' refers to threads, not necessarily to parallel
 % execution.  (The latter is also possible if you are using one of the .par
-% grades and the lowlevel C backend, e.g. grade asm_fast.par.gc).
+% grades or the java or csharp backends.)
 %
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
@@ -24,6 +25,7 @@
 
 :- import_module io.
 
+:- include_module barrier.
 :- include_module channel.
 :- include_module mvar.
 :- include_module semaphore.
-- 
1.9.1