Блог

Возьмите эту программу Ruby (MRI):

 @n = 0
loop do
    @n  = 1
    break if @n == 11_900
end

ps = `ps auxm | grep ruby`
puts "Memory usage: #{ps.split[5].to_i/1024.0} Mb"
  

Используя встроенную loop функцию, она бесконечно выполняет цикл, пока @n значение не будет равно 11 900, затем печатает память, используемую Ruby в процессе (я использовал системный вызов из-за отсутствия хорошего рабочего профилировщика памяти).

При выполнении выводится: Memory usage: 9.16796875 Mb или где-то между 8,99 Мб и 9,49 Мб.

Сравните с этой функцией:

 @n = 0
def lp
  @n  = 1
  if @n == 11_900
    return
  end
  lp
end
lp
  

Используя самозваную функцию, lp она выполняет цикл до @n тех пор, пока значение не будет равно 11 900 (предел стека).

При выполнении выводится: Memory usage: 10.20703125 Mb или где-то между 9,96 Мб и 10,41 Мб.

Почему первая программа занимает почти на мегабайт меньше памяти, чем вторая? Чем встроенный цикл отличается от искусственного цикла?

Единственная причина, о которой я могу думать с моими ограниченными знаниями, заключается в том, что loop функция компилируется непосредственно в C, тогда как вторая программа имеет много накладных расходов с определением функции и т.д.

Ваш первый цикл является итеративным, а второй — рекурсивным.

Другими словами, вы вызываете один и тот же метод из самого себя снова и снова. Это создает огромный стек. Вы можете увидеть это, вызвав исключение в заданной точке:

 @n = 0
def lp
  @n  = 1
  raise if @n >= 10
  lp
end
lp
  

Дает:

 loop.rb:4:in `lp': unhandled exception
        from loop.rb:5:in `lp'
        from loop.rb:5:in `lp'
        from loop.rb:5:in `lp'
        from loop.rb:5:in `lp'
        from loop.rb:5:in `lp'
        from loop.rb:5:in `lp'
        from loop.rb:5:in `lp'
        from loop.rb:5:in `lp'
        from loop.rb:5:in `lp'
        from loop.rb:7:in `<main>'
  

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

Хотя Ruby не оптимизирует конечные вызовы по умолчанию, вы можете включить это вручную:

 # tailcall.rb

tailcall = ARGV.include?('-t')

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: tailcall,
  trace_instruction: false
}

RubyVM::InstructionSequence.new(<<-RUBY).eval
  @n = 0
  def lp
    @n  = 1
    if @n == 11_900
      return
    end
    lp
  end
  lp
RUBY

puts "Memory usage: #{`ps -o rss= -p #{$$}`.to_i} kB"
  

Из оболочки без оптимизации:

 $ ruby --disable-all tailcall.rb
Memory usage: 4952 kB
  

и с оптимизацией:

 $ ruby --disable-all tailcall.rb -t
Memory usage: 3860 kB
  

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

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