futures-sort

8.12

futures-sort🔗ℹ

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

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.

parameter
(futures-sort-parallel-depth) → exact-nonnegative-integer?
(futures-sort-parallel-depth depth) → void?
depth : exact-nonnegative-integer?

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

Like vector-futures-sort!.

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

Like vector-futures-sort! but for fxvector?.

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

Like vector-futures-sort!/progress but for fxvector?.

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?.