{"size": 7373, "ext": "scrbl", "max_stars_repo_path": "paper/implementation.scrbl", "max_stars_repo_name": "wilbowma/pgmp", "max_stars_repo_stars_event_min_datetime": "2016-06-25T13:28:56.000Z", "max_stars_repo_stars_event_max_datetime": "2016-06-25T13:28:56.000Z", "max_issues_repo_path": "paper/implementation.scrbl", "max_issues_repo_name": "bluephoenix47/pgmp", "max_issues_repo_issues_event_min_datetime": "2015-02-12T17:56:28.000Z", "max_issues_repo_issues_event_max_datetime": "2015-04-14T04:04:26.000Z", "max_forks_repo_path": "paper/implementation.scrbl", "max_forks_repo_name": "bluephoenix47/pgmp", "max_forks_repo_forks_event_min_datetime": "2016-04-10T19:03:41.000Z", "max_forks_repo_forks_event_max_datetime": "2016-04-10T19:03:41.000Z"}
{"max_stars_count": 1, "max_issues_count": 8, "max_forks_count": 1, "avg_line_length": 49.1533333333, "max_line_length": 83, "alphanum_fraction": 0.8167638682}
#lang scribble/base
@(require
  "defs.rkt"
  "bib.rkt"
  scribble/manual
  scriblib/footnote
  scriblib/figure)

@title[#:tag "implementation" "Implementations"]
To validate the design principles from @Secref{design}, we provide two
implementations.
This section describes implementations in Chez Scheme and Racket and
discusses some implementation concerns.
While both languages belong to the Lisp family, they differ in their
meta-programming and profiling facilities.

@section[#:tag "impl-chez"]{Chez Scheme Implementation}
Chez Scheme implements precise counter-based profiling, using standard
and efficient block-level profiling
techniques@~citea["ball1994optimally" "burger1998infrastructure"].
The Chez Scheme profiler effectively profiles every source expression
and provides profiles in terms of source-code locations.

In Chez Scheme, we implement profile points using @emph{source
objects}@~citea{dybvig93} which can be attached to syntax objects.
Chez Scheme uses source objects to report errors at their precise source
location.
Chez Scheme source objects contain a filename and starting and ending
character positions.
The Chez Scheme reader automatically creates and attaches source objects
to each syntax object it reads from a file.

Chez Scheme provides an API to programmatically manipulate source
objects and attach them to syntax objects@~cite[csug-ch11].
We use this API to implement @racket[make-profile-point] and
@racket[annotate-expr].
The former deterministically generates fresh source objects by adding a
suffix to the filename of a base source object.
This scheme has the added benefit of preserving source locations for
error messages when errors occur in the output of a profile-guided
meta-programs.

We modify the meta-programming system to maintain an associative map of
source objects to profile weights, which implements
@racket[(current-profile-information)].
We implement the function @nonbreaking{@racket[profile-query]} by simply
querying this map.
The function @racket[load-profile] updates this map from a file.
To write this map to a file, the function @racket[store-profile] first
retrieves the profile information from the profiler and computes the
profile weights for each source object.

@section[#:tag "impl-racket"]{Racket Implementation}
Racket includes an @racketmodname[errortrace] profiling library.
The @racketmodname[errortrace] library provides counter-based profiling
and returns profiles in terms of source code locations, similar to the
Chez Scheme profiler.
Note that in contrast to the Chez Scheme profiler, the
@racketmodname[errortrace] library profiles only function calls.

In Racket, we implement profile points in essentially the same way as in
Chez Scheme---by using source information attached to each syntax
object.
The Racket reader automatically attaches the filename, line number, etc
to every syntax object it reads from @nonbreaking{a file.}

Racket provides an API for attaching source information when building a
new syntax object.
A separate library exists that provides a more extensive API for
manipulating source information.
We use this library to implement @racket[make-profile-point] and
@nonbreaking{@racket[annotate-expr]} in essentially the same way as in Chez Scheme.
There is one key difference because the @racketmodname[errortrace]
library profiles only functions calls.
When annotating an expression @racket[e] with profile point @racket[p],
we generate a new function @racket[f] whose body is @racket[e].
The result of @racket[annotate-expr] is a call to the generated function
@racket[f].
This call to @racket[f] is annotated with the profile point @racket[p].
While this results in different performance characteristics while
profiling, it does not change the counters used to calculate profile
weights.

We implement a library that maintains the associative map from source
locations to profile weights.
The library provides our API as simple Racket functions that can be
called by meta-programs.
We are able to implement the entire API as a user-level library due to
Racket's advanced meta-programming facilities and the extensive API
provided by the @racketmodname[errortrace] profiler.

@section{Source and Block-level PGO}
One goal of our approach is to avoid interfering with traditional, e.g.,
basic-block-level PGO, which Chez Scheme also supports.
However, since meta-programs may generate different source code after
optimization, the low-level representation would have to change when
meta-programs perform optimizations.
The different low-level code would invalidate the low-level profile
information.
To solve this problem, the source code is compiled three times in a
specific order, instead of the usual two times.
Doing so ensures that profile information remains consistent at both the
source-level and the block-level.
First, we compile while instrumenting the code to profile source
expressions.
After running the instrumented program on representative inputs, we get
the profile weights as in @Figure-ref{profile-weight-comps}.
Second, we recompile, using those profile weights to perform
profile-guided meta-program optimizations, while instrumenting
the code to profile basic blocks.
After running this instrumented program, we get the profile weights for
the basic blocks generated from the optimized source program.
These block-level profile weights will not be invalidated as long as we
continue to optimize using the source-level profile weights.
That is, the high-level code generated by the meta-program
optimizations, e.g., @Figure-ref{sample-expansion}, will remain stable
as long as we continue to optimize using the source profile weights.
Because the generated high-level code remains stable, the generated
low-level code also remains stable.
Third (the final compilation), we recompile using both the profile
weights for the source expressions and for the basic blocks to do both
profile-guided meta-programming and @nonbreaking{low-level PGOs.}

@section[#:tag "impl-overhead"]{Compile-Time and Profiling Overhead}
As with any technique for performing profile-guided optimizations, our
approach introduces compile-time overhead for optimizations and run-time
overhead when profiling.

The compile-time overhead of our API is small.
In our implementations, loading profile information is linear in the
number of profile points, and querying the weight of a particular
profile point is amortized constant-time.
Since they run at compile time, a profile-guided meta-program might
slow down or speed up compilation, depending on the complexity
of the meta-program and whether it produces more or less code as
a result of @nonbreaking{the optimization.}

The API does not directly introduce run-time overhead; however,
a meta-programming system using our technique inherits overhead from the
profiler used in the implementation.
Previous work measured about 9% run-time overhead introduced by the Chez
Scheme profiler@~citea{burger1998infrastructure}.
According to the @racketmodname[errortrace] documentation, the profiler
introduces a factor of 4 to 12 slowdown.
This does not include the additional instrumentation our implementation
of @racket[annotate-expr] performs, i.e., wrapping each annotated
expression in a function call.
Typically, profiling is disabled for production runs of a program, so
this overhead affects only profiled runs.
