# speculation

A framework for safe, programmable, speculative parallelism

http://github.com/ekmett/speculation

 LTS Haskell 12.26: 1.5.0.3 Stackage Nightly 2018-09-28: 1.5.0.3 Latest on Hackage: 1.5.0.3

See all snapshots speculation appears in

Maintained by
This version can be pinned in stack with:speculation-1.5.0.3@sha256:d8c7de7defa74ce883d4167b5e11595dc13fcfc5d7ccc56ce8265d3abbcbf2c2,4500

#### Module documentation for 1.5.0.3

Depends on 4 packages(full list with versions):

# speculation

A framework for safe, programmable, speculative parallelism, loosely based on:

This package provides speculative function application and speculative folds. Speculative STM transactions take the place of the transactional rollback machinery from the paper.

## Speculative Function Application (Control.Concurrent.Speculation)

Various speculative function application combinators are provided. Two fairly canonical samples are described here.

#### spec

spec :: Eq a => a -> (a -> b) -> a -> b

spec g f a evaluates f g while forcing a, if g == a then f g is returned. Otherwise f a is evaluated.

Furthermore, if the argument has already been evaluated, we avoid sparking the parallel computation at all.

If g is a good guess at the value of a, this is one way to induce parallelism in an otherwise sequential task.

However, if g isn't available more cheaply than a, then this saves no work, and if g is wrong, you risk evaluating the function twice. spec a f a = f \$! a

The best-case timeline looks like: [–– f g ––] [—– a —–] [– spec g f a –]

The worst-case timeline looks like: [–– f g ––] [—– a —–] [–– f a ––] [—–– spec g f a ———–]

Compare these to the timeline of f \$! a: [–– a —–] [–– f a ––]

#### specSTM

specSTM provides a similar compressed timeline for speculated STM actions, but also rolls back side-effects.

## Speculative Folds (Data.Foldable.Speculation)

A speculative version of the combinators from Data.Foldable is provided as Data.Foldable.Speculation.

Each combinator therein takes an extra argument that is used to speculate on the value of the list.

#### foldr

foldr :: (Foldable f, Eq b) => (Int -> b) -> (a -> b -> b) -> b -> f a -> b

Given a valid estimator g, foldr g f z xs yields the same answer as Foldable.foldr' f z xs.

g n should supply an estimate of the value returned from folding over the last n elements of the container.

As with spec, if the guess g n is accurate a reasonable percentage of the time and faster to compute than the ensuing fold, then this can provide increased opportunities for parallelism.

#### foldl

foldl :: (Foldable f, Eq b) => (Int -> b) -> (b -> a -> b) -> b -> f a -> b

foldl works similarly to Foldable.foldl', except that g n should provide an estimate for the first n elements.

## Contact Information

Contributions and bug reports are welcome!

I can be reached through the user ekmett on github, as edwardk on irc.freenode.net #haskell channel, or by email at ekmett@gmail.com.

-Edward Kmett

## Changes

/1.5.0.3/

• Support GHC 8
• Support transformers 0.5

/1.5.0.2/

• Build warning-free on GHC 7.10+
• Removed a redundant constraint from the type of sequenceByA_.
• Removed a redundant Monad m constraint from instance MonadSpec (ContT r m).

/1.5/

• Removed the use of tag-bits. This enables the API to be Trustworthy.

/1.4/

/1.3/

• Removed old benchmark/test framework.
• Make numSparks support mandatory.
• Moved to Control.Concurrent from Data
• Added MonadSpec, so we can make instances for Codensity, etc. in other packages
• Removed the ContT r STM combinators
• Cleaned out old issues
• Made compatible with the removal of the Eq/Show superclasses of Num in GHC 7.3+

/1.2.0.2/

• Fixed name collision with the new Distribution.Simple.testHook in Setup.lhs

/1.2.0.1/

• Weakened dependencies

/1.2.0.0/:

• Reorganized the module hierarchy into Data.Speculation

/1.1.0.0/:

/1.0.0.0/:

• Released

/0.9.0/:

• Removed interim boxing in the unsafeIsEvaluated and unsafeGetTagBits check

/0.8.1/: