22.05.2025 10:01
PatientZero 9 3200 Источник

Эта статья — краткая заметка о двух связанных друг с другом эмпирических правилах.

Поднимайте If вверх

Если внутри функции есть условие if, то подумайте, нельзя ли его переместить в вызывающую сторону:

// ХОРОШО
fn frobnicate(walrus: Walrus) {
    ...
}
// ПЛОХО
fn frobnicate(walrus: Option<Walrus>) {
  let walrus = match walrus {
    Some(it) => it,
    None => return,
  };
  ...
}

В подобных примерах часто существуют предварительные условия: функция может проверять предусловие внутри и «ничего не делать», если оно не выполняется, или же может передать задачу проверки предварительного условия вызывающей её стороне, а при помощи типов (или assert) принудительно удовлетворить этому условию. Подъём проверок вверх, особенно в случае предварительных условий, может иметь лавинообразный эффект и привести к уменьшению общего количества проверок. Именно поэтому и возникло это правило.

Ещё одна причина заключается в том, что поток управления и if сложны, к тому же оказываются источниками багов. Поднимая if наверх, мы часто приходим к централизации потока управления в одной функции, имеющей сложную логику ветвления, но сама работа при этом делегируется к простым линейным подпрограммам.

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

fn f() {
  if foo && bar {
    if foo {
    } else {
    }
  }
}
fn g() {
  if foo && bar {
    h()
  }
}
fn h() {
  if foo {
  } else {
  }
}

В случае f гораздо проще заметить «мёртвое» ветвление, чем в последовательности g и h!

Есть и другой схожий паттерн, который я называю рефакторингом «растворяющихся enum». Иногда код начинает выглядеть так:

enum E {
  Foo(i32),
  Bar(String),
}
fn main() {
  let e = f();
  g(e)
}
fn f() -> E {
  if condition {
    E::Foo(x)
  } else {
    E::Bar(y)
  }
}
fn g(e: E) {
  match e {
    E::Foo(x) => foo(x),
    E::Bar(y) => bar(y)
  }
}

Здесь две команды ветвления; если поднять их наверх, то становится очевидно, что это одно и то же условие, которое повторяется трижды (в третий раз оно превращается в структуру данных):

fn main() {
  if condition {
    foo(x)
  } else {
    bar(y)
  }
}

Опускайте For вниз

Этот совет взят из подхода, ориентированного на обработку данных. Программы обычно работают с сериями объектов, или, по крайней мере, горячий путь выполнения обычно связан с обработкой множества сущностей. Именно из-за количества сущностей путь и становится в первую очередь горячим. Поэтому часто бывает разумно ввести концепцию «группы» объектов и в базовом случае выполнять операции с группами, а скалярная версия при этом будет особым случаем групповой обработки:

// ХОРОШО
frobnicate_batch(walruses)
// ПЛОХО
for walrus in walruses {
  frobnicate(walrus)
}

Основное преимущество здесь — производительность. А крайних случаях — огромный рост производительности.

Если у вас есть целая группа объектов для обработки, можно амортизировать затраты на запуск и более гибко определять порядок обработки. На самом деле, вам даже не нужно обрабатывать сущности в каком-либо конкретном порядке: можно реализовать трюк с векторизацией/массивом структур, чтобы сначала обрабатывать одно поле всех сущностей, а затем переходить к другим полям.

Наверно, самый забавный пример здесь — это умножение многочленов на основании быстрого преобразования Фурье: оказывается, одновременное вычисление многочлена в куче точек можно выполнять быстрее, чем кучу вычислений отдельных точек!

Два эти совета про for и if даже можно комбинировать!

// ХОРОШО
if condition {
  for walrus in walruses {
    walrus.frobnicate()
  }
} else {
  for walrus in walruses {
    walrus.transmogrify()
  }
}
// ПЛОХО
for walrus in walruses {
  if condition {
    walrus.frobnicate()
  } else {
    walrus.transmogrify()
  }
}

Версия ХОРОШО хороша тем, что ей не приходится многократно проверять condition, она избавляется от ветвления в горячем цикле, а потенциально и обеспечивает возможность векторизации. Этот паттерн работает и на микро-, и на макроуровне — хорошей версией архитектуры можно считать TigerBeetle, в которой в плоскости данных мы одновременно работаем с группами объектов, чтобы амортизировать стоимость принятия решений в плоскости управления.

Хотя совет про for в первую очередь связан с повышением производительности, иногда он и улучшает выразительность. Когда-то был довольно успешен jQuery, работавший с коллекциями элементов. Язык абстрактных векторных пространств чаще оказывается более удобным инструментом, чем куча уравнений с координатами.

Подведём итог: поднимайте if наверх и опускайте for вниз!

Комментарии (9)


  1. redf1sh
    22.05.2025 10:03
    #28338072

    Современные компиляторы умеют это делать. Оптимизация называется loop unswitching


  1. plFlok
    22.05.2025 10:03
    #28338172

    эмпирических

    Ну как эмпирических. Всполне себе формальных.
    O(1) vs O(N) в лучших случаях.


  1. dedmagic
    22.05.2025 10:03
    #28338358

    Может, я неправильно понял.
    Есть функция с одним if, которая вызывается 15 раз.
    Предлагается этот if вынести в вызывающий код, и у нас станет 15 if вместо одного?


    1. domix32
      22.05.2025 10:03
      #28338586

      На 15 штуках не сильно принципиально, но если штук заметно больше, то выгоднее сначала отфильтровать/поделить штуки по if и уже после вызывать обработку штук. Это во первых открывает путь к применению автовекторизации (то бишь когда в регистр процессора кладётся несколько штук сразу и все они обрабатываются за один такт), во вторых становится cache friendly - инвалидацию кэшей процессора можно будет делать реже, потому что предсказание веток уже сделано фильтром.


      1. dedmagic
        22.05.2025 10:03
        #28338710

        От силы 1% кода, который пишется, требует оптимизации на уровне регистров и кеша процессора. При этом 100% кода читается и модифицируется.

        Так что критерии читабельности и поддерживаемости значительно превалируют.

        И часто критична (ну или хотя бы очень важна) скорость написания кода. Что быстрее – воткнуть один if или анализировать вызовы функции на предмет "отфильтровать/поделить" и затем заниматься изменением дизайна кода?


      1. Naf2000
        22.05.2025 10:03
        #28339246

        и получаем кучу копи-паста (мы же вынесли условие из функции в места ее вызовов) и удачи при изменении условия

        и вот еще - в функции стоит условие проверки аргументов на валидность - тоже условие поднимать выше - выносить из функции?


  1. adeshere
    22.05.2025 10:03
    #28339248

    Основное преимущество здесь — производительность. А крайних случаях — огромный рост производительности.

    Я, конечно, не настоящий программист (пишу на фортране). Но невольно возникает вопрос: а так ли уж часто сверхсложная логика и требование высокой производительности переплетены настолько, что их не разделишь? Лично я просто стараюсь

    писать понятно

    то есть читабельно человеком, и чтобы не ставить подножек оптимизатору

    а дальше пусть голова болит у оптимизатора. То же перечисление - это же по сути массив, а массивы, по идее, любой компилятор должен распараллеливать на ура?

    Как выше заметил redf1sh2, современные компиляторы умеют многое делать. Особенно если им не мешать. Может, у меня однобокий взгляд, но у нас в фортране простые for-циклы обычно пишутся в виде массивного оператора, например:

    if (condition) A=1/B,

    (тут A и B - массивы). Такой код оборачивать в функцию часто не нужно вообще. Соответственно, рекомендация автора статьи выполнена автоматически ;-). Но, вовсе не ради какой-то оптимизации, а просто мне так запись понятнее.

    При этом, однако, никто не мешает вставить if внутрь цикла:

    where (B > 1) A=1./B

    Получается поэлементная операция (делим на себя те элементы массива, которые больше 1), которая столь же прекрасно распараллеливается. Было бы просто неуважением к компилятору подозревать его в неспособности справиться задачей такого рода. Поэтому и в этом случае я пишу так, как понятнее и удобнее человеку (читателю).

    Я понимаю, что массивные операции есть не во всех языках, и что у компилятора могут возникнуть трудности, если, например, мы работаем не с нативным массивом, а с массивом структур, и там надо обработать какое-то поле. Но, если речь идет о второй древнейшой профессии втором древнейшем языке, то ведь обычно справляется же?! Значит, и в современных языках тоже должен справляться

    ну или вот-вот научится

    Конечно, из любых правил есть исключения. Но строить всю парадигму на базе тех нескольких процентов случаев, где
    1) эффективность критична, но
    2) компилятор не умеет превратить хорошо структурированный (=читаемый) код в быстродействующую программу -

    это как то странно, не правда ли?

    Поэтому я согласен с автором статьи в том, что логику обычно стоит поднять повыше (в разумных пределах, конечно). Но, глядя со своей колокольни, не очень согласен в том, что

    во главе угла при этом должна стоять именно эффективность, а не читаемость кода

    Может, конечно, это специфика моей предметной области - я обрабатываю научные временные ряды. Но вот в моем случае программы, написанные простым языком, почти всегда получаются достаточно эффективными, чтобы можно было не париться о каких-то особенных ухищрениях. Правда, ряды данных у нас не очень большие (обычно десятки-сотни миллионов значений, хотя изредка бывают и миллиарды). При этом каждая запись - это просто одно или несколько чисел. Без сложных текстовых полей и структур. Короче, далеко не "биг дата". Там мой "наивный подход" уже не факт, что прокатит.

    > dedmagic1> От силы 1% кода, который пишется, требует оптимизации на уровне регистров и кеша процессора. При этом 100% кода читается и модифицируется (...).

    Вот именно что ;-)


  1. fugasio
    22.05.2025 10:03
    #28339818

    Это вроде как логически понятно, если условие не индивидуально для каждого walrus, зачем проверять его каждый раз?


  1. Naf2000
    22.05.2025 10:03
    #28340460

    По поводу примера с условием в цикле. Создать функциональную переменную, которой по условию присвоить необходимую рутину. В цикле вызывать - в результате нет дублирования цикла