The FMX enumeration anti-pattern

[Update: a couple of months after I wrote this post, Delphi XE3 was released. In it, the issue I discuss below was mostly, if not entirely eradicated from the FMX source code.]

Checking up on DelphiFeeds.com, I see a member of Embarcadero Developer Relations (Stephen Ball) has just blogged some example code. In it, he demonstrates a class helper that adds methods for enumerating a FireMonkey control, doing so in a way that just picks out nested objects of a certain class. Here’s the gist of it:

function TFMXObjectHelper.ChildrenCountOfType(aType: TClass): Integer;
var
  Idx: Integer;
  Obj: TFmxObject;
begin
  Result := 0;
  for Idx := 0 to Pred(Self.ChildrenCount) do
  begin
    Obj := Self.Children[Idx];
    if Obj is aType then Inc(Result);
    Result := Result + Obj.ChildrenCountOfType(aType);
  end;
end;

function TFMXObjectHelper.ChildrenOfTypeAtIndex(aType: TClass; Index: Integer): TFMXObject;
var
  I, Remaining: Integer;
  Obj: TFmxObject;
  CurrItem: TFmxObject;
  Nodes: Integer;
begin
  Remaining := Index;
  for I := 0 to Pred(Self.ChildrenCount) do
  begin
    CurrItem := Self.Children[I];
    if (CurrItem is aType) then
    begin
      if (Remaining <= 0) then
        Exit(CurrItem)
      else
        Dec(Remaining,1);
    end;
    Nodes := CurrItem.ChildrenCountOfType(aType);
    if (Nodes <= Remaining) then
      Dec(Remaining, Nodes)
    else
    begin
      Obj := CurrItem.ChildrenOfTypeAtIndex(aType, Remaining);
      Exit(Obj);
    end;
  end;
end;

And, in use:

var
  Item: TTreeViewItem;
begin
  for I := 0 to Pred(tvAssociations.ChildrenCountOfType(TTreeViewItem)) do
  begin
    Item := tvAssociations.ChildrenOfTypeAtIndex(TTreeViewItem, I) as TTreeViewItem;
    //do some stuff with the item
  end;

Hmm… Let’s say tvAssociations contains 500 items. Using this code, first the entire list of child (and grandchild) controls is walked through to determine how many of them are of the desired class (i.e., TTreeViewItem), then the list is traversed again until the first matching child object is found, then traversed from the start once more to find the second, then from the beginning once again to find the third matching child object and so on. At the risk of sounding picky, isn’t this a good example of an anti-pattern?

‘Now now’, you might say, ‘no need to play high and mighty over a quick demo from a Developer Relations guy!’ And indeed, if this problem extended no further than a quick demo from a member of Developer Relations I would agree. However, if you browse the FMX source code, you will find this anti-pattern repeated again and again. Ever wondered why large menus in FMX can be so damn slow, even when it is the native menu bar being used? Wonder no more.

Part of the issue is that FMX, while borrowing the VCL’s component model, does not use TCollection, which would otherwise force the use of a single class for child objects. Instead, you can in principle put anything on a FMX TListBox (for example). In implementing the Items property of TListBox, the FMX author was then led to use the anti-pattern under discussion, since while in almost all cases a list box’s content will be comprised of TListBoxItem instances only, it might not be.

Particularly in the menu code, this problem is made worse by an addiction to an indexing style…

for I := 0 to Obj.Count - 1
  if Obj[I].Foo then ...

…when a more basic enumeration pattern is all that is needed:

for Item in Obj do
  if Item.Foo then ...

This snippet uses the for/in syntax, though something like FindFirst/FindNext/FindClose implements the underlying pattern just as well.

For sure, the phrase ‘more basic’ here only applies on one level. This is because in order to fully realise the ‘basic’ enumeration pattern, you need to cover the possibility that code may attempt to change the enumerated object’s state during the middle of it being enumerated (in particular, what should happen when an item is added, or attempted to be added?). Even still, the benefit of this approach – assuming it is implemented properly – is that there is no need to enumerate everything of the container internally if the calling code proves only interested in a child object that comes early on. Think of FindFirst/FindNext/FindClose: if those functions didn’t exist, and you instead had a pair of functions on the WalkEverythingToFindTheCount/WalkAgainToFindTheNth anti-pattern, enumerating the top level directory of a drive or device that contained lots of files could take ages!

Nonetheless, if implementing a bare-bones enumerator pattern is considered too taxing, a reasonable halfway house is to implement a single function that returns a dynamic array. This is the style used by Rtti.pas, and while it still involves enumerating everything internally up front, you then avoid repeatedly walking up from the start again thereafter:

type
  TFmxObjectHelper = class helper for TFMXObject
  strict private
    procedure DoAddNestedObjects<T: class>(Parent: TFmxObject;
      TopLevelOnly: Boolean; var Arr: TArray<T>; var Count: Integer);
  public
    function GetNestedObjects<T: class>(TopLevelOnly: Boolean = False): TArray<T>;
  end;

procedure TFmxObjectHelper.DoAddNestedObjects<T>(Parent: TFmxObject;
  TopLevelOnly: Boolean; var Arr: TArray<T>; var Count: Integer);
var
  Child: TFmxObject;
  I: Integer;
begin
  for I := 0 to Parent.ChildrenCount - 1 do
  begin
    Child := Parent.Children[I];
    if Child is T then
    begin
      if Length(Arr) = Count then SetLength(Arr, Count + 64);
      Arr[Count] := T(Child);
      Inc(Count);
    end;
    if not TopLevelOnly then DoAddNestedObjects<T>(Child, TopLevelOnly, Arr, Count);
  end;
end;

function TFmxObjectHelper.GetNestedObjects<T>(TopLevelOnly: Boolean): TArray<T>;
var
  Count: Integer;
begin
  Count := 0;
  DoAddNestedObjects<T>(Self, TopLevelOnly, Result, Count);
  SetLength(Result, Count);
end;

Then, in use:

var
  Item: TTreeViewItem;
begin
  for Item in tvAssociations.GetNestedObjects<TTreeViewItem> do
  begin
    //do some stuff with the item
  end;

Notice this approach also has the benefit of being slightly more stronger typed that the original – i.e., no ‘as’ cast is needed – since the array returned is an array of the class the client code is interested in, not of TFmxObject.

Advertisements

30 thoughts on “The FMX enumeration anti-pattern

    • Well… the non-visual side of the OS X support is good, albeit with the benefit of not being all that new (it’s heavily indebted to Kylix). As for FMX though, I think I’ve said enough myself!

      • Kylix 1 was so slow, that i never used Kylix again 🙂
        Of course CPU are faster today, yet i still fill that was not assuring comparison.

        Abour XE2 code quality – at least it is kinda poetic to read some places.
        I would just quote my qc 101306. I was really stunned reading that part 🙂


        NormalizeRect
        31337 Eastern Eggs for 31337 readers.
        Pure mathematical beauty.
        Performance without performance in mind.

        procedure TRectF.NormalizeRect; – nice and beautiful.

        procedure TRect.NormalizeRect; – nice puzzle. But if implemented like one above, would be both faster an easier to read.

        function NormalizeRect(const ARect: TRectF): TRectF; overload;
        1) should be merged with TRectF method – one should be proxy for another.
        2) the code itself… Abomination, sorry.

      • “Kylix 1 was so slow, that i never used Kylix again”

        With respect to what exactly? My comment was solely with respect to the compiler and RTL, so anything concerning the IDE or CLX (for example) would be irrelevant.

        • Both IDE visual designer (more) and running up (less, but noiticeable),

          It was run on Celeron3 850MHz / 768MB Win2000 under VmWare with video driver compiled and installed.
          I could easily run some Linux games inside like 3D pinball and such, so it was not mere lack of processor power.

          And why would you wrote IDE off ? The visual designer is built atop of VCL/CLX/FMX and is just an advanced user of it. A kind of stress-test.
          And the rest of IDE is just an application made with VCL/CLX/FMX.
          If IDE is slow or unreliable it pretty well characterizes the current library state.

          • Except Kylix was a little different. It was a Win32 binary running under Wine. That’s considerably different than a binary compiled native for the OS, which makes calls into the OS run-time, instead of making calls into Win which are, in turn, manipulated and passed on to the OS. Kylix itself had a huge emulation layer between it and the OS that projects built with Kylix did not have.

        • “If IDE is slow or unreliable it pretty well characterizes the current library state.”

          The compiler and RTL in XE2/OS X is good, partly because it was already mature, and FMX is crap – that’s all I was saying. You’ve grabbed hold of my use of the word ‘Kylix’ and taken it completely out of context – I made no claim whatsoever about the IDE, let alone CLX.

          And no, ‘if the IDE is slow or unreliable’, that does not in itself say anything about other things – if both the IDE and visual framework in Kylix were dodgy, it was for independent reasons, since the IDE didn’t use CLX. (It was a modified version of the Delphi IDE, running via WineLib.)

          By the same token, the fact FMX is crap isn’t anything technically to do with CLX either, since they are completely separate codebases. In contrast, the OS X compiler and RTL in XE2 *do* have a lot to do with their Kylix equivalents, since they are developments of them.

  1. That’s “ouch” again… about as bad as that other snippet around text rendering that was posted sometime ago, and the worse is that indeed, they’re not isolated cases… 😦

  2. Also I disagree with devrel or official sample sub-optimal code being somewhat “okay”, as these are the articles people will build upon and reuse as reference material.

    When you encounter them later on in your own code-base, and have to explain that the guy and company that posted the example didn’t knew how to properly code or use their own product, you always have to face a wall of incomprehension.

    • ‘Also I disagree with devrel or official sample sub-optimal code being somewhat “okay”’ – my aim was to be constructive, especially as this isn’t the first time I’ve blogged about a Developer Relations person being uninformed… In fact, if it weren’t for the book (and therefore, possibility of being accused of having mixed motives), I would have posted too about the DLL/dylib article the same person did a bit ago.

      • I wouldn’t have minded that post. I’ve just recently started playing with FMX, and tried using that article as a learning experience. It wasn’t awful, but I did encounter a couple of issues with it. Emailing the author wasn’t very helpful either, unfortunately. His title is Technical Sales Consultant and is based in UK. Not sure how that actually compares to the DevRel guys I know.

      • Well, I’ve termed him as part of ‘Developer Relations’ because he seems to be doing the job people in Developer Relations did in the past. I have no particular knowledge of Embaracdero’s internal structure.

  3. Don’t forget, that FMX should be compatible with FPC. Not that FPC, which we have now, but FPC that we had a few years ago, when development of the FMX started.

    • Yes, that is part of the explanation – at least with the version of FPC that FMX was developed with, the example code I present in this post won’t compile. There are also other problems in the FMX source that wouldn’t have arisen if Embarcadero-era language improvements had been exploited – e.g., using the ability to cast from an interface to an object would have avoided certain bugs in the menu code again. Moreover, various other things could have been more elegantly written were newer language and RTL features used (for example, custom FMX controls need to be explicitly registered with the streaming system, which should be completely unnecessary in the times of extended RTTI). However, the core VCL code in Delphi 1 didn’t have the benefit of generics and so forth, yet was of a much, much higher quality than the core FMX code in XE2.

  4. >using the ability to cast from an interface to an object

    Which incidentally is implemented very poorly by the compiler & RTL and should probably be avoided (at least as far as XE goes). After trying to use it in DWS, I’ve reverted to using an IGetSelf and then casting on the object. The thing surprisingly ended up on top of my profiler results, while with IGetSelf + “as” barely registers when profiling.
    The code for casts from interface to object seems like another case of Shlemiel’s algorithm…

    • Well when you come across bugs in the FMX source due to it not being used, you may mollify your opinion slightly…

      That said, the only explanation I can offer for your performance issue is that the special GUID for the object cast is checked for last, so if the class implements lots of interfaces (IIRC you’re rather keener on interfaces than me aren’t you…?), they will all be checked for first. See the source for TObject.GetInterface to see what I mean – the actual implementation is very straightforward. Care to expand on your ‘Shlemiel’s algorithm’ comment…?

    • I’m definitely missing something – using the following test, I find the built-in solution faster, not slower:

      uses
        System.SysUtils, System.Diagnostics;
      
      type
        IObjectGetter = interface
        ['{FF298D15-13E0-42DD-96EE-65C2CE5B5A0A}']
          function GetObject: TObject;
        end;
      
        IFoo = interface
        ['{CC20DF7D-386D-4F49-9DD8-F1E2EA012504}']
          procedure Bar;
        end;
      
        TFoo = class(TInterfacedObject, IFoo, IObjectGetter)
          procedure Bar;
          function GetObject: TObject;
        end;
      
      procedure TFoo.Bar;
      begin
      end;
      
      function TFoo.GetObject: TObject;
      begin
        Result := Self;
      end;
      
      procedure RunTest(const Name: string; const TestFunc: TFunc<TFoo>);
      var
        Foo: TFoo;
        I: Integer;
        Stopwatch: TStopwatch;
      begin
        Write(Name, ': ');
        Stopwatch := TStopwatch.StartNew;
        for I := 1 to 100000000 do
        begin
          Foo := TestFunc;
          Foo.Bar;
        end;
        Stopwatch.Stop;
        WriteLn(Stopwatch.ElapsedMilliseconds, 'ms');
      end;
      
      var
        Intf: IFoo;
      begin
        Intf := TFoo.Create;
        RunTest('Built in',
          function : TFoo
          begin
            Result := Intf as TFoo;
          end);
        RunTest('Custom',
          function : TFoo
          begin
            Result := (Intf as IObjectGetter).GetObject as TFoo;
          end);
        ReadLn;
      end.
      
      • Answering from iPad here, but that was with “IFoo = interface (IObjectGetter)”, so with no “as” on the interface

      • Eric is right: You code (Intf as IObjectGetter) will call GetInterface() method, so is of no benefit when compared with the “Intf as TFoo” version. Using interface(IObjectGetter) is MUCH faster.
        For a fast cross-version solution, see http://blog.synopse.info/post/2012/06/13/Retrieve-the-object-instance-from-an-interface – I guess this code will be quite as fast as IObjectGetter.GetObject, and will work with any Interface (modulo “fake” classes).

        • “Your code (Intf as IObjectGetter) will call GetInterface() method”.

          Well, yeah… Keep in mind I’m not keen on the interfaces implementation generally (a COM-specific notion of interfaces should never have been baked into the language IMO), whereas you and Eric are relatively happy with it…?

        • I’m personally staying away from the COM-side of interfaces whenever those interfaces are purely Delphi (I don’t give them a GUID for starters), and use them mostly for either separation of interface/implementation or automated memory management (because that’s the only we have, not because I like it).

          It would have been nice if interfaces had existed outside of COM concepts as well, just as it would be nice if we had an empty root object (rather than TObject and all its baggage), as having both (+RTTI) would have opened interesting possibilities in terms of memory management f.i.

        • “looks like deep sub-comments don’t look too readable”

          Er, well the trick is to reply to yourself rather than the other guy…

      • Confirmed, in your code change to

        IFoo = interface (IObjectGetter)

        and then add

        RunTest(‘Native’,
        function : TFoo
        begin
        Result := Intf.GetObject as TFoo;
        end);

        it’ll be the fastest of the bunch by far, and its execution performance doesn’t depend on how many interfaces are implemented by the class, or how varied the classes are (TObject.GetInterface on the other hand, is sort of re-computing the instance each time, hence Shlemiel, and it also exhibits poor cache coherency if you have many different classes involved behind the interfaces).

        The (Intf as ISomeIntf) approach doesn’t depend on how many interfaces are implemented, but suffers from an implicit ref-count and exception frame.

        One might as well derive all its Delphi interfaces from an IGetSelf and be done with it, its only disadvantage is that it won’t work on a nil interface, but that’s corner case IME.

      • I think this deserves a separate post, as you seem to have changed tack slightly and are now complaining about the GetInterface method’s implementation.

        • Not really, think of it as complaining that “as” uses GetInterface (it didn’t have too), and that incidentally it’s a deathmatch weapon – just posted about that 🙂

          • Relative issue blogged somewhere was “Supports” function calling GetInterface internally and then unexpectedly freeing the object (if it was not used in ref-counted manner).

            The reasoning was “i do not GET the interface, i only ask WHETHER i can do it or not).

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