Skip to content

TaskParallelism

Jump to bottom
Pascal Costanza edited this page Aug 24, 2017 · 6 revisions

Task-based parallelism

1. Packages parallel, speculative, and sequential

1.1. Package parallel

The package parallel provides functions for expressing task-based parallel algorithms, by spawning each task in its own goroutine, and managing task synchronization and panics implicitly to make the semantics similar to a sequential execution of the same program. (Parallelism is not concurrency. Unlike in concurrent programming, mimicking sequential semantics is actually desirable to a certain extent when using parallelism to speed up otherwise sequential algorithms.)

1.2. Package speculative

Some of the functions are also available as speculative variants in the speculative package. The implementations in the parallel package always wait for all spawned tasks to terminate, whereas the implementations in the speculative package terminate earlier if they can.

While functions in the speculative package may terminate early, they do not proactively stop the execution of the spawned goroutines. To ensure that compute resources are freed up in such cases, user programs need to use some other safe form of communication to gracefully stop their execution, for example by using the cancelation feature of Go's context package. (Any such additional communication is likely to add additional performance overhead, which may not be desirable and which is why this is not done by default.)

1.3. Package sequential

All functions are also available as purely sequential implementations in the sequential package, which are useful for testing and debugging. (It is not recommended to use the implementations of the sequential package for any other purpose, because they are almost certainly too inefficient for regular sequential programs.)

2. Functions Do, And, and Or

Function Parameters Results also speculative?
Do ...Thunk --- no
ErrDo ...ErrThunk error yes
And ...Predicate bool yes
ErrAnd ...ErrPredicate bool, error yes
Or ...Predicate bool yes
ErrOr ...ErrPredicate bool, error yes

2.1. Basic variants

Do, And, and Or are useful for executing two or more tasks in parallel, by invoking them each in their own goroutine. Do does this for tasks implemented as functions without return values. And and Or do this for predicates that return boolean values, and combine these return values with the && or || operator.

2.2. Err-variants

ErrDo, ErrAnd, and ErrOr are like Do, And, and Or, except that the spawned tasks can additionally also return error values. If any task returns an error value different from nil, the left-most of those non-nil error value is returned by ErrDo, ErrAnd, or ErrOr (in addition to the primary return value in the case of ErrAnd and ErrOr).

2.3. speculative variants

parallel.Do, parallel.ErrDo, parallel.And, parallel.ErrAnd, parallel.Or, and parallel.ErrOr wait for all spawned tasks to terminate before returning.

The speculative package additionally provides the following variants:

  • speculative.ErrDo terminates early if any of the spawned tasks returns an error value different from nil.
  • speculative.And and speculative.Or terminate early if the final return value is known early (if any of the spawned predicates returns false for And, or true for Or).
  • speculative.ErrAnd and speculative.ErrOr terminate early both if the final return value is known early, or if any predicate returns a non-nil error value.

3. Functions Range, RangeAnd, RangeOr, and RangeReduce

The Range-functions described below are useful for expressing parallel algorithms over slices, or other domains that can be covered by a range of consecutive integers. They all receive a range and a single range function, divide the range up into subranges, and spawn the range function for each of these subranges. Some of the functions described below also combine return values of the subrange tasks into an overall result, and do so in parallel.

Function Parameters Results also speculative?
Range low, high, n int, f RangeFunc none no
ErrRange low, high, n int, f ErrRangeFunc error yes
RangeAnd low, high, n int, f RangePredicate bool yes
ErrRangeAnd low, high, n int, f ErrRangePredicate bool, error yes
RangeOr low, high, n int, f RangePredicate bool yes
ErrRangeOr low, high, n int, f ErrRangePredicate bool, error yes
RangeReduce low, high, n int, reduce RangeReducer, pair PairReducer interface{} no
ErrRangeReduce low, high, n int, reduce ErrRangeReducer, pair ErrPairReducer interface{}, error yes
IntRangeReduce low, high, n int, reduce IntRangeReducer, pair IntPairReducer int no
ErrIntRangeReduce low, high, n int, reduce ErrIntRangeReducer, pair ErrIntPairReducer int, error yes
Float64RangeReduce low, high, n int, reduce Float64RangeReducer, pair Float64PairReducer float64 no
ErrFloat64RangeReduce low, high, n int, reduce ErrFloat64RangeReducer, pair ErrFloat64RangeReducer float64, error yes
StringRangeReduce low, high, n int, reduce StringRangeReducer, pair StringPairReducer string no
ErrStringRangeReduce low, high, n int, reduce ErrStringRangeReducer, pair ErrStringPairReducer string, error yes

3.1. Ranges

The range is always specified by a low and high integer, with low <= high, and the functions will cover the half-open interval ranging from low to high, including low but excluding high.

The n parameter can typically be set to 0. It is used to determine how the size of the overall range high - low is divided up over the available worker threads. If n is 0, a reasonable default is chosen that typically works well. If n is greater than 0, the size of the overall range high - low is divided by n. (This means that n tasks are spawned. Quite often, n should be larger than the number of available worker threads to improve load balancing. Passing 0 for n ensures that this is taken into account.)

The subrange functions that are passed by user programs as parameters receive a low and high integer specifying the respective subrange, with low <= high. They should in turn cover the respective half-open interval ranging from low to high, including low but excluding high, and usually do so sequentially with a simple for loop.

3.2. Basic variants

Range, RangeAnd, and RangeOr are similar to Do, And, and Or, except they receive a range and a single range function each. They divide the range up into subranges and spawn the range function for each of these subranges. RangeAnd and RangeOr additionally combine the boolean return values of the range predicates with the && or || operator.

RangeReduce is similar to RangeAnd and RangeOr, except that the results are of type interface{} instead of bool, and the results are combined using another function that is explicitly passed as a parameter. IntRangeReduce, Float64RangeReduce, and StringRangeReduce can be used in case it is known that the result types are int, float64, or string respectively.

3.3. Err-variants

ErrRange, ErrRangeAnd, ErrRangeOr, ErrRangeReduce, ErrIntRangeReduce, ErrFloat64RangeReduce, and ErrStringRangeReduce behave like the corresponding non-Err-variants above, except that the subrange functions can additionally also return error values. If any subrange function returns an error value different from nil, the left-most of those non-nil error value is returned.

3.4. speculative variants

parallel.Range, parallel.RangeAnd, parallel.RangeOr, parallel.RangeReduce, parallel.IntRangeReduce, parallel.Float64RangeReduce, parallel.StringRangeReduce, and their corresponding Err-variants, wait for all spawned tasks to terminate before returning.

The speculative package additionally provides the following variants:

4. Panics

All of the functions from the parallel package described above also take care of dealing with panics: If one or more of the tasks spawned by a parallel function panics, the panic is recovered in the corresponding goroutine, and the parallel function then panics with the left-most of the recovered panic values.

The handling of panics is done left-to-right to ensure that the behavior is semantically similar to a corresponding sequential left-to-right execution, just as is the case with error values.

Hoever, functions in the speculative package may not propagate panics from one task in case they terminate early because of a known return value or a non-nil error value originating from a different task. See the documentations of the speculative functions for more precise details of the semantics.

Clone this wiki locally