Skip to content
Snippets Groups Projects
performance.html 20 KiB
Newer Older
<!DOCTYPE html>
<html>
<head>
	<title>PyPy - Performance</title>
	<meta http-equiv="content-language" content="en" />
	<meta http-equiv="content-type" content="text/html; charset=utf-8" />
	<meta name="author" content="PyPy Team" />
	<meta name="description" content="PyPy" />
	<meta name="copyright" content="MIT" />
	<meta name="document-rating" content="general" />
	<link rel="stylesheet" type="text/css" media="screen" title="default" href="css/site.css" />
	<link rel="alternate" type="application/rss+xml" title="RSS Feed for PyPy" href="http://feeds.feedburner.com/PyPyStatusBlog" />
  <link rel="stylesheet" type="text/css" href="css/jquery-ui-1.8.14.custom.css" />
	<script type="text/javascript" src="https://use.typekit.com/hdt8sni.js"></script>
	<script type="text/javascript">try{Typekit.load();}catch(e){}</script>
	<script type="text/javascript" src="https://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js"></script>
  <script type="text/javascript" src="js/jquery-ui-1.8.14.custom.min.js"></script>
  <script type="text/javascript" src="js/script2.js?bust=1"></script>
</head>
<body>
<script type="text/javascript">
	var _gaq = [['_setAccount', 'UA-7778406-3'], ['_trackPageview']];
	if (document.location.protocol !== 'file:') {
		(function() {
			var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
			ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
			(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(ga);
		})();
	}
</script>
<div id="body-outer"><div id="body-inner"><div id="body" class="clearfix">
<div id="header">
    <div id="menu-follow">
    <div><a href="https://bitbucket.org/pypy/pypy"><img src="https://www.selenic.com/hg-logo/logo-droplets-25.png" width="14px" height="14px" /></a></div>
		<div><a href="http://feeds.feedburner.com/PyPyStatusBlog" title="Subscribe to the RSS Feed"><img src="https://feedburner.google.com/fb/lib/images/icons/feed-icon-12x12-orange.gif" alt="Subscribe to the RSS Feed" width="14px" height="14px" /></a></div>
	<div id="logo"><a href="http://pypy.org"><img src="image/pypy-logo.png" alt="PyPy" height="110px" /></a></div>
	<hr class="clear-left" />
    <div id="menu-sub">
      <a href="index.html">Home</a>
        <span class="menu-sub-sep"> | </span>
      <a href="features.html">What is PyPy?</a>
        <span class="menu-sub-sep"> | </span>
      <a href="download.html">Download</a>
        <span class="menu-sub-sep"> | </span>
      <a href="compat.html">Compatibility</a>
        <span class="menu-sub-sep"> | </span>
      <a href="performance.html">Performance</a>
        <span class="menu-sub-sep"> | </span>
      <a href="http://doc.pypy.org">Dev Documentation</a>
        <span class="menu-sub-sep"> | </span>
      <a href="http://morepypy.blogspot.com">Blog</a>
        <span class="menu-sub-sep"> | </span>
      <a href="people.html">People</a>
        <span class="menu-sub-sep"> | </span>
      <a href="contact.html">Contact</a>
        <br />
    </div>
	<hr class="clear" />
</div>
<div id="content">
<div>
<div id="main">
Maciej Fijalkowski's avatar
Maciej Fijalkowski committed
<h1 class="title">Performance</h1>
<div class="contents topic" id="contents">
<p class="topic-title first">Contents</p>
<ul class="simple">
Armin Rigo's avatar
Armin Rigo committed
<li><a class="reference internal" href="#profiling-vmprof" id="id1">Profiling: vmprof</a></li>
<li><a class="reference internal" href="#optimization-strategy" id="id2">Optimization strategy</a></li>
<li><a class="reference internal" href="#micro-tuning-tips" id="id3">Micro-tuning tips</a></li>
<li><a class="reference internal" href="#insider-s-point-of-view" id="id4">Insider's point of view</a></li>
</ul>
</div>
<p>This document collects strategies, tactics and tricks for making your
code run faster under PyPy.  Many of these are also useful hints for
stock Python and other languages.  For contrast, we also describe some
CPython (stock Python) optimizations that are not needed in PyPy.</p>
Armin Rigo's avatar
Armin Rigo committed
<hr class="docutils" />
<div class="section" id="profiling-vmprof">
<span id="profiling"></span><span id="profiler"></span><h1><a class="toc-backref" href="#id1">Profiling: vmprof</a></h1>
<p>As a general rule, when considering performance issues, follow these
three points: first <em>measure</em> them (it is counter-productive to fight
imaginary performance issues); then <em>profile</em> your code (it is useless
to optimize the wrong parts).  Only optimize then.</p>
<p>PyPy 2.6 introduced <a class="reference external" href="https://vmprof.readthedocs.org/">vmprof</a>, a very-low-overhead statistical profiler.
The standard, non-statistical <tt class="docutils literal">cProfile</tt> is also supported, and can be
enabled without turning off the JIT.  We do recommend vmprof anyway
because turning on cProfile can distort the result (sometimes massively,
though hopefully this should not be too common).</p>
</div>
<hr class="docutils" />
<div class="section" id="optimization-strategy">
Armin Rigo's avatar
Armin Rigo committed
<h1><a class="toc-backref" href="#id2">Optimization strategy</a></h1>
<p>These suggestions apply to all computer languages.  They're here as
reminders of things to try before any Python or PyPy-specific tweaking.</p>
<div class="section" id="build-a-regression-test-suite">
<h2>Build a regression-test suite</h2>
<p>Before you start tuning, build a regression-test suite for your code.
This front-loads a significant amount of work, but it means you can
try lots of optimizations without worrying so much about introducing
functional bugs.</p>
</div>
<div class="section" id="measure-don-t-guess">
<h2>Measure, don't guess</h2>
<p>Human beings are bad at guessing or intuiting where the hotspots in code are.
Armin Rigo's avatar
Armin Rigo committed
Measure, don't guess; use a <a class="reference internal" href="#profiler">profiler</a> to pin down the 20% of the
code where the code is spending 80% of its time, then speed-tune that.</p>
<p>Measuring will save you a lot of effort wasted on tuning parts of the code
that aren't actually bottlenecks.</p>
<p>As you tune, re-profile frequently  so you can see how the hottest spots
are shifting around.</p>
</div>
<div class="section" id="i-o-bound-is-different-from-compute-bound">
<h2>I/O-bound is different from compute-bound</h2>
<p>Be aware of the difference between code that is compute-bound (slow
because it's doing a huge number of instructions) and code that is I/O
bound (slow because of disk or network delays).</p>
<p>Expect to get most of your gains from optimizing compute-bound code.
It's usually (though not always) a sign that you're near the end of
Armin Rigo's avatar
Armin Rigo committed
worthwhile tuning when <a class="reference internal" href="#profiling">profiling</a> shows that the bulk of the
application's time is spent on network and disk I/O.</p>
</div>
<div class="section" id="tune-your-algorithms-first">
<h2>Tune your algorithms first</h2>
<p>Generally, when your code is doing things that are O(n**2) or larger
in the size of your data set, the cost of those operations is going
to swamp any small gains you can pick up with the tricks we describe
here.</p>
<p>Tune your algorithms first.  It's time to think about applying our
list of micro-tuning tips  <em>after</em> you think you've optimized out
intrinsically expensive operations.</p>
<p>That said, be prepared for the possibility that you will discover
better-hidden algorithmic problems as you micro-tune.  Likely
you will go through this cycle more than once.</p>
</div>
<div class="section" id="focus-on-tight-loops">
<h2>Focus on tight loops</h2>
<p>It's extremely common for high time costs to lurk within some
innocuous-looking code inside a tight loop - especially in code
that does something like a searching/matching/lookup operation
or any kind of graph traversal.</p>
<p>Probably the most common kind of performance-killer in compute-bound
code is an O(n**2) operation that is disguised by being some sort of
O(n) lookup or match inside an O(n) loop.</p>
<p>Another common time-sink is relatively expensive common-setup
operations that are performed inside tight loops but could be moved
to before they start.  (For a representative case of this, see the
micro-tuning tip on regexp compilation.)</p>
</div>
<div class="section" id="smaller-is-faster">
<h2>Smaller is faster</h2>
<p>Modern computers have multiple levels of memory caching, some directly
on the processor chip.  Causing a cache miss at any level incurs a
performance penalty proportional to random-access time for the next
outward (and much slower) layer of cache.</p>
<p>Accordingly, smaller is faster.  Programs or routines with a small
enough working set to fit inside a fast cache will be as fast as
that cache is. To make your code fast, reduce the length of the
series of Python or JIT-compiler opcodes it generates by making
it simpler.</p>
<p>The tradeoff here is that algorithmic tuning often trades time for
space - that is, it increases the size of an algorithm's working set
by including pre-computations or tables or reverse maps in order to
avoid O(n**2) operations.</p>
<p>It's impossible to predict in advance where the sweet spot in that
tradeoff will be.  You have to try different things and measure -
which takes us right back to &ldquo;Measure, don't guess&rdquo;.  And another
function of your regression test suite can be as a speed benchmark.</p>
</div>
</div>
Armin Rigo's avatar
Armin Rigo committed
<hr class="docutils" />
<div class="section" id="micro-tuning-tips">
Armin Rigo's avatar
Armin Rigo committed
<h1><a class="toc-backref" href="#id3">Micro-tuning tips</a></h1>
<p>These are in no particular order.</p>
<div class="section" id="keep-it-simple">
<h2>Keep it simple</h2>
<p>Simple is better than complex. The PyPy JIT is not very smart; the
simpler your code is the better it will run. Here again, though, you face
a tradeoff: you may need to pay with more algorithmic complexity in order
to avoid brute-force operations that are O(n**2) or worse.</p>
<p>Write plain-vanilla code in plain-vanilla ways. The PyPy JIT has many
productions that optimize a common usage pattern against an uncommon
usage pattern.</p>
</div>
<div class="section" id="global-variables">
<h2>Global variables</h2>
<p>In CPython, global variables and functions (including package imports)
are much more expensive to reference than locals; avoid them.  (This
is also good modularity practice).</p>
<p>The cost of CPython global references is high enough that, for example, if you
have code in a frequently-visited inner loop that uses int() a lot, it
may be worthwhile to create a local copy of the reference with &ldquo;int =
int&rdquo; in an enclosing block.</p>
<p>However, this in <em>not</em> true in JITted PyPy code. The &ldquo;int = int&rdquo; hack
won't buy you performance, it's just an extra copy.  The modularity
reason for avoiding globals are still valid.</p>
</div>
<div class="section" id="regular-expressions">
<h2>Regular expressions</h2>
<p>Regular-expression compilation is expensive.  If the regexp pattern in
a search, match, or replace operation is static (doesn't mutate at
runtime) refactor so it's only done once.</p>
<p>If the regexp compilation is in a class method, consider doing it as
the initializer of a regexp-valued static (shared) class member and
using that class member in your operation.</p>
<p>If the regexp compilation is in a free function, consider moving it
to module level and referencing the resulting regexp object
(but see the warning above about global variables).</p>
</div>
<div class="section" id="old-vs-new-style-classes">
<h2>Old- vs. new-style classes</h2>
<p>New-style classes allow faster attribute access and take up less core
per instance than old-style classes.  Much of this advantage may be
Armin Rigo's avatar
Armin Rigo committed
lost, however, if attribute names are not constant. For example: x.a
= y or even setattr(x, &lsquo;a&rsquo;, y) will be much faster than a dynamic
version: setattr(x, &lsquo;a&rsquo; + some_variable, y).</p>
<p>Classes that inherit from both new- and old-style classes are
<em>extremely</em> slow; avoid at all costs.</p>
<p>In PyPy, isinstance() called against an old-style class was very slow
until 2.0.</p>
</div>
<div class="section" id="string-concatenation-is-expensive">
<h2>String concatenation is expensive</h2>
<p>In CPython, you may want to replace:</p>
<pre class="literal-block">
s = head + body + maybe + tail
</pre>
<p>with the admittedly less readable:</p>
<pre class="literal-block">
Armin Rigo's avatar
Armin Rigo committed
s = &quot;%(head)s%(body)s%(maybe)s%(tail)s&quot; % locals()
</pre>
<p>or even:</p>
<pre class="literal-block">
s = &quot;{head}{body}{maybe}{tail}&quot;.format(**locals())
</pre>
<p>Both of the latter forms avoid multiple-allocation overhead.
But PyPy's JIT makes the overhead of intermediate concatenations
go away in linear code that keeps the number of concatenations
small, bound and constant.  (And <tt class="docutils literal">locals()</tt> is rather slow
with PyPy's JIT.)</p>
<p>On the other hand, in code like this with a string-valued foo() function:</p>
<pre class="literal-block">
for x in mylist:
    s += foo(x)
</pre>
<p>the JIT cannot optimize out intermediate copies.  This code is
actually quadratic in the total size of the mylist strings due to
repeated string copies of ever-larger prefix segments.</p>
<p>This:</p>
<pre class="literal-block">
parts = []
for x in mylist:
    parts.append(foo(x))
s = &quot;&quot;.join(parts)
</pre>
<p>can be much faster because all the string concatenation in the last
line creates exactly one new string object with one C-level copy
sequence (and list operations are relatively cheap).</p>
</div>
<div class="section" id="frame-introspection-and-tracing-are-slow">
<h2>Frame introspection and tracing are slow</h2>
<p>Certain function calls can disable PyPy's speed options over
stretches of surrounding code called &ldquo;JIT scopes&rdquo;.</p>
<p>A JIT like PyPy's works based on the assumption that the only thing
worth optimizing are loops that are executed often. Whenever the
interpreter enters a loop in the interpreted program, the JIT records
what the interpreter does, creating a trace. This trace is optimized,
compiled to machine code and executed when the loop is hit with the
conditions observed during tracing.  This trace is one kind of JIT scope.</p>
<p>Another kind of JIT scope that matters is a function, considered as
a unit for inlining.</p>
<p>Note that a JIT scope is a run-time phenomenon, not a compile-time
one.  It's not confined by source-code module boundaries.  A library-
or foreign-module call in a frequently-called loop or inlined function
will be part of its JIT scope.</p>
<p>locals(), globals(), sys._getframe(), sys.exc_info(), and sys.settrace
work in PyPy, but they incur a performance penalty that can be huge by
disabling the JIT over the enclosing JIT scope.</p>
<p><em>(Thanks Eric S. Raymond for the text above)</em></p>
</div>
</div>
Armin Rigo's avatar
Armin Rigo committed
<hr class="docutils" />
<div class="section" id="insider-s-point-of-view">
Armin Rigo's avatar
Armin Rigo committed
<h1><a class="toc-backref" href="#id4">Insider's point of view</a></h1>
<p>This section describes performance issues from the point of view of
insiders of the project; it should be particularly interesting if you
plan to contribute in that area.</p>
<p>One of the goals of the PyPy project is to provide a fast and compliant
python interpreter. Some of the ways we achieve this are by providing a
high-performance garbage collector (GC) and a high-performance
Just-in-Time compiler (JIT).  Results of comparing PyPy and CPython can
be found on the <a class="reference external" href="http://speed.pypy.org">speed website</a>. Those benchmarks are not a random
collection: they are a combination of real-world Python programs &ndash;
benchmarks originally included with the (now dead) Unladen Swallow
project &ndash; and benchmarks for which we found PyPy to be slow (and improved).
Consult the descriptions of each for details.</p>
<p>The JIT, however, is not a magic bullet. There are several characteristics
that might surprise people who are not used to JITs in
general or to the PyPy JIT in particular.  The JIT is generally good at
speeding up straight-forward Python code that spends a lot of time in the
bytecode dispatch loop, i.e., running actual Python code &ndash; as opposed
to running things that only are invoked by Python code.  Good
examples include numeric calculations or any kind of heavily
object-oriented program.  Bad examples include doing computations with
large longs &ndash; which is performed by unoptimizable support code.  When the
JIT cannot help, PyPy is generally slower than CPython.</p>
<p>More specifically, the JIT is known not to work on:</p>
<ul class="simple">
<li><strong>Tests</strong>: The ideal unit tests execute each piece of tested code
once.  This leaves no time for the JIT to warm up.</li>
<li><strong>Really short-running scripts</strong>: A rule of thumb is if something runs below
0.2s the JIT has no chance, but it depends a lot on the program in question.
In general, make sure you warm up your program before running benchmarks, if
you're measuring something long-running like a server.  The time required
to warm up the JIT varies; give it at least a couple of seconds.  (PyPy's
JIT takes an especially long time to warm up.)</li>
<li><strong>Long-running runtime functions</strong>: These are the functions provided
by the runtime of PyPy that do a significant amount of work.
PyPy's runtime is generally not as optimized as CPython's and we expect those
functions to take somewhere between the same time as CPython to twice as long.
This includes, for example, computing with longs, or sorting large lists.
A counterexample is regular expressions: although they take time, they
come with their own JIT.</li>
</ul>
<p>Unrelated things that we know PyPy to be slow at (note that we're probably
working on it):</p>
<ul class="simple">
<li><strong>CPython C extension modules</strong>: Any C extension module recompiled
with PyPy takes a very large hit in performance.  PyPy supports C
extension modules solely to provide basic functionality.
If the extension module is for speedup purposes only, then it
makes no sense to use it with PyPy at the moment.  Instead, remove it
and use a native Python implementation, which also allows opportunities
for JIT optimization.  If the extension module is
both performance-critical and an interface to some C library, then it
might be worthwhile to consider rewriting it as a pure Python version
that uses <a class="reference external" href="http://cffi.readthedocs.org/">CFFI</a> for the interface.</li>
<li><strong>Missing RPython modules</strong>: A few modules of the standard library
(like <tt class="docutils literal">csv</tt> and <tt class="docutils literal">cPickle</tt>) are written in C in CPython, but written
natively in pure Python in PyPy.  Sometimes the JIT is able to do a
good job on them, and sometimes not.  In most cases (like <tt class="docutils literal">csv</tt> and
<tt class="docutils literal">cPickle</tt>), we're slower than CPython, with the notable exception of
<tt class="docutils literal">json</tt> and <tt class="docutils literal">heapq</tt>.</li>
<li><strong>Abuse of itertools</strong>: The itertools module is often &ldquo;abused&rdquo; in the
sense that it is used for the wrong purposes.  From our point of view,
itertools is great if you have iterations over millions of items, but
not for most other cases.  It gives you 3 lines in functional style
that replace 10 lines of Python loops (longer but arguably much easier
to read).  The pure Python version is generally not slower even on
CPython, and on PyPy it allows the JIT to work much better &ndash; simple
Python code is fast.  The same argument also applies to <tt class="docutils literal">filter()</tt>,
<tt class="docutils literal">reduce()</tt>, and to some extend <tt class="docutils literal">map()</tt> (although the simple case
is JITted), and to all usages of the <tt class="docutils literal">operator</tt> module we can think
of.</li>
<li><strong>Ctypes</strong>: Ctypes is slower than on CPython.  Consider <a class="reference external" href="http://cffi.readthedocs.org/">CFFI</a> instead,
which has special paths inside the JIT.</li>
</ul>
<p>We generally consider things that are slower on PyPy than CPython to be bugs
of PyPy.  If you find some issue that is not documented here,
Armin Rigo's avatar
Armin Rigo committed
please report it to our <a class="reference external" href="https://bitbucket.org/pypy/pypy/issues?status=new&amp;status=open">bug tracker</a> for investigation.</p>
<div id="sidebar">
</div>
</div>
</div>
</div></div></div>
</body>
</html>