Returning to SlowCode

At the end of this chapter, I'll return to the now well-known SlowCode example. At the end of the previous chapter, we significantly adapted the code and ended with a version that calculates prime numbers with the Sieve of Eratosthenes (SlowCode_Sieve). That version processed 10 million numbers in 1,072 milliseconds. Let's see if we can improve that.

The obvious target for optimization is the Reverse function which creates the result by appending characters one at a time. We've seen in this chapter that modifying a string can cause frequent memory allocations:

function Reverse(s: string): string;
var
  ch: char;
begin
  Result := '';
  for ch in s do
    Result := ch + Result;
end;

Instead of optimizing this function, let's look at how it is used. The Filter method uses it to reverse a number:

reversed := StrToInt(Reverse(IntToStr(i)));

This statement brings in another memory allocation (in function IntToStr which creates a new string), and executes some code that has to parse a string and return a number (StrToInt). Quite some work for an operation that doesn't really need strings at all.

It turns out that it is very simple to reverse a decimal number without using strings. You just have to repeatedly divide it by 10 and multiply remainders back into a new number:

function ReverseInt(value: Integer): Integer;
begin
  Result := 0;
  while value <> 0 do
  begin
    Result := Result * 10 + (value mod 10);
    value := value div 10;
  end;
end;

The new Filter method can then use this method to reverse a number:

function Filter(list: TList<Integer>): TArray<Integer>;
var
  i: Integer;
  reversed: Integer;
begin
  SetLength(Result, 0);
  for i in list do
  begin
    reversed := ReverseInt(i);
    if not ElementInDataDivides(list, reversed) then
    begin
      SetLength(Result, Length(Result) + 1);
      Result[High(Result)] := i;
    end;
  end;
end;

The new code in the demo program, SlowCode_Sieve_v2 indeed runs a bit faster. It processes 10 million elements in 851 milliseconds, which is roughly a 20% improvement.

Is there something more that we learned in this chapter and can be applied to that program? Sure—turn on the optimization! Just add one line—{$OPTIMIZATION ON}—and you'll get a significantly faster version. SlowCode_Sieve_v2_opt processes 10 million elements in a mere 529 ms!

There is still room for improvement in that program. It will, however, have to wait until the next chapter.