A quick lesson in performance tuning. In the arduino code base, people will often use Serial.parseInt to read integer data from a Serial stream, and someone was asking me about the overhead involved. So, I decided to take a look for them. First, I looked at the implementation of parseInt:
long Stream::parseInt()
{
return parseInt(NO_SKIP_CHAR); // terminate on first non-digit character (or timeout)
}Ok, so it calls through to another function, adding a skip character that means "no skip character". Here's a first red flag. So, let's look at that function:
long Stream::parseInt(char skipChar)
{
bool isNegative = false;
long value = 0;
int c;
c = peekNextDigit();
// ignore non numeric leading characters
if(c < 0)
return 0; // zero returned if timeout
do{
if(c == skipChar)
; // ignore this charactor
else if(c == '-')
isNegative = true;
else if(c >= '0' && c <= '9') // is c a digit?
value = value * 10 + c - '0';
read(); // consume the character we got with peek
c = timedPeek();
}
while( (c >= '0' && c <= '9') || c == skipChar );
if(isNegative)
value = -value;
return value;
}Where to begin with the potential problems/performance issues? The opening bit of the function is mostly ok (not going to dig into peekNextDigit today), it's the loop that I see a lot of room for improvement in.
First off is the conditional ordering. When parsing ints, you're likely to be getting multi-digit numbers, which means the most common thing you are going to get will be ... digits. However, it checks for the skip character first, then checks for the - character to flag a negative number, and then it checks to see if c is between the characters '0' and '9' to build the value. After the first time through the loop, however, there's going to be a redundant check against the digit values (once the if chain inside the loop, and one in the while conditional for the loop), but there's also going to be two comparisons. One against the skipChar, and one against the negative sign (even though the while loop conditional will ensure that a '-' never reaches that code). How might we write this better?
Well, we know we really only need to check the first character read to see if it's a '-'. So why bother doing that in the loop at all? Then, let's see if we can get rid of some of the extra-redundant checks that are going on in here:
long Stream::parseInt(char skipChar)
{
// don't call the skipChar version, that is just dumb
long value = 0;
char c = peekNextDigit();
if(c<0) return 0;
// check if we're negative, and if so, skip to the next character
bool isNegative = (c=='-');
if(isNegative) { read(); c = timedPeek(); }
while( isdigit(c) || c == skipChar) {
if(c != skipChar) {
value = (value * 10) + (c - '0');
}
read(); c = timedPeek();
}
if(isNegative) value = -value;
return value;
}There, that's a fair bit better. There's still going to be a redundant check against the character range for the first digit for non-negative numbers (because peekNextDigit will do this as well), but without also digging into/fixing peekNextDigit, there's not a lot we can do about that. Now, though, for each digit after the first, there will be only 1 range comparison, and two comparisons against the skip character (vs. the original code which is 2 range comparisons (which is itself a 3 stage operation), 2 skip char comparisons, and a '-' comparison). Also note the use of isdigit(c). On some platforms, this is a simple memory load and bit check. Even on avr, the range check that it does producses smaller code than the explicit conditional.
However, we're still not done. Given that the version of parseInt that takes a skipChar is a protected function (meaning, most arduino users will never be able to call it), and given that pretty much every time I've seen people call parseInt, it's NEVER been with a skip character defined, let's make a more refined version of parseInt:
long Stream::parseInt()
{
// don't call the skipChar version, that is just dumb
long value = 0;
char c = peekNextDigit();
if(c<0) return 0;
// check if we're negative, and if so, skip to the next character
bool isNegative = (c=='-');
if(isNegative) { read(); c = timedPeek(); }
while( isdigit(c)) {
value = (value * 10) + (c - '0');
read(); c = timedPeek();
}
if(isNegative) value = -value;
return value;
}Hey, no comparsisons against an uninteresting skipChar, much better!
==some cyclecount breakdown on avr==
There are still a bunch of problems with this code, especially if one is playing on avr. The first is the fact that value is a 32-bit long. That's 4 bytes - all avr opcodes only work on single byte values. This means that the "value * 10" multiply there is going to actually call a function which will take ~35 cycles. Then, even though the c - '0' will only take one cycle, adding that result into value will take 4 more cycles.
Also, since value is 4 bytes, it's using enough registers that it needs to be saved/restored around the calls to read/timedPeek - there's another 16 cycles (why so many? the std/ldd opcodes, when you are using a displacement, the stores and loads are 2 cycles for each byte, and there's 4 bytes, so 4 reads, 4 writes, at 2 cycles each is 16 cycles)
That means that using parseInt on AVR has ~56 cycles of overhead per digit just from dealing with a 4 byte value, and that's not including all the other overhead that's going on in here.
TODO: provide disassembly of the various functions as well as timings for performance.