MaPLe (MPL)

MaPLe is a functional language for provably efficient and safe multicore
parallelism.

Features:

Support for the full Standard ML programming language, extended with
task-parallel and data-parallel primitives.
Native performance on both x86 and Arm architectures.
Whole-program compilation based on MLton,
with aggressive optimizations to achieve performance competitive
with languages such as C/C++.
Efficient memory representations, including:
- Untagged and unboxed native integers and floating-point numbers.
- Flattened tuples and records.
- Native arrays with contiguous unboxed elements.
Simple and fast foreign-function calls into C, based on
MLtonFFI.
Support for both regular and irregular fine-grained parallelism,
with provably efficient automatic parallelism management [7]
to control the overheads of task creation.
Provably efficient parallel garbage collection based on
hierarchical memory management and disentanglement
[1,2,3,4,5,6].
Support for large core counts and large memory sizes. MPL scales to hundreds
of cores, and can efficiently handle heap sizes of as much as 1TB or more.

MPL is being actively developed. If you are interested in contributing to
the project, PRs are welcome!

If you are you interested in using MPL, consider checking
out the tutorial.
You might also be interested in exploring
mpllib
(a library for MPL) and the
Parallel ML benchmark suite.

References

[7]
Automatic Parallelism Management.
Sam Westrick, Matthew Fluet, Mike Rainey, and Umut A. Acar.
POPL 2024.

[6]
Efficient Parallel Functional Programming with Effects.
Jatin Arora, Sam Westrick, and Umut A. Acar.
PLDI 2023.

[5]
Entanglement Detection with Near-Zero Cost.
Sam Westrick, Jatin Arora, and Umut A. Acar.
ICFP 2022.

[4]
Provably Space-Efficient Parallel Functional Programming.
Jatin Arora, Sam Westrick, and Umut A. Acar.
POPL 2021.

[3]
Disentanglement in Nested-Parallel Programs.
Sam Westrick, Rohan Yadav, Matthew Fluet, and Umut A. Acar.
POPL 2020.

[2]
Hierarchical Memory Management for Mutable State.
Adrien Guatto, Sam Westrick, Ram Raghunathan, Umut Acar, and Matthew Fluet.
PPoPP 2018.

[1]
Hierarchical Memory Management for Parallel Programs.
Ram Raghunathan, Stefan K. Muller, Umut A. Acar, and Guy Blelloch.
ICFP 2016.

Try It Out

Instructions for installing MPL natively (on Linux or Mac) are further below.

If you want to quickly try out using MPL, you can download the Docker image and
run one of the examples.

$ docker pull shwestrick/mpl
$ docker run -it shwestrick/mpl /bin/bash
...# examples/bin/primes @mpl procs 4 --

To write and compile your own code, we recommend
mounting a local directory inside the container. For example, here’s how you
can use MPL to compile and run your own main.mlb in the current directory.
(To mount some other directory, replace $(pwd -P) with a different path.)

$ ls
main.mlb
$ docker run -it -v $(pwd -P):/root/mycode shwestrick/mpl /bin/bash
...# cd /root/mycode
...# mpl main.mlb
...# ./main @mpl procs 4 --

Benchmark Suite

The Parallel ML benchmark suite
provides many examples of sophisticated parallel algorithms and
applications in MPL, as well as cross-language performance comparisons with
C++, Go, Java,
and multicore OCaml.

Libraries and Projects

We recommend using the smlpkg package
manager. MaPLe supports the full SML language, so existing libraries for
SML can be used.

Here are a few libraries and projects that make use of MaPLe for parallelism:

github.com/MPLLang/mpllib: grab-bag
library with a variety of data structures (sequences, sets, dictionaries,
graphs, matrices, meshes, images, etc.) and parallel algorithms
(map, reduce, scan, filter, sorting, search, tokenization, graph processing,
computational geometry, etc.). Also includes basic utilies
(e.g. parsing command-line arguments) and benchmarking infrastructure.
github.com/shwestrick/sml-audio:
a library for audio processing and I/O support for .wav files.
github.com/shwestrick/sml-matrix-market:
a library for parsing MatrixMarket files
github.com/shwestrick/mpl-seam-carve:
image resizing by seam carving,
demonstrating parallelism in MaPLe.
github.com/shwestrick/mpl-wc:
a simple clone of the Unix wc utility demonstrating parallelism in MaPLe.
github.com/shwestrick/mpl-1brc:
an example solution to the 1 Billion Row Challenge,
demonstrating some features of MaPLe.
github.com/shwestrick/mpl-tinykaboom:
a port of a port (Futhark) of the
KABOOM (C++) tiny graphics program.
github.com/UmutAcarLab/grafeyn:
a hybrid Feynman-Schrödinger pure quantum simulator written in MaPLe.

Parallel and Concurrent Extensions

MaPLe extends SML with a number of primitives for parallelism and concurrency.
Take a look at examples/ to see these primitives in action.

The `ForkJoin` Structure

val par: (unit -> 'a) * (unit -> 'b) -> 'a * 'b
val parfor: int -> (int * int) -> (int -> unit) -> unit
val alloc: int -> 'a array
val parform: (int * int) -> (int -> unit) -> unit
val reducem: ('a * 'a -> 'a) -> 'a -> (int * int) -> (int -> 'a) -> 'a

The par primitive takes two functions to execute in parallel and
returns their results.

The parfor primitive is a “parallel for loop”. It takes a grain-size g, a
range (i, j), and a function f, and executes f(k) in parallel for each
i <= k < j. The grain-size g is for manual granularity
control: parfor splits the input range into approximately (j-i)/g subranges,
each of size at most g, and each subrange is processed sequentially. The
grain-size must be at least 1, in which case the loop is “fully parallel”.
Note: This function should only be used if a reasonable grain size can be
passed as argument. This is often cumbersome.
In general, we recommend using parform instead (described below).

The alloc primitive takes a length and returns a fresh, uninitialized array
of that size. Warning: To guarantee no errors, the programmer must be
careful to initialize the array before reading from it. alloc is intended to
be used as a low-level primitive in the efficient implementation of
high-performance libraries. It is integrated with the scheduler and memory
management system to perform allocation in parallel and be safe-for-GC.

The parform primitive is a parallel for loop, similar to parfor above,
except with no grain parameter. The parallelism of the loop is automatically
managed. In general, we recommend using parform instead of parfor.

The reducem primitive performs an automatically managed parallel reduction.
It takes a “sum” function c, a “zero” element z, a range (i,j), and
a function f, and computes the “sum” of [f(i), ..., f(j-1)] in parallel
with respect to c. For example:

reduce op+ 0 (0, Array.length a) (fn i => Array.sub (a, i)) computes the
sum of an array a
reduce Real.max Real.negInf (0, n) (fn i => f (Real.fromInt i / Real.fromInt n))
samples a function f: real -> real at n evenly-spaced locations in
the range [0.0, 1.0] to find the maximum value.

The `MLton.Parallel` Structure

val compareAndSwap: 'a ref -> ('a * 'a) -> 'a
val arrayCompareAndSwap: ('a array * int) -> ('a * 'a) -> 'a
val fetchAndAdd: int ref -> int -> int
val arrayFetchAndAdd: int array * int -> int -> int

compareAndSwap r (x, y) performs an atomic
CAS
which attempts to atomically swap the contents of r from x to y,
returning the original value stored in r before the CAS.
Polymorphic equality is determined
in the same way as MLton.eq, which is a
standard equality check for simple types (char, int, word, etc.) and
a pointer equality check for other types (array, string, tuples, datatypes,
etc.). The semantics are a bit murky.

arrayCompareAndSwap (a, i) (x, y) behaves the same as compareAndSwap but
on arrays instead of references. This performs a CAS at index i of array
a, and does not read or write at any other locations of the array.

fetchAndAdd r d performs an atomic fetch-and-add
which atomically retrieves and the value of the specified memory cell r
adds d to it, returning the original value stored in r before the update.

arrayFetchAndAdd (a, i) d behaves the same as fetchAndAdd except on
arrays instead of references. It performs a fetch-and-add at index i of
array a, and does not read or write at any other locations of the array.

Using MPL

MPL uses .mlb files (ML Basis) to describe
source files for compilation. A typical .mlb file for MPL is shown
below. The first three lines of this file respectively load:

The SML Basis Library
The ForkJoin structure, as described above
The MLton structure, which includes the MPL extension
MLton.Parallel as described above, as well as various
MLton-specific features. Not all MLton
features are supported (see “Unsupported MLton Features” below).
```
( libraries )
$(SML_LIB)/basis/basis.mlb
$(SML_LIB)/basis/fork-join.mlb
$(SML_LIB)/basis/mlton.mlb

( your source files… )
A.sml
B.sml


### Compiling a Program
The command to compile a `.mlb` is as follows. By default, MPL
produces an executable with the same base name as the source file, i.e.
this would create an executable named `foo`:

$ mpl [compile-time options…] foo.mlb


MPL has a number of compile-time options derived from MLton, which are
documented [here](http://mlton.org/CompileTimeOptions). Note that MPL only
supports C codegen and does not support profiling.
Some useful compile-time options are
* `-output <NAME>` Give a specific name to the produced executable.
* `-default-type int64 -default-type word64` Use 64-bit integers and words
by default.
* `-debug true -debug-runtime true -keep g` For debugging, keeps the generated
C files and uses the debug version of the runtime (with assertions enabled).
The resulting executable is somewhat peruse-able with tools like `gdb`.
For example:

$ mpl -default-type -int64 -output foo sources.mlb


### Running a Program
MPL executables can take options at the command line that control the run-time
system. The syntax is

$ [@mpl [run-time options…] —] [program args…]

The runtime arguments must begin with `@mpl` and end with `--`, and these are
not visible to the program via
[CommandLine.arguments](http://sml-family.org/Basis/command-line.html).
Some useful run-time options are
* `procs <N>` Use `N` worker threads to run the program.
* `set-affinity` Pin worker threads to processors. Can be used in combination
with `affinity-base <B>` and `affinity-stride <S>` to pin thread `i` to
processor number `B + S*i`.
* `block-size <X>` Set the heap block size to `X` bytes. This can be
written with suffixes K, M, and G, e.g. `64K` is 64 kilobytes. The block-size
must be a multiple of the system page size (typically 4K). By default it is
set to one page.
For example, the following runs a program `foo` with a single command-line
argument `bar` using 4 pinned processors.

$ foo @mpl procs 4 set-affinity — bar


## Bugs and Known Issues
### Basis Library
The basis library is inherited from (sequential) SML. It has not yet been 
thoroughly scrubbed, and some functions may not be safe for parallelism
([#41](https://github.com/MPLLang/mpl/issues/41)).
### Garbage Collection
* ([#115](https://github.com/MPLLang/mpl/issues/115)) The GC is currently
disabled at the "top level" (outside any calls to `ForkJoin.par`).
For highly parallel programs, this has generally not been a problem so far,
but it can cause a memory explosion for programs that are mostly (or entirely)
sequential.
## Unsupported MLton Features
Many [MLton-specific features](http://mlton.org/MLtonStructure) are
unsupported, including (but not limited to):
* `share`
* `shareAll`
* `size`
* `Finalizable`
* `Profile`
* `Signal`
* `Thread` (partially supported but not documented)
* `Cont` (partially supported but not documented)
* `Weak`
* `World`
## Build and Install (from source)
### Requirements
MPL can be installed natively on Linux (x86-64) or Mac (x86-64 or Arm),
including Apple Silicon chips (M1, M2, M3, etc.)
The following software is required.
 * [GCC](http://gcc.gnu.org)
 * [GMP](http://gmplib.org) (GNU Multiple Precision arithmetic library)
 * [GNU Make](http://savannah.gnu.org/projects/make), [GNU Bash](http://www.gnu.org/software/bash/)
 * binutils (`ar`, `ranlib`, `strip`, ...)
 * miscellaneous Unix utilities (`diff`, `find`, `grep`, `gzip`, `patch`, `sed`, `tar`, `xargs`, ...)
 * Standard ML compiler and tools:
   - Recommended: [MLton](http://mlton.org) (`mlton`, `mllex`, and `mlyacc`).  Pre-built binary packages for MLton can be installed via an OS package manager or (for select platforms) obtained from http://mlton.org.
   - Supported but not recommended: [SML/NJ](http://www.smlnj.org) (`sml`, `ml-lex`, `ml-yacc`).
 * (If using [`mpl-switch`](https://github.com/mpllang/mpl-switch)): Python 3, and `git`.
### Installation with `mpl-switch` (Mac and Linux)
The [`mpl-switch`](https://github.com/mpllang/mpl-switch) utility makes it
easy to install multiple versions of MPL on the same system and switch
between them:
```bash
$ git clone https://github.com/mpllang/mpl-switch
# ... add ./mpl-switch/ to your PATH ...
$ mpl-switch init
$ mpl-switch install v0.5.3
$ mpl-switch select v0.5.3
# MPL is now installed at ~/.mpl/bin/mpl
# final step: add ~/.mpl/bin/ to your PATH

You can use any commit hash or tag name from the MPL repo to pick a
particular version of MPL. Installed versions are stored in ~/.mpl/; this
folder is safe to delete at any moment, as it can always be regenerated. To
see what versions of MPL are currently installed, do:

$ mpl-switch list

Manual Instructions (Linux)

You can manually build mpl by cloning this repo and then performing the following.

Build the executable. This produces an executable at build/bin/mpl:

$ make

Put it where you want it. After building, MPL can then be installed
to a custom directory with the PREFIX option:

$ make PREFIX=/opt/mpl install

Note: At the moment, we do not recommend doing make install without
setting PREFIX=..., because this can clobber an existing installation of
MLton. (See issue #170.)

Manual Instructions (Mac)