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

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 [less-than?])  void?

  unsorted : vector?
  less-than? : (any/c any/c . -> . any/c) = (λ (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 unsorted [less-than?])  vector?

  unsorted : vector?
  less-than? : (any/c any/c . -> . any/c) = (λ (a b) (< a b))
Sorts vector? like vector-futures-sort! without modifying the original unsorted vector and allocating a fresh vector for the result.

procedure

(vector-futures-sort!/progress 
  unsorted 
  [less-than? 
  #:progress-proc progress-proc 
  #:progress-sleep progress-sleep]) 
  void?
  unsorted : vector?
  less-than? : (any/c any/c . -> . any/c) = (λ (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

(vector-futures-sort/progress unsorted 
  [less-than? 
  #:progress-proc progress-proc 
  #:progress-sleep progress-sleep]) 
  void?
  unsorted : vector?
  less-than? : (any/c any/c . -> . any/c) = (λ (a b) (< a b))
  progress-proc : (or/c procedure? false?) = #f
  progress-sleep : positive? = 0.1
Sorts vector? like vector-futures-sort!/progress without modifying the original unsorted vector and allocating a fresh vector for the result.

procedure

(fxvector-futures-sort! unsorted    
  [less-than?])  void?
  unsorted : fxvector?
  less-than? : (any/c any/c . -> . any/c)
   = (λ (a b) (unsafe-fx< a b))

procedure

(fxvector-futures-sort unsorted [less-than?])  fxvector?

  unsorted : fxvector?
  less-than? : (any/c any/c . -> . any/c) = (λ (a b) (< a b))
Sorts fxvector? like fxvector-futures-sort! without modifying the original unsorted fxvector and allocating a fresh fxvector for the result.

procedure

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

procedure

(fxvector-futures-sort/progress 
  unsorted 
  [less-than? 
  #:progress-proc progress-proc 
  #:progress-sleep progress-sleep]) 
  fxvector?
  unsorted : fxvector?
  less-than? : (any/c any/c . -> . any/c)
   = (λ (a b) (unsafe-fx< a b))
  progress-proc : (or/c procedure? false?) = #f
  progress-sleep : positive? = 0.1
Sorts fxvector? like fxvector-futures-sort!/progress without modifying the original unsorted fxvector and allocating a fresh fxvector for the result.