callcc performance non-linear wrt stack size - why?

[Mikael Brockman]

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

 

[Mikael Brockman]

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).

 

[Mikael Brockman]

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.