Чому risp, Lisp із нативною компіляцією, програє CPython на map/fold: алокації, а не кодогенерація

risp — це невеликий Lisp-інтерпретатор лише на std, написаний на Rust — не той туторіал «Risp» 2019 року з тією самою назвою, а проєкт із трьома рушіями виконання (огляд): деревообхідний інтерпретатор, байткодова VM із кешуванням у регістрах і, за --features jit, JIT на Cranelift, який компілює цілочисельні функції прямо в нативний машинний код. Я побудував кожен із цих шарів, щоб наздогнати CPython, і на цілочисельних бенчмарках JIT виграє з ганебним відривом. Тоді я скерував той самий JIT на map і fold, очікував чергового розгрому й програв CPython у 3×. Історія про те, чому я програв, — найкорисніше, чого цей проєкт навчив мене про продуктивність, бо причина не та, яку вгадує майже кожен.

Цілочисельні бенчмарки роблять JIT схожим на надзброю

Коли кожне значення — це i64, який живе в регістрі процесора, JIT не просто ледь випереджає інтерпретатор — він лишає його в іншому часовому поясі. Ось цілочисельні рядки risp проти CPython 3.14:

benchmark              tree-walker     VM      JIT    CPython 3.14
fib(30)                    1670 ms   108 ms    7 ms      62 ms
arith loop 2e6             2382 ms   100 ms    5 ms      93 ms
dispatch 2e6               4841 ms   213 ms    5 ms     211 ms

fib(30) за 7 мілісекунд: приблизно у 9× швидше за CPython, а насичений потоком керування цикл dispatch — це 5 мс на JIT проти 211 мс у CPython, тобто десь у 40×. Це не випадковість одного бенчмарку; це структурна віддача від зведення цілочисельного підмножини до Cranelift IR. Коли ви компілюєте арифметику i64 у регістри, ви обходите будь-який байткодовий інтерпретатор, включно з CPython, бо ви повністю прибрали інтерпретацію.

Тож коли я навчив прелюдію risp — fold, map, filter — виконуватися на VM і JIT, а не лише на деревообхідному інтерпретаторі, прогноз написався сам собою: запусти бенчмарк map/fold під --jit, отримай однозначне число мілісекунд, зроби коло пошани. Цього не сталося.

На списочних рядках JIT не генерує взагалі нічого

Ось списочні рядки вищого порядку з того самого запуску:

benchmark              tree-walker     VM      JIT    CPython 3.14
fold(+) over 2e5            351 ms    33 ms   32 ms      18 ms
map sq + fold 2e5          622 ms    65 ms   65 ms      21 ms
filter + fold 2e5          531 ms    52 ms   52 ms      20 ms

Дві речі впадають в око. По-перше, колонка JIT дорівнює колонці VM. 65 ms і 65 ms; 52 ms і 52 ms. Порівняйте це з цілочисельними рядками, де jit (7 мс) сидить на порядок нижче за vm (108 мс). Цей розрив і є нативний код — його присутність доводить, що Cranelift скомпілював функцію, а його відсутність доводить, що Cranelift подивився на функцію й пішов геть. Для map sq + fold --jit і --vm — це байт-у-байт одна й та сама програма: JIT лишив списочний код байткодом і не згенерував для нього жодної інструкції машинного коду.

По-друге, CPython виграє. 21 мс проти risp-ових 65 мс на map sq + fold — у 3× — саме на тому навантаженні, де JIT risp мав би бути надзброєю. Lisp із нативною компіляцією програє «повільній скриптовій мові» у три рази.

Якщо ви зупинитеся на читанні тут, ви зробите висновок, що JIT зламаний або прелюдія погано написана. Ні те, ні інше неправда, і різниця має значення.

Утримання JIT від компіляції — це коректно, а не баг

JIT risp — це цілочисельний JIT за задумом. Його аналіз придатності ставить одне питання до кожної функції: чи це самодостатня арифметика i64 — if, let, cond, and/or, оператори порівняння й математики та виклики інших функцій точно таких самих? Якщо так, кожне значення живе в регістрі, і Cranelift генерує щільний нативний цикл. Якщо ні, функція лишається на байткодовій VM. Це та сама дисципліна «відмовся, а не вгадуй», яка тримає JIT коректним: один непідтримуваний лист дискваліфікує всю функцію.

map, filter і fold — це категоричне «ні», і ви можете прочитати чому прямо в прелюдії. Ось fold і map, що протягує акумулятор, визначений у самому risp, а не як вбудована функція Rust:

;; Left fold. Tail-recursive, so folding a list is constant frame-stack; any
;; recursion in `f` grows the heap frame-stack, not the Rust stack.
(def fold
  (lambda (f init xs)
    (if (null? xs)
        init
        (fold f (f init (car xs)) (cdr xs)))))

(def map--acc
  (lambda (f xs acc)
    (if (null? xs) (reverse acc) (map--acc f (cdr xs) (cons (f (car xs)) acc)))))
(def map (lambda (f xs) (map--acc f xs '())))

Подивіться, чого торкається цей код. Аргументи — це не i64; це Value, 24-байтовий тегований enum (int, float, string, symbol, pair, closure, builtin), який не можна тримати в регістрі так, як i64. Список у risp — це ланцюг Rc<Pair>, тож кожен cons — це алокація в купі, а map--acc викликає cons раз на елемент, будуючи новий список. Кожен car, cdr і cons клонує й скидає Rc, тож нативний код мусив би коректно генерувати інкремент/декремент лічильника посилань і логіку Drop: ту частину JIT для динамічної мови, яка найімовірніше пошкодить пам’ять, якщо помилитися. А (f (car xs)) — це динамічна диспетчеризація: f може бути вказівником на Rust fn, скомпільованим замиканням чи замиканням деревообхідного інтерпретатора — це розгалуження під час виконання, а не статичний виклик.

Щоб скомпілювати це нативно, ви не розширюєте цілочисельний JIT; ви будуєте другий, значно більший — JIT для упакованих значень з ABI для алокацій у купі, лічильником посилань у машинному коді й диспетчеризацією замикань. Це машинерія, на яку серйозна реалізація Scheme витрачає роки, і для хобі-Lisp лише на std вона затьмарила б решту кодової бази. Утримання JIT тут — це коректне рішення навмисно вузького інструмента. Що лишає справжнє питання незачепленим: CPython теж не JIT-ить це, тож чому він утричі швидший?

Справжня причина — лінивість, а не кодогенерація

Ось бенчмарк CPython:

reduce(operator.add, map(lambda x: x * x, range(1, 200001)), 0)

У Python 3 range, map і filter — це ліниві ітератори. Цей конвеєр не виділяє жодного проміжного списку. Він стрімить: витягни один x із range, піднеси до квадрата, передай у reduce, згорни в акумулятор, відкинь, повтори. Пікова додаткова пам’ять — це один елемент за раз. functools.reduce і operator.add реалізовані на C, тож цикл згортки — це C-шний цикл while, а не байткод Python; на елемент виконується лише lambda x: x*x, а адаптивний спеціалізувальний інтерпретатор CPython 3.11+ inline-кешує int * int до швидкого шляху. Тимчасові об’єкти PyLong малі, короткоживучі й майже миттєво переробляються free-list’ами pymalloc.

Тепер подивіться, що насправді робить бенчмарк risp:

(fold + 0 (map (lambda (x) (* x x)) (range 200000)))

map, filter і range у risp жадібні. Кожен етап матеріалізує повний список, перш ніж запуститься наступний:

• (range 200000) будує cons-список на 200 000 комірок.
• (map sq …) обходить його й будує ще один cons-список на 200 000 комірок.
• потім fold обходить той другий список.

Це приблизно 400 000 алокацій Rc<Pair> у купі — плюс трафік лічильника посилань на їх побудову й знищення — яких CPython ніколи не виконує. За консервативної оцінки 50–100 нс на алокацію-та-звільнення, це більшість risp-ових 65 мс, витрачена ще до того, як відбулося хоч одне множення.

Це вся історія в одному реченні: risp обмежений алокаціями; CPython стрімить. Вузьке місце — це не диспетчеризація інтерпретатора, та річ, яку прибирає JIT, — це купа. CPython виграв цей бенчмарк не швидшим інтерпретатором і не власним JIT. Він виграв тим, що взагалі не будував списків. Це означає, що інстинкт «скомпілюй це в машинний код, щоб було швидше» цілиться зовсім не в ту мішень: ви можете згенерувати бездоганний нативний код для обходу й усе одно заплатити 400 000 алокацій. JIT ніколи не був важелем. Це інверсія арифметичної історії, де нерозпаковані i64 дозволяють VM обійти CPython — там значення жили на стеку; тут вони живуть у купі, і саме цей один факт перевертає результат.

Виправлення, впорядковані за віддачею, і ключовий момент

Є три способи обійти CPython тут, і саме порядок за віддачею-на-зусилля є уроком.

1. Лінивість / злиття — справжній важіль, і йому не потрібен JIT. Злий map і fold так, щоб жодний проміжний список ніколи не будувався: стрім піднеси-до- квадрата-й-акумулюй, точно так, як це робить CPython. Це прибирає ~200 000 алокацій начисто; зроби range теж лінивим — і ти прибереш інші ~200 000. Прелюдія вже постачає керовану даними версію цього без захоплень — transduce згортає цілий конвеєр в один прохід, а reduce-range — це стрімінговий аналог лінивого range з CPython:

;; Reduce `[lo hi)` with `rf` from `acc`, one integer at a time, no list built.
(def reduce-range
  (lambda (rf acc lo hi)
    (if (< lo hi)
        (reduce-range rf (rf acc lo) (+ lo 1) hi)
        acc)))

Для джерела нічого не виділяється; цілі існують лише як змінні циклу. Це зміна бібліотеки й представлення — злиті конвеєри й ліниві послідовності — а не зміна компілятора, і це найвигідніший окремий хід на всьому бенчмарку.

2. Bump/arena-алокатор для cons-комірок. Якщо ви хочете зберегти жадібні списки з їхньою простою семантикою, атакуйте вартість алокацій напряму: регіонно виділяйте комірки на час життя обчислення замість окремої алокації та Rc на комірку. pymalloc у CPython добрий; цільова arena для короткоживучої, насиченої списками фази може бути кращою. Менша зміна, те саме вузьке місце, жодного нового обчислювача.

3. Ключовий момент — злиття змушує виграти наявний JIT. Причина, чому цілочисельний JIT не міг торкнутися map/fold, у тому, що списки заштовхували упаковані значення й трафік купи в цикл. Злий конвеєр — і списки зникають, а те, що лишається, — це самодостатній цілочисельний цикл: витягни i64, піднеси до квадрата, додай до акумулятора i64. Це точно та форма, яку наявний JIT на Cranelift уже компілює в нативний код і вже обходить CPython у 9–40×. Прелюдія робить це буквальним за допомогою макроса злиття sum-of, який вбудовує тіла етапів inline, тож тіло циклу — це чиста арифметика над i/acc без жодного виклику назовні:

(defmacro sum-of args
  (let ((loop (gensym))
        (stages (reverse (cdr (reverse args))))   ; all but last
        (src (car (reverse args))))               ; the (range lo hi) form
    (let ((lo (car (cdr src)))
          (hi (car (cdr (cdr src)))))
      `(begin
         (def ,loop
           (lambda (i acc)
             (if (< i ,hi)
                 (,loop (+ i 1) ,(sum-of--build stages (quote i) (quote acc)))
                 acc)))
         (,loop ,lo 0)))))

Згенерований def плюс виклик — це точно JIT-придатна форма, яка доведено компілюється в нативний код. Вам узагалі не потрібен JIT для упакованих значень — вам потрібно прибрати списки, щоб цілочисельний JIT, який ви вже маєте, став застосовним. Лінивість і JIT — це не конкурентні відповіді; саме злиття розблоковує JIT.

Узагальнюваний урок

Спокусливою хибною відповіддю було «JIT виконує VM, тож просто змусь JIT компілювати й прелюдію теж». JIT справді працює на VM — він нативно компілює придатні цілочисельні функції й лишає решту байткодом — а списочні функції не придатні й не можуть бути розумно зробленими придатними. Гнатися цим шляхом означає будувати другий, величезний JIT, щоб атакувати вузьке місце — алокації, — якого JIT навіть не зачіпає.

Урок узагальнюється далеко за межі risp: якщо ви хочете зрозуміти, чому кожен шар структурований саме так, читання вихідного коду risp — це практичний туторіал із Rust сам по собі. У ширшому сенсі, на коді, насиченому структурами даних, домінантна вартість — це алокації й трафік пам’яті, а не диспетчеризація інтерпретатора. Саме тому ліниві ітератори CPython обходять тут Lisp із нативною компіляцією, і саме тому найвигідніша оптимізація майже завжди — це робити менше алокацій, а не виконувати ті самі алокації швидше. Кодогенерація — це відповідь, коли значення живуть у регістрах. Коли вони живуть у купі, відповідь — припинити їх туди класти, і щойно ви це зробите, 7-мілісекундний JIT, який уже володіє fib, тихо володітиме й map/fold.