# Bytecode Hacking for Great Justice

DO NOT TRY THIS AT HOME! NO PYTHONS WERE HURT IN THE CREATION OF THIS BLOG POST!

Check out the code at code at github.com/mynameisfiber/pytailcall

As an exercise into learning more about python 2.7 bytecode, I wanted to implement the thing that pythonistas love to hate - tail call optimization! This isn’t novel at all, but I chose to implement this only using the standard library so that I could understand more about generating and modifying bytecode. As a result, I’m sure there are many edge cases that I don’t consider so please, keep your sys-ops sane and do not use this code in production. In the end, even though the code is fun it is a filthy hack that shouldn’t be used in production code and should never be considered to make it’s way into the python source. One point I really like on Guido’s blog post about this issue is tail recursion optimization ruins the stack traces and detracts from python’s ability to debug easily.

Tail calls are when a function is recursing and returns simply on a function call to itself. This is different than normal recursion where multiple things can be happening on our recursed return statement. So, for example, this is tail recursion,

def factorial(N, result=1):
if N == 1:
return result
return factorial(N-1, N*result)


While this is not,

def factorial(N):
if N == 1:
return 1
return N * factorial(N-1)


So we can see that normal recursion uses the return register in order to maintain the state of the calculation. By contrast, tail recursion uses a function parameter. This is made particularly simple in python because you can have keyword arguments with default values to initialize the calculation.

The thing that makes tail calls particularly useful is the ability to optimize them. Generally when a function gets called, the system must set up a function stack in memory that maintains the state of the function, including local variables and code pointers, so that the function can go on its merry way. However, when we do a tail recursion we are trying to enter the same function stack that we are already in, just with changes to the values of the arguments! This can be quickly optimized by never creating the new function stack and instead just modifying the argument values and starting the function from the beginning!

One way of doing this is manually unravelling the recursion. For our example above, the factorial would become,

def factorial(N, result=1):
while True:
if N == 1:
return result
N, result = N-1, N*result


Not only will this speed up our code, but we also don’t have to worry about those pesky recursion limits that python imposes on us. Furthermore, the transformation is quite simple. All we did was add a while True: to the beginning of the function and change any tail calls with changes to the argument variables.

There are a whole host of methods to do this automatically (partial functions, exceptions, etc., but I thought it would be fun to do this by re-writing the bytecode of the function itself. Let’s start by looking at the actual bytecode of the factorial function using the dis module from the standard library.

>>> dis.dis(factorial)
# bytecode                                             # relevant python
# -----------------------------------------------------#---------------------
2           0 LOAD_FAST                0 (N)         # if N == 1:
6 COMPARE_OP               2 (==)        #
9 POP_JUMP_IF_FALSE       16             #
#
3          12 LOAD_FAST               1 (result)     #    return result
15 RETURN_VALUE                           #
#
4     >>   16 LOAD_GLOBAL              0 (factorial) # return factorial(N-1, N*result)
25 BINARY_SUBTRACT                        #
32 BINARY_MULTIPLY                        #
33 CALL_FUNCTION            2             #
36 RETURN_VALUE                           #


We can see the full structure of our function in the bytecode. First we load up N and the constant 1 and compare them using the COMPARE_OP bytecode. If the result if false, we jump to line 16 and if not we load the variable result into the stack and return it. On line 16, we first load the reference to the function named factorial (which happens to be the same function we’re in!) and start building up the arguments. First we load up N and 1 and call BINARY_SUBTRACT which will leave the value of N-1 on the stack. Then we load up N and result and multiply them with BINARY_MULTIPLY which will push the value of N-1 onto the stack. By calling the CALL_FUNCTION bytecode (with the argument 2 indicating that there are two arguments to the function), python can go out and start running the function in another context until it returns and we can call RETURN_VALUE on line 36 to return whatever is left in the stack. This may seem like a convoluted way of approaching how a function works (although it has its uses!), but after a while spent looking at opcodes this starts to make just as much sense as python itself!

In an ideal world, what would we want this bytecode to look like? Looking up the references on JUMP_ABSOLUTE, we can rewrite the above bytecode to be,

  2     >>    0 LOAD_FAST                0 (N)
6 COMPARE_OP               2 (==)
9 POP_JUMP_IF_FALSE       16

15 RETURN_VALUE

4     >>   16 LOAD_FAST                0 (N)
22 BINARY_SUBTRACT
29 BINARY_MULTIPLY
30 STORE_FAST               1 (result)
33 STORE_FAST               0 (N)
36 JUMP_ABSOLUTE            0


The differences here start at line 16. Instead of loading a reference to the recursed function, we immediately start filling up the stack with what were the arguments to the function. Then, once our arguments have been computed, instead of doing a CALL_FUNCTION, we start running a sequence of STORE_FAST to pop the calculated arguments off the stack and into the actual argument variables. Now that the arguments have been modified, we can call JUMP_ABSOLUTE with an argument of 0 in order to jump back to the beginning of the function and starting again. This last aspect, the JUMP_ABSOLUTE back to the beginning of the function as oppose to setting up a while loop, is one of the reasons this function is faster than the manual unrolling of the recursion we did above; we don’t need to calculate the conditions of the loop or do any modifications to our state, we simply start processing opcodes at line 0 again.

This may seem simple, but there are many corner cases that will get you (and in fact got me in the hours of SystemError exceptions I wrestled with). First of all, if the recursive return is already within what python calls a block (ie: a loop or a try..except..finally block), we need to call the POP_BLOCK opcode the right amount of times before our JUMP_ABSOLUTE so that we properly terminate any setup those sections need.

Another problem, and probably much more annoying than the block counts, is that of changing the size and thus the addresses of the bytecodes. When bytecode is represented, it is simply a list of unsigned four-bit integers. Some of these integers represent jumps to other points in the list, and it refers to those other points by either relative offsets (e.g., jump five integers to the right) or by absolute addresses (e.g., jump to the tenth integer). In order to make sure these jumps go to the correct place after we modify the bytecode, we must keep a list of what we added (and where) and, once our editing is done, go back through and modify any addresses to again point to the correct place.

Once all these problems are solved, we are left with a general decorator to transform all of our tail recursion into the iterative versions! And this is indeed much faster. Looking at the benchmark supplied with pytailcall, we can see that we reduce the overhead of recursion (by eliminating it) and are able to recurse much more than we were previously able to.

In the benchmark above, native is the original function (note that native python could not complete all of the benchmarks due to maximum recursion errors). partial_func is a trick which wraps the function in a partial and changes it’s internal reference to itself. return_tuple is another bytecode hack that changes the recursion into a specialized return statement that triggers another call to the function. Finally, internal_loop is the bytecode hack described above.

So, by committing this ungodly sin against all things python stands for, we can get a 33% speedup over python tail recursed code! In general though, this was a great exercise in learning much more about how python bytecode works and the underlying structure of a function. While this sort of bytecode hacking is exactly that, a hack, being able to read bytecode and understand the output of dis.dis is incredibly useful when optimizing python code for actual production systems. If you want to know more about that aspect of the optimization, and other more rigorous methods of optimization, check out High Performance Python.

-Micha

Older

## Latest posts

##### Nov 15, 2022 · newsletter
November 2022 Perhaps November conjures thoughts of holiday feasts and festivities, but for us, it’s the perfect time to chew the fat about machine learning! Make room on your plate for a peek behind the scenes into our current research on harnessing synthetic image generation to improve classification tasks. And, as usual, we reflect on our favorite reads of the month. New Research! In the first half of this year, we focused on natural language processing with our Text Style Transfer blog series.
##### Nov 14, 2022 · post
by Introduction This post documents the first part of a research effort to quantify the impact of synthetic data augmentation in training a deep learning model for detecting manufacturing defects on steel surfaces. We chose to generate synthetic data using CycleGAN,1 an architecture involving several networks that jointly learn a mapping between two image domains from unpaired examples (I’ll elaborate below). Research from recent years has demonstrated improvement on tasks like defect detection2 and image segmentation3 by augmenting real image data sets with synthetic data, since deep learning algorithms require massive amounts of data, and data collection can easily become a bottleneck.
##### Oct 20, 2022 · newsletter
October 2022 We’ve got another action-packed newsletter for October! Highlights this month include the re-release of a classic CFFL research report, an example-heavy tutorial on Dask for distributed ML, and our picks for the best reads of the month. Open Data Science Conference Cloudera Fast Forward Labs will be at ODSC West near San Fransisco on November 1st-3rd, 2022! If you’ll be in the Bay Area, don’t miss Andrew and Melanie who will be presenting our recent research on Neutralizing Subjectivity Bias with HuggingFace Transformers.
##### Sep 21, 2022 · newsletter
September 2022 Welcome to the September edition of the Cloudera Fast Forward Labs newsletter. This month we’re talking about ethics and we have all kinds of goodies to share including the final installment of our Text Style Transfer series and a couple of offerings from our newest research engineer. Throw in some choice must-reads and an ASR demo, and you’ve got yourself an action-packed newsletter! New Research! Ethical Considerations When Designing an NLG System In the final post of our blog series on Text Style Transfer, we discuss some ethical considerations when working with natural language generation systems, and describe the design of our prototype application: Exploring Intelligent Writing Assistance.
##### Sep 8, 2022 · post
by This post has a companion piece: Ethics Sheet for AI-assisted Comic Book Art Generation I want to make a comic book. Actually, I want to make tools for making comic books. See, the problem is, I can’t draw too good. I mean, I’m working on it. Check out these self portraits drawn 6 months apart: Left: “Sad Face”. February 2022. Right: “Eyyyy”. August 2022. But I have a long way to go until my illustrations would be considered professional quality, notwithstanding the time it would take me to develop the many other skills needed for making comic books.
##### Aug 18, 2022 · newsletter
August 2022 Welcome to the August edition of the Cloudera Fast Forward Labs newsletter. This month we’re thrilled to introduce a new member of the FFL team, share TWO new applied machine learning prototypes we’ve built, and, as always, offer up some intriguing reads. New Research Engineer! If you’re a regular reader of our newsletter, you likely noticed that we’ve been searching for new research engineers to join the Cloudera Fast Forward Labs team.

### Popular posts

##### Oct 30, 2019 · newsletter
Exciting Applications of Graph Neural Networks
##### Nov 14, 2018 · post
Federated learning: distributed machine learning with data locality and privacy
##### Apr 10, 2018 · post
PyTorch for Recommenders 101
##### Oct 4, 2017 · post
First Look: Using Three.js for 2D Data Visualization
##### Aug 22, 2016 · whitepaper
Under the Hood of the Variational Autoencoder (in Prose and Code)
##### Feb 24, 2016 · post
"Hello world" in Keras (or, Scikit-learn versus Keras)

# Reports

In-depth guides to specific machine learning capabilities

# Prototypes

Machine learning prototypes and interactive notebooks

## ASR with Whisper

Explore the capabilities of OpenAI's Whisper for automatic speech recognition by creating your own voice recordings!

## NeuralQA

A usable library for question answering on large datasets.
https://neuralqa.fastforwardlabs.com

## Explain BERT for Question Answering Models

Tensorflow 2.0 notebook to explain and visualize a HuggingFace BERT for Question Answering model.