tasty-bench-fit-0.1.1: Determine time complexity of a given function

Test.Tasty.Bench.Fit

Description

Guess complexity of the function.

Synopsis

# Fit benchmarks

Determine time complexity of the function:

>>> fit $mkFitConfig (\x -> sum [1..x]) (10, 10000) 1.2153e-8 * x >>> fit$ mkFitConfig (\x -> Data.List.nub [1..x]) (10, 10000)
2.8369e-9 * x ^ 2
>>> fit $mkFitConfig (\x -> Data.List.sort$ take (fromIntegral x) $iterate (\n -> n * 6364136223846793005 + 1) (1 :: Int)) (10, 100000) 5.2990e-8 * x * log x  One can usually get reliable results for functions, which do not allocate much: like in-place vector sort or fused list operations like sum [1..x]. Unfortunately, fitting functions, which allocate a lot, is likely to be disappointing: GC kicks in irregularly depending on nursery and heap sizes and often skews observations beyond any recognition. Consider running such measurements with -O0 or in ghci prompt. This is how the usage example above was generated. Without optimizations your program allocates much more and triggers GC regularly, somewhat evening out its effect. While suitable for automatic estimates, fit generally provides bad user experience in interactive environments, because it can take a very long time before it returns a result without any heartbeat in between. Consider using fits or enabling debug flag. Same as fit, but interactively emits a list of complexities, gradually converging to the final result. If fit takes too long, you might wish to implement your own criterion of convergence atop of fits directly. >>> cmpls <- fits$ mkFitConfig (\x -> sum [1..x]) (10, 10000)
>>> traverse print cmpls
3.36e-8 * x ^ 0.903
1.39e-8 * x
1.38e-8 * x
...


Arguments

 :: NFData a => (Word -> a) Raw function to measure, without nf. -> (Word, Word) The smallest and the largest sizes of the input. -> FitConfig

Generate a default fit / fits configuration.

data FitConfig Source #

Configuration for fit / fits.

Constructors

 FitConfig FieldsfitBench :: Word -> BenchmarkableWhich function to measure? Typically nf f.fitLow :: WordThe smallest size of the input. It should be as small as possible, but big enough for the main asymptotic term to dwarf constant overhead and other terms.fitHigh :: WordThe largest size of the input. As large as practically possible, at least 100x larger than the smallest size.fitTimeout :: TimeoutTimeout of individual measurements.fitRelStDev :: RelStDevTarget relative standard deviation of individual measurements.fitOracle :: Map Word Measurement -> ComplexityAn oracle to determine complexity from measurements. Typically guessComplexity.

# Complexity

Complexity a b k represents a time complexity $$k \, x^a \log^b x$$, where $$x$$ is problem's size.

Constructors

 Complexity FieldscmplVarPower :: !Double cmplLogPower :: !Word cmplMultiplier :: !Double

#### Instances

Instances details
 Source # Instance detailsDefined in Test.Tasty.Bench.Fit.Complexity Associated Typestype Rep Complexity :: Type -> Type # Methods Source # Instance detailsDefined in Test.Tasty.Bench.Fit.Complexity MethodsshowList :: [Complexity] -> ShowS # Source # Instance detailsDefined in Test.Tasty.Bench.Fit.Complexity Methodsrnf :: Complexity -> () # Source # Instance detailsDefined in Test.Tasty.Bench.Fit.Complexity Methods Source # Instance detailsDefined in Test.Tasty.Bench.Fit.Complexity Methods type Rep Complexity Source # Instance detailsDefined in Test.Tasty.Bench.Fit.Complexity type Rep Complexity = D1 ('MetaData "Complexity" "Test.Tasty.Bench.Fit.Complexity" "tasty-bench-fit-0.1.1-7ebaa8WLrPx6uH5KIjB4xg" 'False) (C1 ('MetaCons "Complexity" 'PrefixI 'True) (S1 ('MetaSel ('Just "cmplVarPower") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 Double) :*: (S1 ('MetaSel ('Just "cmplLogPower") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 Word) :*: S1 ('MetaSel ('Just "cmplMultiplier") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 Double))))

Represents a time measurement for a given problem's size.

Constructors

 Measurement FieldsmeasTime :: !Double measStDev :: !Double

#### Instances

Instances details
 Source # Instance detailsDefined in Test.Tasty.Bench.Utils Associated Typestype Rep Measurement :: Type -> Type # Methods Source # Instance detailsDefined in Test.Tasty.Bench.Utils MethodsshowList :: [Measurement] -> ShowS # Source # Instance detailsDefined in Test.Tasty.Bench.Utils Methodsrnf :: Measurement -> () # Source # Instance detailsDefined in Test.Tasty.Bench.Utils Methods Source # Instance detailsDefined in Test.Tasty.Bench.Utils Methods type Rep Measurement Source # Instance detailsDefined in Test.Tasty.Bench.Utils type Rep Measurement = D1 ('MetaData "Measurement" "Test.Tasty.Bench.Utils" "tasty-bench-fit-0.1.1-7ebaa8WLrPx6uH5KIjB4xg" 'False) (C1 ('MetaCons "Measurement" 'PrefixI 'True) (S1 ('MetaSel ('Just "measTime") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 Double) :*: S1 ('MetaSel ('Just "measStDev") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 Double)))

Guess time complexity from a map where keys are problem's sizes and values are time measurements (or instruction counts).

>>> :set -XNumDecimals
>>> guessComplexity $Data.Map.fromList$ map ($$x, t) -> (x, Measurement t 1)) [(2, 4), (3, 10), (4, 15), (5, 25)] 0.993 * x ^ 2 >>> guessComplexity  Data.Map.fromList  map (\(x, t) -> (x, Measurement t 1)) [(1e2, 2.1), (1e3, 2.9), (1e4, 4.1), (1e5, 4.9)] 0.433 * log x  This function uses following simplifying assumptions: • All coefficients are non-negative. • The power of \( \log x$$ (cmplLogPower) is unlikely to be $$> 1$$.
• The power of $$x$$ (cmplVarPower) is unlikely to be fractional.

This function is unsuitable to guess superpolynomial and higher classes of complexity.

Same as guessComplexity, but the power of $$\log x$$ (cmplLogPower) is pinned to be 0.

Since: 0.1.1

Evaluate time complexity for a given size of the problem.

# Predicates

Is the complexity $$f(x) = k$$?

Is the complexity $$f(x) = k \log x$$?

Is the complexity $$f(x) = k \, x$$?

Is the complexity $$f(x) = k \, x \log x$$?

Is the complexity $$f(x) = k \, x^2$$?

Is the complexity $$f(x) = k \, x^3$$?