Скорость: векторы, матрицы и немного Rust

Урок 13 курса "Собери своего арбитражного бота". Здесь начинается мир 4: бот уже работает, теперь он должен стать быстрым и готовым к показу. Сегодня вы узнаете, почему сканер замедляется и что с этим делать.

Почему здесь важна скорость

Прочитанная цена ценна лишь мгновение. Урок 11 показал это: другие боты видят тот же разрыв, а медленный сканер приходит к пустому стакану. Сканер, которому нужно две секунды на проверку рынка, проверяет рынок, которого уже нет.

Поэтому вопрос на сегодня простой. Сколько кругов бот может проверять в секунду и как увеличить это число?

Прямой подход: три цикла

Первый сканер, который пишет почти каждый, проверяет каждый круг из трех валют: обменять A на B, B на C, C обратно на A, затем перемножить три курса. Если произведение больше 1, появляются деньги. В коде это три вложенных цикла.

Соберем рынок из 120 валют. Курсы получим из скрытых значений с комиссией 0.2 процента на каждую сделку, поэтому ни одна сделка не прибыльна. Затем добавим одну неверно оцененную пару: при обмене валюты 7 на валюту 40 она дает на 2 процента больше положенного.

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")

Тестовый запуск вывел:

1.0139 (0, 7, 40) 0.55 s

Сканер нашел добавленную ошибку: обменять 0 на 7, 7 на 40, 40 обратно на 0, и 1 единица превращается в 1.0139. Добавка в 2 процента, за вычетом трех комиссий по 0.2 процента, оставляет около 1.4 процента.

На это ушло 0.55 секунды. Для демо это нормально, для рынка это слишком медленно. Число кругов растет как куб числа валют: для 120 валют получается около 1.7 миллиона кругов, для 240 около 13.8 миллиона, то есть в восемь раз больше. При удвоении рынка цикл работает в восемь раз медленнее.

Идея 1: много умножений сразу

Компьютер перемножает два списка из миллиона чисел гораздо быстрее, чем цикл Python обрабатывает их по одной паре. Причина в том, что цикл Python тратит большую часть времени на служебную работу: какой это тип, где следующий элемент. Библиотека вроде numpy передает весь список быстрому скомпилированному коду, который делает служебную работу один раз.

У этого приема есть название: векторизация. Вместо "для каждого элемента сделай это" вы пишете "сделай это со всеми элементами".

Наши курсы образуют таблицу из 120 строк и 120 столбцов. В математике это называется матрицей, а таблица из трех измерений является стопкой таких матриц. Для каждой тройки (i, j, k) нам нужно произведение rate[i][j] * rate[j][k] * rate[k][i]. Создадим три представления одной таблицы, каждое выровнено в своем направлении, и перемножим их:

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")

Как читать первую строку функции. R[:, :, None] является таблицей с добавленным пустым третьим направлением, поэтому она меняется по i и j. R[None, :, :] меняется по j и k. R.T[:, None, :] является транспонированной таблицей, в ней поменяны строки и столбцы, поэтому ее элемент в (i, k) равен R[k][i]. При умножении трех объектов размера 120 на 120 на 1, 1 на 120 на 120 и 120 на 1 на 120 получается куб 120 на 120 на 120, каждая ячейка содержит ровно одно произведение. Следующие строки обнуляют ячейки с повторяющимся индексом, а argmax находит наибольшую ячейку.

Тестовый запуск вывел:

1.0139 (0, 7, 40) 0.009 s

Тот же ответ за 0.009 секунды вместо 0.55: примерно в 60 раз быстрее, всего в трех строках вместо цикла. Проверьте сами: если ответ отличается от версии с циклами, в одной из них есть ошибка.

Цена приема

В кубе N × N × N ячеек, каждая содержит 8-байтовое число. Для 120 валют это 14 MB, все нормально. Для 240 валют это 110 MB, а для 1000 валют это 8 GB, что уже не помещается. Замеры тестового запуска, только умножение:

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

При удвоении размера работа все равно замедляется примерно в 8 до 15 раз, потому что куб продолжает расти как куб N. Векторизация меняет постоянный множитель, но не характер роста. Для большого рынка нужно не только выполнять работу быстрее, но и делать ее меньше. Уроки с 6 по 8 посвящены именно этому: Bellman-Ford и родственные алгоритмы пропускают большую часть кругов. На практике сочетают оба подхода: умный алгоритм, который проверяет мало кругов, и быстрый код, который быстро проверяет каждый из них.

Идея 2: компилируемый язык

Rust превращает программу в машинный код до запуска, и его циклы почти ничего не стоят на каждом шаге. Поэтому можно снова взять простейший код с тремя циклами и не хранить куб в памяти. Сохраните курсы из Python в текстовый файл, по одной строке на ряд:

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

Затем программа на Rust:

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());
}

Соберите и запустите ее командой rustc -O best.rs -o best && ./best. Флаг -O включает оптимизатор, без него программа намного медленнее. Тестовый запуск вывел:

rust 1.0139 (0, 7, 40) 0.005 s

0.005 секунды: примерно в 110 раз быстрее циклов Python, немного быстрее numpy и без большого куба в памяти. В программе те же три цикла, что и в первой версии на Python. Изменился только язык.

Сравним три результата:

Что выбрать для бота

• Делайте прототип на Python, с понятным и правильным алгоритмом. Пока ничего не оптимизируйте.
• Измеряйте. Найдите таймером самую медленную часть, как в этом уроке. Предположение о медленном месте оказывается неверным чаще, чем кажется.
• Если медленная часть является большим циклом по числам, сначала попробуйте numpy. Для этого нужно всего несколько строк.
• Если бот должен реагировать за миллисекунды или numpy не хватает памяти, перенесите одну функцию в Rust и вызовите ее из Python либо напишите горячий путь на Rust. Остальная часть бота, конфигурация, логирование, бумажная торговля, может остаться на Python.
• Более быстрый цикл никогда не заменяет более хороший алгоритм. Проверка 14 миллионов кругов, ускоренная в 100 раз, все равно проигрывает алгоритму, который проверяет 1000.

Попросите ИИ-агента написать и проверить код

Расплывчатый запрос:

Сделай мой сканер быстрым.

Запрос с числами для сверки:

Напиши fast.py. Собери рынок по коду урока 13, seed 5, 120 валют, комиссия 0.2 процента, rate[7][40] умножается на 1.02. Реализуй best_loops и best_numpy и выведи каждый результат и время. Обе функции должны вернуть множитель 1.0139 для круга (0, 7, 40); если результаты отличаются, сообщи об этом и исправь ошибку. Затем напиши best.rs, который читает курсы из rates.csv и находит тот же круг тремя циклами, собери его с rustc -O и выведи время. Не меняй числа рынка.

Проверьте, что все три ответа совпадают, до того как смотреть на скорость. Быстрый неверный ответ бесполезен.

Ваше упражнение

1. Запустите код Python и убедитесь, что обе версии выводят 1.0139 и круг (0, 7, 40). Запишите свои замеры времени.
2. Измените N на 60, затем на 200. Как меняется время версии с циклами? Сравните с утверждением, что оно растет как куб N: 200 / 120 в кубе составляет около 4.6.
3. Добавьте вторую ошибку, rate[50][90] *= 1.03, и измените функцию так, чтобы она возвращала три лучших круга, а не только лучший. Подсказка: отсортируйте куб через np.argsort или храните список в цикле.
4. Запустите версию на Rust с rustc без -O, затем с ним. Насколько оптимизатор меняет время?

Что дальше

Теперь вы знаете, куда уходит время и как его вернуть. Урок 14 добавит вторую стратегию: фьючерсы против спота с финансированием, где бот зарабатывает на небольшой разнице, которая повторяется каждые несколько часов, а не на разрыве, который закрывается за секунды.