Callcc performance non-linear wrt stack size - why?

ruby-talk
1

I wrote a silly benchmark to test the speed of callcc as the stack
grows.

class Class
  def make_stack_filler id, n
    (n + 1).times do |i|
      this_method = "#{id.to_s}_#{i}".to_sym
      next_method = "#{id.to_s}_#{i + 1}".to_sym
      
      define_method this_method do |max|
        if i >= max
          yield
        else
          send next_method, max
        end
      end
    end
  end
end

$n = 100
$max_recursions = 1000
$speeds = {}

class Object
  make_stack_filler :stack_filler, $max_recursions do
    $n.times do
      callcc do end
    end
  end
end

(0..$max_recursions).step 10 do |stack_depth|
  GC.start
  t0 = Time.now

  stack_filler_0 stack_depth
  
  t = Time.now
  d_t = t - t0
  cps = $n / d_t
  $speeds[stack_depth] = cps
end

$speeds.each_pair do |depth, speed|
  puts "#{depth} #{speed}"
end

The graphs[1] suggests that callcc performance and stack speed aren't
linearly proportional. If that's right, why? I thought the only
time-consuming part of callcc was the stack copy. Maybe the stack copy
isn't linear? If so, why?

1: http://www.phubuh.org/callcc-graph.png for 0..1000,
   http://www.phubuh.org/callcc-graph-from-100.png for 100..1000

2

Mikael Brockman <mikael@phubuh.org> writes:

I wrote a silly benchmark to test the speed of callcc as the stack
grows.

The graphs[1] suggests that callcc performance and stack speed aren't
linearly proportional. If that's right, why? I thought the only
time-consuming part of callcc was the stack copy. Maybe the stack copy
isn't linear? If so, why?

1: http://www.phubuh.org/callcc-graph.png for 0..1000,
   http://www.phubuh.org/callcc-graph-from-100.png for 100..1000

The function is approximately y = 35338*x^(-0.9267).

3

Mikael Brockman <mikael@phubuh.org> writes:

I wrote a silly benchmark to test the speed of callcc as the stack
grows.

The graphs[1] suggests that callcc performance and stack speed aren't
linearly proportional. If that's right, why? I thought the only
time-consuming part of callcc was the stack copy. Maybe the stack copy
isn't linear? If so, why?

1: http://www.phubuh.org/callcc-graph.png for 0..1000,
   http://www.phubuh.org/callcc-graph-from-100.png for 100..1000

Duh! I was plotting the rate of callcc calls, instead of the speed. Of
course, the latter *is* linear.