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
futures-sort
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).

It is possible to use this library to speed up already written programs using stock vector-sort, vector-sort!, and sort by renaming the required "futures" functions.

(require (rename-in futures-sort
                    [vector-futures-sort vector-sort]
                    [vector-futures-sort! vector-sort!]
                    [futures-sort sort]))

All the functions provided support the same positional and keyword arguments as their respective counterparts and are meant to be a parallel drop-in replacement for those. The #:cache-keys? argument is unused and is accepted only to provide compatibility.

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?    
  start    
  end    
  #:key extract-key    
  #:cache-keys? cache-keys?])  void?
  unsorted : vector?
  less-than? : (any/c any/c . -> . any/c) = (λ (a b) (< a b))
  start : 
(and/c exact-nonnegative-integer?
       (</c (vector-length unsorted)))
 = 0
  end : 
(and/c exact-nonnegative-integer?
       (>/c start)
       (<=/c (vector-length unsorted)))
   = (vector-length unsorted)
  extract-key : (any/c . -> . any/c) = (λ (x) x)
  cache-keys? : boolean? = #f
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.

The #:cache-keys? argument is provided only for compatibility with vector-sort! and similar functions.

procedure

(vector-futures-sort unsorted    
  [less-than?    
  start    
  end    
  #:key extract-key    
  #:cache-keys? cache-keys?])  vector?
  unsorted : vector?
  less-than? : (any/c any/c . -> . any/c) = (λ (a b) (< a b))
  start : 
(and/c exact-nonnegative-integer?
       (</c (vector-length unsorted)))
 = 0
  end : 
(and/c exact-nonnegative-integer?
       (>/c start)
       (<=/c (vector-length unsorted)))
   = (vector-length unsorted)
  extract-key : (any/c . -> . any/c) = (λ (x) x)
  cache-keys? : boolean? = #f
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? 
  start 
  end 
  #:key extract-key 
  #:cache-keys? cache-keys? 
  #:progress-proc progress-proc 
  #:progress-sleep progress-sleep]) 
  void?
  unsorted : vector?
  less-than? : (any/c any/c . -> . any/c) = (λ (a b) (< a b))
  start : 
(and/c exact-nonnegative-integer?
       (</c (vector-length unsorted)))
 = 0
  end : 
(and/c exact-nonnegative-integer?
       (>/c start)
       (<=/c (vector-length unsorted)))
   = (vector-length unsorted)
  extract-key : (any/c . -> . any/c) = (λ (x) x)
  cache-keys? : boolean? = #f
  progress-proc : 
(or/c (fixnum? fixnum? . -> . any/c)
      false?)
 = #f
  progress-sleep : positive? = 0.1

If progress-proc is not #f, it gets called every progress-sleep seconds. The procedure must accept two arguments:

(λ (progress total)
  ...)

The progress is the number of merges already performed and total is (sub1 (- end start)).

procedure

(vector-futures-sort/progress unsorted 
  [less-than? 
  start 
  end 
  #:key extract-key 
  #:cache-keys? cache-keys? 
  #:progress-proc progress-proc 
  #:progress-sleep progress-sleep]) 
  void?
  unsorted : vector?
  less-than? : (any/c any/c . -> . any/c) = (λ (a b) (< a b))
  start : 
(and/c exact-nonnegative-integer?
       (</c (vector-length unsorted)))
 = 0
  end : 
(and/c exact-nonnegative-integer?
       (>/c start)
       (<=/c (vector-length unsorted)))
   = (vector-length unsorted)
  extract-key : (any/c . -> . any/c) = (λ (x) x)
  cache-keys? : boolean? = #f
  progress-proc : 
(or/c (fixnum? fixnum? . -> . any/c)
      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?    
  start    
  end    
  #:key extract-key    
  #:cache-keys? cache-keys?])  void?
  unsorted : fxvector?
  less-than? : (any/c any/c . -> . any/c)
   = (λ (a b) (unsafe-fx< a b))
  start : 
(and/c exact-nonnegative-integer?
       (</c (vector-length unsorted)))
 = 0
  end : 
(and/c exact-nonnegative-integer?
       (>/c start)
       (<=/c (vector-length unsorted)))
   = (fxvector-length unsorted)
  extract-key : (any/c . -> . any/c) = (λ (x) x)
  cache-keys? : boolean? = #f

procedure

(fxvector-futures-sort unsorted    
  [less-than?    
  start    
  end    
  #:key extract-key    
  #:cache-keys? cache-keys?])  fxvector?
  unsorted : fxvector?
  less-than? : (any/c any/c . -> . any/c) = (λ (a b) (< a b))
  start : 
(and/c exact-nonnegative-integer?
       (</c (vector-length unsorted)))
 = 0
  end : 
(and/c exact-nonnegative-integer?
       (>/c start)
       (<=/c (vector-length unsorted)))
   = (fxvector-length unsorted)
  extract-key : (any/c . -> . any/c) = (λ (x) x)
  cache-keys? : boolean? = #f
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? 
  start 
  end 
  #:key extract-key 
  #:cache-keys? cache-keys? 
  #: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))
  start : 
(and/c exact-nonnegative-integer?
       (</c (vector-length unsorted)))
 = 0
  end : 
(and/c exact-nonnegative-integer?
       (>/c start)
       (<=/c (vector-length unsorted)))
   = (fxvector-length unsorted)
  extract-key : (any/c . -> . any/c) = (λ (x) x)
  cache-keys? : boolean? = #f
  progress-proc : 
(or/c (fixnum? fixnum? . -> . any/c)
      false?)
 = #f
  progress-sleep : positive? = 0.1

procedure

(fxvector-futures-sort/progress 
  unsorted 
  [less-than? 
  start 
  end 
  #:key extract-key 
  #:cache-keys? cache-keys? 
  #: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))
  start : 
(and/c exact-nonnegative-integer?
       (</c (vector-length unsorted)))
 = 0
  end : 
(and/c exact-nonnegative-integer?
       (>/c start)
       (<=/c (vector-length unsorted)))
   = (fxvector-length unsorted)
  extract-key : (any/c . -> . any/c) = (λ (x) x)
  cache-keys? : boolean? = #f
  progress-proc : 
(or/c (fixnum? fixnum? . -> . any/c)
      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.

procedure

(futures-sort lst    
  less-than?    
  [#:key extract-key    
  #:cache-keys? cache-keys?])  list?
  lst : list?
  less-than? : (any/c any/c . -> . any/c)
  extract-key : (any/c . -> . any/c) = (λ (x) x)
  cache-keys? : boolean? = #f
A simple wrapper that converts lst to vector?, sorts it using vector-futures-sort! and converts it back to list?.