Author: Carl Friedrich Bolz <[email protected]>
Branch: extradoc
Changeset: r3651:de9b086899b6
Date: 2011-06-12 21:44 +0200
http://bitbucket.org/pypy/extradoc/changeset/de9b086899b6/
Log: fix some formatting stuff, start to import some papers that we will
need into the bib file
diff --git a/talk/iwtc11/paper.bib b/talk/iwtc11/paper.bib
--- a/talk/iwtc11/paper.bib
+++ b/talk/iwtc11/paper.bib
@@ -0,0 +1,323 @@
+
+@inproceedings{deutsch_efficient_1984,
+ address = {Salt Lake City, Utah},
+ title = {Efficient implementation of the Smalltalk-80 system},
+ isbn = {0-89791-125-3},
+ url = {http://portal.acm.org/citation.cfm?id=800017.800542},
+ doi = {10.1145/800017.800542},
+ abstract = {The Smalltalk-80* programming language includes dynamic
storage allocation, full upward funargs, and universally polymorphic
procedures; the Smalltalk-80 programming system features interactive execution
with incremental compilation, and implementation portability. These features of
modern programming systems are among the most difficult to implement
efficiently, even individually. A new implementation of the Smalltalk-80
system, hosted on a small microprocessor-based computer, achieves high
performance while retaining complete (object code) compatibility with existing
implementations. This paper discusses the most significant optimization
techniques developed over the course of the project, many of which are
applicable to other languages. The key idea is to represent certain runtime
state (both code and data) in more than one form, and to convert between forms
when needed.},
+ booktitle = {{POPL}},
+ publisher = {{ACM}},
+ author = {Deutsch, L. Peter and Schiffman, Allan M.},
+ year = {1984}
+},
+
+@inproceedings{carl_friedrich_bolz_towards_2010,
+ address = {Hagenberg, Austria},
+ title = {Towards a Jitting {VM} for Prolog execution},
+ isbn = {978-1-4503-0132-9},
+ url = {http://portal.acm.org/citation.cfm?id=1836102},
+ doi = {10.1145/1836089.1836102},
+ abstract = {Most Prolog implementations are implemented in low-level
languages such as C and are based on a variation of the {WAM} instruction set,
which enhances their performance but makes them hard to write. In addition,
many of the more dynamic features of Prolog (like assert), despite their
popularity, are not well supported. We present a high-level continuation-based
Prolog interpreter based on the {PyPy} project. The {PyPy} project makes it
possible to easily and efficiently implement dynamic languages. It provides
tools that automatically generate a just-in-time compiler for a given
interpreter of the target language, by using partial evaluation techniques. The
resulting Prolog implementation is surprisingly efficient: it clearly
outperforms existing interpreters of Prolog in high-level languages such as
Java. Moreover, on some benchmarks, our system outperforms state-of-the-art
{WAM-based} Prolog implementations. Our paper aims to show that declarative
languages su
ch as Prolog can indeed benefit from having a just-in-time compiler and that
{PyPy} can form the basis for implementing programming languages other than
Python.},
+ booktitle = {{PPDP}},
+ publisher = {{ACM}},
+ author = {Carl Friedrich Bolz and Michael Leuschel and David Schneider},
+ year = {2010},
+ keywords = {interpreters, jit, logic programming, partial evaluation}
+},
+
+@inproceedings{bebenita_spur:_2010,
+ address = {{Reno/Tahoe}, Nevada, {USA}},
+ title = {{SPUR:} a trace-based {JIT} compiler for {CIL}},
+ isbn = {978-1-4503-0203-6},
+ shorttitle = {{SPUR}},
+ url =
{http://portal.acm.org/citation.cfm?id=1869459.1869517&coll=GUIDE&dl=GUIDE&type=series&idx=SERIES318&part=series&WantType=Proceedings&title=OOPSLA%2FSPLASH&CFID=106280261&CFTOKEN=29377718},
+ doi = {10.1145/1869459.1869517},
+ abstract = {Tracing just-in-time compilers {(TJITs)} determine
frequently executed traces (hot paths and loops) in running programs and focus
their optimization effort by emitting optimized machine code specialized to
these traces. Prior work has established this strategy to be especially
beneficial for dynamic languages such as {JavaScript}, where the {TJIT}
interfaces with the interpreter and produces machine code from the {JavaScript}
trace.},
+ booktitle = {{OOPSLA}},
+ publisher = {{ACM}},
+ author = {Bebenita, Michael and Brandner, Florian and Fahndrich, Manuel
and Logozzo, Francesco and Schulte, Wolfram and Tillmann, Nikolai and Venter,
Herman},
+ year = {2010},
+ keywords = {cil, dynamic compilation, javascript, just-in-time, tracing}
+},
+
+@inproceedings{gal_trace-based_2009,
+ address = {New York, New York},
+ series = {{PLDI} '09},
+ title = {Trace-based just-in-time type specialization for dynamic
languages},
+ isbn = {978-1-60558-392-1},
+ location = {Dublin, Ireland},
+ doi = {10.1145/1542476.1542528},
+ abstract = {Dynamic languages such as {JavaScript} are more difficult
to compile than statically typed ones. Since no concrete type information is
available, traditional compilers need to emit generic code that can handle all
possible type combinations at runtime. We present an alternative compilation
technique for dynamically-typed languages that identifies frequently executed
loop traces at run-time and then generates machine code on the fly that is
specialized for the actual dynamic types occurring on each path through the
loop. Our method provides cheap inter-procedural type specialization, and an
elegant and efficient way of incrementally compiling lazily discovered
alternative paths through nested loops. We have implemented a dynamic compiler
for {JavaScript} based on our technique and we have measured speedups of 10x
and more for certain benchmark programs.},
+ booktitle = {{PLDI}},
+ publisher = {{ACM}},
+ author = {Gal, Andreas and Eich, Brendan and Shaver, Mike and Anderson,
David and Mandelin, David and Haghighat, Mohammad R and Kaplan, Blake and
Hoare, Graydon and Zbarsky, Boris and Orendorff, Jason and Ruderman, Jesse and
Smith, Edwin W and Reitmaier, Rick and Bebenita, Michael and Chang, Mason and
Franz, Michael},
+ year = {2009},
+ note = {{ACM} {ID:} 1542528},
+ keywords = {code generation, design, dynamically typed languages,
experimentation, incremental compilers, languages, measurement, performance,
run-time environments, trace-based compilation}
+},
+
+@inproceedings{bolz_towards_2009,
+ title = {Towards {Just-In-Time} Partial Evaluation of Prolog},
+ doi = {10.1007/978-3-642-12592-8_12},
+ booktitle = {Logic Program Synthesis and Transformation},
+ author = {Bolz, Carl Friedrich and Leuschel, Michael and Rigo, Armin},
+ year = {2009},
+ pages = {158–172}
+},
+
+@inproceedings{bolz_allocation_2011,
+ series = {{PEPM} '11},
+ title = {Allocation removal by partial evaluation in a tracing {JIT}},
+ location = {Austin, Texas, {USA}},
+ doi = {10.1145/1929501.1929508},
+ abstract = {The performance of many dynamic language implementations
suffers from high allocation rates and runtime type checks. This makes dynamic
languages less applicable to purely algorithmic problems, despite their growing
popularity. In this paper we present a simple compiler optimization based on
online partial evaluation to remove object allocations and runtime type checks
in the context of a tracing {JIT.} We evaluate the optimization using a Python
{VM} and find that it gives good results for all our (real-life) benchmarks.},
+ booktitle = {{PEPM}},
+ author = {Bolz, Carl Friedrich and Cuni, Antonio and Fijałkowski,
Maciej and Leuschel, Michael and Pedroni, Samuele and Rigo, Armin},
+ year = {2011},
+ keywords = {code generation, experimentation, interpreters, languages,
optimization, partial evaluation, performance, run-time environments, tracing
jit}
+},
+
+@article{hiniker_improving_2005,
+ series = {{MICRO} 38},
+ title = {Improving Region Selection in Dynamic Optimization Systems},
+ location = {Barcelona, Spain},
+ url = {http://dx.doi.org/10.1109/MICRO.2005.22},
+ doi = {http://dx.doi.org/10.1109/MICRO.2005.22},
+ abstract = {The performance of a dynamic optimization system depends
heavily on the code it selects to optimize. Many current systems follow the
design of {HP} Dynamo and select a single interprocedural path, or trace, as
the unit of code optimization and code caching. Though this approach to region
selection has worked well in practice, we show that it is possible to adapt
this basic approach to produce regions with greater locality, less needless
code duplication, and fewer profiling counters. In particular, we propose two
new region-selection algorithms and evaluate them against Dynamo¿s
selection mechanism, {Next-Executing} Tail {(NET).} Our first algorithm,
{Last-Executed} Iteration {(LEI)}, identifies cyclic paths of execution better
than {NET}, improving locality of execution while reducing the size of the code
cache. Our second algorithm allows overlapping traces of similar execution
frequency to be combined into a single large region. This second technique can
be applied to both {NET} and {LEI}, and we find that it significantly
improves metrics of locality and memory overhead for each.},
+ journal = {Proceedings of the 38th annual {IEEE/ACM} International
Symposium on Microarchitecture},
+ author = {Hiniker, David and Hazelwood, Kim and Smith, Michael D},
+ year = {2005},
+ note = {{ACM} {ID:} 1100546},
+ keywords = {microprocessors and microcomputers, optimization,
performance},
+ pages = {141–154}
+},
+
+@inproceedings{chang_tracing_2009,
+ address = {Washington, {DC}},
+ title = {Tracing for Web 3.0: Trace Compilation for the Next Generation
Web Applications},
+ isbn = {978-1-60558-375-4},
+ shorttitle = {Tracing for web 3.0},
+ url = {http://portal.acm.org/citation.cfm?id=1508293.1508304},
+ doi = {10.1145/1508293.1508304},
+ abstract = {Today's web applications are pushing the limits of modern
web browsers. The emergence of the browser as the platform of choice for rich
client-side applications has shifted the use of in-browser {JavaScript} from
small scripting programs to large computationally intensive application logic.
For many web applications, {JavaScript} performance has become one of the
bottlenecks preventing the development of even more interactive client side
applications. While traditional just-in-time compilation is successful for
statically typed virtual machine based languages like Java, compiling
{JavaScript} turns out to be a challenging task. Many {JavaScript} programs and
scripts are short-lived, and users expect a responsive browser during page
loading. This leaves little time for compilation of {JavaScript} to generate
machine code.},
+ booktitle = {{VEE}},
+ publisher = {{ACM}},
+ author = {Chang, Mason and Smith, Edwin and Reitmaier, Rick and
Bebenita, Michael and Gal, Andreas and Wimmer, Christian and Eich, Brendan and
Franz, Michael},
+ year = {2009},
+ keywords = {dynamically typed languages, forth, tamarin, trace trees,
tracing, type specialization},
+ pages = {71--80}
+},
+
+@inproceedings{davide_ancona_rpython:_2007,
+ address = {Montreal, Quebec, Canada},
+ title = {{RPython:} a step towards reconciling dynamically and
statically typed {OO} languages},
+ isbn = {978-1-59593-868-8},
+ shorttitle = {{RPython}},
+ url = {http://portal.acm.org/citation.cfm?id=1297091},
+ doi = {10.1145/1297081.1297091},
+ abstract = {Although the C-based interpreter of Python is reasonably
fast, implementations on the {CLI} or the {JVM} platforms offers some
advantages in terms of robustness and interoperability. Unfortunately, because
the {CLI} and {JVM} are primarily designed to execute statically typed,
object-oriented languages, most dynamic language implementations cannot use the
native bytecodes for common operations like method calls and exception
handling; as a result, they are not able to take full advantage of the power
offered by the {CLI} and {JVM.}},
+ booktitle = {{DLS}},
+ publisher = {{ACM}},
+ author = {Davide Ancona and Massimo Ancona and Antonio Cuni and
Nicholas D. Matsakis},
+ year = {2007},
+ keywords = {{JVM}, .net, Python}
+},
+
+@article{futamura_partial_1999,
+ title = {Partial Evaluation of Computation Process - An Approach to a
{Compiler-Compiler}},
+ volume = {12},
+ url = {http://citeseer.ist.psu.edu/futamura99partial.html},
+ number = {4},
+ journal = {{Higher-Order} and Symbolic Computation},
+ author = {Futamura, Yoshihiko},
+ year = {1999},
+ keywords = {Futamura},
+ pages = {381--391}
+},
+
+@book{jones_partial_1993,
+ title = {Partial evaluation and automatic program generation},
+ isbn = {0-13-020249-5},
+ url = {http://portal.acm.org/citation.cfm?id=153676},
+ abstract = {This book is out of print. For copies, Please refer to the
following online page},
+ publisher = {{Prentice-Hall}},
+ author = {Jones, Neil D. and Gomard, Carsten K. and Sestoft, Peter},
+ year = {1993}
+},
+
+@inproceedings{armin_rigo_pypys_2006,
+ address = {Portland, Oregon, {USA}},
+ title = {{PyPy's} approach to virtual machine construction},
+ isbn = {{1-59593-491-X}},
+ url = {http://portal.acm.org/citation.cfm?id=1176753},
+ doi = {10.1145/1176617.1176753},
+ abstract = {The {PyPy} project seeks to prove both on a research and a
practical level the feasibility of constructing a virtual machine {(VM)} for a
dynamic language in a dynamic language - in this case, Python. The aim is to
translate (i.e. compile) the {VM} to arbitrary target environments, ranging in
level from {C/Posix} to {Smalltalk/Squeak} via Java and {CLI/.NET}, while still
being of reasonable efficiency within these {environments.A} key tool to
achieve this goal is the systematic reuse of the Python language as a system
programming language at various levels of our architecture and translation
process. For each level, we design a corresponding type system and apply a
generic type inference engine - for example, the garbage collector is written
in a style that manipulates simulated pointer and address objects, and when
translated to C these operations become C-level pointer and address
instructions.},
+ booktitle = {{DLS}},
+ publisher = {{ACM}},
+ author = {Armin Rigo and Samuele Pedroni},
+ year = {2006},
+ keywords = {metacircularity, Python, retargettable code generation,
type inference, {VM}}
+},
+
+@article{georges_statistically_2007,
+ title = {Statistically rigorous java performance evaluation},
+ volume = {42},
+ url = {http://portal.acm.org/citation.cfm?id=1297105.1297033},
+ doi = {10.1145/1297105.1297033},
+ abstract = {Java performance is far from being trivial to benchmark
because it is affected by various factors such as the Java application, its
input, the virtual machine, the garbage collector, the heap size, etc. In
addition, non-determinism at run-time causes the execution time of a Java
program to differ from run to run. There are a number of sources of
non-determinism such as {Just-In-Time} {(JIT)} compilation and optimization in
the virtual machine {(VM)} driven by timer-based method sampling, thread
scheduling, garbage collection, and various.},
+ number = {10},
+ journal = {{SIGPLAN} Notices},
+ author = {Georges, Andy and Buytaert, Dries and Eeckhout, Lieven},
+ year = {2007},
+ keywords = {benchmarking, data analysis, methodology, statistics},
+ pages = {57--76}
+},
+
+@inproceedings{bolz_tracing_2009,
+ address = {Genova, Italy},
+ title = {Tracing the meta-level: {PyPy's} tracing {JIT} compiler},
+ isbn = {978-1-60558-541-3},
+ shorttitle = {Tracing the meta-level},
+ url = {http://portal.acm.org/citation.cfm?id=1565827},
+ doi = {10.1145/1565824.1565827},
+ abstract = {We attempt to apply the technique of Tracing {JIT}
Compilers in the context of the {PyPy} project, i.e., to programs that are
interpreters for some dynamic languages, including Python. Tracing {JIT}
compilers can greatly speed up programs that spend most of their time in loops
in which they take similar code paths. However, applying an unmodified tracing
{JIT} to a program that is itself a bytecode interpreter results in very
limited or no speedup. In this paper we show how to guide tracing {JIT}
compilers to greatly improve the speed of bytecode interpreters. One crucial
point is to unroll the bytecode dispatch loop, based on two kinds of hints
provided by the implementer of the bytecode interpreter. We evaluate our
technique by applying it to two {PyPy} interpreters: one is a small example,
and the other one is the full Python interpreter.},
+ booktitle = {{ICOOOLPS}},
+ publisher = {{ACM}},
+ author = {Bolz, Carl Friedrich and Cuni, Antonio and Fijałkowski,
Maciej and Rigo, Armin},
+ year = {2009},
+ pages = {18--25}
+},
+
+@article{bala_dynamo:_2000,
+ title = {Dynamo: a transparent dynamic optimization system},
+ volume = {35},
+ shorttitle = {Dynamo},
+ url = {http://citeseer.ist.psu.edu/bala00dynamo.html},
+ number = {5},
+ journal = {{ACM} {SIGPLAN} Notices},
+ author = {Bala, Vasanth and Duesterwald, Evelyn and Banerjia, Sanjeev},
+ year = {2000},
+ keywords = {toread},
+ pages = {1--12}
+},
+
+@techreport{andreas_gal_incremental_2006,
+ title = {Incremental Dynamic Code Generation with Trace Trees},
+ abstract = {The unit of compilation for traditional just-in-time
compilers is the method. We have explored trace-based compilation, in which the
unit of compilation is a loop, potentially spanning multiple methods and even
library code. Using a new intermediate representation that is discovered and
updated lazily on-demand while the program is being executed, our compiler
generates code that is competitive with traditional dynamic compilers, but that
uses only a fraction of the compile time and memory footprint.},
+ number = {{ICS-TR-06-16}},
+ institution = {Donald Bren School of Information and Computer Science,
University of California, Irvine},
+ author = {Andreas Gal and Michael Franz},
+ month = nov,
+ year = {2006},
+ pages = {11}
+},
+
+@inproceedings{gal_hotpathvm:_2006,
+ address = {Ottawa, Ontario, Canada},
+ title = {{HotpathVM:} an effective {JIT} compiler for
resource-constrained devices},
+ isbn = {1-59593-332-6},
+ shorttitle = {{HotpathVM}},
+ url = {http://portal.acm.org/citation.cfm?doid=1134760.1134780},
+ doi = {10.1145/1134760.1134780},
+ abstract = {We present a just-in-time compiler for a Java {VM} that is
small enough to fit on resource-constrained devices, yet is surprisingly
effective. Our system dynamically identifies traces of frequently executed
bytecode instructions (which may span several basic blocks across several
methods) and compiles them via Static Single Assignment {(SSA)} construction.
Our novel use of {SSA} form in this context allows to hoist instructions across
trace side-exits without necessitating expensive compensation code in off-trace
paths. The overall memory consumption (code and data) of our system is only 150
{kBytes}, yet benchmarks show a speedup that in some cases rivals heavy-weight
just-in-time compilers.},
+ booktitle = {{VEE}},
+ publisher = {{ACM}},
+ author = {Gal, Andreas and Probst, Christian W. and Franz, Michael},
+ year = {2006},
+ keywords = {dynamic compilation, embedded, software trace scheduling,
{SSA}, {VM}}
+},
+
+@inproceedings{mario_wolczko_towards_1999,
+ title = {Towards a Universal Implementation Substrate for
{Object-Oriented} Languages},
+ abstract = {Self is a minimalist object-oriented language with a
sophisticated implementation that utilizes adaptive optimization. We have built
implementations of Smalltalk and Java by translation to Self. These
implementations were much easier to construct in Self than by conventional
means, and perform surprisingly well (competitively with conventional,
commercial implementations). This leads us to believe that a Self-like system
may form the basis of a universal substrate for implementation of
object-oriented languages.},
+ booktitle = {{OOPSLA} workshop on Simplicity, Performance, and
Portability in Virtual Machine Design},
+ author = {Mario Wolczko and Ole Agesen and David Ungar},
+ year = {1999},
+ keywords = {fixme}
+},
+
+@inproceedings{hoelzle_optimizing_1994,
+ address = {Orlando, Florida, United States},
+ title = {Optimizing dynamically-dispatched calls with run-time type
feedback},
+ isbn = {{0-89791-662-X}},
+ url = {http://portal.acm.org/citation.cfm?id=178243.178478},
+ doi = {10.1145/178243.178478},
+ abstract = {Note: {OCR} errors may be found in this Reference List
extracted from the full text article. {ACM} has opted to expose the complete
List rather than only correct and linked references.},
+ booktitle = {{PLDI}},
+ publisher = {{ACM}},
+ author = {Hölzle, Urs and Ungar, David},
+ year = {1994},
+ keywords = {{JIT}, polymorphic inline cache, self, type-feedback},
+ pages = {326--336}
+},
+
+@inproceedings{yermolovich_optimization_2009,
+ address = {Orlando, Florida, {USA}},
+ title = {Optimization of dynamic languages using hierarchical layering
of virtual machines},
+ isbn = {978-1-60558-769-1},
+ url = {http://portal.acm.org/citation.cfm?id=1640134.1640147},
+ doi = {10.1145/1640134.1640147},
+ abstract = {Creating an interpreter is a simple and fast way to
implement a dynamic programming language. With this ease also come major
drawbacks. Interpreters are significantly slower than compiled machine code
because they have a high dispatch overhead and cannot perform optimizations. To
overcome these limitations, interpreters are commonly combined with
just-in-time compilers to improve the overall performance. However, this means
that a just-in-time compiler has to be implemented for each language.
+
+We explore the approach of taking an interpreter of a dynamic
+language and running it on top of an optimizing trace-based virtual machine,
i.e., we run a guest {VM} on top of a host {VM.} The host {VM} uses trace
recording to observe the guest {VM} executing the application program. Each
recorded trace represents a sequence
+of guest {VM} bytecodes corresponding to a given execution path
+through the application program. The host {VM} optimizes and compiles these
traces to machine code, thus eliminating the need for a custom just-in-time
compiler for the guest {VM.} The guest {VM} only needs to provide basic
information about its interpreter loop to the
+host {VM.}},
+ booktitle = {{DLS}},
+ publisher = {{ACM}},
+ author = {Yermolovich, Alexander and Wimmer, Christian and Franz,
Michael},
+ year = {2009},
+ keywords = {actionscript, dynamic languages, hierarchical virtual
machines, trace compilation},
+ pages = {79--88}
+},
+
+@inproceedings{chambers_efficient_1989,
+ title = {An efficient implementation of {SELF} a dynamically-typed
object-oriented language based on prototypes},
+ volume = {24},
+ url = {http://portal.acm.org/citation.cfm?id=74884},
+ doi = {10.1145/74878.74884},
+ abstract = {We have developed and implemented techniques that double
the performance of dynamically-typed object-oriented languages. Our {SELF}
implementation runs twice as fast as the fastest Smalltalk implementation,
despite {SELF's} lack of classes and explicit variables. To compensate for the
absence of classes, our system uses implementation-level maps to transparently
group objects cloned from the same prototype, providing data type information
and eliminating the apparent space overhead for prototype-based systems. To
compensate for dynamic typing, user-defined control structures, and the lack of
explicit variables, our system dynamically compiles multiple versions of a
source method, each customized according to its receiver's map. Within each
version the type of the receiver is fixed, and thus the compiler can statically
bind and inline all messages sent to self. Message splitting and type
prediction extract and preserve even more static type information, allowing
the compiler to inline many other messages. Inlining dramatically improves
performance and eliminates the need to hard-wire low-level methods such as
+,==, and {ifTrue:.} Despite inlining and other optimizations, our system still
supports interactive programming environments. The system traverses internal
dependency lists to invalidate all compiled methods affected by a programming
change. The debugger reconstructs inlined stack frames from compiler-generated
debugging information, making inlining invisible to the {SELF} programmer.},
+ booktitle = {{OOPSLA}},
+ author = {Chambers, C. and Ungar, D. and E. Lee},
+ year = {1989},
+ keywords = {self, specialization}
+},
+
+@inproceedings{hoelzle_optimizing_1991,
+ title = {Optimizing {Dynamically-Typed} {Object-Oriented} Languages
With Polymorphic Inline Caches},
+ isbn = {3-540-54262-0},
+ url = {http://portal.acm.org/citation.cfm?id=679193&dl=ACM&coll=portal},
+ booktitle = {{ECOOP}},
+ publisher = {{Springer-Verlag}},
+ author = {Hölzle, Urs and Chambers, Craig and Ungar, David},
+ year = {1991}
+},
+
+@inproceedings{rigo_representation-based_2004,
+ address = {Verona, Italy},
+ title = {Representation-based just-in-time specialization and the Psyco
prototype for Python},
+ isbn = {1-58113-835-0},
+ url = {http://portal.acm.org/citation.cfm?id=1014010},
+ doi = {10.1145/1014007.1014010},
+ abstract = {A powerful application of specialization is to remove
interpretative overhead: a language can be implemented with an interpreter,
whose performance is then improved by specializing it for a given program
source. This approach is only moderately successful with very high level
languages, where the operation of each single step can be highly dependent on
run-time data and context. In the present paper, the Psyco prototype for the
Python language is presented. It introduces two novel techniques. The first is
just-in-time specialization, or specialization by need, which introduces the
"unlifting" ability for a value to be promoted from run-time to compile-time
during specialization -- the inverse of the lift operator of partial
evaluation. Its presence gives an unusual and powerful perspective on the
specialization process. The second technique is representations, a theory of
data-oriented specialization generalizing the traditional specialization
domains (i.e. the
compile-time/run-time dichotomy).},
+ booktitle = {{PEPM}},
+ publisher = {{ACM}},
+ author = {Rigo, Armin},
+ year = {2004},
+ keywords = {{JIT}, Python}
+},
+
+@inproceedings{sullivan_dynamic_2003,
+ address = {San Diego, California},
+ title = {Dynamic native optimization of interpreters},
+ isbn = {1-58113-655-2},
+ url = {http://portal.acm.org/citation.cfm?id=858570.858576},
+ doi = {10.1145/858570.858576},
+ abstract = {For domain specific languages, "scripting languages",
dynamic languages, and for virtual machine-based languages, the most
straightforward implementation strategy is to write an interpreter. A simple
interpreter consists of a loop that fetches the next bytecode, dispatches to
the routine handling that bytecode, then loops. There are many ways to improve
upon this simple mechanism, but as long as the execution of the program is
driven by a representation of the program other than as a stream of native
instructions, there will be some "interpretive {overhead".There} is a long
history of approaches to removing interpretive overhead from programming
language implementations. In practice, what often happens is that, once an
interpreted language becomes popular, pressure builds to improve performance
until eventually a project is undertaken to implement a native Just In Time
{(JIT)} compiler for the language. Implementing a {JIT} is usually a large
effort, affects a s
ignificant part of the existing language implementation, and adds a
significant amount of code and complexity to the overall code {base.In} this
paper, we present an innovative approach that dynamically removes much of the
interpreted overhead from language implementations, with minimal
instrumentation of the original interpreter. While it does not give the
performance improvements of hand-crafted native compilers, our system provides
an appealing point on the language implementation spectrum.},
+ booktitle = {Workshop on Interpreters, virtual machines and emulators},
+ publisher = {{ACM}},
+ author = {Sullivan, Gregory T. and Bruening, Derek L. and Baron, Iris
and Garnett, Timothy and Amarasinghe, Saman},
+ year = {2003}
+}
\ No newline at end of file
diff --git a/talk/iwtc11/paper.tex b/talk/iwtc11/paper.tex
--- a/talk/iwtc11/paper.tex
+++ b/talk/iwtc11/paper.tex
@@ -25,29 +25,95 @@
% 11pt To set in 11-point type instead of 9-point.
% authoryear To obtain author/year citation style instead of numeric.
+\usepackage{ifthen}
+\usepackage{fancyvrb}
+\usepackage{color}
+\usepackage{ulem}
+\usepackage{xspace}
+\usepackage{epsfig}
+\usepackage{amssymb}
\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage[utf8]{inputenc}
+\usepackage{setspace}
+
+\usepackage{listings}
+
+\usepackage[T1]{fontenc}
\usepackage{setspace}
\usepackage{listings}
+\usepackage{beramono}
+
+
+\definecolor{gray}{rgb}{0.3,0.3,0.3}
+
+\lstset{
+ basicstyle=\setstretch{1.05}\ttfamily\footnotesize,
+ language=Python,
+ keywordstyle=\bfseries,
+ stringstyle=\color{blue},
+ commentstyle=\color{gray}\textit,
+ fancyvrb=true,
+ showstringspaces=false,
+ %keywords={def,while,if,elif,return,class,get,set,new,guard_class}
+ numberstyle = \tiny,
+ numbersep = -20pt,
+}
+
+
+\newboolean{showcomments}
+\setboolean{showcomments}{true}
+\ifthenelse{\boolean{showcomments}}
+ {\newcommand{\nb}[2]{
+ \fbox{\bfseries\sffamily\scriptsize#1}
+ {\sf\small$\blacktriangleright$\textit{#2}$\blacktriangleleft$}
+ }
+ \newcommand{\version}{\emph{\scriptsize$-$Id: main.tex 19055 2008-06-05
11:20:31Z cfbolz $-$}}
+ }
+ {\newcommand{\nb}[2]{}
+ \newcommand{\version}{}
+ }
+
+\newcommand\cfbolz[1]{\nb{CFB}{#1}}
+\newcommand\arigo[1]{\nb{AR}{#1}}
+\newcommand\fijal[1]{\nb{FIJAL}{#1}}
+\newcommand\david[1]{\nb{DAVID}{#1}}
+\newcommand\anto[1]{\nb{ANTO}{#1}}
+\newcommand\reva[1]{\nb{Reviewer 1}{#1}}
+\newcommand\revb[1]{\nb{Reviewer 2}{#1}}
+\newcommand\revc[1]{\nb{Reviewer 3}{#1}}
+\newcommand{\commentout}[1]{}
+\newcommand{\ignore}[1]{} % {{\tt \small ignore(#1)}}
+
+\newcommand\ie{i.e.,\xspace}
+\newcommand\eg{e.g.,\xspace}
+\newcommand{\etal}{\emph{et al.}\xspace}
+
+\normalem
+
+\let\oldcite=\cite
+
+\renewcommand\cite[1]{\ifthenelse{\equal{#1}{XXX}}{[citation~needed]}{\oldcite{#1}}}
\begin{document}
-\conferenceinfo{WXYZ '05}{date, City.}
-\copyrightyear{2005}
+\conferenceinfo{IWTC '11}{XXX}
+\copyrightyear{2011}
\copyrightdata{[to be supplied]}
-\titlebanner{banner above paper title} % These are ignored unless
-\preprintfooter{short description of paper} % 'preprint' option specified.
+\titlebanner{draft} % These are ignored unless
+%\preprintfooter{short description of paper} % 'preprint' option specified.
-\title{Title Text}
-\subtitle{Subtitle Text, if any}
+\title{Loop Invariant Code Motion in PyPy's Tracing JIT}
+%\subtitle{Subtitle Text, if any}
-\authorinfo{Name1}
+\authorinfo{Hakan Ardo XXX}
{Affiliation1}
- {Email1}
-\authorinfo{Name2\and Name3}
- {Affiliation2/3}
- {Email2/3}
+ {[email protected]}
+\authorinfo{Carl Friedrich Bolz}
+ {Heinrich-Heine-Universität Düsseldorf}
+ {[email protected]}
\maketitle
@@ -55,13 +121,13 @@
This is the text of the abstract.
\end{abstract}
-\category{CR-number}{subcategory}{third-level}
+\category{D.3.4}{Programming Languages}{Processors}[code generation,
+incremental compilers, interpreters, run-time environments]
\terms
-term1, term2
+Languages, Performance, Experimentation
-\keywords
-keyword1, keyword2
+\keywords{Tracing JIT, Optimization, Loop-Invariant Code Motion}
\section{Introduction}
@@ -132,8 +198,8 @@
\label{fig:objmodel}
\end{figure}
-Using these classes to implement arithmetic shows the basic problem of a
-dynamic language implementation. All the numbers are instances of either
+Using these classes to implement arithmetic shows the basic problem of many
+dynamic language implementations. All the numbers are instances of either
\lstinline{BoxedInteger} or \lstinline{BoxedFloat}, therefore they consume
space on the
heap. Performing many arithmetic operations produces lots of garbage quickly,
putting pressure on the garbage collector. Using double dispatching to
@@ -511,10 +577,10 @@
\section{Benchmarks}
-\appendix
-\section{Appendix Title}
+%\appendix
+%\section{Appendix Title}
-This is the text of the appendix, if you need one.
+%This is the text of the appendix, if you need one.
\acks
@@ -523,15 +589,6 @@
% We recommend abbrvnat bibliography style.
\bibliographystyle{abbrvnat}
-
-% The bibliography should be embedded for final submission.
-
-\begin{thebibliography}{}
-\softraggedright
-
-\bibitem[Smith et~al.(2009)Smith, Jones]{smith02}
-P. Q. Smith, and X. Y. Jones. ...reference text...
-
-\end{thebibliography}
+\bibliography{paper}
\end{document}
_______________________________________________
pypy-commit mailing list
[email protected]
http://mail.python.org/mailman/listinfo/pypy-commit
