Оптимизация хвостовых вызовов в Elixir и Erlang - это не так эффективно и важно, как вы думаете

(Автоматическая) оптимизация хвостовых вызовов (TCO) - это великолепная особенность Elixir и Erlang, о которой вам все рассказывают. Это супер быстро, супер круто и вы обязаны всегда стремиться к тому, чтобы каждая ваша рекурсивная функция использовала хвостовую рекурсию. Что если я скажу вам, что простая рекурсия может быть более быстрой и более эффективной, чем ее аналог, использующий хвостовую рекурсию?

Звучит неправдоподобно, не так ли? В конце концов каждая книга для начинающих обязательно упоминает TCO, рассказывает, насколько это эффективно, и побуждает вас обязательно использовать ее. Плюс, вы возможно использовали рекурсию в языке YourLanguageName, где из-за нее переполнялся стек вызовов или она работала ужасно медленно. У меня тоже такое было и поэтому я всегда думал, что хвостовая рекурсия всегда лучше обычной. Это продолжалось до тех пор, пока в один прекрасный день я не написал функцию, использующую обычную рекурсию (т.е. TCO не применялась к ней). Мне указали на это и я с готовностью переписал функцию на ее аналог, использующий хвостовую рекурсию. Но потом я на секунду задумался и сделал бенчмарк - его результаты бы неожиданными, если не сказать больше.

Прежде, чем мы углубимся в эту тему, давайте вспомним описание TCO из книги Дэйва Томаса Programming Elixir 1.2:

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

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

Давайте разбираться!

Пишем реализацию функции map

Давайте напишем реализацию функции map. Один вариант будет использовать обычную рекурсию, а другой - хвостовую. Так же я добавил третий вариант, использующий хвостовую рекурсию и оператор ++, но не вызывает reverse в конце. И четвертый вариант, просто не использующий reverse. Этот вариант не поворачивает список в конце поэтому он не полностью повторяет функционал других вариантов. Но это не принципиально. Еще я добавил вариант этой функции с другим порядком аргументов.

defmodule MyMap do

  def map_tco(list, function) do
    Enum.reverse _map_tco([], list, function)
  end

  defp _map_tco(acc, [head | tail], function) do
    _map_tco([function.(head) | acc], tail, function)
  end
  defp _map_tco(acc, [], _function) do
    acc
  end

  def map_tco_arg_order(list, function) do
    Enum.reverse do_map_tco_arg_order(list, function, [])
  end

  defp do_map_tco_arg_order([], _function, acc) do
    acc
  end
  defp do_map_tco_arg_order([head | tail], function, acc) do
    do_map_tco_arg_order(tail, function, [function.(head) | acc])
  end

  def map_tco_concat(acc \\ [], list, function)
  def map_tco_concat(acc, [head | tail], function) do
    map_tco_concat(acc ++ [function.(head)], tail, function)
  end
  def map_tco_concat(acc, [], _function) do
    acc
  end

  def map_body([], _func), do: []
  def map_body([head | tail], func) do
    [func.(head) | map_body(tail, func)]
  end

  def map_tco_no_reverse(list, function) do
    _map_tco([], list, function)
  end
end

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

Теперь, когда наши функции готовы, давайте замеряем их производительность при помощи benchee. Бенчмарк запускается на Elixir 1.3 с Erlang 19 и машине i7-4790, работающей на Linux Mint 17.3. Давайте скормим нашим функциям огромный список и увеличим каждый элемент на 1. Так же мы используем реализацию из стандартной библиотеки как ориентир для сравнения:

list = Enum.to_list(1..10_000)
map_fun = fn(i) -> i + 1 end

Benchee.run %{
  "map tail-recursive with ++" =>
    fn -> MyMap.map_tco_concat(list, map_fun) end,
  "map with TCO reverse" =>
    fn -> MyMap.map_tco(list, map_fun) end,
  "stdlib map" =>
    fn -> Enum.map(list, map_fun) end,
  "map simple without TCO" =>
    fn -> MyMap.map_body(list, map_fun) end,
  "map with TCO new arg order" =>
    fn -> MyMap.map_tco_arg_order(list, map_fun) end,
  "map TCO no reverse" =>
    fn -> MyMap.map_tco_no_reverse(list, map_fun) end
}, time: 10, warmup: 10
tobi@happy ~/github/elixir_playground $ mix run bench/tco_blog_post_detailed.exs 
Benchmarking map tail-recursive with ++...
Benchmarking map TCO no reverse...
Benchmarking stdlib map...
Benchmarking map with TCO new arg order...
Benchmarking map simple without TCO...
Benchmarking map with TCO reverse...

Name                                    ips        average    deviation         median
map simple without TCO              6015.31       166.24μs     (±6.88%)       163.00μs
stdlib map                          5815.97       171.94μs    (±11.29%)       163.00μs
map with TCO new arg order          5761.46       173.57μs    (±10.24%)       167.00μs
map TCO no reverse                  5566.08       179.66μs     (±6.39%)       177.00μs
map with TCO reverse                5262.89       190.01μs     (±9.98%)       182.00μs
map tail-recursive with ++             8.66    115494.33μs     (±2.86%)    113537.00μs

Comparison: 
map simple without TCO              6015.31
stdlib map                          5815.97 - 1.03x slower
map with TCO new arg order          5761.46 - 1.04x slower
map TCO no reverse                  5566.08 - 1.08x slower
map with TCO reverse                5262.89 - 1.14x slower
map tail-recursive with ++             8.66 - 694.73x slower

Вот график для более наглядной демонстрации (вертикальная ось - количество итераций в секунду): График производительности

Итак, что же мы видим? Вариант функции, использующий обычную рекурсию, так же быстр, как и вариант из стандартной библиотеки. Их показатели немного различаются, но в пределах погрешности. Вариант, использующий хвостовую рекурсию и оператор ++, ОЧЕНЬ МЕДЛЕННЫЙ потому что добавление элемента в список через ++ чаще всего очень плохая идея (ведь для этого приходится каждый раз перебирать весь связанный список за O(n) времени). Но не это главное.

Главное то, что вариант, использующий хвостовую рекурсию, медленнее примерно на 14%! Даже вариант с хвостовой рекурсией, который не поворачивает список, работает медленнее!

Стоит отметить, что на действительно огромных списках хвостовая рекурсия все же дает прирост в скорости. Вы можете проверить это на списке из 10 миллионов элементов.

Но действительно удивило меня то, что вариант функции, использующий хвостовую рекурсию, с немного измененным порядком аргументов оказался почти на 10% быстрее! И это не случайное совпадение, такой результат стабильно воспроизводится при повторных запусках.

Итак, в чем же дело?

Распространенное заблуждение

То, что хвостовая рекурсия всегда быстрее обычной - распространенное заблуждение. Настолько распространенное, что оно попало в список "Семь мифов о производительности Erlang". Сейчас эта статья немного изменилась, поэтому вот точная цитата:

Функции, использующие простую рекурсию, и функции, использующие хвостовую рекурсию и вызывающие в конце lists:reverse/1, задействуют одинаковое количество памяти. lists:map/2, lists:filter/2, сравнение списков и многие другие рекурсивные функции теперь задействуют одинаковое количество памяти, что и их аналоги, использующие хвостовую рекурсию.

Так что же быстрее? Нужно смотреть по ситуации. На Solaris/Sparc функции, использующие простую рекурсию, работают чуточку быстрее на больших списках. А на архитектуре x86 хвостовая рекурсия быстрее на 30%.

Эта тема также недавно поднималась в списке рассылок Erlang, в обсуждении переделки вышеупомянутой статьи "Семь мифов о производительности Erlang".

Здесь Фред Хеберт отмечает:

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

Так же он написал пост в своем блоге на эту тему.

А оно не взорвется?

У меня был такой же вопрос. Во время работы с clojure koans я ожидал, что функция, использующая обычную рекурсию, взорвет(переполнит) стек вызовов, получив на вход достаточно большой объем данных. Но этого не случилось, как я ни старался.

Видимо, это невозможно т.к. виртуальная машина BEAM, в которой исполняются Erlang и Elixir, отличается от других виртуальных машин своей реализацией. Из-за этого глубина обычной рекурсии ограничена только доступным объемом ОЗУ.

Erlang не имеет ограничения на глубину рекурсии. В нем используется оптимизация хвостовых вызовов. Если рекурсия не является хвостовой, то она ограничена только доступным объемом ОЗУ.

Потребление памяти

А что по поводу потребления памяти? Давайте создадим список из ста миллионов элементов (100_000_000) и передадим его в функцию map, замерив при этом потребление памяти. По результатам замеров функция, использующая хвостовую рекурсию, заняла почти 12 гигабайт памяти, в то время, как функция, использующая обычную рекурсию, заняла чуть больше 11,5 гигабайт. Подробнее можно посмотреть в этом гисте.

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

Теперь только обычная рекурсия?

Если подытожить, то вариант map, использующий обычную рекурсию, имеет следующие преимущества:

  • Он быстрее
  • Он потребляет меньше памяти
  • Его легче читать и понимать

Так почему бы не использовать ее всегда? Давайте взглянем на очень простую функцию, реализованную в лоб, которая определяет, является ли переданное в нее число четным:

defmodule Number do
  def is_even?(0), do: true
  def is_even?(n) do
    !is_even?(n - 1)
  end

  def is_even_tco?(n, acc \\ true)
  def is_even_tco?(0, acc), do: acc
  def is_even_tco?(n, acc) do
    is_even_tco?(n - 1, !acc)
  end
end
number = 10_000_000

Benchee.run %{
  "is_even?" => fn -> Number.is_even?(number) end,
  "is_even_tco?" => fn -> Number.is_even_tco?(number) end,
}

tobi@happy ~/github/elixir_playground $ mix run bench/is_even.exs 
Benchmarking is_even?...
Benchmarking is_even_tco?...

Name                                    ips        average    deviation         median
is_even?                              10.26     97449.21μs     (±0.50%)     97263.00μs
is_even_tco?                           9.39    106484.48μs     (±0.09%)    106459.50μs

Comparison: 
is_even?                              10.26
is_even_tco?                           9.39 - 1.09x slower

Вариант с хвостовой рекурсией здесь все еще на 10% медленнее. Но что с памятью? Запуск функции c 1_000_000 в качестве аргумента потребует 41 мегабайт для варианта с хвостовой рекурсией и почти 6,7 гигабайт для варианта с простой рекурсией. Так же для такого большого входного числа вариант, использующий хвостовую рекурсию, займет 1,3 секунда, а вариант, использующий обычную рекурсию, займет 3,86 секунды. Т.е. для больших входных данных хвостовая рекурсия лучше.

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

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

Выводы

Хвостовая рекурсия все еще работает быстрее и эффективнее на многих задачах. В этой статье я не утверждаю, что TCO это плохо или медленно. Я хочу сказать, что есть случаи, когда обычная рекурсия быстрее и эффективнее, чем хвостовая. Так же я до сих пор не уверен, почему функция, которая использует хвостовую рекурсию и не поворачивает список в конце, работает медленнее, чем ее реализация, использующая обычную рекурсию. Возможно это происходит из-за накладных расходов на передачу аккумулятора.

Так же возможно нам нужно быть более осторожными в обучении. Следует быть более осторожными и не переоценивать возможности TCO и вместе с ним пользу хвостовой рекурсии. Функции, использующие обычную рекурсию, могут быть жизнеспособными или даже являться превосходной альтернативой. И они должны представляться как таковые в учебных материалах.

Конечно, есть случаи, когда использование хвостовой рекурсии просто необходимо. Вот, что пишет об этом Роберт Вирдинг, создатель Erlang:

Главный случай, где TCO критически важна - top-loop процесса. Эти функции никогда не завершаются (кроме падения процесса). Поэтому они будут бесконечно увеличивать стек вызовов. Поэтому здесь нужно использовать хвостовую рекурсию. Аналогичная ситуация возникает, когда ваш top-loop фактически состоит из функций, взаимно вызывающих друг друга.

Чему все это должно научить нас? Не полагайтесь слепо на ваш опыт из других языков программирования. Кроме того, не стройте догадок - всегда проверяйте. Итак, теперь выбор между обычной и хвостовой рекурсией - в основном дело вкуса. Если же вам нужна действительно максимальная производительность, то вам нужно провести тесты производительности для конкретного случая. Вы больше не можете быть уверены, что хвостовая рекурсия всегда будет самым лучшим вариантом.

[Примечание: У оригинальной статьи есть ряд очень ценных комментариев и дополнений. Если вы знаете английский, не поленитесь и почитайте.]

Это вольный перевод статьи "Tail Call Optimization in Elixir & Erlang - not as efficient and important as you probably think", которую написал PragTob.

Коментарии

Используйте Markdown

Спасибо за коментарий!
Ваше сообщение будет доступно после проверки.

#1 Haru Atari

Atropos, нет не планирую. Та статья освещает эту же тему. Фактически тоже самое, только от другого автора. Не вижу смысла переводить две схожих статьи.

#0 Atropos

Спасибо за перевод! Отличная статья! Вы планируете перевод этот статьи (на нее есть ссылка в этой статье) https://ferd.ca/erlang-s-tail-recursion-is-not-a-silver-bullet.html ?