Codon: key to speedup Python

30 Jul, 2024

Introduction

The title may seem absurd at first glance. Combining "speed" and "Python" in the same sentence appears to be an oxymoron. One might wonder if the author has gone mad! This skepticism is particularly understandable in light of the recent research paper, "Energy Efficiency across Programming Languages", which has gained significant attention recently.

The Study and Its Findings

The study evaluated the performance of 27 programming languages, ranging from low-level languages (C/C++, Rust) to high-level languages (Python, JavaScript, etc.), using various methods and algorithms. The researchers used the purest form of each programming language for the tests, meaning that, for example, Python's tests were conducted using only Python, without leveraging libraries written in other languages. (Many Python libraries are, in fact, written in highly performant languages such as C/C++ or Rust.)

The Limitations of "Pure Python"

This research sparked numerous YouTube videos discussing Python's slow performance, which was one of the study's key findings. However, one question kept bothering me: who uses "pure Python," and why? Python's strength lies in its vast library ecosystem, and many of these libraries are written in low-level languages. For instance:

NumPy is written in C and Fortran

SciPy is written in C, C++, and Fortran

Pandas is written in C and Cython

Scikit-learn is written in C, C++, and Cython

Polars, Rye, Ruff, UV, Granian: all written in Rust.

Speeding Up Python

These are just from the libraries I know / have used, there are plenty others that is not mentioned here. This is also what makes Python an excellent "glue" language, allowing it to combine libraries from other programming languages to optimize performance.

In addition to leveraging these libraries, there are other methods to speed up Python, such as using Cython or Codon to compile Python programs. Cython uses C syntax, which limits its use to those familiar with C. Codon, on the other hand, is a C++ based Python compiler that uses Python syntax and requires only the addition of type hints.

Enough talking, let's dive into code!

Code Example: Binary Search

Below is a Binary Search program written in Python.

Section 1: Defining the Binary Search Function

import random
import time


def binary_search(array: list[int], x: int, low: int, high: int) -> int:
    while low <= high:
        mid: int = low + (high - low) // 2
        if array[mid] == x:
            return mid
        elif array[mid] < x:
            low = mid + 1
        else:
            high = mid - 1

    return -1

Section 2: Defining the Partition Function for Quicksort

This function is used in the Quicksort algorithm to partition the array around a pivot element. It takes three parameters: the array, and the low and high indices of the partition range. The function returns the index of the pivot element after partitioning.

def partition(arr: list[int], low: int, high: int) -> int:
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

Section 3: Defining the Quicksort Function

This function implements the Quicksort algorithm to sort an array in ascending order. It takes three parameters: the array, and the low and high indices of the sort range. The function returns the sorted array.

def quicksort(arr: list[int], low: int, high: int) -> list[int]:
    if low < high:
        pi: int = partition(arr, low, high)
        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)

    return arr

Section 4:

This function is the entry point of the program. It generates an unordered array of random integers, sorts the array using Quicksort, and then performs a binary search on the sorted array to find a random element. The function measures the execution time of the program and prints the results.

At the end we call the main function.

def main() -> None:
    element: int = 10_000_000
    loop: int = 10

    start_time: float = time.time()

    for i in range(loop):

        # Create an unordered array
        unordered = [random.randint(1, element) for _ in range(element)]

        print("Unordered array:")
        print(unordered[-50:])
        
        rand_index: int = random.randint(0, element)
        rand_elem: int = unordered[rand_index]
        print(f"\nrandom element: {rand_elem}")

        ordered: list[int] = (quicksort(unordered, 0, element - 1))
        result: int = binary_search(ordered, rand_elem, 0, element - 1)

    end_time: float = time.time()
    duration: float = (end_time - start_time) * 1000  # milliseconds

    print("\nOrdered array in Ascending Order:")
    print(f"{ordered[-50:]}")

    if result == -1:
        print("Not found")
    else:
        print(f"Element is found at index: {result}")

    print("\nBinary search using Quicksort in Python:")
    print(f"Number of elements: {element}")
    print(f"Average time taken for {loop} \
    loops: {(duration/loop)} milliseconds")

main()

You can run it using Python as usual:

python binary_search.py

or use Codon:

codon run -release binary_search.py

Results

As expected, the Python implementation is quite slow, taking 29 seconds to execute. However, the PyCodon version is remarkably faster, completing in just 1 second. Yes, you heard that right – by adding type hints and using the same syntax, we achieved a nearly 27x speedup. I also implemented the Binary Search program in other languages:

Conclusion

As you can see, PyCodon's performance is very close to C's performance, making it an extremely efficient way to speed up Python. I hope this post has enlightened you, the reader: while pure Python may be slow, speeding it up is relatively easy, as demonstrated in this post.

Note: I have spent a significant amount of time optimizing my Python apps for speed and have found that, while tools like Numba exist (which can be even easier to use, requiring only the addition of a decorator), they have limitations. Therefore, I often rely on Cython and now consider Codon to be my go-to tool for speeding up Python.

#c #codon #compiler #high level #low level #programming #python #rust #zig