This is the first article in a series leading up to the dotMath 2.0 beta. This release is focused on new speed improvements for dotMath. While introducing an entirely new compile engine, dotMath 2.0 also focuses on backward compatibility to 1.0.
While dotMath is extremely fast, I’ve found that there is one more factor of 10 speed improvement sitting out there. As a stack-based compiler , making a call to resolve a function is not as efficient as it could be in dotMath. Your entire expression is resolved by nested function calls to manage the execution order. While I’ve mulled the idea of claiming this speed improvement before, on a recent trip I started to question my operating assumptions and came up with a different approach.
To resolve this, my initial approach involved creating a set of registers and chaining the operations in much the same way program counters and processor registers interact on a conventional piece of code. In this manner, I can claim most of that factor-of-10 speed improvement. After looking at the problem a little deeper, I started to wonder if I can make the evaluation process more efficient than that.
Take the following simple expression:
a * b * c * d * e * f * g
Compiling using a conventional language and calling this expression repeatedly, the entire expression gets evaluated each time. This inefficiency arises primarily because the process of variable storage and subsequent execution are disjointed operations. Since dotMath is controlling both, can we actually make this run faster?
Yes we can.
The basic idea is this - we break the processing requirements out into two vectors – one containing the discrete operations (code) and the other containing data (processing values). That said, the data vector not only contains effective register values, but there is one register value per operation. In addition, each variable or static value holds a position within this vector. Because we also maintain the setting of named values AND hold the equation’s dependency graph, we know that by changing the value of “g” in our equation above and requesting a recalc (I am assuming that it has been called at least once before), we only need to perform one calculation instead of six. The performance is now predicated on both the number of terms and the effects of modifying a variable in the equation.
In our earlier equation, changing the value of “g” results in additional time savings above and beyond the factor-of-10 improvement noted above, whereas modifying the value of “a” leaves us at a factor-of-10 improvement. Even the worst case isn’t bad and certainly worth going after.
** dotMath is an expression compiler written entirely in C# and available for download at CodePlex.