EP-0142: Performance & Efficiency Optimizations¶

Abstract¶

The Grand Council Assessment (Shannon) identified concrete performance bottlenecks across 6 modules. This proposal specifies targeted optimizations that preserve functional purity while reducing unnecessary allocations, redundant computations, and bytecode overhead.

Motivation¶

Pure Python sparse operations are inherently slower than C-extension alternatives. Every avoidable overhead — dynamic attribute lookups in inner loops, redundant dictionary copies, uncached module imports, and dense conversions of sparse data — compounds into significant performance degradation. These optimizations maintain the library's zero-dependency, pure-functional character.

Specification¶

1. Hot-Path Local Variable Binding (algebrax.matrix.core)¶

Bind semiring.add and semiring.mul to local variables before inner loops in dot(), mat_vec(), vec_mat(), and inner():

def dot(m1, m2, semiring=None):
    sr = semiring or StandardSemiring()
    _add, _mul, _zero = sr.add, sr.mul, sr.zero  # Local binding
    # ... use _add, _mul, _zero in inner loops

Expected improvement: 15–25% bytecode execution speedup in hot multiplication loops.

2. Semiring Catalog Caching (algebrax.semiring._base)¶

from functools import cache

class Semiring(Protocol[V]):
    @staticmethod
    @cache
    def catalog() -> dict[str, type['Semiring']]:
        ...

Currently re-imports all 24 semiring modules on every call. Caching eliminates repeated import overhead.

3. DFT Twiddle-Factor Precomputation (algebrax.transforms)¶

Pre-extract signal.items() / spectrum.items() in dft() and idft() loops:

def dft(signal, n=None):
    ...
    coef = -2j * cmath.pi / n
    items = list(signal.items())
    for k in range(n):
        val = sum(x_m * cmath.exp(coef * k * m) for m, x_m in items)
        ...

4. Einsum Backtracking (algebrax.tensor)¶

Replace dict(current_assignment) copy at every recursive step with in-place mutation and backtracking:

# Track assigned keys, delete on backtrack instead of copying entire dict
assigned_here = []
for char, k_elem in zip(sub_pattern, key_tuple):
    if char not in current_assignment:
        current_assignment[char] = k_elem
        assigned_here.append(char)
# ... recurse ...
for char in assigned_here:
    del current_assignment[char]  # Backtrack

Expected improvement: \(O(1)\) memory per recursion step vs. \(O(|\text{assignment}|)\) dict copy.

5. Trie Iterator Optimization (algebrax.trie)¶

Replace list concatenation [*path, k] with tuple expansion (*path, k) in __iter__():

def __iter__(self):
    stack = [(self._data, ())]
    while stack:
        node, path = stack.pop()
        if self._value_key in node:
            yield path
        for k, v in node.items():
            if k != self._value_key:
                stack.append((v, (*path, k)))

6. Matrix transpose() Single-Pass Construction¶

Build result dict directly without intermediate defaultdict → final comprehension copy:

def transpose(matrix):
    result: dict = {}
    for r, row in matrix.items():
        for c, val in row.items():
            if c not in result:
                result[c] = {r: val}
            else:
                result[c][r] = val
    return result

Falsifiable Invariants¶

• All existing tests pass with identical outputs (289/289).
• Semiring.catalog() returns identical result on first and subsequent calls.
• dft(idft(x)) ≈ x preserved after twiddle optimization.
• einsum produces identical results with backtracking vs. dict-copy implementation.

Backwards Compatibility¶

Internal optimizations only. No API changes. All functions retain identical signatures and semantics.

Change Log¶

• 2026-08-02: Initial Draft from Grand Council Assessment (Shannon).
• 2026-08-05: Fully implemented all 6 optimizations across matrix.core, semiring._base, transforms, tensor, and trie. Status → Final.