Speed: Vectors, Matrices and a Little Rust

Lesson 13 of the course "Build your own arbitrage bot". World 4 starts here: the bot works, now it has to be fast and ready to show. Today you learn why a scanner gets slow and what to do about it.

Why speed matters here

A price you read is only worth something for a moment. Lesson 11 showed it: other bots see the same gap, and the slower scanner arrives to an empty book. A scanner that needs two seconds to check the market is checking a market that no longer exists.

So the question for today is simple. How many circles can the bot check per second, and how do you make that number bigger?

The head-on way: three loops

The first scanner anyone writes checks every circle of three currencies: change A into B, B into C, C back into A, and multiply the three rates. If the product is above 1, money appears. In code that is three nested loops.

Build a market of 120 currencies. Rates come from hidden values with a 0.2 percent fee on every trade, so nothing is profitable. Then plant one mispriced pair: currency 7 pays 2 percent more than it should when you change it into currency 40.

import random, time
import numpy as np

random.seed(5)
N = 120
value = [random.uniform(1, 100) for _ in range(N)]
# rate[i][j] = how much of j you get for 1 of i, with a 0.2% fee on every trade
rate = [[value[i] / value[j] * 0.998 if i != j else 1.0 for j in range(N)] for i in range(N)]
rate[7][40] *= 1.02          # the planted mistake

def best_loops():
    best, arg = 0.0, None
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if i == j or j == k or k == i:
                    continue
                m = rate[i][j] * rate[j][k] * rate[k][i]
                if m > best:
                    best, arg = m, (i, j, k)
    return best, arg

t = time.perf_counter(); b = best_loops(); print(round(b[0], 4), b[1], round(time.perf_counter() - t, 2), "s")

A test run printed:

1.0139 (0, 7, 40) 0.55 s

The scanner found the planted mistake: change 0 into 7, 7 into 40, 40 back into 0, and 1 unit becomes 1.0139. The 2 percent plant, minus three fees of 0.2 percent, leaves about 1.4 percent.

It took 0.55 seconds. That is fine for a demo and far too slow for a market. The number of circles grows with the cube of the number of currencies: 120 currencies give about 1.7 million circles, 240 give about 13.8 million, which is eight times more. Doubling the market makes the loop eight times slower.

Idea 1: do many multiplications at once

A computer multiplies two lists of a million numbers much faster than a Python loop does it one pair at a time. The reason: a Python loop spends most of its time on bookkeeping (what type is this, where is the next item). A library such as numpy hands the whole list to fast compiled code that does the bookkeeping once.

The trick has a name: vectorization. You stop writing "for each item, do this" and write "do this to all items".

Our rates are a table with 120 rows and 120 columns. In math it is called a matrix, and a table of three dimensions is a stack of such matrices. The product we need for every triple (i, j, k) is rate[i][j] * rate[j][k] * rate[k][i]. Build three views of the same table, each lined up along a different direction, and multiply them:

def best_numpy():
    R = np.array(rate)
    # m[i, j, k] = R[i, j] * R[j, k] * R[k, i], all at once
    m = R[:, :, None] * R[None, :, :] * R.T[:, None, :]
    idx = np.arange(N)
    m[idx, idx, :] = 0; m[idx, :, idx] = 0; m[:, idx, idx] = 0   # drop triples with a repeat
    flat = int(m.argmax())
    return float(m.flat[flat]), np.unravel_index(flat, m.shape)

t = time.perf_counter(); b = best_numpy(); print(round(b[0], 4), tuple(int(x) for x in b[1]), round(time.perf_counter() - t, 3), "s")

How to read the first line of the function. R[:, :, None] is the table with an empty third direction added, so it varies along i and j. R[None, :, :] varies along j and k. R.T[:, None, :] is the transposed table (rows and columns swapped), so its entry at (i, k) is R[k][i]. Multiplying three things of shape 120 by 120 by 1, 1 by 120 by 120, and 120 by 1 by 120 gives a cube of 120 by 120 by 120, and each cell holds exactly one product. The next lines zero out the cells where an index repeats, and argmax finds the biggest cell.

The test run printed:

1.0139 (0, 7, 40) 0.009 s

The same answer in 0.009 seconds instead of 0.55: about 60 times faster, with three lines instead of a loop. Check it yourself: if the answer differs from the loop version, one of them has a bug.

The price of the trick

The cube has N × N × N cells and each is an 8-byte number. For 120 currencies that is 14 MB, fine. For 240 currencies it is 110 MB, and for 1000 currencies 8 GB, which does not fit. Timings from a test run, only the multiplication:

60 numpy 0.001 s
120 numpy 0.007 s
240 numpy 0.105 s

Doubling the size still makes it about 8 to 15 times slower, because the cube still grows with the cube of N. Vectorization changes the constant, not the shape of the growth. For a big market you need less work, not only faster work. Lessons 6 to 8 are that: Bellman-Ford and its relatives skip most circles. In practice you combine both: a clever algorithm that checks few circles, and fast code that checks each one quickly.

Idea 2: a language that compiles

Rust turns your program into machine code before it runs, and its loops cost almost nothing per step. That brings back the simplest code, three loops, and removes the cube in memory. Save the rates to a text file from Python, one row per line:

open("rates.csv", "w").write("\n".join(",".join(repr(x) for x in row) for row in rate))

Then the Rust program:

use std::fs;
use std::time::Instant;

fn main() {
    let text = fs::read_to_string("rates.csv").expect("rates.csv");
    let rate: Vec<Vec<f64>> = text
        .lines()
        .map(|l| l.split(',').map(|x| x.parse().unwrap()).collect())
        .collect();
    let n = rate.len();
    let start = Instant::now();
    let (mut best, mut arg) = (0.0_f64, (0, 0, 0));
    for i in 0..n {
        for j in 0..n {
            if j == i { continue; }
            for k in 0..n {
                if k == i || k == j { continue; }
                let m = rate[i][j] * rate[j][k] * rate[k][i];
                if m > best { best = m; arg = (i, j, k); }
            }
        }
    }
    println!("rust {:.4} {:?} {:.3} s", best, arg, start.elapsed().as_secs_f64());
}

Build and run it with rustc -O best.rs -o best && ./best. The flag -O turns on the optimizer, and without it the program is much slower. The test run printed:

rust 1.0139 (0, 7, 40) 0.005 s

0.005 seconds: about 110 times faster than the Python loops, a bit faster than numpy, and with no big cube in memory. The program has the same three loops as the first Python version. Only the language changed.

Put the three results side by side:

What to choose for your bot

• Prototype in Python, with the algorithm clear and correct. Do not optimize yet.
• Measure. Find the slowest part with a timer, like the ones in this lesson. A guess about the slow part is wrong more often than you expect.
• If the slow part is a big loop over numbers, try numpy first. It costs a few lines.
• If the bot must react in milliseconds, or numpy runs out of memory, move that one function to Rust and call it from Python, or write the hot path in Rust. The rest of the bot (config, logging, paper trading) can stay in Python.
• A faster loop never replaces a better algorithm. A 100 times faster check of 14 million circles still loses to an algorithm that checks 1000.

Let an AI agent write and test it

A vague request:

Make my scanner fast.

A request with the numbers to match:

Write fast.py. Build the market from the lesson 13 code (seed 5, 120 currencies, 0.2 percent fee, rate[7][40] multiplied by 1.02). Implement best_loops and best_numpy and print each result and the time. Both must return the multiplier 1.0139 for circle (0, 7, 40); if they differ, say so and fix the bug. Then write best.rs that reads the rates from rates.csv and finds the same circle with three loops, build it with rustc -O, and print the time. Do not change the numbers of the market.

Check that all three answers agree before you look at the speed. A fast wrong answer is useless.

Your exercise

1. Run the Python code and make sure both versions print 1.0139 and the circle (0, 7, 40). Write down your timings.
2. Change N to 60 and then to 200. How does the time of the loop version change? Compare with the claim that it grows with N cubed (200 / 120 cubed is about 4.6).
3. Plant a second mistake, rate[50][90] *= 1.03, and change the function so that it returns the best three circles, not only the best one. (Hint: sort the cube with np.argsort or keep a list in the loop.)
4. Run the Rust version with rustc without -O and then with it. By how much does the optimizer change the time?

What comes next

You know now where the time goes and how to get it back. Lesson 14 adds a second strategy, futures against spot with funding, where the bot earns from a small difference that repeats every few hours instead of from a gap that closes in seconds.