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,FREEMAIL_FROM autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,103803355c3db607 X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Received: by 10.68.223.40 with SMTP id qr8mr2625968pbc.0.1340989430686; Fri, 29 Jun 2012 10:03:50 -0700 (PDT) Path: l9ni33944pbj.0!nntp.google.com!news2.google.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail From: Keean Schupke Newsgroups: comp.lang.ada Subject: Re: GNAT (GCC) Profile Guided Compilation Date: Fri, 29 Jun 2012 10:03:50 -0700 (PDT) Organization: http://groups.google.com Message-ID: <520bdc39-6004-4142-a227-facf14ebb0e8@googlegroups.com> References: <38b9c365-a2b2-4b8b-8d2a-1ea39d08ce86@googlegroups.com> <982d531a-3972-4971-b802-c7e7778b8649@googlegroups.com> NNTP-Posting-Host: 82.44.19.199 Mime-Version: 1.0 X-Trace: posting.google.com 1340989430 15080 127.0.0.1 (29 Jun 2012 17:03:50 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Fri, 29 Jun 2012 17:03:50 +0000 (UTC) In-Reply-To: <982d531a-3972-4971-b802-c7e7778b8649@googlegroups.com> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=82.44.19.199; posting-account=T5Z2vAoAAAB8ExE3yV3f56dVATtEMNcM User-Agent: G2/1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Date: 2012-06-29T10:03:50-07:00 List-Id: On Friday, 29 June 2012 16:05:07 UTC+1, (unknown) wrote: > More specifically, this: >=20 > --8<------8<------8<---- > -- (C)2011 Keean Schupke, all rights reserved.=20 > generic=20 > type Element_Type is private;=20 > -- Element_Type is a small object; could be also eventually an index > -- for an array of larger objects, or an access type to a larger object > type Set_Index is range <>;=20 > package Eager_Disjointsets is=20 > type Set_Type is limited private;=20 > function Find(=20 > Set : in Set_Type;=20 > Index : in Set_Index=20 > ) return Set_Index;=20 > pragma Inline_Always(Find);=20 >=20 > procedure Makeset(=20 > Set : in out Set_Type;=20 > Index : in Set_Index=20 > );=20 > pragma Inline_Always(Makeset);=20 >=20 > procedure Link(=20 > Set : in out Set_Type;=20 > Left, Right : in out Set_Index=20 > );=20 > pragma Inline_Always(Link);=20 >=20 > function Get(=20 > Set : in Set_Type;=20 > Index : in Set_Index=20 > ) return Element_Type;=20 > pragma Inline_Always(Get);=20 >=20 > function Next(=20 > Set : in Set_Type;=20 > Index : in Set_Index=20 > ) return Set_Index;=20 > pragma Inline_Always(Next);=20 >=20 > procedure Set_Next(=20 > Set : in out Set_Type;=20 > Index : in Set_Index;=20 > Next : in Set_Index=20 > );=20 > pragma Inline_Always(Set_Next);=20 >=20 > private=20 > type Node_Type is limited record=20 > Canonical : Set_Index;=20 > Successor : Set_Index;=20 > Size : Natural;=20 > Value : aliased Element_Type;=20 > end record;=20 > type Set_Type is array (Set_Index) of Node_Type;=20 > end Eager_Disjointsets;=20 >=20 > package body Eager_Disjointsets is >=20 > -- Ad-hoc added by GdM for compiling the package > generic > type Element is private; > procedure Swap(a, b: in out Element); > pragma Inline(Swap); > procedure Swap(a, b: in out Element) is > c: Element; > begin > c:=3D a; > a:=3D b; > b:=3D c; > end Swap; >=20 > -- Ad-hoc added by GdM for compiling the package > procedure Add(to: in out Natural; what: Natural) is > pragma Inline(Add); > begin > to:=3D to + what; > end Add; >=20 > procedure Makeset( > Set : in out Set_Type; > Index : in Set_Index > ) is=20 > begin > Set(Index).Canonical :=3D Index; > Set(Index).Size :=3D 1; > end Makeset; >=20 > function Find( > Set : in Set_Type; > Index : in Set_Index > ) return Set_Index is begin > return Set(Index).Canonical; > end Find; >=20 > procedure Swap_Indexes is new Swap(Set_Index); >=20 > procedure Link( > Set : in out Set_Type; > Left, Right : in out Set_Index) is > begin > if Set(Left).Size <=3D Set(Right).Size then > Swap_Indexes(Left, Right); > end if; >=20 > declare > Index : Set_Index :=3D Right; > begin > Link_Loop : loop > Set(Index).Canonical :=3D Left; > Index :=3D Set(Index).Successor; > exit Link_Loop when Index =3D Right; > end loop Link_Loop; > end; >=20 > Add(Set(Left).Size, Set(Right).Size); >=20 > Swap_Indexes(Set(Left).Successor, Set(Right).Successor); > end Link; >=20 > function Get( > Set : in Set_Type; > Index : in Set_Index > ) return Element_Type is begin > return Set(Index).Value; > end Get; >=20 > function Next( > Set : in Set_Type; > Index : in Set_Index > ) return Set_Index is begin > return Set(Index).Successor; > end Next; >=20 > procedure Set_Next( > Set : in out Set_Type; > Index : in Set_Index; > Next : in Set_Index > ) is begin > Set(Index).Successor :=3D Next; > end Set_Next; > end Eager_Disjointsets; I will give it a go, but if you notice my implementation puts the Element_T= ype into the Node structure itself rather than having a pointer (Access) to= a separate object. In C++ this node is 20 bytes (8 each for the canonical = and successor pointers, and 4 for the subset-size). The 'Element' I am usin= g is 12 bytes (a record of two integers and and array of 4 bytes). In my te= sts in C++ a single array of 32 bytes packing the payload into the node usi= ng templates (or generics in Ada) outperformed two lists, as there was one = less pointer dereference. Here I think the performance is dominated by the = cache behaviour, so I don't expect this change to be faster, but I will giv= e it a go. Note: this is not really answering my question about the lack of improvemen= t due to profile-guided compilation - but perhaps that side of things is mo= re a compiler issue. Does anyone have any ideas about that side of things? Cheers, Keean.