std/parallel/lib

A collection that cuts itself into pieces without being read first: its length, and the piece of it the positions of a range cover. parallel() cuts one into chunks by its length alone; anything else is read into a list first.

Piece is whatever carries a part of the collection best - a List and an Array answer an ArrayList of the items, which a worker may take as it is, and a Range of integers answers a smaller range, so cutting it costs two additions. What a chunk crosses to another worker as is the piece, which is why it is a type of its own rather than Self.

type Stretch with Cut<Int, Range<Int>> {
  first: Int
  count: Int

  fn iterate(): Iterator<Int> {
    (first..(first + count)).iterate()
  }

  fn length(): Int {
    count
  }

  fn cut(range: Range<Int>): Range<Int> {
    (first + range.start)..(first + range.end)
  }
}

print Stretch(5, 10).parallel().sum().await()

• The piece has to hold the same items, in the same order, as iterating the collection over those positions: the answer of parallel() is the sequential one only if cutting and iterating agree.

A list cuts into lists of its items: a piece holds nothing the list holds, so a worker may take it as it is.

An array cuts into lists of its items, the way a list does.

A range of integers cuts into smaller ranges: position index is the value start + index.

Spreads a pipeline over the workers: anything that can be iterated.

Spreads a collection that cuts itself over the workers, without reading it first.

Spreads a list over the workers. A list is a Cut, and this is that parallel() again: a value of the List trait cannot be handed over as a value of Cut - Cut is implemented for List and is no supertrait of it, so no table a list carries holds it - so it calls its own cut instead.

A pipeline whose stages run on several workers, with the results in input order. Made by parallel() on anything that can be iterated; nothing runs until a terminal - toList, collect, count, sum, minBy, maxBy, find, forEach - is called, and the terminal answers a Task. The stages before it run in one pass per chunk.

const total = (1..=100).parallel().map({ _ * 2 }).sum().await()
print total

A window onto a list that windows lent out: a stretch of the list's items, read and written in place, which the body of the region gets for as long as it runs and never keeps.

It names a stretch of the region and holds no item itself: the items it reads and writes are the list's own, not a copy of them, and a write through it is what the caller's list holds after the region. It is an ordinary type and not a shared type, because a shared type implements only shared traits and Length and MutableIndex are none; what keeps it inside the body is the checker, not an identity. It has a length and an index and nothing else - no append, no insert, no removeAt, no close - because the borders are the region's and the region is the only thing that makes one. Item is Plain, so two windows of one list never share anything but the list.

var values: ArrayList<Int> = ArrayList.from(0..6)
windows values, 2 { var window =>
  for var item in window {
    item = item * 10
  }
}
print values

A window lives as long as the call of the body it was handed to: the checker refuses one that is stored in a field or a binding of a wider scope, returned, or captured by a spawn (docs/design/CONCURRENCY.md section 6).

• windows - the region that hands windows out.
• Plain - what the items of a window are.

Cuts items into count windows and runs body once per window, on as many workers as there are, writing in place: the data-parallel loop over one list, with no copy of it and no list built for the answer. The call returns once every window is done, so the caller reads the list right after it.

The borders. Window index covers the items from index * length / count up to (index + 1) * length / count, rounded down: a function of the length and the count alone, never of the workers, the load or the order in which the windows finish. So two windows differ by at most one item, and none is empty unless there are more windows than items. Which worker runs which window is not fixed; what each window holds is.

Where the windows run. The caller's worker works as one of them: it claims windows one after the other until none is left, and up to count - 1 other workers claim the rest beside it. Where there is one worker, or the others are busy, the caller runs every window itself, so a region never waits for a worker that does not come. The items never cross a worker: every window is the list's own storage, which is made unique first where another holder shares it - the one copy, made before the region, and not a copy at the crossing.

var values: ArrayList<Float> = ArrayList.from([1.0, 2.0, 3.0, 4.0, 5.0])
windows values, 2 { var window =>
  for var item in window {
    item = item * 2.0
  }
}
print values

When count is less than 1, with windows` needs at least one window, and was asked for <count>. A panic of the body is the body's own.

• The list is a var ArrayList: the region lends its storage out, which a List behind a trait cannot do. Read anything else into one first (ArrayList.from).
• The body may run on any worker, so it reads what it captures and never a var of the caller: write through the window, which is the one place the region makes safe to write.
• A record of Plain fields whose items are counted runs every window on the caller's worker, one after the other - the same answer, without the speed-up.

• Window - what the body gets.
• Parallel - a pipeline over a collection, where the answer is a new one rather than the old one written in place.
• Workers.copies - the counter that shows the region copies nothing at the crossing.