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]

Flags

Manual Flags

NameDescriptionDefault
debug

Emit ongoing diagnostic information.

Disabled

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

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1, 0.1.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.4 && <0.5) [details]
License MIT
Author Bodigrim
Maintainer andrew.lelechenko@gmail.com
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 2024-07-08T23:19:44Z
Distributions LTSHaskell:0.1, NixOS:0.1, Stackage:0.1.1
Downloads 148 total (27 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2024-07-08 [all 1 reports]

Readme for tasty-bench-fit-0.1.1

[back to package description]

tasty-bench-fit

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.