futures-sort
futures-sort-parallel-depth
vector-futures-sort!
vector-futures-sort!/  progress
fxvector-futures-sort!
fxvector-futures-sort!/  progress
7.4

futures-sort

Dominik Pantůček <dominik.pantucek@trustica.cz>

 (require futures-sort) package: futures-sort

This library leverages futures for implementing parallel merge-sort of vector? and fxvector?. By default it tries to use all available processors as reported by (processor-count).

A parameter specifying the maximum depth of merge-sort where futures are leveraged. Total number of futures in the deepest layer is at most 2^{depth}.

Default value is \log_2p rounded up to whole integer for p=(processor-count).

procedure

(vector-futures-sort! unsorted [compare])  void?

  unsorted : vector?
  compare : procedure? = (λ (a b) (< a b))
Sorts vector? in place.

The procedure uses merge sort with n merge operations. Its overall algorithmic time complexity is O(n\cdot\log_2 n) and memory complexity is O(n) as it needs to allocate memory for copy of the original vector.

The implementation uses futures for the first futures-sort-parallel-depth splitting steps.

If a custom compare function is provided, it should be a lambda term and not a reference to some other function. For example, providing fx< as compare blocks running in parallel, but using the default compare function as is provides support for maximum parallelism.

procedure

(vector-futures-sort!/progress 
  unsorted 
  [compare 
  #:progress-proc progress-proc 
  #:progress-sleep progress-sleep]) 
  void?
  unsorted : vector?
  compare : procedure? = (λ (a b) (< a b))
  progress-proc : (or/c procedure? false?) = #f
  progress-sleep : positive? = 0.1

If progress-proc is not #f, it gets called every progress-sleep seconds.

procedure

(fxvector-futures-sort! unsorted [compare])  void?

  unsorted : fxvector?
  compare : procedure? = (λ (a b) (unsafe-fx< a b))

procedure

(fxvector-futures-sort!/progress 
  unsorted 
  [compare 
  #:progress-proc progress-proc 
  #:progress-sleep progress-sleep]) 
  void?
  unsorted : fxvector?
  compare : procedure? = (λ (a b) (unsafe-fx< a b))
  progress-proc : (or/c procedure? false?) = #f
  progress-sleep : positive? = 0.1