v0.5.0

Additions and updates:

• functor MatCOO
  • preliminary support for MatrixMarket files in COO format. These are especially used in SuiteSparse.
  • Efficient sparse matrix-vector multiplication over this format
• structure StableMergeLowSpan
  • An O(log n)-span parallel merge implementation. Not necessarily faster than the normal Merge and StableMerge implementations, because all of these codes are highly parallel and memory-bound anyway. But it is interesting regardless.
• structure DoubleBinarySearch
  • efficient binary search simultaneously over two sorted sequences. This is a subroutine of the low-span merge.
• structure RuntimeStats
  • Detailed runtime statistics for newer versions of MPL
  • Updated Benchmark.run now uses this in normal output
• structure WriteFile
  • Just a simple dump(filename: string, contents: string) function
  • (should flesh this out in future versions)
• structure Rat
  • simple implementation of precise rational numbers
• functor MkComplex
  • basic functions on complex numbers

Note also that we've renamed branch master -> main.

v0.4.0 (Oct 20, 2022)

Adds a few collections:

• structure ParFuncArray: an implementation of parallel functional arrays (based on Kumar et al.). Essentially, lock-free (actually wait-free) mutable arrays with pure functional semantics, even in the presence of concurrency+parallelism. Under the hood, arrays are automatic shared and rebuilt on-demand to ensure determinism.
• structure Hashset and Hashtable: simple implementations of lock-free hash tables, based on linear probing and open addressing.
• functor ChunkedTreap: an implementation of purely functional treaps with chunked leaves, an approach which is more space-efficient than basic trees. The functor is parameterized, to allow for a variety of different pure sequence types to be used as leaf chunks.

v0.3.0 (Aug 21, 2022)

Just a few small things, including documentation (see doc/) and some additional functionality (needed by other packages using this library):

• CommandLineArgs.parseStrings: parses multiple instances of -K V at command line.
• Seq.fromRevList: reverse and convert to list in one go
• Util.{all,exists}: convenient loops for checking conditions in a range
• Util.equalLists: comparing polymorphic lists
• OldDelayedSeq module (older, but occasionally faster version of DelayedSeq)

v0.2.0

v0.2.0 (July 10, 2022): Additional sorting, shuffling, and searching

Summary

Add the following:

• structure StableMerge for stable parallel merge operations. Work-efficient and polylogarithmic span.
• structure StableSort for stable parallel sort (specifically, mergesort). Work-efficient and polylogarithmic span.
• structure Shuffle for pseudorandom parallel shuffling. Work-efficient and polylogarithmic span.
• BinarySearch.searchPosition for searching based on a target position rather than a target key.

Additional (currently undocumented) changes:

• New VertexSubset type within AdjacencyGraph, with sparse and dense representations.
• functor CheckSort for verifying correctness of sorting functions
• functor MkGrep which implements a parallel version of the Unix grep utility. Takes a Seq: SEQUENCE argument to test performance of difference sequence implementations. Best performance with DelayedSeq.
• thread-safe Util.intToString alternative to basis library Int.toString (in the future, this should be integrated into mainline MPL basis library)

Stable merge

structure StableMerge:
sig
  (* same as Seq.t  :)  *)
  type 'a seq = 'a ArraySlice.slice

  
  (** ===========================================
    * Purely functional. 
    *)

  (* no parallelism; intended for small sequences *)
  val mergeSerial: ('a * 'a -> order) -> 'a seq * 'a seq -> 'a seq

  (* highly parallel; intended for large sequences *)
  val merge: ('a * 'a -> order) -> 'a seq * 'a seq -> 'a seq

  
  (** ===========================================
    * DANGER: imperative. Use with care!
    *)

  val writeMergeSerial:
       ('a * 'a -> order)   (* compare *)
    -> 'a seq * 'a seq      (* (sorted) sequences to merge *)
    -> 'a seq               (* output *)
    -> unit

  val writeMerge:
       ('a * 'a -> order)   (* compare *)
    -> 'a seq * 'a seq      (* (sorted) sequences to merge *)
    -> 'a seq               (* output *)
    -> unit
end

Stable sort

structure StableSort:
sig
  (* same as Seq.t   :)  *)
  type 'a seq = 'a ArraySlice.slice
  val sortInPlace: ('a * 'a -> order) -> 'a seq -> unit
  val sort: ('a * 'a -> order) -> 'a seq -> 'a seq
end

Shuffling

structure Shuffle:
sig
  val shuffle: 'a Seq.t -> int -> 'a Seq.t
end

shuffle s seed produces a pseudorandom permutation of s based on the random seed seed. For a particular seed, it will always produce the same result. Any two shuffles (using two different seeds) are independent. E.g. shuffle s seed is independent of shuffle s (seed+1).

Linear work and polylogarithmic span.

Binary search position

structure BinarySearch:
sig
  (* ... other existing functions ... *)

  val searchPosition: 'a Seq.t -> ('a -> order) -> int
end

searchPosition s cmpTargetAgainst finds a target position in the sequence by using cmpTargetAgainst to point towards the target position. This is useful when you aren't looking for a specific element, but some location within a sequence. Note that this is more general than the plain search function, because we can implement search in terms of searchPosition as follows: fun search cmp s x = searchPosition s (fn y => cmp (x, y)).

v0.1.0

Initial release!

Contains a wide variety of parallel algorithms, data structures, and utilities, such as:

• sequences, sets, dictionaries, matrices, etc.
• sorting, searching, etc.
• text processing (tokenization, string search)
• images (.ppm, .gif formats)
• graph processing (CSR and edge list formats)
• audio (signal processing and .wav format)
• computational geometry (nearest neighbors, meshes, triangulation, convex hull)
• command-line arguments
• benchmarking

More coming in the future...