Add benchmarking suite - Githubissues

amnh / PCG

𝙋𝙝𝙮𝙡𝙤𝙜𝙚𝙣𝙚𝙩𝙞𝙘 𝘾𝙤𝙢𝙥𝙤𝙣𝙚𝙣𝙩 𝙂𝙧𝙖𝙥𝙝 ⸺ Haskell program and libraries for general phylogenetic graph search

28 stars 1 forks source link

Add benchmarking suite #88

Closed recursion-ninja closed 3 years ago

recursion-ninja commented 5 years ago

Add a benchmarking suite for given functions. We can use criterion and weigh to measure the run-time and memory usage respectively. Try to test time and space complexities using these libraries. If we can write our own abstraction for this, that would be great.

Should also investigate how well parallelism is being utilized. Specifically strictness with data parallelism.

recursion-ninja commented 5 years ago

Some specific things to test:

[ ] Wagner build functionality to be O(n^2) time complexity and O(n) space complexity with respect to the input leaf set.
[ ] Single pass of the network build should be at worst O(e^2) time complexity with respect to the input edge set.
- [ ] Scoring a graph should be O(n) time complexity with respect to the number of input characters.

recursion-ninja commented 5 years ago

This library might be very useful. Worth exploring:

https://github.com/mathandley/AutoBench

Boarders commented 5 years ago

Currently AutoBench is not on hackage and is quite hard to build with our project (e.g. it uses an earlier version of megaparsec). I think it is still worth exploring in the future if a more robust version is developed.

recursion-ninja commented 5 years ago

Which version of megaparsec is it using to build?

Boarders commented 5 years ago

It has the bounds: megaparsec >= 6.2 && < 6.6,

recursion-ninja commented 5 years ago

*sigh*, I had updated to megaparsec >= 7.0 && < 8.0 for some reason, but I can't remember what it was.

If it looks promising, maybe I can make a PR to upgrade AutoBench to use megaparsec >= 7.0. The process was quite painless for me with our code base.

recursion-ninja commented 5 years ago

We should take the random TCM generation and tree/sequence data generation from utils/generate-tcm.hs and utils/generate-data-set.hs, respectively into testing modules. Should be useful in conjunction with AutoBench.

recursion-ninja commented 3 years ago

We have since added several benchmarking suites, though not the ones outlined above. Closing as this issue's completion is "good enough" for now. We can make a new, more specific in the future for more benchmark targets.