Generic arithmetic

In terms of syntax, the capabilities of Delphi generics are closely modelled on C#’s implementation, at least as found in C# 2.0, even down to certain quirks that are otherwise difficult to explain — e.g., Delphi using ‘record’ as the name for the general value type constraint (C# uses ‘struct’ for the same thing, with the same overloading of meaning). Modelling as much as possible on the C# implementation is in some ways a good thing (I’ve been reading up on Java generics recently, and ‘oh dear’ is all I have to say about them!). In other ways it’s a bit annoying though, the negative aspects in my view being centred on the limited set of available constraints.

One particularly significant omission here are operator constraints, i.e. the ability to specify that a type parameter must/can/will suppport the + operator or whatever. Looking over the C# side of the fence, I’ve read of various ways of circumventing this. An early suggestion — advocated by a certain Anders Hejlsberg when generics were first introduced to C# — was to define a set of helper classes (specifically, an abstract generic base class and one concrete descendant per type). The basic idea here is similar to the one used by the Delphi RTL’s generic collection classes (IComparer and all that). Personally I find Generics.Defaults’ use of interfaces all a bit heavyweight-yet-hacky (truly, ‘IInterface=IUnknown’ is to Delphi what ‘generic type instantiation=type erasure’ is to Java…). So, for experimental purposes, I came up with the following metaclass-using variant instead (much cleaner IMO!). As this is just a test, I’ve only defined an Add helper method, though in principle others like Substract and Multiply could be given too:

uses
  SysUtils,
  Generics.Collections,
  Diagnostics;

type
  TCalculator<T> = class abstract
    class function Add(const A, B: T): T; virtual; abstract;
  end;

  TDoubleCalculator = class(TCalculator<Double>)
    class function Add(const A, B: Double): Double; override;
  end;

  TIntegerCalculator = class(TCalculator<Integer>)
    class function Add(const A, B: Integer): Integer; override;
  end;

  TSingleCalculator = class(TCalculator<Single>)
    class function Add(const A, B: Single): Single; override;
  end;

  TGenericMaths<T; Calculator: TCalculator<T>> = record
    class function Sum(List: TList<T>): T; static;
  end;

class function TDoubleCalculator.Add(const A, B: Double): Double;
begin
  Result := A + B;
end;

class function TIntegerCalculator.Add(const A, B: Integer): Integer;
begin
  Result := A + B;
end;

class function TSingleCalculator.Add(const A, B: Single): Single;
begin
  Result := A + B;
end;

class function TGenericMaths<T, Calculator>.Sum(List: TList<T>): T;
var
  Elem: T;
begin
  Result := Default(T);
  for Elem in List do
    Result := Calculator.Add(Result, Elem);
end;

All pretty trivial I hope you agree. The next question, though, is how the virtual method calls would impact performance, so I next wrote the following test code —

var
  I, IntElem, IntTotal: Integer;
  DoubleElem, DoubleTotal: Double;
  DoubleList: TList<Double>;
  IntList: TList<Integer>;
  SingleElem, SingleTotal: Single;
  SingleList: TList<Single>;
  Stopwatch: TStopwatch;
begin
  Randomize;
  Writeln('Testing integers - generating data...');
  IntList := TList<Integer>.Create;
  try
    IntList.Capacity := $1FFFFFF;
    for I := 1 to IntList.Capacity do
      IntList.Add(Random(20));
    for I := 1 to 3 do
    begin
      Stopwatch := TStopwatch.StartNew;
      IntTotal := TGenericMaths<Integer, TIntegerCalculator>.Sum(IntList);
      Stopwatch.Stop;
      Writeln('TGenericMaths calculated ', IntTotal, ' and took ',
        Stopwatch.ElapsedMilliseconds, 'ms');
      Stopwatch := TStopwatch.StartNew;
      IntTotal := 0;
      for IntElem in IntList do
        IntTotal := IntTotal + IntElem;
      Stopwatch.Stop;
      Writeln('    Doing things manually calculated ', IntTotal, ' and took ',
        Stopwatch.ElapsedMilliseconds, 'ms');
    end;
  finally
    IntList.Free;
  end;
  Writeln('');
  Writeln('Testing doubles - generating data...');
  DoubleList := TList<Double>.Create;
  try
    DoubleList.Capacity := $FFFFFF;
    for I := 1 to DoubleList.Capacity do
      DoubleList.Add(Random);
    for I := 1 to 3 do
    begin
      Stopwatch := TStopwatch.StartNew;
      DoubleTotal := TGenericMaths<Double, TDoubleCalculator>.Sum(DoubleList);
      Stopwatch.Stop;
      Writeln('TGenericMaths calculated ', DoubleTotal, ' and took ',
        Stopwatch.ElapsedMilliseconds, 'ms');
      Stopwatch := TStopwatch.StartNew;
      DoubleTotal := 0;
      for DoubleElem in DoubleList do
        DoubleTotal := DoubleTotal + DoubleElem;
      Stopwatch.Stop;
      Writeln('    Doing things manually calculated ', DoubleTotal, ' and took ',
        Stopwatch.ElapsedMilliseconds, 'ms');
    end;
  finally
    DoubleList.Free;
  end;
  Writeln('');
  Writeln('Testing singles - generating data...');
  SingleList := TList<Single>.Create;
  try
    SingleList.Capacity := $1FFFFFF;
    for I := 1 to SingleList.Capacity do
      SingleList.Add(Random);
    for I := 1 to 3 do
    begin
      Stopwatch := TStopwatch.StartNew;
      SingleTotal := TGenericMaths<Single, TSingleCalculator>.Sum(SingleList);
      Stopwatch.Stop;
      Writeln('TGenericMaths calculated ', SingleTotal, ' and took ',
        Stopwatch.ElapsedMilliseconds, 'ms');
      Stopwatch := TStopwatch.StartNew;
      SingleTotal := 0;
      for SingleElem in SingleList do
        SingleTotal := SingleTotal + SingleElem;
      Stopwatch.Stop;
      Writeln('    Doing things manually calculated ', SingleTotal, ' and took ',
        Stopwatch.ElapsedMilliseconds, 'ms');
    end;
  finally
    SingleList.Free;
  end;
  ReadLn;
end.

Leaving aside the irony of massive code duplication in code to do with generics (ahem), here’s a screenshot of some example output when I run the resulting program on my laptop (click on the graphic to see it at full size):

This was using the default release build configuration. Using the default debug configuration, the numbers are much worse all round obviously, but the difference between the generic and manual single data test is somewhat narrower, for reasons I don’t have the knowledge to suggest.

Anyhow, plainly, nothing would be as good as operator constraints being implemented by the compiler. Nonetheless, there are apparently alternative methods available in C# now that drastically narrow or even remove the performance gap between generic and manual approaches, if perhaps at the cost of compile-time type checking (see here or here). So far as I can tell, these rely on things not available in Delphi-land. I wonder whether any performance geek has ideas to the contrary…?

var
I, IntElem, IntTotal: Integer;
DoubleElem, DoubleTotal: Double;
DoubleList: TList<Double>;
IntList: TList<Integer>;
SingleElem, SingleTotal: Single;
SingleList: TList<Single>;
Stopwatch: TStopwatch;
begin
Randomize;
Writeln(‘Testing integers – generating data…’);
IntList := TList<Integer>.Create;
try
IntList.Capacity := $1FFFFFF;
for I := 1 to IntList.Capacity do
IntList.Add(Random(20));
for I := 1 to 3 do
begin
Stopwatch := TStopwatch.StartNew;
IntTotal := TGenericMaths<Integer, TIntegerCalculator>.Sum(IntList);
Stopwatch.Stop;
Writeln(‘TGenericMaths calculated ‘, IntTotal, ‘ and took ‘,
Stopwatch.ElapsedMilliseconds, ‘ms’);
Stopwatch := TStopwatch.StartNew;
IntTotal := 0;
for IntElem in IntList do
IntTotal := IntTotal + IntElem; //well, Inc(IntTotal, IntElem) would be better…
Stopwatch.Stop;
Writeln(‘    Doing things manually calculated ‘, IntTotal, ‘ and took ‘,
Stopwatch.ElapsedMilliseconds, ‘ms’);
end;
finally
IntList.Free;
end;
Writeln(”);
Writeln(‘Testing doubles – generating data…’);
DoubleList := TList<Double>.Create;
try
DoubleList.Capacity := $FFFFFF;
for I := 1 to DoubleList.Capacity do
DoubleList.Add(Random);
for I := 1 to 3 do
begin
Stopwatch := TStopwatch.StartNew;
DoubleTotal := TGenericMaths<Double, TDoubleCalculator>.Sum(DoubleList);
Stopwatch.Stop;
Writeln(‘TGenericMaths calculated ‘, DoubleTotal, ‘ and took ‘,
Stopwatch.ElapsedMilliseconds, ‘ms’);
Stopwatch := TStopwatch.StartNew;
DoubleTotal := 0;
for DoubleElem in DoubleList do
DoubleTotal := DoubleTotal + DoubleElem;
Stopwatch.Stop;
Writeln(‘    Doing things manually calculated ‘, DoubleTotal, ‘ and took ‘,
Stopwatch.ElapsedMilliseconds, ‘ms’);
end;
finally
DoubleList.Free;
end;
Writeln(”);
Writeln(‘Testing singles – generating data…’);
SingleList := TList<Single>.Create;
try
SingleList.Capacity := $1FFFFFF;
for I := 1 to SingleList.Capacity do
SingleList.Add(Random);
for I := 1 to 3 do
begin
Stopwatch := TStopwatch.StartNew;
SingleTotal := TGenericMaths<Single, TSingleCalculator>.Sum(SingleList);
Stopwatch.Stop;
Writeln(‘TGenericMaths calculated ‘, SingleTotal, ‘ and took ‘,
Stopwatch.ElapsedMilliseconds, ‘ms’);
Stopwatch := TStopwatch.StartNew;
SingleTotal := 0;
for SingleElem in SingleList do
SingleTotal := SingleTotal + SingleElem;
Stopwatch.Stop;
Writeln(‘    Doing things manually calculated ‘, SingleTotal, ‘ and took ‘,
Stopwatch.ElapsedMilliseconds, ‘ms’);
end;
finally
SingleList.Free;
end;
ReadLn;
Advertisements

9 thoughts on “Generic arithmetic

  1. Brilliant. I especially love this line:

    “IInterface=IUnknown’ is to Delphi what ‘generic type instantiation=type erasure’ is to Java”

    I think there are some pretty deep compiler dependencies on IUnknown, and allowing an interface to not be reference counted, would be (a) wonderful, and I think (b) really hard to put into the current compiler design. Maybe in the totally-new-compiler future, we could have interfaces that don’t require reference counting.

    Just today I had to debug some code that had, for the same object (a VCL Frame descendant), cases where it is freed by reference-counting reaching zero, plus cases where it was freed from code explicitly (bad), and then, even worse, places where it was freed by special CM_RELEASE handlers someone added. Can you say object-lifetime hell? Sure you can.

    Warren

    • Hi Warren

      ‘I think there are some pretty deep compiler dependencies on IUnknown’

      Hey, stuff compiler dependencies, there are some pretty deep dependencies in my own code! 😉 The way I look at it, Delphi’s interface type serves three purposes, all good ones when taken separately: making COM development easier, allowing custom code to make use of the compiler’s automatic reference counting abilities, and to give Delphi an interface type a la Java’s (remembering we’re talking about 1997, when interfaces made their entrance to Delphi). Unfortunately, while the first two purposes go together fairly well (explicit GUIDs for type identity are ugly but tolerable), the third certainly doesn’t. In fact, IInterface probably serves the interface purpose the worst of the three!

      Basically, I think I’d quite like a new type, not called IInterface (how about ‘protocols’ a la Objective C?) that could be ‘implemented’ (maybe just duck-typed) to *any* sort of method/routine container, be it a class, metaclass, record or even unit.

  2. Generics.Defaults may be hacky, but certainly not heavyweight.

    It implements the interfaces as global functions which do not require any reference counts, nor can the reference counting mechanism get in the way.

    There are no instances, since the methods do not need access to any instance variables. This makes the interfaces extremely lightweight. Nothing is allocated, nothing is managed by reference counts. If the author had used the common way of doing interfaces, it would have been more heavyweight.

    FWIW, I would have liked a mechanism to implement similar things for user code, so we could implement IToStringConverter or some such in a similarly lightweight fashion.

    I think a new type, duck-typed to all objects matching the signature, and even usable as generic constraint, would be great.

    • “Generics.Defaults may be hacky, but certainly not heavyweight”

      For sure, its pre-baked implementations are so by dint of a ‘COM development in C’ approach, but the framework it defines for custom comparers isn’t. I mean really: interfaces are defined, only for a 3-level class hierarchy to be too, only this hierarchy isn’t actually used by the default implementations, and moreover, ‘implements’ the interface methods only by stubbing them with abstract methods.

      “There are no instances, since the methods do not need access to any instance variables. This makes the interfaces extremely lightweight. Nothing is allocated, nothing is managed by reference counts.”

      Great! All the advantages of using metaclasses like in my example, only with about ten times the code, a hundred times the complication, and a thorough-going reliance on language implementation details.

      “If the author had used the common way of doing interfaces, it would have been more heavyweight.”

      The author didn’t *have* to use interfaces at all.

      ‘FWIW, I would have liked a mechanism to implement similar things for user code, so we could implement IToStringConverter or some such in a similarly lightweight fashion.’

      Or just have used metaclasses instead of interfaces! Presumably Delphi-style metaclasses don’t really exist though, since C# and Java don’t have them…

      • <>

        I already tried a similar approach with metaclasses several years ago. I don’t remember the exact details anymore, but what one can do with metaclasses is limited, compared to what interfaces provide. I finally found I had to use interfaces, nolens volens, although I really wanted to avoid them.

        The interface approach was the only possible way, AFAICT. It works for your example, fine, but AFAIR, it has its limitations. I’ll try to find the code I then had to be able to actually tell you what wall I hit.

        I wonder how you’d implement the framework in Generics.Defaults using your approach, instead of the current one with interfaces. A simple example for only a few built-in types would do.

      • ‘what one can do with metaclasses is limited, compared to what interfaces provide’

        For sure – in particular, you can’t have overlapping hiearchies, and a lack of state is enforced without a bit of work. However, if the requirements are simple, compilicating matters with Delphi-style interfaces just makes things… complicated.

        ‘I’ll try to find the code I then had to be able to actually tell you what wall I hit.’

        That would be interesting.

        ‘I wonder how you’d implement the framework in Generics.Defaults using your approach’

        I’ll have a go some time.

      • Come to think of it, was the problem being able to specify custom comparers? The compiler doesn’t allow using the ‘class of’ syntax on a generic.

        • [[
          Come to think of it, was the problem being able to specify custom comparers? The compiler doesn’t allow using the ‘class of’ syntax on a generic.
          ]]

          No. There were other problems I encountered.

        • “There were other problems I encountered.”

          E.g.? Playing around, I think I’ve just done it in the case of IComparer.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s