callcc performance non-linear wrt stack size - why?

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

  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
     
    Mikael Brockman, Sep 25, 2004
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. 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
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    1
    Views:
    1,121
    Roedy Green
    Nov 15, 2005
  2. Mr. SweatyFinger
    Replies:
    2
    Views:
    1,949
    Smokey Grindel
    Dec 2, 2006
  3. Surinder Singh
    Replies:
    1
    Views:
    1,206
    Richard Bos
    Dec 20, 2007
  4. Jim Bob

    Why does Ruby have callcc?

    Jim Bob, Aug 6, 2003, in forum: Ruby
    Replies:
    22
    Views:
    241
  5. zuzu
    Replies:
    14
    Views:
    232
    Phil Tomson
    Aug 23, 2004
Loading...

Share This Page