High Performance Python

The main properties of interest in a computing unit are the number of operations it can do in one cycle and the number of cycles it can do in one second. The first value is measured by its instructions per cycle(IPC), while the latter value is measured by its clock speed.

• SIMD: Single instruction, multiple data. Efficient with high IPC. (CPU vectorization instruction)
• Hyperthreading presents a virtual second CPU to the host OS, and clever hardware logic tries

to interleave two threads of instructions into the execution units on a single CPU. When successful, gains of up to 30% over a single thread can be achieved.

When trying to optimize the memory patterns of a program, we are simply optimizing which data is placed where, how it is laid out (in order to increase the number of sequential reads), and how many times it is moved among the various locations.

• The frontside bus is the connection between the RAM and the L1/L2 cache
• Two main properties of a bus:
  • how much data can be moved in one transfer (bus width)
  • how many transfers the bus can do per second (bus frequency).

• Memory Fragmentation: due to garbage-collected
• Dynamic Types: Using Cython to mitigate this problem
• GIL: Using Cython or foreign functions

• When to use: The task requires mainly linear algebra and matrix manipulations.
  1. Ensure that the memory use of the problem will fit within the GPU.
  2. Evaluate whether the algorithm requires a lot of branching conditions.(GPU's memory is limited)
  3. Evaluate how much data needs to be moved between the GPU and the CPU.
• Drawbacks: Communicates through the PCI bus, which is much slower than the frontside bus

• Disable Turbo Boost in the BIOS.
• Disable the operating system's ability to override the SpeedStep(in BIOS).
• Use only AC power (never battery power).
• Disable background tools like backups and Dropbox while running experiments.
• Run the experiments many times to obtain a stable measurement.
• Possibly drop to run level 1 (Unix) so that no other tasks are running.
• Reboot and rerun the experiments to double-confirm the results.
• Unit testing a complicated section of code that generates a large numerical output may be difficult. Do not be afraid to output a text file of results to run through diff or to use a pickled object.

• lists also store how large they are, so of the six allocated blocks, only five are usable.
• bisect gives easy methods to add elements into a list while maintaining its sorting
• List pre-allocation equation in Python 3.7: M = (N >> 3) + (3 if N < 9 else 6)

Python process will have some extra memory overhead for resource caching. For tuples of sizes 1–20, however, when they are no longer in use, the space isn't immediately given back to the system, which reduced system calls for memory allocation.

In [1]: %timeit l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
62 ns ± 0.714 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

In [2]: %timeit t = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
9.41 ns ± 0.113 ns per loop (mean ± std. dev. of 7 runs, 100000000 loops each)

• should implement __hash__, __eq__, __cmp__
• User-defined classes have default hash and comparison functions using the object's placement in memory.(given by id function)

1. hashing: turn key into an integer number
2. masking: fits the allocated number of buckets
3. Using probing to find a new place if collision happens

# pseudocode of finding index
def index_sequence(key, mask=0b111, PERTURB_SHIFT=5):
    perturb = hash(key)  # hashing
    i = perturb & mask  # masking
    yield i
    # probing
    while True:
        perturb >>= PERTURB_SHIFT  # use high-order bits
        i = (i * 5 + perturb + 1) & mask  # simple linear function and masking again
        yield i

• Optimization: Python first appends the key/value data into a standard array and then stores only the index into this array in the hash table. The array also helps keep the insertion order of items.
• How well distributed the data throughout the hash table is called the load factor and is related to the entropy of the hash function
• By default, the smallest size of a dictionary or set is 8, and it will resize by 3x if the dictionary is more than two-thirds full. (possible sizes: 8->18->39->81->165->…)

Namespace Management heavily uses dictionaries to do its lookups.

The steps to look for a variable/function/module

1. Searching locals(): which has entries for all local variables, and this is the only part of the chain that doesn't require a dictionary lookup
2. Searching globals()
3. Searching __builtin__ objects: __builtin__ is technically a module object

import math


def test1(x):
    """
    >>> %timeit test1(123456)
    94 µs ± 387 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

    18 LOAD_GLOBAL              1 (math)
    20 LOAD_METHOD              2 (sin)
    22 LOAD_FAST                0 (x)
    24 CALL_METHOD              1

    """
    res = 1
    for _ in range(1000):
        res += math.sin(x)
    return res


def test2(x):
    """
    >>> %timeit test2(123456)
    72.5 µs ± 2.66 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

    22 LOAD_FAST                2 (res)
    24 LOAD_FAST                1 (sin)
    26 LOAD_FAST                0 (x)
    28 CALL_FUNCTION            1

    """
    sin = math.sin
    res = 1
    for _ in range(1000):
        res += sin(x)
    return res

1. first, get an iterator through iter(iterable)
2. call iterator.next() to get new values until a StopIteration is raised.

# The Python loop
for i in object:
    do_work(i)

# Is equivalent to
object_iterator = iter(object)
while True:
    try:
        i = next(object_iterator)
    except StopIteration:
        break
    else:
        do_work(i)

• cycle, repeat, chain, groupby, islice
• compress: like boolean-index in pandas
• accumulate: reduce though summation
• takewhile, dropwhile: add a condition that will end a generator.
• starmap: Used instead of map() when argument parameters are already grouped in tuples from a single iterable
• tee(iterable, n): Return n independent iterators from a single iterable. Useful for splitting one generator into n generators.
• zip_longest: zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-
• Combinatoric iterators: product (cartesian product), permutations, combinations

Objects in array are sequentially in memory. Using the array type when creating lists of data that must be iterated on is actually slower than simply creating a list. This is because the array object stores a very low-level representation of the numbers it stores, and this must be converted into a Python-compatible version before being returned to the user. This extra overhead happens every time you index an array type. That implementation decision has made the array object less suitable for math and more suitable for storing fixed-type data more efficiently in memory.

• numpy gives us memory locality and vectorized operations.

One downfall of numpy's optimization of vector operations is that it occurs on only one operation at a time. numexpr can help take an entire vector expression and compile it into very efficient code that is optimized to minimize cache misses and temporary space used. In addition, the expressions can utilize multiple CPU cores(with OpenMP).

• Operations on columns often generate temporary intermediate arrays, which consume RAM.
• Make pandas parallel and scalable with dask module.
• Columns of the same dtype are grouped together by a BlockManager.
• df.apply(..., raw=True) stops the creation of an intermediate Series object, uses raw numpy array instead.
• Install the optional dependencies numexpr and bottleneck for additional performance improvements
• Use bulwark to check the schema of dataframes up front.
• Converting the Series to a Category dtype when dealing with low cardinality data. df["col"].astype("category")

Two main routes:

• reducing the time taken to get data to the CPU.
• reducing the amount of work that the CPU had to do.

# In setup.py
from distutils.core import setup

from Cython.Build import cythonize

setup(ext_modules=cythonize("cythonfn.pyx", compiler_directives={"language_level": "3"}))

When we run python setup.py build_ext --inplace, Cython will look for cythonfn.pyx and build cythonfn[…].so.

• Different GC strategy(mark-and-sweep) than CPython(reference counting)
• PyPy supports projects like numpy that require C bindings through the CPython extension compatibility layer cpyext, but it has an overhead of 4–6×, which generally makes numpy too slow.
• May use more RAM than CPython.

Transonic attempts to unify Cython, Pythran, and Numba, and potentially other compilers, behind one interface to enable quick evaluation of multiple compilers without having to rewrite code.

A NumPy-compatible array library accelerated by CUDA

See http://compilers.pydata.org/