Эссе разбирает принцип «push ifs up, fors down» из Tiger Style TigerBeetle

Исходная рекомендация взята из документа Tiger Style компании TigerBeetle: все ветвления (switch/if) стоит держать в «родительской» функции, а неветвящуюся логику выносить во вспомогательные. За управление потоком отвечает одна функция, остальным оно безразлично. Сжато это формулируется так: «push ifs up and fors down» (поднимай условия вверх, опускай циклы вниз). Те же идеи ранее описывал в своём блоге matklad.

Первая часть эссе пересказывает пример matklad. Если функция frobnicate принимает Option и сама разбирает случай None, то ветвление лучше перенести к вызывающему коду: тогда функция берёт обычный Walrus, её тип прямо фиксирует предусловие, а пространство допустимых входов сужается и работает как фильтрация. Для циклов наоборот: вместо вызова frobnicate(walrus) в цикле предлагается frobnicate_batch(walruses), где цикл находится внутри. Тогда горячий цикл выполняется без ветвления и может быть векторизован. Два приёма сочетаются: вызывающий код отбрасывает None из коллекции Option, разворачивает остальное в Vec и передаёт его в frobnicate_batch, которая случая None вообще не знает.

Вторая часть проводит аналогию с оптимизацией запросов в реляционных базах данных. Проекции и выборки (WHERE) выполняют как можно раньше, а соединения (join) откладывают, чтобы они работали на меньших данных. Терминология здесь «перевёрнута»: план запроса, дерево, данные идут от листьев к корню, поэтому «вниз по дереву» означает «раньше по времени». Когда оптимизатор «опускает» предикат, это то, что в остальном тексте названо «вверх» или «раньше». Аналог «fors вниз», векторизованное (пакетное) исполнение: вместо построчного вызова оператора через виртуальный next() (стиль Volcano) оператор вызывается один раз на пакет примерно в тысячу кортежей и крутит внутри плотный цикл. Накладные расходы и решения на вызов оплачиваются раз на пакет, а внутренний цикл содержит мало ветвлений и дружит с кэшем.

Третья часть, взгляд из функционального программирования и теории категорий. «Поднятие if» трактуется как ограничение до подобъекта: множество элементов, удовлетворяющих предикату, с вложением (мономорфизмом) в исходное множество. До этого вызываемая функция принимала любой A и проверяла условие внутри; после, проверку делает вызывающий код, а входной тип функции, это подмножество, что в коде выражается типом Walrus вместо Option. Option при этом, копроизведение 1 + Walrus, а функция из копроизведения по универсальному свойству есть пара функций, по одной на слагаемое. Поднятие if «разнимает» эту пару: вызывающий код обрабатывает случай «ничего», а основная функция, только компонент Walrus.

Далее разбирается совет «фильтруй до map». Выражения filter p (map f xs) и map f (filter p xs) не эквивалентны: в первом p проверяет результат f, во втором, вход. Законная перестановка задаётся равенством filter p . map f == map f . filter (p . f). Автор выводит его через параметричность, представляя filter как catMaybes . map (keep p); естественность catMaybes и обеспечивает законность преобразования. Выгода не автоматическая: filter (p . f) всё равно вычисляет f для каждого элемента, чтобы проверить его. Перестановка окупается, когда p . f упрощается до дешёвого предиката q на входе, обычно потому, что p смотрит на часть значения, которую f не трогает. Обе стороны остаются одним проходом O(n); экономятся вызовы f на элементах, которые всё равно отбросят.

Итоговые условия допустимости такие. Вынос if из цикла корректен, когда условие не зависит от итерации (loop-invariant); условие, зависящее от элемента, из цикла уйти не может и может лишь переместиться на границу и быть записанным в типе. Спуск выборки ниже соединения допустим, если предикат ссылается на столбцы только одной стороны соединения. Фильтрация до map корректна по закону выше и экономит работу, только если p . f сводится к дешёвому предикату на входе. Часть «fors вниз», скорее про стоимость, чем про эквивалентность: стрелка меняется с A -> B на [A] -> [B], и затраты на подготовку платятся один раз на пакет. Вывод автора: именно алгебра подсказывает, какие перестановки законны.

Ключевые факты

• Рекомендация из Tiger Style (TigerBeetle): ветвления держать в родительской функции, а циклы опускать вглубь; ту же идею ранее разбирал matklad.
• Пример: функция принимает Walrus вместо Option, а вместо frobnicate в цикле используется frobnicate_batch(walruses) с циклом внутри: горячий цикл без ветвления можно векторизовать.
• Аналогия в базах данных: проекции и выборки выполняются раньше соединений, а векторизованное исполнение вызывает оператор раз на пакет примерно в тысячу кортежей вместо построчного вызова.
• Закон filter p . map f == map f . filter (p . f) делает перестановку законной, но не обязательно дешевле: filter (p . f) всё равно вычисляет f для каждого элемента.
• Условия законности: if выносится из цикла, только если условие не зависит от итерации; выборка спускается ниже join, только если предикат касается столбцов одной стороны.

Почему это важно

Эссе не приносит новых результатов: это пересказ известной идиомы из Tiger Style TigerBeetle и блога matklad. Его ценность в том, что одна и та же мысль («где живёт решение» и «где крутится цикл») показана как общий принцип: в типах функций, в планах запросов баз данных и в алгебре комбинаторов. Заодно текст чётко обозначает границы: идиома не универсальна, и у каждой перестановки есть условия законности.

Кому это важно

Прикладным программистам, которые делят большие функции на части и решают, где держать проверки и циклы. Тем, кто пишет код с тяжёлыми циклами и думает о векторизации. Тем, кто интересуется устройством оптимизаторов запросов или связью программирования с теорией категорий. К ИИ материал отношения не имеет: это общая инженерная тема.

Как это применить

Практический смысл, по тексту: если функция ветвится по входу, подумайте, не перенести ли ветвление к вызывающему коду и не выразить ли предусловие типом (Walrus вместо Option). Если функция вызывается в цикле, предложите пакетный вариант с циклом внутри. Перед любой перестановкой проверьте условия: условие не зависит от итерации (для вынесения из цикла), предикат опирается на столбцы одной стороны (для спуска ниже соединения), p . f сводится к дешёвому предикату на входе (для фильтрации до map).

Можно ли доверять

Это авторское эссе, в тексте не приведено ни замеров, ни бенчмарков, поэтому выигрыш по скорости не подтверждён цифрами: заявления о векторизации и о кэш-дружелюбности внутреннего цикла даны как рассуждения. Размер пакета «около тысячи кортежей», приблизительная величина и не привязана к конкретной СУБД. Правила про законность преобразований (вывод закона filter/map через естественность catMaybes), формальные выкладки, их можно проверить самостоятельно.

Риски и подводные камни

Главные ограничения названы в самом тексте. Условие, зависящее от элемента, нельзя вынести из цикла: его можно лишь перенести на границу и записать в типе. Перестановка filter и map не всегда дешевле, пока p . f не упрощается до дешёвого предиката. Терминология легко запутывает: в запросах «вниз по дереву» означает «раньше», что соответствует «вверх» в самой идиоме. Часть «fors вниз», про стоимость, а не про эквивалентность, поэтому выигрыш зависит от того, как велика цена подготовки на вызов.

«Поднимай if вверх, а for опускай вниз.»

— Tiger Style, документ TigerBeetle