Data.Vector.Algorithms.Quicksort.Fork2

This module defines how quicksort is parallelised using the Fork2 class.

Main interface

class Fork2 a x m | a -> x where

Parallelization strategy for the quicksort algorithm with single-pivot partitioning. Specifies how to apply a pair of functions to their respective inputs (which will be recursive quicksort calls).

NB the name Fork2 suggests that two threads will be only forked.

Parameter meaning; - a - the parallelisation we're defining instance for - x - type of tokens that strategy can pass around to track recursive calls - m - monad the strategy operates in. Some strategies only make sense in a particular monad, e.g. parellelisation via forkIO

Methods

startWork :: a -> m x

Will get called only once by quicksort when sorting starts, returns token to be passed around. Other tokens, e.g. for new spawned threads, are created by the strategy in the corresponding class instance.

endWork :: a -> x -> m ()

Will get called by quicksort when it finishes sorting its array. Will receive previously created token.

fork2

Arguments

:: (HasLength b, HasLength d)

=> a

Parallelisation algorithm that can carry extra info, e.g. for synchronization

-> x

Token for current execution thread, will be passed to endWork when done

-> Int

Recursion depth

-> (x -> b -> m ())

One recursive quicksort call

-> (x -> d -> m ())

The other recursive quicksort call

-> b

One of the subarrays after partitioning to be sorted

-> d

The other subarray to be sorted

-> m ()

Instances

Fork2 ParStrategies () IO

Defined in Data.Vector.Algorithms.Quicksort.Fork2

Methods

startWork :: ParStrategies -> IO ()

endWork :: ParStrategies -> () -> IO ()

fork2 :: (HasLength b, HasLength d) => ParStrategies -> () -> Int -> (() -> b -> IO ()) -> (() -> d -> IO ()) -> b -> d -> IO ()

Monad m => Fork2 Sequential () m

Defined in Data.Vector.Algorithms.Quicksort.Fork2

Methods

startWork :: Sequential -> m ()

endWork :: Sequential -> () -> m ()

fork2 :: (HasLength b, HasLength d) => Sequential -> () -> Int -> (() -> b -> m ()) -> (() -> d -> m ()) -> b -> d -> m ()

Fork2 ParStrategies () (ST s)

This instance is a bit surprising - ST monad, after all, doesn’t have concurrency and threads everywhere its s parameter to signal, among other things, that it’s single execution thread.

Still, quicksort in this package hopefully doesn’t do anything funny that may break under parallelism. Use of this instance for other purposes has at least the same caveats as use of unsafeInterleaveST (i.e. not recommended, especially considering that the instance may change).

Defined in Data.Vector.Algorithms.Quicksort.Fork2

Methods

startWork :: ParStrategies -> ST s ()

endWork :: ParStrategies -> () -> ST s ()

fork2 :: (HasLength b, HasLength d) => ParStrategies -> () -> Int -> (() -> b -> ST s ()) -> (() -> d -> ST s ()) -> b -> d -> ST s ()

Fork2 Parallel (Bool, Bool) IO

Defined in Data.Vector.Algorithms.Quicksort.Fork2

Methods

startWork :: Parallel -> IO (Bool, Bool)

endWork :: Parallel -> (Bool, Bool) -> IO ()

fork2 :: (HasLength b, HasLength d) => Parallel -> (Bool, Bool) -> Int -> ((Bool, Bool) -> b -> IO ()) -> ((Bool, Bool) -> d -> IO ()) -> b -> d -> IO ()

No parallelisation

data Sequential

Trivial parallelisation strategy that executes everything sequentially in current thread. Good default overall.

Constructors

Sequential

Instances

Monad m => Fork2 Sequential () m

Defined in Data.Vector.Algorithms.Quicksort.Fork2

Methods

startWork :: Sequential -> m ()

endWork :: Sequential -> () -> m ()

fork2 :: (HasLength b, HasLength d) => Sequential -> () -> Int -> (() -> b -> m ()) -> (() -> d -> m ()) -> b -> d -> m ()

Parallelisation with threads

data Parallel

At most N concurrent jobs will be spawned to evaluate recursive calls after quicksort partitioning.

Warning: currently not as fast as sparks-based ParStrategies strategy, take care to benchmark before using.

Instances

Fork2 Parallel (Bool, Bool) IO

Defined in Data.Vector.Algorithms.Quicksort.Fork2

Methods

startWork :: Parallel -> IO (Bool, Bool)

endWork :: Parallel -> (Bool, Bool) -> IO ()

fork2 :: (HasLength b, HasLength d) => Parallel -> (Bool, Bool) -> Int -> ((Bool, Bool) -> b -> IO ()) -> ((Bool, Bool) -> d -> IO ()) -> b -> d -> IO ()

mkParallel :: Int -> IO Parallel

Make parallelisation strategy with at most N threads.

waitParallel :: Parallel -> IO ()

Wait until all threads related to a particular Parallel instance finish.

Parallelisation with sparks

data ParStrategies

Parallelise with sparks. After partitioning, if sides are sufficiently big then spark will be created to evaluate one of the parts while another will continue to be evaluated in current execution thread.

This strategy works in both IO and ST monads (see docs for relevant instance for some discussion on how that works).

Sparks will seamlessly use all available RTS capabilities (configured with +RTS -N flag) and according to benchmarks in this package have pretty low synchronization overhead as opposed to thread-based parallelisation that Parallel offers. These benefits allow sparks to work on much smaller chunks and exercise more parallelism.

Instances

Fork2 ParStrategies () IO

Defined in Data.Vector.Algorithms.Quicksort.Fork2

Methods

startWork :: ParStrategies -> IO ()

endWork :: ParStrategies -> () -> IO ()

fork2 :: (HasLength b, HasLength d) => ParStrategies -> () -> Int -> (() -> b -> IO ()) -> (() -> d -> IO ()) -> b -> d -> IO ()

Fork2 ParStrategies () (ST s)

This instance is a bit surprising - ST monad, after all, doesn’t have concurrency and threads everywhere its s parameter to signal, among other things, that it’s single execution thread.

Still, quicksort in this package hopefully doesn’t do anything funny that may break under parallelism. Use of this instance for other purposes has at least the same caveats as use of unsafeInterleaveST (i.e. not recommended, especially considering that the instance may change).

Defined in Data.Vector.Algorithms.Quicksort.Fork2

Methods

startWork :: ParStrategies -> ST s ()

endWork :: ParStrategies -> () -> ST s ()

fork2 :: (HasLength b, HasLength d) => ParStrategies -> () -> Int -> (() -> b -> ST s ()) -> (() -> d -> ST s ()) -> b -> d -> ST s ()

defaultParStrategies :: ParStrategies

Parallelise with sparks for reasonably big vectors.

setParStrategiesCutoff :: Int -> ParStrategies -> ParStrategies

Adjust length of vectors for which parallelisation will be performed.

Helpers

class HasLength a

Helper that can be used to estimatae sizes of subproblems.

For inscance, too small array will not benefit from sorting it in parallel because parallelisation overhead will likely trump any time savings.

Minimal complete definition

getLength

Instances

MVector v a => HasLength (v s a)

Defined in Data.Vector.Algorithms.Quicksort.Fork2

Methods

getLength :: v s a -> Int

getLength :: HasLength a => a -> Int

Length of item