[m-rev.] diff 1/2: Add barriers (for concurrency) to the standard library

[Paul Bone]

This has already been reviewed.  But that was a while ago so I'm sending it
to the list now while I'm committing it.  Thanks.

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

library/thread.semaphore.m:
    Add a comment.
---
 NEWS                       |   8 ++-
 library/library.m          |   3 +-
 library/thread.barrier.m   | 123 +++++++++++++++++++++++++++++++++++++++++++++
 library/thread.m           |  10 ++--
 library/thread.semaphore.m |   1 +
 5 files changed, 138 insertions(+), 7 deletions(-)
 create mode 100644 library/thread.barrier.m

diff --git a/NEWS b/NEWS
index bece4a9..92c40b0 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..508fd44
--- /dev/null
+++ b/library/thread.barrier.m
@@ -0,0 +1,123 @@
+%-----------------------------------------------------------------------------%
+% 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: low
+%
+% 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.
+%
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- 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.
+
+    % wait(Barrier, !IO)
+    %
+    % Indicate that the current thread has reached the barrier.  Throws a
+    % software_error/1 exception if this barrier has been used by more than
+    % N threads.
+    %
+:- pred wait(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::in, io::di, io::uo) is det.
+
+%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
+
+:- implementation.
+
+% 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.
+
+:- 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).
+
+%------------------------------------------------------------------------------%
+
+wait(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($file, $pred,
+            "Too many threads called barrier/3 on this barrier.")
+    ).
+
+release(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..385bf06 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
-% 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).
+% The term `concurrency' refers to threads, not necessarily to parallel
+% execution of those threads.  (The latter is also possible if you are using
+% one of the .par grades or the Java or C# backends.)
 %
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
@@ -24,6 +25,7 @@
 
 :- import_module io.
 
+:- include_module barrier.
 :- include_module channel.
 :- include_module mvar.
 :- include_module semaphore.
diff --git a/library/thread.semaphore.m b/library/thread.semaphore.m
index ea52d8d..7058105 100644
--- a/library/thread.semaphore.m
+++ b/library/thread.semaphore.m
@@ -207,6 +207,7 @@ ML_finalize_semaphore(void *obj, void *cd)
         MR_schedule_context(ctxt);
 
         /* yield() */
+        /* This context switch can be done more directly and faster */
         MR_save_context(MR_ENGINE(MR_eng_this_context));
       #ifdef ML_THREAD_AVOID_LABEL_ADDRS
         MR_ENGINE(MR_eng_this_context)->MR_ctxt_resume =
-- 
2.0.0.rc0