Algorithm runtime statistics

[nishihatapalmer]

Algorithm Runtime Statistics

This PR adds the capability to instrument algorithms with code that tracks the runtime operation of the algorithms, as opposed to their performance. It gathers the following stats by default:

• memory used
• size of lookup tables
• text bytes read
• pattern bytes read
• number of branches
• number of lookups
• number of significant computations performed
• number of jumps (position of search algorithm advanced)
• number of writes
• number of verification attempts.

For each run, it computes the average jump obtained during search (text length / number of jumps), and the percent of text read.

It also provides up to 6 algorithm-defined custom values that can be tracked and named. All measurements are analysed to provide median, mean, standard deviation, minimum and maximum values for each run, and the individual measurements are also output.

Design

Any algorithm that is instrumented to gather runtime statistics must have a filename prefixed by stat_. These versions will be run when smart is run on the algorithms using the flag -stats algo.

A detailed description of how to operate and instrument the algorithms is in the file AlgorithmMeasurements.md.

Additional

Some extra features are also included here. These are:

• Statistics output on the command line is now in fixed length columns to make reading easier.
• All patterns used in an experiment are output to a CSV file that contains the length, measurement number, ASCII-printable version of the pattern (where possible), and a hex version of the pattern bytes.

[nishihatapalmer]

Some sample algorithms have stats versions included, but will need to instrument quite a few of the remaining ones (and the other Q-gram sizes too).