callcc performance non-linear wrt stack size - why?

Discussion in 'Ruby' started by Mikael Brockman, Sep 25, 2004.

1. Mikael BrockmanGuest

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, Sep 25, 2004

2. Mikael BrockmanGuest

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

Mikael Brockman, Sep 25, 2004

3. Mikael BrockmanGuest

Mikael Brockman <> 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.

Mikael Brockman, Sep 25, 2004