From: Mikael Brockman <mikael@...>
Date: 2004-09-26T02:25:11+09:00
Subject: callcc performance non-linear wrt stack size - why?

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