From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,5642b5e0552e165e
X-Google-Attributes: gid103376,public
From: Simon Wright <simon@pogner.demon.co.uk>
Subject: Re: Performance and Thread Safety of the Booch Components
Date: 2000/04/22
Message-ID: <x7v8zy6vbxz.fsf@pogner.demon.co.uk>
X-Deja-AN: 614555452
X-NNTP-Posting-Host: pogner.demon.co.uk:158.152.70.98
References: <1e9flrw.13c8d0t190e9v6N%herwin@gmu.edu>
 <39006687.9341ACAA@telepath.com>
X-Trace: news.demon.co.uk 956475230 nnrp-09:2742 NO-IDENT
 pogner.demon.co.uk:158.152.70.98
Organization: At Home
Newsgroups: comp.lang.ada
X-Complaints-To: abuse@demon.net
Date: 2000-04-22T00:00:00+00:00
List-Id: <comp.lang.ada>

Ted Dennison <dennison@telepath.com> writes:

> Harry Erwin wrote:
> 
> > Experience with the STL in C++ has shown that the standard container
> > classes and associated algorithms degrade performance severely unless a
> > significant level of optimization is turned on. This is in part due to
> > the number of temporary objects and function calls that get generated.
> 
> ...
> 
> > The Booch components appear to be generally exception-safe and
> > exception-neutral. Are there any issues known that I should be aware
> > of?--other than one esoteric bug involving copying between queues of
> > different types that I've already reported.
> 
> I don't think they really have been highly tuned for performance. As an
> example, we were using doing multiple lookups using a map object in a loop
> that gets executed at 60Hz for a simulator. Performance was terrible even on
> GreenHills' highest optimization levels, so I looked at it with a
> subprogram-level performance analyzer. It turned out that even the *bounded*
> maps (which you'd figure wouldn't do dynamic allocation) were dynamicly
> allocating an iterator every lookup.

Yes, this was a bad move. My excuse is that the performance of "new"
on Linux is pretty good (well, not unacceptable to me as an occasional
user :-) -- it took about 80 uS on my P200+ box to create an Iterator.

Unfortunately, "new" on VxWorks is a lot slower. Most VxWorks users, I
expect, allocte memory at startup and deprecate "new" at other times.

Ted wasn't helped that the specialised Iterators in Maps didn't get
updated at the same time as I changed the standard passive iterators
to use an existing Iterator object rather than creating their own.

I've invented a new Iterator scheme, appended to this article in
gnatchop-compatible form (I see it uses 'Img, a GNAT-specific
attribute, sorry) which reduces that 80uS to 4 uS, wow! -- and it
doesn't use "new" at all.

There is a subtle bug in the old scheme (the one in the present
release), where Iterators were assignable but were implemented as a
smart pointer to a shared data structure. The new scheme at least
should allow a proper Adjustment on assignment (but I have yet to
think of an example where that would be useful).

I see that the C++ BCs that are my baseline don't implement any sort
of internal locking on containers that are being iterated over. This
has been a worry for me for a long time.

>                                      I fixed that, then found that it was
> still quite slow due to the fact that the (20 or so byte) result of the
> lookup was getting passed as a "return" value through 3 successive
> function's return calls. That resulted in each object in the map getting
> copied 4 times at 60Hz. You'd think that there'd be some way for the
> compiler to optimize that down to one copy at the assignemt on the outside,
> but I couldn't find it. So I just wrote a procedure version and that did the
> trick.

Perhaps "pragma Inline" might have helped. At the expense of bloat,
perhaps.

I certainly intend to take up Ted's suggestion (at least in the
internals of the library). Of course, these optimisations amy just
turn out to be pessimisations for other users ..

> I submitted all these changes to Simon Wright for possible incorporation
> into the official components, but of course this is only Maps. I'm not
> trying to rag on Simon here, or those who came before him. I'm just pointing
> out that Booch is a volunteer effort. Improvements in functionality come
> when someone with the proper tools takes an interest in it. If you have
> interest in high-performance components, and you have access to a execution
> profiler, I'd encourage you to use the components. Just be prepared to have
> to make a couple of twiddles here and there (and please send them back to
> Simon, so the next person won't have to do it too).

Seconded!

Code follows:
=======================================================================
with Ada.Finalization;
package Iteration is
  type Container is abstract tagged private;
  type Iterator is abstract tagged private;
  function New_Iterator (For_The_Container : Container) return Iterator'Class
    is abstract;
  procedure Reset (It : in out Iterator) is abstract;
private
  type Container is abstract new Ada.Finalization.Controlled with null record;
  type Container_Ptr is access all Container'Class;
  for Container_Ptr'Storage_Size use 0;
  type Iterator is abstract tagged record
    For_The_Container : Container_Ptr;
  end record;
end Iteration;
package Iteration.Child is
  type Child_Container is new Container with private;
  function New_Iterator
     (For_The_Container : Child_Container) return Iterator'Class;
private
  type Child_Container is new Container with null record;
  type Child_Iterator is new Iterator with null record;
  procedure Reset (It : in out Child_Iterator);
end Iteration.Child;
with Ada.Text_Io;
with System.Address_To_Access_Conversions;
package body Iteration.Child is
  package Allow_Access
  is new System.Address_To_Access_Conversions (Child_Container);
  function New_Iterator
     (For_The_Container : Child_Container) return Iterator'Class is
    Result : Child_Iterator
       := (For_The_Container =>
              Allow_Access.To_Pointer (For_The_Container'Address).all'Access);
  begin
 --     Ada.Text_Io.Put_Line ("Iteration.Child.New_Iterator (Child_Container).");
    Reset (Result);
    return Result;
  end New_Iterator;
  procedure Reset (It : in out Child_Iterator) is
  begin
 --     Ada.Text_Io.Put_Line ("Iteration.Child.Reset (Child_Iterator).");
    null;
  end Reset;
end Iteration.Child;
with Ada.Calendar;
with Ada.Text_Io;
with Iteration.Child;
procedure Iteration_Test is
  C : Iteration.Child.Child_Container;
  Loops : constant Positive := 100_000;
  Start : Ada.Calendar.Time;
  Taken : Duration;
  use Ada.Text_Io;
  use type Ada.Calendar.Time;
begin
  Put_Line ("Timing" & Loops'Img & " simple iterator allocations:");
  Start := Ada.Calendar.Clock;
  for I in 1 .. Loops loop
    declare
      It : Iteration.Iterator'Class := Iteration.Child.New_Iterator (C);
    begin
      null;
    end;
  end loop;
  Taken := (Ada.Calendar.Clock - Start) / Loops;
  Put_Line (".. took" & Duration'Image (Taken) & " sec on average.");

  Put_Line ("Timing" & Loops'Img & " dispatching iterator allocations:");
  Start := Ada.Calendar.Clock;
  for I in 1 .. Loops loop
    declare
      It : Iteration.Iterator'Class
         := Iteration.New_Iterator (Iteration.Container'Class (C));
    begin
      null;
    end;
  end loop;
  Taken := (Ada.Calendar.Clock - Start) / Loops;
  Put_Line (".. took" & Duration'Image (Taken) & " sec on average.");

  Put_Line ("Timing" & Loops'Img & " dispatching iterator reallocations:");
  Start := Ada.Calendar.Clock;
  declare
    It : Iteration.Iterator'Class
       := Iteration.New_Iterator (Iteration.Container'Class (C));
  begin
    for I in 1 .. Loops loop
      It := Iteration.New_Iterator (Iteration.Container'Class (C));
    end loop;
  end;
  Taken := (Ada.Calendar.Clock - Start) / Loops;
  Put_Line (".. took" & Duration'Image (Taken) & " sec on average.");

  Put_Line("done.");
end Iteration_Test;