[fpc-devel] Little feature teaser

[Sven Barth]

On 02.08.2013 17:01, Mattias Gaertner wrote:
> On Fri, 02 Aug 2013 13:18:53 +0200
> Sven Barth <pascaldragon at googlemail.com> wrote:
>
>> [...]
>> === source begin ===
>>
>> program tgenfuncs;
>>
>> {$modeswitch result}
>>
>> generic function IsIn<T>(aElement: T; const aArray: array of T): Boolean;
>> var
>>     elem: T;
>> begin
>>     for elem in aArray do
>>       if elem = aElement then
>>         Exit(True);
>>     Result := False;
>> end;
>>
>> begin
>>     Writeln(specialize IsIn<LongInt>(42, [21, 42, 84]));
>>     Writeln(specialize IsIn<LongInt>(5, [21, 42, 84]));
>
> What is the speed?
> Is it much slower compared to a line of "if
> (aElement=val) or (..)... then" or a "case" statement?

You can do the comparison yourself, as a "specialize IsIn<LongInt>" will 
generate a version of "IsIn<T>" where each "T" is replaced by "LongInt" 
and be completely reparsed. So it's the same as if you wrote the 
following from the beginning:

=== code begin ===

function IsIn(aElement: LongInt; const aArray: array of LongInt): Boolean;
var
   elem: LongInt;
begin
   for elem in aArray do
     if elem = aElement then
       Exit(True);
   Result := False;
end;

=== code end ===

AFAIK the compiler implements the for-in for arrays as a normal for-loop 
and thus I'd suspect that the "IsIn<T>" function is faster for a larger 
amount of elements (=> less jumps). Your approach with ifs is basically 
a loop unrolling which is better with fewer iterations.
If you'd declare the "IsIn<T>" function as "inline" and the compiler 
would correctly handle this(*1) the compiler could in theory be able to 
fold the complete for-loop together in the example I gave (because only 
constants are used there). I don't know though whether the compiler is 
currently able to deduce this (I'll need to test that ^^).

(*1) The problem currently is that the implementation needs to be 
available when the call is parsed, but specializations are created at 
the end of parsing a unit. So this would need to be adjusted to allow 
inline generic functions to work correctly (I plan this, but not now).

> What about code size?

The code size for one unit is the same as if you had (in that example) 
declared a variant of "IsIn" for each "LongInt" and "String". So for 
each "IsIn<T>" specialization with different types new code is generated 
if it does not yet exist in that unit. This means that if you call 
"IsIn<LongInt>" in different units you'll have a "IsIn<LongInt>" 
implementation in each unit. This is the same as for generic types btw.

Regards,
Sven