pragma Pathway - optimising optimizing profiling

pragma Pathway - optimising optimizing profiling

[Nick Roberts]

Thanks to all those people who gave me their comments about deadlock
and pragma Zero_Fill etc.

I'd like to ask people's comments about another pragma I intend to
implement in ECLAT.

The problem is that I want to implement optimisation based on
profiling. The idea is that you compile your program, run it using
typical (anticipated) input data or executional circumstances,
gathering profiling data, and then recompile, optimising the emitted
code based on the gathered profiling data.

There are a number of useful optimisations possible, especially
optimisations related to the memory hierarchy (caches). As modern
hardware is becoming more and more heavily reliant on good use of
the memory caches to achieve its maximum potential throughput, these
optimisations are becoming more and more important.

One apparent difficulty, to my mind, is that the profiling data
gathered must be related in some way to executional pathways through
the program. If this cannot be done in terms of source text (but
rather in terms of some intermediate form derived by the compiler
 from the source text), then it would be very hard indeed to avoid
recompilation invalidating the profiling data, especially if the
source text being recompiled had been altered.

My plan to avoid this difficulty is to introduce a pragma which will
provide a way to associate a place in the source text with an
executional pathway through the program by name. I propose to call
the pragma Pathway, and it will have the syntax:

    pragma Pathway ([Name =>] pathway_identifier);

The pathway_identifer must be unique within the program with respect
to any identifiers mentioned in other Pathway pragmas. The pragma is
allowed anywhere a statement is allowed.

The dymanic semantics of the pragma are that it represents a pseudo
statement, whose execution causes a counter associated with the
pathway_identifier to be incremented. Each counter is initialised to
0 before the execution of any unit of the program. At program
termination, the values of the counters are written out to a profiling
data file, each value associated with its identifer.

Upon recompilation, the compiler can use the profiling data for
optimisation. I'll write a tool to sum profiling data files, so that
cumulative data for multiple runs can be used for this purpose.

The advantage of this technique, as I see it, is that the source text
of the program can be manipulated without invalidating (some or all
of) the already gathered profiling data. For example, supposing one
originally had:

       if not Cond then
          pragma Pathway(Cond_False);
          ... -- actions 1
       else
          pragma Pathway(Cond_True);
          ... -- actions 2
       end;

and one edited this to the (perhaps more readable) form:

       if Cond then
          pragma Pathway(Cond_True);
          ... -- actions 2
       else
          pragma Pathway(Cond_False);
          ... -- actions 1
       end;

It is possible to tell the compiler where existing pathways have
moved to in the new code.

One would have to be careful not to accidentally tell the compiler
that a pathway has moved, when in reality a new pathway has been
created (and probably several old pathways have been destroyed). In
this case, it may be necessary to regenerate the profiling data.

The obvious disadvantage of this technique is that one's beautiful
Ada source text could end up liberally sprinkled with ugly pragmas.
This could have a seriously detrimental effect on readability, and
it's very likely to be inconvenient. It would not be appropriate to
use this pragma widely, but only in those places in the program where
optimisations based on profiling data will be important.

I propose to make the format of the profiling data files compatible
with the (informal) CSV (comma separated variable-length record)
standard, so that profiling data can be readily inspected,
manipulated, and maybe even originated, in just about any spreadsheet
or database tool.

I would add a package:

    package System.Profiling is
       type Profiling_Counter is private;
       procedure Initialize (Counter:    out Profiling_Counter);
       procedure Update     (Counter: in out Profiling_Counter);
       procedure Finalize   (Counter: in     Profiling_Counter;
                             Name:    in     String);
       procedure Begin_Initialization;
       procedure End_Initialization;
       procedure Begin_Finalization;
       procedure End_Finalization;
    private
       ...
    end;

The compiler would declare a hidden variable of type Profiling_Counter
for each pathway mentioned in a pragma Pathway in the program. It
would call Begin_Initialization, then Initialize(C) for every counter
C, and then End_Initialization, before beginning the elaboration of
any program unit. During execution of the program, counters would be
incremented by calling Update(C). After completion of the program
(main task), the compiler would call Begin_Finalization, then
Finalize(C,N) for every counter C (whose pathway_identifier was N, as a
string), then End_Finalization.

The default body for this package woud open a file named "eclatpro.csv"
when Begin_Finalization was called, and output data upon calls to
Finalize, closing the file upon End_Finalization.

Obviously the compiler would have switches to turn on or off:
generation of profiling data by the emitted code; optimisations based
on the profiling data in "eclatpro.csv" (or another explicitly named
file).

I'm not suggesting this pragma be part of the language standard, but
I'd be interested if there is another compiler that does the same thing
(and how it does it).

I wonder if anyone might want to copy this design for their own
compiler? This would delight me!

-- 
TIA, Nick Roberts

Re: pragma Pathway - optimising optimizing profiling

[Mark Lorenzen]

"Nick Roberts" <nick.roberts@acm.org> writes:

> Thanks to all those people who gave me their comments about deadlock
> and pragma Zero_Fill etc.
> 
> I'd like to ask people's comments about another pragma I intend to
> implement in ECLAT.

[Large presentation of pragma Pathway removed]

Optimization is a job for the compiler and not the programmer. There
will of course always be special cases, where the compiler needs a
guiding hand in order to choose the correct optimization.

But profile-driven optimization is not one of those cases, when we
talk about the GNAT compiler. According to this announcement
http://gcc.gnu.org/news/profiledriven.html there is (or at least being
worked on) an infrastructure in GCC to use the output from a profiling
tool (such as the GNU profiler) and feed it back into GCC in order to
perform optimizations that will benefit the recorded profile. Please
correct me if I am wrong.

Btw.: If you want to count the number of time a functions has been
called, you can use the GNU profiler. This mimics your pragma, but
does not need code instrumentation.

> 
> TIA, Nick Roberts

Regards,
- Mark Lorenzen