<div dir="ltr"><br><br><div class="gmail_quote"><div dir="ltr">On Wed, 27 Jan 2016 at 10:26 Yury Selivanov <<a href="mailto:yselivanov.ml@gmail.com">yselivanov.ml@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi,<br>
<br>
<br>
tl;dr The summary is that I have a patch that improves CPython<br>
performance up to 5-10% on macro benchmarks.  Benchmarks results on<br>
Macbook Pro/Mac OS X, desktop CPU/Linux, server CPU/Linux are available<br>
at [1].  There are no slowdowns that I could reproduce consistently.<br>
<br>
There are twodifferent optimizations that yield this speedup:<br>
LOAD_METHOD/CALL_METHOD opcodes and per-opcode cache in ceval loop.<br>
<br>
<br>
LOAD_METHOD & CALL_METHOD<br>
-------------------------<br>
<br>
We had a lot of conversations with Victor about his PEP 509, and he sent<br>
me a link to his amazing compilation of notes about CPython performance<br>
[2].  One optimization that he pointed out to me was LOAD/CALL_METHOD<br>
opcodes, an idea first originated in PyPy.<br>
<br>
There is a patch that implements this optimization, it's tracked here:<br>
[3].  There are some low level details that I explained in the issue,<br>
but I'll go over the high level design in this email as well.<br>
<br>
Every time you access a method attribute on an object, a BoundMethod<br>
object is created. It is a fairly expensive operation, despite a<br>
freelist of BoundMethods (so that memory allocation is generally<br>
avoided).  The idea is to detect what looks like a method call in the<br>
compiler, and emit a pair of specialized bytecodes for that.<br>
<br>
So instead of LOAD_GLOBAL/LOAD_ATTR/CALL_FUNCTION we will have<br>
LOAD_GLOBAL/LOAD_METHOD/CALL_METHOD.<br>
<br>
LOAD_METHOD looks at the object on top of the stack, and checks if the<br>
name resolves to a method or to a regular attribute.  If it's a method,<br>
then we push the unbound method object and the object to the stack.  If<br>
it's an attribute, we push the resolved attribute and NULL.<br>
<br>
When CALL_METHOD looks at the stack it knows how to call the unbound<br>
method properly (pushing the object as a first arg), or how to call a<br>
regular callable.<br>
<br>
This idea does make CPython faster around 2-4%.  And it surely doesn't<br>
make it slower.  I think it's a safe bet to at least implement this<br>
optimization in CPython 3.6.<br>
<br>
So far, the patch only optimizes positional-only method calls. It's<br>
possible to optimize all kind of calls, but this will necessitate 3 more<br>
opcodes (explained in the issue).  We'll need to do some careful<br>
benchmarking to see if it's really needed.<br>
<br>
<br>
Per-opcode cache in ceval<br>
-------------------------<br>
<br>
While reading PEP 509, I was thinking about how we can use<br>
dict->ma_version in ceval to speed up globals lookups.  One of the key<br>
assumptions (and this is what makes JITs possible) is that real-life<br>
programs don't modify globals and rebind builtins (often), and that most<br>
code paths operate on objects of the same type.<br>
<br>
In CPython, all pure Python functions have code objects.  When you call<br>
a function, ceval executes its code object in a frame. Frames contain<br>
contextual information, including pointers to the globals and builtins<br>
dict.  The key observation here is that almost all code objects always<br>
have same pointers to the globals (the module they were defined in) and<br>
to the builtins.  And it's not a good programming practice to mutate<br>
globals or rebind builtins.<br>
<br>
Let's look at this function:<br>
<br>
def spam():<br>
     print(ham)<br>
<br>
Here are its opcodes:<br>
<br>
   2           0 LOAD_GLOBAL              0 (print)<br>
               3 LOAD_GLOBAL              1 (ham)<br>
               6 CALL_FUNCTION            1 (1 positional, 0 keyword pair)<br>
               9 POP_TOP<br>
              10 LOAD_CONST               0 (None)<br>
              13 RETURN_VALUE<br>
<br>
The opcodes we want to optimize are LAOD_GLOBAL, 0 and 3.  Let's look at<br>
the first one, that loads the 'print' function from builtins.  The<br>
opcode knows the following bits of information:<br>
<br>
- its offset (0),<br>
- its argument (0 -> 'print'),<br>
- its type (LOAD_GLOBAL).<br>
<br>
And these bits of information will *never* change.  So if this opcode<br>
could resolve the 'print' name (from globals or builtins, likely the<br>
latter) and save the pointer to it somewhere, along with<br>
globals->ma_version and builtins->ma_version, it could, on its second<br>
call, just load this cached info back, check that the globals and<br>
builtins dict haven't changed and push the cached ref to the stack.<br>
That would save it from doing two dict lookups.<br>
<br>
We can also optimize LOAD_METHOD.  There are high chances, that 'obj' in<br>
'obj.method()' will be of the same type every time we execute the code<br>
object.  So if we'd have an opcodes cache, LOAD_METHOD could then cache<br>
a pointer to the resolved unbound method, a pointer to obj.__class__,<br>
and tp_version_tag of obj.__class__.  Then it would only need to check<br>
if the cached object type is the same (and that it wasn't modified) and<br>
that obj.__dict__ doesn't override 'method'.  Long story short, this<br>
caching really speeds up method calls on types implemented in C.<br>
list.append becomes very fast, because list doesn't have a __dict__, so<br>
the check is very cheap (with cache).<br></blockquote><div><br></div><div>What would it take to make this work with Python-defined classes? I guess that would require knowing the version of the instance's __dict__, the instance's __class__ version, the MRO, and where the method object was found in the MRO and any intermediary classes to know if it was suddenly shadowed? I think that's everything. :)</div><div><br></div><div>Obviously that's a lot, but I wonder how many classes have a deep inheritance model vs. inheriting only from `object`? In that case you only have to check self.__dict__.ma_version, self.__class__, self.__class__.__dict__.ma_version, and self.__class__.__class__ == `type`. I guess another way to look at this is to get an idea of how complex do the checks have to get before caching something like this is not worth it (probably also depends on how often you mutate self.__dict__ thanks to mutating attributes, but you could in that instance just decide to always look at self.__dict__ for the method's key and then do the ma_version cache check for everything coming from the class).</div><div><br></div><div>Otherwise we can consider looking at the the caching strategies that Self helped pioneer (<a href="http://bibliography.selflanguage.org/">http://bibliography.selflanguage.org/</a>) that all of the various JS engines lifted and consider caching all method lookups.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
A straightforward way to implement such a cache is simple, but consumes<br>
a lot of memory, that would be just wasted, since we only need such a<br>
cache for LOAD_GLOBAL and LOAD_METHOD opcodes. So we have to be creative<br>
about the cache design.  Here's what I came up with:<br>
<br>
1. We add a few fields to the code object.<br>
<br>
2. ceval will count how many times each code object is executed.<br>
<br>
3. When the code object is executed over ~900 times, we mark it as<br>
"hot".</blockquote><div><br></div><div>What happens if you simply consider all code as hot? Is the overhead of building the mapping such that you really need this, or is this simply to avoid some memory/startup cost?</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">  We also create an 'unsigned char' array "MAPPING", with length<br>
set to match the length of the code object.  So we have a 1-to-1 mapping<br>
between opcodes and MAPPING array.<br>
<br>
4. Next ~100 calls, while the code object is "hot", LOAD_GLOBAL and<br>
LOAD_METHOD do "MAPPING[opcode_offset()]++".<br>
<br>
5. After 1024 calls to the code object, ceval loop will iterate through<br>
the MAPPING, counting all opcodes that were executed more than 50 times.<br></blockquote><div><br></div><div>Where did the "50 times" boundary come from? Was this measured somehow or did you just guess at a number?</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
6. We then create an array of cache structs "CACHE" (here's a link to<br>
the updated code.h file: [6]).  We update MAPPING to be a mapping<br>
between opcode position and position in the CACHE. The code object is<br>
now "optimized".<br>
<br>
7. When the code object is "optimized", LOAD_METHOD and LOAD_GLOBAL use<br>
the CACHE array for fast path.<br>
<br>
8. When there is a cache miss, i.e. the builtins/global/obj.__dict__<br>
were mutated, the opcode marks its entry in 'CACHE' as deoptimized, and<br>
it will never try to use the cache again.<br>
<br>
Here's a link to the issue tracker with the first version of the patch:<br>
[5].  I'm working on the patch in a github repo here: [4].<br>
<br>
<br>
Summary<br>
-------<br>
<br>
There are many things about this algorithm that we can improve/tweak.<br>
Perhaps we should profile code objects longer, or account for time they<br>
were executed.  Maybe we shouldn't deoptimize opcodes on their first<br>
cache miss.  Maybe we can come up with better data structures.  We also<br>
need to profile the memory and see how much more this cache will require.<br>
<br>
One thing I'm certain about, is that we can get a 5-10% speedup of<br>
CPython with relatively low memory impact.  And I think it's worth<br>
exploring that!<br></blockquote><div><br></div><div>Great!</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
If you're interested in these kind of optimizations, please help with<br>
code reviews, ideas, profiling and benchmarks.  The latter is especially<br>
important, I'd never imagine how hard it is to come up with a good macro<br>
benchmark.<br></blockquote><div><br></div><div>Have you tried <a href="http://hg.python.org/benchmarks">hg.python.org/benchmarks</a>? Or are you looking for new benchmarks? If the latter then we should probably strike up a discussion on speed@ and start considering a new, unified benchmark suite that CPython, PyPy, Pyston, Jython, and IronPython can all agree on.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
I also want to thank my company MagicStack (<a href="http://magic.io" rel="noreferrer" target="_blank">magic.io</a>) for sponsoring<br>
this work.<br></blockquote><div><br></div><div>Yep, thanks to all the companies sponsoring people doing work lately to try and speed things up! </div></div></div>