Re: GNAT (GCC) Profile Guided Compilation

[stefan-lucks@see-the.signature]

On Fri, 29 Jun 2012, Keean Schupke wrote:

> On Friday, 29 June 2012 11:01:30 UTC+1, Keean Schupke  wrote:

> > Maintaining the address of the current cell is faster than using 
> > indexed addressing (mainly because of the extra parameter that needs 
> > to be passed around increasing the pressure on register allocation).

I guess you did some benchmarking, regarding that issue?

> > I would be interested to understand how an algorithm can be 
> > implemented in a more Ada way?

Faster or slower, you are extensively using access types (Element_Access 
and Set_Access). This is something Ada programmers usually try to avoid, 
except when there is an urgent need for some dynamic memory management 
(e.g., implementing one's own Container library). 

>     generic
>         type Element_Type is limited private;
>         type Element_Access is not null access all Element_Type;
>         type Set_Index is range <>;
>     package Eager_Disjointsets is
>         type Set_Type is limited private;
>         type Set_Access is not null access all Set_Type;

What, exactly, do you use Element_Access for? And why, exactly, do you 
bother to define Set_Access?

>         function Find(
>             Set : in Set_Access;
>             Index : in Set_Index
>         ) return Set_Index;
>         pragma Inline_Always(Find);
 
Why don't you just write the following? (Same for your other operations.)

	function find
	  (Set   : in Set_Type;
	   Index : in Set_Index) return Set_Index;

[...]

>     private
>         type Node_Type is limited record
>             Canonical : Set_Index;
>             Successor : Set_Index;
>             Size : Natural;
>             Value : aliased Element_Type;
>         end record;
>         type Set_Type is array (Set_Index) of Node_Type;
>     end Eager_Disjointsets;

Why, exactly, do you make Value aliased? Is this related to your "faster 
than indexed addressing" point above?

This may be hard for the compiler to properly optimize: An aliased 
component Element_Type in a record ... and then there is an array of such 
records, and all is inside a generic package. 

If you really need Value to be aliased (do you?), then you can try out 
rewriting Set_Type:

  type Set_Index_Array is array(Set_Index) of Set_Index;
  type Size_Array      is array(Set_Index) of Natural;
  type Value_Array     is array(Set_Index) of aliased Element_Type;

  type Set_Type is record
    Canonical, Successor: Set_Index_Array;
    Size:                 Size_Array;
    Value:                Value_Array;
  end record;

I have no idea if the above modification helps to speed up the 
computation, or not. It may backfire, I don't know. 

>     package body Eager_Disjointsets is
>         function Find(
>             Set : in Set_Access;
>             Index : in Set_Index
>         ) return Set_Index is begin
>             return Set(Index).Canonical;
>         end Find;

Now, here you would have to write "return Set.Canonical(Index);"

>     -- (C)2011 Keean Schupke, all rights reserved.
>     generic
>         Size : Int;
>         type Element_Type is limited private;
>         type Element_Access is not null access all Element_Type;
>     package Eager_Disjointsets is
>         type Set_Type is limited private;
>         type Set_Access is not null access all Set_Type;
>         type Node_Type is limited private;
>         type Cursor is access all Node_Type;

Is Int another name for Integer?

I understand that for performance reason you introduced Cursor as access 
all Node_Type and later Set_Array as aliased array of Node_Type.

But again, what do you need Element_Access and Set_Access for?

>         package Node_Address is new 
>         System.Address_To_Access_Conversions(Node_Type);

Probably, the compiler finds that out by itself -- but you may want to 
make it explicit that Node_Size doesn't change:

>         Node_Size : constant Storage_Offset := Node_Type'Object_Size
>             / System.Storage_Elements.Storage_Element'Size;

Also, if Node_Size isn't a power of 2, it may be difficult for the 
compiler to decide on the alignment of objects of type Node_Type -- with 
possible effects on caching. On one hand, it may be good to pack the 
objects closely together, to make as many fit into a single cache line as 
possible. On the other hand, it is bad if a part of a certain node is in 
one cache line, another part in another cache line.

>         function Find(
>             Node : in Cursor
>         ) return Cursor is begin
>             return Cursor(Node.Canonical);
>         end Find;

Not related to performance, but why don't you just write 
"return Node.Canonical;" as Node.Canonical is of type Cursor, anyway?


-- 
---- Stefan.Lucks (at) uni-weimar.de, University of Weimar, Germany  ----
    <http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
------  I  love  the  taste  of  Cryptanalysis  in  the  morning!  ------