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.
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).
(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)) |
|
|
extract-key : (any/c . -> . any/c) = (λ (x) x) |
cache-keys? : boolean? = #f |
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.
(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)) |
|
|
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.
(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)) |
|
|
extract-key : (any/c . -> . any/c) = (λ (x) x) |
cache-keys? : boolean? = #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:
The
progress is the number of merges already performed
and total is
(sub1 (- end start)).
(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)) |
|
|
extract-key : (any/c . -> . any/c) = (λ (x) x) |
cache-keys? : boolean? = #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.
(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)) |
|
|
| end | | : | | | | | | = | | (fxvector-length unsorted) |
|
extract-key : (any/c . -> . any/c) = (λ (x) x) |
cache-keys? : boolean? = #f |
Like vector-futures-sort! but for fxvector?.
(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)) |
|
| end | | : | | | | | | = | | (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.
(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)) |
|
|
| end | | : | | | | | | = | | (fxvector-length unsorted) |
|
extract-key : (any/c . -> . any/c) = (λ (x) x) |
cache-keys? : boolean? = #f |
|
progress-sleep : positive? = 0.1 |
Like vector-futures-sort!/progress but for fxvector?.
(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)) |
|
|
| end | | : | | | | | | = | | (fxvector-length unsorted) |
|
extract-key : (any/c . -> . any/c) = (λ (x) x) |
cache-keys? : boolean? = #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.
(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?.