Elijah Schutz Elijah Schutz - 1 month ago 13
Ruby Question

Ruby Memory Usage: Methodical Loop Versus Built In Loop

Take this Ruby (MRI) program:

@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"


Using the builtin
loop
function it infinitely loops until
@n
equals 11,900, then prints the memory used by Ruby in the process (I used a system call for lack of a good, working memory profiler).

When executed, this outputs:
Memory usage: 9.16796875 Mb
, or anywhere between about 8.99 Mb and 9.49 Mb.

Compare to this function:

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


Using a self-calling function,
lp
, it loops until
@n
equals 11,900 (the stack limit).

When executed, this outputs:
Memory usage: 10.20703125 Mb
, or anywhere between about 9.96 Mb and 10.41 Mb.

Why is it that the first program occupies almost a megabyte less memory than the second? How does the builtin loop differ from an artificial loop?

The only reason I am able to think of with my limited knowledge is that the
loop
function compiles directly to C whereas the second program has a lot of overhead with the function definition etc.

Answer

Your first loop is iterative and your second loop is recursive.

In other words, you are calling the same method from itself over and over again. This builds a huge stack. You can see this by raising an exception at a given point:

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

Gives:

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>'

You are using a special kind of recursion here called tail recursion and it can be optimized.

Although Ruby does not optimize tail calls by default, you can enable it manually:

# 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"

From shell without optimization:

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

and with optimization:

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

Using tail call optimization makes the recursive algorithm as memory efficient as its iterative counterpart. It also prevents a stack overflow.

Comments