Undo performance

The undo manager uses CArray to implement the undo history. As a result, the performance of undo notification varies significantly depending on whether undo is limited, or unlimited. Performance was measured using a test function that repeatedly generates the same undo event, as shown below. To simulate realistic conditions, the test function was called from the timer hook, and the results were stored in an array and written after the test, avoiding potential interference from file I/O.

If undo is unlimited, notification time is mostly constant, except when the CArray has to grow. Since growing entails copying the entire array to a new memory location, the time required to grow the CArray increases linearly with the number of undoable edits. In a test of 10000 iterations, undo notification took an average of 50 microseconds. The actual samples were nearly indistinguishable from the average, except when the array grew, resulting in peaks which increased linearly, up to 1.6 milliseconds by the end of the test. The time between peaks also increased linearly as expected, due to MFC's heuristic method of computing the grow size. There were also a few seemingly random, unexplained spikes of nearly 2.5 milliseconds.

If undo is limited, notification time is constant. This is because once the limit is reached, adding a new notification deletes the oldest event from the history. Deleting from the front of a CArray requires copying the entire array down one element, but the array size is constant, so there's no memory reallocation, and the time required to do the copy doesn't change. In a test of 10000 iterations, undo notification took an average of 60 microseconds, only 10 microseconds more than the unlimited case. The actual samples were similar to the average, with randomly-spaced peaks up to around 150 microseconds. Again there were some unexplained spikes, though they were an order of magnitude lower, around 250 microseconds.

Note that OnPlugBypass with undo notification commented out takes an average of 38 microseconds, so in all cases undo notification takes longer than other work performed by OnPlugBypass.

Conclusion: undo performance is suboptimal, due to the use of CArray. An implementation based on CList would almost certainly perform better for unlimited undo, and probably the same or slightly better for limited undo. This optimization needs to be weighed against substantially increased complexity in the undo manager, e.g. array indexing would have to be replaced by iteration.

This hypothesis was tested by slapping together a minimally functional CList-based implementation and repeating the test. The result: for unlimited undo, the average time was 48 microseconds, and the actual samples showed only minor deviations, e.g. 80 or 150 microseconds, except for the occasional unexplained 2.5 millisecond spike. On the other hand, the undo manager complications look pretty formidable.

static  const   MAX_SAMPS = 10000;
float   samp[MAX_SAMPS];
int samps = 0;
void CMainFrame::OnTimer(UINT nIDEvent)
{
    if (m_Plugin[0].IsCreated()) {
#if 0   // zero for unlimited undo
        if (!samps)
            m_UndoMgr.SetLevels(100);
#endif
        OnPlugBypass();
        if (samps == MAX_SAMPS) {
            FILE *fp = fopen("undo bench.txt", "wc");
            for (int i = 0; i < samps; i++)
                fprintf(fp, "%d\t%f\n", i, samp[i]);
            fclose(fp);
            exit(0);
        }
    }
    ...

#include "benchmark.h"
extern float samp[];
extern int samps;
void CFFPlugsDlg::OnPlugBypass() 
{
    int sel = GetCurSel();
    if (sel >= 0) {
CBenchmark  b;
        NotifyUndoableEdit(UCODE_BYPASS);
samp[samps++] = float(b.Elapsed());
        BypassPlugin(sel, !IsPluginBypassed(sel));
    }
}