Making Python programs fast

Kovid Goyal

The need for speed

• Single core performance flatlined
• Performance == energy saving == battery life
• Users love performant software
• I feel the need, the need for speed

Is it even possible?

• Python is slow (100x slowdown)
• No heroes to save us
• Nonetheless, it is possible

Terminal	Language	MB/s
Konsole	C++	27
Alacritty	Rust	54
GNOME Terminal	C++	62
kitty	Python + C	135

A little bit about kitty

• A terminal emulator
• Make terminals a powerful platform
• Uses Python for its UI and control
• Uses C and GPU for performance

Case study: base64

• Encode binary data as text
• 3 input bytes → 4 letters

        │Enc│  │ode│      │d  │
        └─┬─┘  └─┬─┘  …   └─┬─┘
          │      │          │
          ↓      ↓          ↓
         RW5j   b2Rl  …    ZA==
        

• Used widely in communication, escape codes in kitty

base64: A baseline

Add some street smarts

Intermezzo: memoryview

Parallelism to the rescue?

Python + C

from base64 import standard_b64encode

Intermezzo: SIMD

• Single Instruction Multiple Data
• Upto 64 bytes at a time
• base64 encoding: 3 byte chunks
• aklomp/base64

    void base64_encode(
        const char *src, size_t srclen, char *out, size_t *outlen
    )

Python C API

Where strong men fear to tread

Rate: 21.5 GB/s 20x native!!

Needed boilerplate

Streaming base64 encoding

HTML 5 Parsing

• The WHATWG HTML 5 spec is some 1500 pages
• html5lib is awesome!
• It parses the HTML 5 spec at ~1.1 MB/s
• How much better can we do?
• Not like base64, need object representation

An efficient object representation

• The lxml package
• The Gumbo C HTML 5 parser
• A simple translation: kovidgoyal/html5-parser
• Under 1000 lines of C code
• Rate: 28.1 MB/s ~28x

Premature optimization…

• … is the root of all evil
• Use the cProfile module

• Code that is in the hot path
• Code that has a nice data boundary

An example of profiling

• Users reported opening certain e-books in calibre was very slow
• Run function to preprocess book in profiler

Do less work and do it in C++

• Just need to transform a few properties
• Basic parsing is easy
• ~1200 lines of C++

Convert those entities in C

• HTML entities: & name | number ;
• Use SIMD to find &
• Use perfect hashing (gperf)
• ~200 lines of C

A short tour of SIMD

• Vector of input values → Vector of output values
• No control flow
  • Masks
  • Shifts and broadcasts
  • Boolean operators
  • Arithmetic operators
  • Counting bits
• Originally conceived for maths

Example: Let’s find Mr. X

│s│o│m│e│t│e│x│t│ … in SIMD register A
└─┴─┴─┴─┴─┴─┴─┴─┘

│x│x│x│x│x│x│x│x│ … in SIMD register B
└─┴─┴─┴─┴─┴─┴─┴─┘
C = A cmpeq B

│0│0│0│0│0│0│255│0│ … in SIMD register C
└─┴─┴─┴─┴─┴─┴───┴─┘
Number of leading zeroes is the answer

│X│X│X│X│X│X│X│X│ … in SIMD register D
└─┴─┴─┴─┴─┴─┴─┴─┘
C = A cmpeq B | A cmpeq D

A bird’s eye view of base64

• Recall: 3 bytes become 4

    3 * 8 == 24 == 4 * 6 bits
    2 ^ 6 == 64 (aka base64)
  

• SIMD: Multiple groups: 12 → 16

    [AAAB | BBCC | CDDD | 0000] → [0AAA | 0BBB | 0CCC | 0DDD ]
    Focus on a single word: 0AAA
    Spread out its 24 bits into four groups of 6
    0AAA = [ 00000000 | aaaaaa | bbbbbb | cccccc | dddddd ]
    0AAA = [ 00aaaaaa | 00bbbbbb | 00cccccc | 00dddddd ]
  

• Done in parallel on 16, 32 or 64 bytes at a time

Branchless base64 lookup

Branchless lookup pseudo code

Key takeaways

Python programs can be very fast

• Profile and identify
• Look for pure Python opportunities
• Eliminate extra copies
• Use memoryview for binary data

Don’t be afraid of C