Fair comparison of algorithms, memory usage

[nishihatapalmer]

One of the things I've learned about benchmarking search algorithms is you have to compare like with like. I see an earlier issue asking for the amount of memory used by each algorithm to be reported, and that would be very useful information to have.

I have been working on a very simple addition - a simple function that calculates how many entries can be safely used without going over a maximum memory limit, (often limited to a power of two for hash tables). I've modified a few algorithms to pick a hash table size enforcing the memory limit, and this gives much more interesting results when you know the algorithms are using roughly the same amount of memory as each other.

My technique isn't very pleasant to work with. You have to re-compile all the algorithms if you change the memory limit, as it's hard coded in memlimit.h. So I don't see this as a general PR anytime soon, but I am making use of it myself when comparing algorithms.

My purpose in raising the issue is to understand if this is something worth pursuing - would anyone else be interested in these capabilities?

[nishihatapalmer]

OK, good to know this is something that doesn't only interest me.

So I'll have a think about how to tune memory usage of algorithms (that can be tuned), and how to report back actual memory usage. I guess memory usage could vary by pattern, although all the single pattern algorithms I'm aware of don't.

[nishihatapalmer]

I've made some progress on this. It's now possible to obtain various statistics on the running algorithms. Since I had to create an interface to get the memory of each algorithm, I added quite a few more interesting stats as it was essentially not much more work.

It does not require existing algorithms to be modified. Stats can be added as required, which takes about 20 minutes for each algorithm.

• Algorithms that support stats should include mainstats.h instead of main.h and implement the search stat functions.
• Algorithms that don't support stats don't have to do anything.

Stats available are:

struct searchInfo {
    int patternLength;
    long textLength;
    long searchIndexBytes;
    long searchIndexEntries;
    long mainLoopCount;
    long textBytesRead;
    long indexLookupCount;
    long fastPathCount;
    long fastPathShifts;
    long slowPathCount;
    long slowPathShifts;
    long validationCount;
    long validationShifts;
    long numShifts;
    long totalShifts;
    int matchCount;
    long algoValues[MAX_ALGO_VALUES];
};

The array of algoValues at the end support per-algorithm statistics. If an algorithm wants to provide stats beyond the standard set, it just has to define a name for each stat it is providing, and store the values in algoValues. So shift-table oriented algorithms can provide the total shifts available in the shift table, and bit-oriented algorithms can provide other table statistics.

I'd like to get a read on whether this is a reasonable direction or not.

[nishihatapalmer]

Here is a sample of the output where three algorithms provide stats: horspool, qf43 and twfr4. twfr4 doesn't yet track numshifts in this output.

[nishihatapalmer]

The current implementation mirrors the stat collection for time values - it records the average values across all the runs, the stats for the best time result, and the stats for the worst time result.

Other than outputting to console, I haven't done anything else with these stats, but I intend to write them into the HTML reports and probably to write a results file as well.

[nishihatapalmer]

As an example. here is the search stats implementation for Horspool.. To implement search stats, you first copy the algorithm over, removing the search time macros. Then you just add up what's going on in a run.

struct searchInfo searchStats(unsigned char *P, int m, unsigned char *T, int n) {
    int i, s, hbc[SIGMA];
    Pre_Horspool(P, m, hbc);

    /* Basic search info */
    struct searchInfo results = {0};
    initStats(&results, m, n, SIGMA, sizeof(int));

    /* Table stats */
    int totalShift = 0;
    for (i = 0; i < SIGMA; i++) {
        totalShift += hbc[i];
    }
    results.algoValues[0] = totalShift;

    /* Instrumented Searching */
    s = 0;
    while(s<=n-m) {
        results.mainLoopCount += 1;
        i=0;
        while(i<m && P[i]==T[s+i]) {
            i++;
            results.textBytesRead++;
        }
        if(i==m) {
            results.matchCount++;
        }
        results.validationCount++;
        int shift = hbc[T[s+m-1]];
        s+=shift;
        results.textBytesRead++;
        results.indexLookupCount++;
        results.totalShifts += shift;
        results.numShifts++;
    }
    return results;
}

struct algoValueNames getAlgoValueNames() {
    struct algoValueNames names = {0};
    strncpy(names.algoValueName[0], "table shifts", MAX_ALGO_VALUE_NAME_LEN);
    return names;
}

[Helias]

Hi, I am really happy of your progress for this issue, hope other users will enjoy it.

Unfortunately I am not using smart in this period and I have no time to try, but I am glad to see that you are enjoying this 🚀

[nishihatapalmer]

OK, good to know the work might be useful for others and it's going in the right direction. I'd like to get the changes finished up so I can use smart - to benchmark various algorithms I'm playing with!

[nishihatapalmer]

Update

I now have stats implemented. It writes out statistics to the console during running, tables in the HTML report (after each chart for each algorithm), and also writes them out to a tab delimited text file, for best, mean and worst. Stats have been added to BM, HOR, all the HASH, WFR, TWFR and QF algorithms. I've spent some time making it easy to add stats to existing algorithms, so the work to do is minimal.

I'm not going to submit a PR straight away, as I want to work with it for a bit to get used to it and find any edge cases if they exist. I think I'll be ready to submit a PR in a week or two.

[nishihatapalmer]

In terms of PR submission, I'm going to create separate PRs for the main stats implementation, and then families of algorithms.

I don't want to create a huge review burden at one time, so stats can be added to algorithms as and when we're happy.

[nishihatapalmer]

As a side note, the stats are already proving useful when profiling existing algorithms and developing new ones. I'm using them to examine some new algorithms I'm playing with.

[nishihatapalmer]

Update

Stats seem stable. I'm going to use them for another week or so in anger, then I'll start to submit PRs.

[nishihatapalmer]

Just submitted PRs for this, #19 #20 #21 #22 #23

[nishihatapalmer]

I'm more than willing to add stats to other algorithm families if we think it would be useful. I've just included the ones I've been looking at myself recently, and BM as it's a classic.

If you think there's particular ones that would be of interest, I'd be interested in your opinion. I was thinking of doing the BNDM and BOM families next.