Optimizing Python Code Using Cython: A Beginner’s Introduction

Optimizing Python Code Using Cython: A Beginner’s Introduction

There are much better resources than this blog that will lead you down the rabbit hole of Cythonizing your Python code, but this is just a very easy introduction, outlining my own personal experiments as a Cython beginner, myself. In this tutorial, we will use my dictionary creation tool, brutalist, as a really bad example of how to Cythonize some Python code.

In order to get the most out of Cython, you really need to have some Python functions in your code that can translate really well into the C programming language — a good example would be math operations and such. As you know, Python is an interpreted language, whereas C is a compiled language. If you don’t know the differences, you can read about them here, but basically, Cython is able to turn Python modules into compiled binaries that are executed by the machine rather than the interpreter. For all intents and purposes, we are mainly talking about faster code execution.

The reason brutalist is not a prime candidate for distribution as a Cythonized program is because the performance enhancements are extremely minimal. For the majority of its use cases, Python is perfectly-adequate, and you can generate a list of millions of words in a few seconds, to a few minutes, depending on how large the input list is. If you run brutalist normally, whether Cythonized or not, you will generally see the same exact execution times. The difference only comes when it has to process a shitload of data.

So, that being said, from my test cases with some larger input lists, Cythonization does actually provide around a 10% decrease in execution time for brutalist. If we are talking about an input file such as rockyou.txt, that could possibly shave off hours (if the program didn’t crash beforehand, as I’ve never fed it input that large). However, the purpose of this article is not to try and break my program or even perform benchmarks which I have already performed but didn’t write down. The purpose is to quicly show the reader how to Cythonize Python functions into a module that can be imported.

This tutorial will not go into detail about breaking down individual functions or using amortization. It’s a simple and straightforward guide to simple Cythonizationificationism, a term that I just now coined. It should be noted that if you actually go to the trouble of statically-typing some things during the Cythonizationification process, that will be of great use to the compiler, in which case poor brutalist could probably do a little better than a 10% performance increase.


Step 1 – Format your code correctly

Brutalist was already set up in a way that it could be turned into a module fairly easily. Please don’t copy this code, because the project is under active development, so you are much better off cloning the official repo and re-doing the step we’re about to do. The version used here is v1.6.9…nice.

All we need to do in this particular case is remove if __name__ == "__main__": and then change our indentation level so that the program would run basically the exact same way just without the builtin main function. I will be honest. I used Visual Studio Code to change my indentation level. I am not yet a vim master, and iTerm2 is not playing nice with the meta key in nano until I restart the program, so I chose another method. Just decrease the damn indent in whichever way you choose. You can compare to the version in the official repo, but essentially what we end up with looks like this:

#!/usr/bin/env python3
##############################################################################
#    Copyright (C) 2019  phx <https://github.com/phx>
#
#    This program is free software: you can redistribute it and/or modify
#    it under the terms of the GNU General Public License as published by
#    the Free Software Foundation, either version 3 of the License, or
#    (at your option) any later version.
#
#    This program is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#    GNU General Public License for more details.
#
#    You should have received a copy of the GNU General Public License
#    along with this program.  If not, see <https://www.gnu.org/licenses/>.
##############################################################################

import sys, re


def show_help():
    print()
    print("Usage: brutalist <[password] | -p [password] | -i [input file]> <[extended options]>\n")
    print("Options:")
    print("       [no params]                             takes input from stdin.")
    print("       [string]                                first argument is used as password.")
    print("       -p | --password                         second argument is used as password.")
    print("       -i | -f | --file [input file]           file is used as input.\n")
    print("Extended Options:")
    print("       -c | --limit-special | --limit-chars    limits special characters to '!@#$%*-+_'")
    print("       -n | --limit-numbers                    only includes common 1 and 2 digit suffixes + special")
    print("       -l | --limit                            limits both 3 digit numbers and special characters")
    print("            --leet                             includes all leet speak combinations (will increase size and time)")
    print()
    sys.exit()


def resubs(spass):
    spass = spass.strip()
    for key in CHARACTERS:
        for x in CHARACTERS[key]:
            tmp = re.sub(key, x, spass)
            subs.append(tmp)


def subappend(tmp):
    tmp = tmp.strip()
    if tmp not in subs:
        subs.append(tmp)
        resubs(tmp)


def get_subs(ch, char):
    spass = before + char + after
    spass = spass.strip()
    for key in CHARACTERS:
        for x in CHARACTERS[key]:
            subs.append(re.sub(key, x, spass))

    lower_char = char.lower()
    if '--leet' in sys.argv:
        for sc in range(len(spass)):
            b = spass[:sc]
            a = spass[sc+1:]
            if ch == sc:
                if lower_char == 'a':
                    subs.append(b + '4' + a)
                    subs.append(b + '@' + a)
                    resubs(b + '4' + a)
                    resubs(b + '@' + a)
                if lower_char == 'b':
                    subs.append(b + '3' + a)
                    subs.append(b + '13' + a)
                    resubs(b + '3' + a)
                    resubs(b + '13' + a)
                if lower_char == 'c':
                    subs.append(b + '(' + a)
                    resubs(b + '(' + a)
                if lower_char == 'd':
                    subs.append(b + '[)' + a)
                    resubs(b + '[)' + a)
                if lower_char == 'e':
                    subs.append(b + '3' + a)
                    resubs(b + '3' + a)
                if lower_char == 'f':
                    subs.append(b + '|=' + a)
                    resubs(b + '|=' + a)
                if lower_char == 'g':
                    subs.append(b + '6' + a)
                    resubs(b + '6' + a)
                if lower_char == 'h':
                    subs.append(b + '|-|' + a)
                    resubs(b + '|-|' + a)
                if lower_char == 'i':
                    subs.append(b + '|' + a)
                    subs.append(b + '1' + a)
                    resubs(b + '|' + a)
                    resubs(b + '1' + a)
                if lower_char == 'l':
                    subs.append(b + '1' + a)
                    resubs(b + '1' + a)
                    subs.append(b + '|' + a)
                    resubs(b + '|' + a)
                if lower_char == 'm':
                    subs.append(b + '|Y|' + a)
                    resubs(b + '|Y|' + a)
                if lower_char == 'n':
                    subs.append(b + '/V' + a)
                    resubs(b + '/V' + a)
                if lower_char == 'o':
                    subs.append(b + '0' + a)
                    resubs(b + '0' + a)
                if lower_char == 'p':
                    subs.append(b + '|>' + a)
                    resubs(b + '|>' + a)
                if lower_char == 'q':
                    subs.append(b + '0,' + a)
                    resubs(b + '0,' + a)
                if lower_char == 'r':
                    subs.append(b + '|2' + a)
                    resubs(b + '|2' + a)
                if lower_char == 's':
                    subs.append(b + '5' + a)
                    subs.append(b + '$' + a)
                    resubs(b + '5' + a)
                    resubs(b + '$' + a)
                if lower_char == 't':
                    subs.append(b + '7' + a)
                    subs.append(b + '+' + a)
                    resubs(b + '7' + a)
                    resubs(b + '+' + a)
                if lower_char == 'u':
                    subs.append(b + '[_]' + a)
                    resubs(b + '[_]' + a)
                if lower_char == 'w':
                    resubs(b + 'vv' + a)
                    resubs(b + 'uu' + a)
                if lower_char == 'x':
                    subs.append(b + '}-{' + a)
                    resubs(b + '}-{' + a)
                if lower_char == 'y':
                    subs.append(b + '`/' + a)
                    resubs(b + '`/' + a)
                if lower_char == 'z':
                    subs.append(b + '2' + a)
                    resubs(b + '2' + a)
    else:
        for sc in range(len(spass)):
            b = spass[:sc]
            a = spass[sc+1:]
            if ch == sc:
                if lower_char == 'a':
                    subs.append(b + '@' + a)
                    resubs(b + '@' + a)
                if lower_char == 'b':
                    subs.append(b + '3' + a)
                    resubs(b + '3' + a)
                if lower_char == 'e':
                    subs.append(b + '3' + a)
                    resubs(b + '3' + a)
                if lower_char == 'g':
                    subs.append(b + '6' + a)
                    resubs(b + '6' + a)
                if lower_char == 'i':
                    subs.append(b + '1' + a)
                    resubs(b + '1' + a)
                if lower_char == 'l':
                    subs.append(b + '1' + a)
                    resubs(b + '1' + a)
                if lower_char == 'o':
                    subs.append(b + '0' + a)
                    resubs(b + '0' + a)
                if lower_char == 'q':
                    subs.append(b + '0,' + a)
                    resubs(b + '0,' + a)
                if lower_char == 's':
                    subs.append(b + '5' + a)
                    subs.append(b + '$' + a)
                    resubs(b + '5' + a)
                    resubs(b + '$' + a)
                if lower_char == 'z':
                    subs.append(b + '2' + a)
                    resubs(b + '2' + a)

"""
this is where __main__ was before removing indentation for Cython module compatibility:
if __name__ == '__main__':
"""

if '--leet' in sys.argv:
    CHARACTERS = {
            r'[Aa]': ['A', 'a', '4', '@'],
            r'[Bb]': ['B', 'b', '3', '13'],
            r'[Cc]': ['C', 'c', '('],
            r'[Dd]': ['D', 'd', '[)'],
            r'[Ee]': ['E', 'e', '3'],
            r'[Ff]': ['F', 'f', '|='],
            r'[Gg]': ['G', 'g', '6'],
            r'[Hh]': ['H', 'h', '|-|'],
            r'[Ii]': ['I', 'i', '1', '|'],
            r'[Jj]': ['J', 'j', '.]'],
            r'[Kk]': ['K', 'k', '|<'],
            r'[Ll]': ['L', 'l', '1', '|'],
            r'[Mm]': ['M', 'm', '|Y|'],
            r'[Nn]': ['N', 'n', '/V'],
            r'[Oo]': ['O', 'o', '0'],
            r'[Pp]': ['P', 'p', '|>'],
            r'[Qq]': ['Q', 'q', '0,'],
            r'[Rr]': ['R', 'r', '|2'],
            r'[Ss]': ['S', 's', '5', '$'],
            r'[Tt]': ['T', 't', '7', '+'],
            r'[Uu]': ['U', 'u', '[_]'],
            r'[Vv]': ['V', 'v'],
            r'[Ww]': ['W', 'w', 'vv', 'uu'],
            r'[Xx]': ['X', 'x', '}-{'],
            r'[Yy]': ['Y', 'y', '`/'],
            r'[Zz]': ['Z', 'z', '2']
        }
else:
    CHARACTERS = {
            r'[Aa]': ['A', 'a', '4', '@'],
            r'[Bb]': ['B', 'b', '3'],
            r'[Cc]': ['C', 'c'],
            r'[Dd]': ['D', 'd'],
            r'[Ee]': ['E', 'e', '3'],
            r'[Ff]': ['F', 'f'],
            r'[Gg]': ['G', 'g', '6'],
            r'[Hh]': ['H', 'h'],
            r'[Ii]': ['I', 'i', '1'],
            r'[Jj]': ['J', 'j'],
            r'[Kk]': ['K', 'k'],
            r'[Ll]': ['L', 'l', '1'],
            r'[Mm]': ['M', 'm'],
            r'[Nn]': ['N', 'n'],
            r'[Oo]': ['O', 'o', '0'],
            r'[Pp]': ['P', 'p'],
            r'[Qq]': ['Q', 'q'],
            r'[Rr]': ['R', 'r'],
            r'[Ss]': ['S', 's', '5', '$'],
            r'[Tt]': ['T', 't'],
            r'[Uu]': ['U', 'u'],
            r'[Vv]': ['V', 'v'],
            r'[Ww]': ['W', 'w'],
            r'[Xx]': ['X', 'x'],
            r'[Yy]': ['Y', 'y'],
            r'[Zz]': ['Z', 'z', '2']
        }


for help in ['help', '-help', '--help', '-h']:
    if help in sys.argv:
        show_help()

password_list = []

# If only 1 argument that doesn't match options, use argument as password:
if len(sys.argv) <= 1:
    try:
        passwords = [x for x in sys.stdin.readlines()]
        for password in passwords:
            password_list.append(password.strip())
    except:
        show_help()
elif len(sys.argv) == 2:
    flag = None
    for opt in ['-p', '--password', '-i', '--input', '-f', '--file', '-c', '--limit-special', '--limit-chars', '-n', '--limit-numbers', '-l', '--limit', '--leet']:
            if opt in sys.argv:
                flag = True
    if not flag:
        password_list.append(sys.argv[1].strip())
    else:
        try:
            passwords = [x for x in sys.stdin.readlines()]
            for password in passwords:
                password_list.append(password.strip())
        except:
            show_help()
elif len(sys.argv) >= 3:
    # Check for -p|--password argument:
    for param in ['-p', '--password']:
        if param == sys.argv[1]:
            password_list.append(sys.argv[2].strip())

    # Check for file input:
    file = None
    for param in ['-i', '-f', '--file']:
        if param == sys.argv[1]:
            password_file = sys.argv[2]
            file = True
    if file:
        try:
            with open(password_file, 'r') as fp:
                for line in fp:
                    password_list.append(line.strip())
        except:
            show_help()
else:
    try:
        passwords = [x for x in sys.stdin.readlines()]
        for password in passwords:
            password_list.append(password.strip())
    except:
        show_help()

# Character limits:
flag = None
special_characters = '!@#$%^&*+-=_.;~()[]'
for opt in ['-l', '-c', '--limit-special', '--limit-chars', '--limit']:
    for arg in sys.argv:
        if opt == arg:
            flag = True
if flag:
    special_characters='!@#$%*-+_'

passwords = set(password_list)

subs = []
number_suffixes = []
combos = []

for password in passwords:
    resubs(password)

    # switch to upper
    up = password.upper()
    resubs(up)
    for ch, _ in enumerate(up):
        before = up[:ch]
        char = up[ch]
        after = up[ch+1:]
        uchar = up[ch].replace(char, char.lower())
        subs.append(before + uchar + after)
        subs.append(before.upper() + uchar + after.upper())
        subs.append(before.lower() + uchar + after.lower())
        subs.append(before.upper() + uchar + after.lower())
        subs.append(before.lower() + uchar + after.upper())
        resubs(before + uchar + after)
        resubs(before.upper() + uchar + after.upper())
        resubs(before.lower() + uchar + after.lower())
        resubs(before.upper() + uchar + after.lower())
        resubs(before.lower() + uchar + after.upper())
        get_subs(ch, uchar)

    # switch to lower
    lp = password.lower()
    resubs(lp)
    for ch, _ in enumerate(lp):
        before = lp[:ch]
        char = lp[ch]
        after = lp[ch+1:]
        lchar = lp[ch].replace(char, char.upper())
        subs.append(before + lchar + after)
        subs.append(before.upper() + lchar + after.upper())
        subs.append(before.lower() + lchar + after.lower())
        subs.append(before.upper() + lchar + after.lower())
        subs.append(before.lower() + lchar + after.upper())
        resubs(before + lchar + after)
        resubs(before.upper() + lchar + after.upper())
        resubs(before.lower() + lchar + after.lower())
        resubs(before.upper() + lchar + after.lower())
        resubs(before.lower() + lchar + after.upper())
        get_subs(ch, lchar)

    unique_subs = set(subs)

    numbers = '0123456789'
    for sub in unique_subs:
        combos.append(sub)

    # See if limit is set for numbers:
    limit = None
    for opt in ['-n', '--limit-numbers', '-l', '--limit']:
        for arg in sys.argv:
            if opt == arg:
                limit = True

    # Append single digit numbers and single digit repeating numbers
    for sub in unique_subs:
        for num in numbers:
            combos.append(sub + num)
            if limit:
                combos.append(sub + num + num)

    # Append special character, single digit + char, repeating digit + char
    for sub in unique_subs:
        for c in special_characters:
            combos.append(sub + c)
            for num in numbers:
                combos.append(sub + num + c)
                if not limit:
                    combos.append(sub + num + num + c)

    if limit:
        # Create 3 digit incrementing suffixes:
        for ch, _ in enumerate(numbers):
            if 9 > ch >= 0:
                number_suffixes.append(numbers[ch-1:ch+2])
        number_suffixes.remove('')

        # Append 3 digit incrementing suffixes and special characters
        for sub in unique_subs:
            for suf in number_suffixes:
                combos.append(sub + suf)
                for c in special_characters:
                    combos.append(sub + suf + c)

    else:
        two_digit_suffixes = ["{0:02}".format(i) for i in range(100)]
        three_digit_suffixes = ["{0:03}".format(i) for i in range(1000)]

        # Append all 2 digit suffix combos and + special char
        for sub in unique_subs:
            for suf2 in two_digit_suffixes:
                combos.append(sub + suf2)
                for c in special_characters:
                    combos.append(sub + suf2 + c)

        # Append all 3 digit suffix combos and + special char
        for sub in unique_subs:
            for suf3 in three_digit_suffixes:
                combos.append(sub + suf3)
                for c in special_characters:
                    combos.append(sub + suf3 + c)

unique_combos = list(set(combos))
for password in unique_combos:
    print(password)

Step 2 – Install Cython and create setup.py

I always opt for a virtual environment to keep ’em separated, as ye olde Offspring would suggest, but that’s outside the scope of this tutorial. If you have the virtualenv module installed already, just kick off python3 -m virtualenv --clear -p python3 venv && source venv/bin/activate.

Next we’re going to install Cython via pip. If you don’t have pip installed either, then who are you? That’s also outside the scope of this tutorial. Everybody needs pip, specifically pip3 in this case, or just pip if you’re using virtualenv under python3, in which case pip will default to pip3:

pip3 install cython
vim setup.py

Contents of setup.py:

#!/usr/bin/env python3
from setuptools import setup
from Cython.Build import cythonize

setup(
    ext_modules=cythonize('brutalist.py')
)

Step 3 – Create a main.py to call the brutalist module, and build the brutalist module using Cython

You could just as easily have renamed brutalist.py to module.py and have setup.py reference module.py, and then have a newly-created brutalist.py execute an import module statement, but we are going to be executing main.py instead, because why not.

vi main.py

Contents of main.py:

#!/usr/bin/env python3
import brutalist

if __name__ == '__main__':
    brutalist

Compile the brutalist module that will be imported by main.py:

python setup.py build_ext --inplace

Now you can run main.py in any way that you would ordinarily run brutalist.py from the documentation in the README. I’ll do a quick comparison using a list of the following words in passwords.txt:

administrator
tomcat
admin
password
calvin

Results are shown below:

$ ./brutalist.py -p administrator --leet
(average) 242.07

$ ./main.py -p administrator --leet
(average) 247.45

$ ./brutalist.py --limit < passwords.txt
(average) 2.24

$ ./main.py --limit < passwords.txt
(average) 2.02

$ ./brutalist.py --leet < passwords.txt
(average) 806.18

$ ./main.py --leet < passwords.txt
(average) 790.797

python avg: 350.16
cython avg: 346.76 (1% faster)

The gains can be minimal, and under certain circumstances, the Cython version can actually take even slightly longer to run, depending on the options you use. Cython is much more useful when using math-intense operations and with modules such as numpy. That being said, when you throw a large dictionary at this guy, Cython has its perks. I have run numerous benchmarks against both implementations, and Cython proved to be anywhere from 2%-50% faster in execution time when using lists of multiple words.

I also tried PyPy which is an entirely different interpreter that uses a JIT compiler, but had mixed results. I will do some further benchmarking, and if I find that PyPy functions better as a whole, then I might consider implementing that as a dependency in the brutalist.rb homebrew formula. However, as far as brutalist is concerned on the whole, it can work just fine using standard Python, and there’s no need to complicate things just to shave a few seconds off.

I hope this tutorial helped to provide a little insight into how cythonizationification can help optimize your Python programs — as long as they are fit to be optimized. There are much better resources out there to help you dig deep into Python optimization via C, so get to Googling!

Leave a Reply