# i      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghportable provisionalEdward Kmett <ekmett@gmail.com> Safe-Inferredijklmnopqrstuvw ijklmnopq ikjlmnopqrstuvwportable provisionalEdward Kmett <ekmett@gmail.com> Trustworthy g f a evaluates f g while forcing a, if g == a then f g is returned, otherwise f a is evaluated and returned. Furthermore, if the argument has already been evaluated or are not running on the threaded runtime, we skip the f g7 computation entirely. If a good guess at the value of ao is available, this is one way to induce parallelism in an otherwise sequential task. However, if the guess isn't available more cheaply than the actual answer, then this saves no work and if the guess is wrong, you risk evaluating the function twice. Under high load or in a runtime with access to a single capability, since 'f g'i is computed via the spark queue, the speculation will be skipped and you will obtain the same answer as 'f $! a'. #The best-case timeline looks like:   foreground: [----- a -----] 1 foreground: [-] (check g == a) " spark: [----- f g -----] " overall: [--- spec g f a ---] $The worst-case timeline looks like:   foreground: [----- a -----] < foreground: [-] (check g == a) - foreground: [---- f a ----] " spark: [----- f g -----] - overall: [-------- spec g f a ---------] Note that, if f g= takes longer than a to compute, in the HEAD release of GHC, f g9 will be collected and killed during garbage collection.   foreground: [----- a -----] < foreground: [-] (check g == a) - foreground: [---- f a ----] W spark: [---- f g ----###### (#'s mark when this spark is collectable) - overall: [--------- spec g f a --------] Under high load:   foreground: [----- a -----] < foreground: [-] (check g == a) - foreground: [---- f a ----] - overall: [-------- spec g f a ---------] !Compare these to the timeline of f $! a:  foreground: [----- a -----] + foreground: [---- f a ----] + orverall: [---------- f $! a ---------] ) with a user defined comparison function + comparing by projection onto another type  g f a evaluates  fg = do g' <- g; f g', while forcing a , then if g' == a then fg, is returned. Otherwise the side-effects of fg are rolled back and f a is evaluated. gP is allowed to be a monadic action, so that we can kickstart the computation of a earlier. Under high load, or when we are not using the parallel runtime, the speculation is avoided, to enable this to more closely approximate the runtime profile of spec. If the argument a is already evaluated, we don't bother to perform f g at all.  If a good guess at the value of aV is available, this is one way to induce parallelism in an otherwise sequential task. However, if the guess isn']t available more cheaply than the actual answer then this saves no work, and if the guess is 0 wrong, you risk evaluating the function twice. #The best-case timeline looks like:   foreground: [--- g >>= f ---] % spark: [------- a -------] 9 foreground: [-] (compare g' == a) ' overall: [---- specSTM g f a ----] $The worst-case timeline looks like:  ! foreground: [---- g >>= f ----] $ spark: [------- a -------] 9 foreground: [-] (check if g' == a) 4 foreground: [--] (rollback) ; foreground: [------ f a ------] ; overall: [------------ specSTM g f a ----------------] Under high load,  degrades less gracefully than :  ! foreground: [---- g >>= f ----] 3 spark: [------- a -------] H foreground: [-] (check if g' == a) C foreground: [--] (rollback) J foreground: [------ f a ------] J overall: [--------------------specSTM g f a ------------------------] !Compare these to the timeline of f $! a: ! foreground: [------- a -------] 3 foreground: [------ f a ------] * using a user defined comparison function   . x (==)portable provisionalEdward Kmett <ekmett@gmail.com> Safe-Inferredspec* with a user supplied comparison function When a is unevaluated,  g a% evaluates the current continuation  with g while testing if g y a%, if they differ, it re-evalutes the  continuation with a. If a, was already evaluated, the continuation is  just directly applied to a instead. spec'* with a user supplied comparison function  z   z Safe-Inferred Given a valid estimator g,   g f xs yields the same answer as   f xs. g nP should supply an estimate of the value of the monoidal summation over the last n elements of the container. If g nd is accurate a reasonable percentage of the time and faster to compute than the fold, then this can 2 provide increased opportunities for parallelism.   using  Given a valid estimator g,   g f xs yields the same answer as   f xs. g nP should supply an estimate of the value of the monoidal summation over the last n elements of the container. If g nd is accurate a reasonable percentage of the time and faster to compute than the fold, then this can 2 provide increased opportunities for parallelism.   using  Given a valid estimator g,  g f z xs yields the same answer as foldr' f z xs. g nL should supply an estimate of the value returned from folding over the last n elements of the container. If g nd is accurate a reasonable percentage of the time and faster to compute than the fold, then this can 2 provide increased opportunities for parallelism. Given a valid estimator g,  g f z xs yields the same answer as foldl' f z xs. g nM should supply an estimate of the value returned from folding over the first n elements of the container. If g nd is accurate a reasonable percentage of the time and faster to compute than the fold, then this can 2 provide increased opportunities for parallelism. EMap each element of a structure to an action, evaluate these actions , from left to right and ignore the results.   is  with its arguments flipped. "PMap each element of the structure to a monadic action, evaluating these actions . from left to right and ignoring the results. #PMap each element of the structure to a monadic action, evaluating these actions U from left to right and ignoring the results, while transactional side-effects from ) mis-speculated actions are rolled back. %  is " with its arguments flipped. &  is " with its arguments flipped. ?  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGH?  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGH?  !()-."$%'*,/0#&+1234569:78;<=>?@ABCDEFGH?  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGH(non-portable (UnboxedTuples, Rank2Types) provisionalEdward Kmett <ekmett@gmail.com> Trustworthy${|}~IJKLMNOPQRSTUVWXYZ[\IJKLMNOPQRSTUVWXYZ[\MNWXSTOPUVYZQR[\IJKL!{|}~IJKLMNOPQRSTUVWXYZ[\portable provisionalEdward Kmett <ekmett@gmail.com> Safe-Inferred]Given a valid estimator g, ] g xs converts xs! into a list of the prefix sums. g nQ should supply an estimate of the value of the monoidal summation over the first n elements of the container. If g nj is accurate a reasonable percentage of the time and faster to compute than the prefix sum, then this can 2 provide increased opportunities for parallelism. ^] using  _Given a valid estimator g, _ g f xs converts xs! into a list of the prefix sums. g nQ should supply an estimate of the value of the monoidal summation over the first n elements of the container. If g nd is accurate a reasonable percentage of the time and faster to compute than the scan, then this can 2 provide increased opportunities for parallelism.  scan = scanMap id  scanMap = scanMapBy (==) aGiven a valid estimator g, a g f z xs yields the same answer as scanr' f z xs. g nM should supply an estimate of the value returned from scanning over the last n elements of the container. If g nd is accurate a reasonable percentage of the time and faster to compute than the scan, then this can 2 provide increased opportunities for parallelism. ]^_`abcdefgh ]^_`abcdefgh ]^_`abcdefgh ]^_`abcdefgh      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrsstuvwxyz{|}~speculation-1.5Control.Concurrent.Speculation$Control.Concurrent.Speculation.Class'Control.Concurrent.Speculation.Foldable*Control.Concurrent.Speculation.Traversable#Control.Concurrent.Speculation.List'Control.Concurrent.Speculation.InternalspecspecByspecOnspecSTM specBySTM specOnSTM MonadSpecspecByMspecMspecOnMfoldfoldByfoldMap foldMapByfoldrfoldrByfoldlMfoldlByMfoldrMfoldrByMfoldlSTM foldlBySTMfoldrSTM foldrBySTMfoldlfoldlByfoldr1foldr1Byfoldl1foldl1By traverse_ traverseBy_for_forBy_mapM_mapSTM_mapByM_forM_forSTM_forByM_ sequenceA_ sequenceByA_ sequence_ sequenceSTM_ sequenceBy_asumasumBymsummsumBytoListtoListByconcatconcatBy concatMap concatMapByandorallanysumsumByproduct productBymaximum maximumByminimum minimumByelemelemBynotElem notElemByfindfindBy mapAccumL mapAccumLBy mapAccumR mapAccumRBytraverse traverseBymapMmapByMmapSTMmapBySTM sequenceA sequenceByAsequence sequenceByforforByforMforByMforSTMforBySTMscanscanByscanMap scanMapByscanrscanrByscanlscanlByscanr1scanr1Byscanl1scanl1ByMaybeAcc NothingAccJustAccAcc extractAcc fromMaybeAccerrorEmptyStructure returning$fTraversableMaybeAcc$fFoldableMaybeAcc$fFunctorMaybeAcc$fTraversableAcc $fFoldableAcc $fFunctorAccbase Data.Functiononghc-prim GHC.Classes==$fMonadSpecContTAccT IntAccumR IntAccumLacc runIntAccumL runIntAccumRrunAccT$fApplicativeAccT $fFunctorAccT$fApplicativeIntAccumR$fFunctorIntAccumR$fApplicativeIntAccumL$fFunctorIntAccumL