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

[Julien Fischer]

Hi Paul,

On Thu, 3 Apr 2014, Paul Bone wrote:

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

...

> 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

Stability should be one of {low,medium,high}.  It should probably be low
for now.

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

I suggest shifting this TODO list down to the beginning of the
implementation section.


> +%-----------------------------------------------------------------------------%
> +%-----------------------------------------------------------------------------%
> +
> +:- module thread.barrier.
> +
> +:- interface.

Delete the blank line between the :- module and :- interface
declarations.

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

I prefer the name wait/3 (as with barriers in POSIX threads).  (We also
use that name for the equivalent operation on semaphores, so it would be
more consistent.)

You should also document what happens if more than N threads call this,
i.e. it calls throws a software_error/1 exception.

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

I suggest s/release_barrier/release/

> +%------------------------------------------------------------------------------%
> +%------------------------------------------------------------------------------%
> +
> +:- 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.")
> +    ).

Call unexpected/3 there with $file as the first argument.

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


I suggest:

     not necessarily to parallel execution of those threads.

(Just to make it clear what sort of parallelism is being talked about.)

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

... Java or C# backends.

(The lowercase versions are the grades.)

Cheers,
Julien.