Performance Guide

Best practices for building efficient large-scale optimization models

1 Introduction

Optyx is designed to handle large optimization problems efficiently. However, the way you build expressions can dramatically impact performance. This guide explains the common pitfalls and recommended patterns.

By the end of this tutorial, you’ll understand:

• Why loops create performance problems
• How to use vectorized operations
• When the iterative autodiff engine kicks in
• Power-user utilities for edge cases

---

2 The Problem with Loops

When you build an objective function using a Python loop, you create a deep expression tree:

from optyx import VectorVariable
from optyx.core.autodiff import gradient, _estimate_tree_depth

# Building an expression in a loop
x = VectorVariable("x", 100)
obj = x[0] ** 2
for i in range(1, 100):
    obj = obj + x[i] ** 2

# Check the tree depth
depth = _estimate_tree_depth(obj)
print(f"Expression tree depth: {depth}")

Expression tree depth: 100

This creates a left-skewed binary tree where each + operation nests inside the previous one:

                    (+)              ← depth 99
                   /   \
                (+)    x[99]²
               /   \
            (+)    x[98]²
           /   \
         ...   ...
        /
    x[0]²                           ← depth 0

2.1 Why This Matters

1. Gradient computation must traverse the entire tree
2. Python’s recursion limit (~1000) can be hit for large n
3. Memory usage grows with tree depth

For n=500, the tree depth is ~500. For n=5000, it’s ~5000.

---

3 Automatic Iterative Fallback

Optyx automatically switches to an iterative gradient algorithm when it detects deep expression trees:

# This works fine despite deep tree - automatic switching!
x = VectorVariable("x", 1000)
obj = x[0] ** 2
for i in range(1, 1000):
    obj = obj + x[i] ** 2

# gradient() auto-detects depth >= 400 and uses iterative algorithm
grad = gradient(obj, x[0])
print(f"Gradient computed: {grad}")

Gradient computed: (Constant(2) * Variable('x[0]'))

The threshold is ~400 levels. Below this, the faster recursive algorithm is used. Above it, the iterative algorithm handles arbitrarily deep trees.

---

4 Recommended: Vectorized Operations

While the iterative fallback works, vectorized operations are always faster:

import time

x = VectorVariable("x", 1000)

# ❌ Loop-built expression (works but slower)
start = time.perf_counter()
obj_loop = x[0] ** 2
for i in range(1, 1000):
    obj_loop = obj_loop + x[i] ** 2
loop_time = time.perf_counter() - start

# ✅ Vectorized expression (fast, flat tree)
start = time.perf_counter()
obj_vec = x.dot(x)  # Same result: sum of squares
vec_time = time.perf_counter() - start

print(f"Loop construction: {loop_time*1000:.2f} ms")
print(f"Vector construction: {vec_time*1000:.2f} ms")
print(f"Speedup: {loop_time/vec_time:.1f}x")

Loop construction: 2.21 ms
Vector construction: 0.05 ms
Speedup: 42.0x

4.1 Equivalence Table

Loop Pattern	Vectorized Equivalent
sum(x[i] for i in range(n))	x.sum()
sum(x[i]**2 for i in range(n))	x.dot(x)
sum(c[i]*x[i] for i in range(n))	c @ x (where c is ndarray)
sum((x[i] - y[i])**2 ...)	(x - y).dot(x - y)

4.2 Matrix Operations

import numpy as np
from optyx import VectorVariable

n = 50
Q = np.eye(n)  # Example matrix

x = VectorVariable("x", n)

# ❌ SLOW: Double loop creates O(n²) depth tree
# obj = 0
# for i in range(n):
#     for j in range(n):
#         obj = obj + Q[i,j] * x[i] * x[j]

# ✅ FAST: Math-like quadratic form with O(1) gradient
obj = x.dot(Q @ x)  # Automatically creates QuadraticForm
print(f"Quadratic form type: {type(obj).__name__}")  # QuadraticForm

Quadratic form type: QuadraticForm

TipAutomatic Optimization

x.dot(Q @ x) is automatically recognized as a quadratic form pattern and creates a QuadraticForm expression with an O(1) gradient rule: ∇(xᵀQx) = (Q + Qᵀ)x.

---

5 Depth Estimation

You can check expression depth before computing gradients:

from optyx.core.autodiff import _estimate_tree_depth

x = VectorVariable("x", 500)

# Left-skewed tree (common from loops)
left_tree = x[0]
for i in range(1, 500):
    left_tree = left_tree + x[i]

# Check depth with default left-spine heuristic (fast)
depth_fast = _estimate_tree_depth(left_tree)
print(f"Left-spine estimate: {depth_fast}")

# Full traversal for exact depth (slower but accurate for any tree shape)
depth_exact = _estimate_tree_depth(left_tree, full_traversal=True)
print(f"Full traversal: {depth_exact}")

Left-spine estimate: 499
Full traversal: 499

The left-spine heuristic is O(depth) and accurate for left-skewed trees (the common case). Use full_traversal=True when you need exact depth for right-skewed or balanced trees.

---

6 Power User: Recursion Limit Override

In rare cases, you might want to temporarily increase Python’s recursion limit:

from optyx import increased_recursion_limit

# Context manager restores the original limit when done
with increased_recursion_limit(5000):
    # Code that might need deep recursion
    pass

# Back to normal limit

WarningUse with Caution

Very high limits can cause stack overflow crashes. The automatic iterative algorithm is the preferred solution for deep trees.

---

7 Performance Summary

Approach	Tree Depth	Gradient Time	Recommendation
Loop-built	O(n)	O(n) per variable	Avoid for large n
Vectorized	O(1)	O(1) via native rules	✅ Preferred
Iterative fallback	Any	O(n) total nodes	Automatic for deep trees

7.1 Key Takeaways

1. Use vectorized operations (x.sum(), x.dot(x), c @ x) whenever possible
2. Loops are fine for small n (< 100) but don’t scale
3. Optyx handles deep trees automatically via iterative gradient computation
4. Check depth with _estimate_tree_depth() if you’re unsure

---

8 Next Steps

• Vectors Tutorial: Learn all VectorVariable operations
• Matrices Tutorial: Matrix operations and quadratic forms
• Autodiff Tutorial: How gradients are computed