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

[ development, library, mit ] [ Propose Tags ]

Benchmark a given function for variable input sizes and find out its time complexity.

[Skip to Readme]


[Index] [Quick Jump]


Manual Flags


Emit ongoing diagnostic information.


Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info


Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


  • No Candidates
Versions [RSS] 0.1
Change log CHANGELOG.md
Dependencies base (>=4.11 && <5), containers (>=0.5.11 && <0.8), deepseq (>=1.4 && <1.6), infinite-list (>=0.1 && <0.2), regression-simple (>=0.2.1 && <0.3), tasty (>=1.4 && <1.6), tasty-bench (>=0.3.4 && <0.4) [details]
License MIT
Author Bodigrim
Maintainer andrew.lelechenko@gmail.com
Revised Revision 2 made by Bodigrim at 2023-09-27T22:23:36Z
Category Development
Home page https://github.com/Bodigrim/tasty-bench-fit
Source repo head: git clone https://github.com/Bodigrim/tasty-bench-fit
Uploaded by Bodigrim at 2023-05-01T21:26:41Z
Distributions LTSHaskell:0.1, NixOS:0.1, Stackage:0.1
Downloads 96 total (11 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2023-05-01 [all 1 reports]

Readme for tasty-bench-fit-0.1

[back to package description]


Benchmark a given function for variable input sizes and find out its time complexity.

> 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.