Focus, callstack and recursive processing

Call stack limitations

The world of mobile computing is getting better and better, but there are some limitations when dealing with smart gadgets running iOS or Android. The first thing is obviously the speed, which doesn’t even come close to what an average home computer can muster. Even my 5 year old test machine can outrun any mobile device without making so much as a dent in the cpu-o-meter.

The second limitation people are going to discover, depending of-course on the line of work you do, is that mobile devices is the proverbial banker when it comes to memory – implying that your call stack is but a microbial-fraction of what we are used to. What does this mean? Well every time you call a method under Javascript, you eat up one call-slot. If this procedure in turns calls another, and another (and so on) it quickly gobbles up the meager call stack limit. The size of the call stack is varied and depends on the vendor, as of writing iOS is sticking to it’s near obsolete range of 100 recursive calls while Android is said (I couldn’t find any official information on this) to have a call stack of about 800.

To kiss or not to kiss, that is the question

Kiss (keep it simple stupid) is one way to go when it comes to mobile development. But there are times when you must resort to classical speed mechanisms to reach the full potential of a system. As such I am in the process of optimizing the base-classes for speed and simplicity (some form of balance preferably). The method is really simple and it’s known as loop expansion (or just “unrolling”). Let’s for sake of argument say you have a control with a lot of child objects, like a grid or a list. Instead of doing a simple for/next loop, like this:

[sourcecode language=”delphi”]
Procedure TMyObject.DoSomething;
var
x:Integer;
Begin
for x:=0 to FChildren.Count-1 do
Begin
process(FChildren[x]);
end;
end;
[/sourcecode]

The above example is perfectly valid, but it’s quite slow depending on the data-load you expect. A list control could be expected to handle hundreds if not thousands of elements – so we want to speed things up and minimize loop time:

[sourcecode language=”delphi”]
Procedure TMyObject.DoSomething;
var
mLongs:Integer;
mShort:Integer;
mCount:Integer;
mIndex:Integer;
begin
mCount:=FChildren.Count;
mLongs:=mCount shr 3;
mShort:=mCount mod 8;

while mLongs>0 do
Begin
process(FChildren[mIndex]);inc(mIndex);
process(FChildren[mIndex]);inc(mIndex);
process(FChildren[mIndex]);inc(mIndex);
process(FChildren[mIndex]);inc(mIndex);
process(FChildren[mIndex]);inc(mIndex);
process(FChildren[mIndex]);inc(mIndex);
process(FChildren[mIndex]);inc(mIndex);
process(FChildren[mIndex]);inc(mIndex);
dec(mLongs);
end;

while mShort>0 do
Begin
process(FChildren[mIndex]);inc(mIndex);
dec(mShort);
end;
end;
[/sourcecode]

Speed-wise, at least when it comes to crunching fixed data like pixels or typed JS arrays, is nearly incomparable to the first approach. It obviously produce more code – but the benefits are just to good to ignore (roughly 4 times as fast).

As long as your final build does not exceed 10 megabytes, which is Apple’s limit on single javascript files, it’s not a problem (and that would be a huge, huge project if you ask me).

Men first, women and children last

When doing recursive calls that affect an entire object model you have to deal with the men first, meaning of-course those elements that does not have children attach to them (oh this is gonna get me into so much trouble if my wife reads it). Why? Because we want to minimize the number of recursive calls (or steps taken) a control has to make. Let’s use the simple formula to demonstrate (this would also be loop expanded in the final release):

[sourcecode language=”delphi”]
Procedure TMyObject.DoSomething;
var
x:Integer;
mCount:Integer;
mStack: TObjectList;
mObj: TObject;
Begin
//avoid multiple calls to getCount in FChildren array
mCount:=FChildren.Count-1;
for x:=0 to mCount do
Begin
//minimize call to getItem in FChildren array
mObj:=FChildren[x];
if mObj.count=0 then
// No kids? Do singles first
process(mObj) else
Begin
//kids? Ok, we’ll handle that later
if mStack=NIL then
mStack:=TobjectList.Create;
mStack.add(mObj);
end;
end;

if mStack<>NIL then
Begin
mCount:=mStack.Count;
while mCount>0 do
Begin
mObj:=mStack[mCount-1];
process(mObj);
dec(mCount);
end;
mStack.free;
end;
end;
[/sourcecode]

And last but not least, the “process” method should be inlined if possible, thats 50% of the point here. If you can avoid a secondary call – then avoid it, that’s how you cut down on call-stack overload and as a nice benefit you get a speed boost.

Notes

#1 [29.09.11, 18:31]: Eric Grange pointed out (as did two readers on this page) that the same effect will happen if we apply FChildren.Count-1 and start from zero. That would be slightly faster to since we dont execute a continous subtraction of the index. A clear error on my part.

#2 [29.09.11, 18:31]: Interestingly, the -1 trick was originally used for string processing (hence starting at 1) and has nothing to do with speed per-see, except that you save an “if FChildren.Count>0 then” in some languages. But this tiny advantage is indeed lost by the use of [-1] in the loop itself. Some basic compilers will execute the code even if FChildren.count =0. This is an old habit from the days of Amiga BlitzBasic programming.

#3 [29.09.11, 18:35]: Also the “process()” call should only be concidered pseudo code. It’s the loop expansion that’s being demonstrated. Preferably you would work with the data directly at this point rather than call another proc, since the whole point is to limit the number of calls while speeding up a process. It’s not meant as a literal example, but as the bare-bones of a technique.