Compact code, but efficient?

by Caleb Tennis

In my previous entry I had some takers on trying to write a nice, compact, method that handled round a float down to a certain decimal place.

For fun, I decided to benchmark each implementation, along with a small C implementation I wrote. Here's the lineup:


require 'benchmark'
require 'prec_c'
include Benchmark

class Float
  def prec_caleb1(x)
    sprintf("%.0" + x.to_i.to_s + "f", self).to_f
  end

  def prec_caleb2(x)
    (("%.0" + x.to_i.to_s + "f") % self).to_f
  end

  def prec_james(x)
    ("%.0#{x.to_i}f" % self).to_f
  end

  def prec_jonas(x)
    (self * 10**x).to_i / (10**x).to_f
  end

  def prec_fansipans(x)
    to_s[/.*\..{#{x}}/]
  end
end

n = 50000
bm do |x|
  r = rand(6)
  x.report { for i in 1..n; 5.44235102.prec_c(r); end; }
  x.report { for i in 1..n; 5.44235102.prec_caleb1(r); end; }
  x.report { for i in 1..n; 5.44235102.prec_caleb2(r); end; }
  x.report { for i in 1..n; 5.44235102.prec_james(r); end; }
  x.report { for i in 1..n; 5.44235102.prec_jonas(r); end; }
  x.report { for i in 1..n; 5.44235102.prec_fansipans(r); end; }
end


I ran the code a couple of times to make sure the results came up rough the same. They did. Here are the results (sorry for the formatting):


impl user system total real
caleb_c 0.330000 0.000000 0.330000 ( 0.325121)

caleb1 0.450000 0.000000 0.450000 ( 0.454775)

caleb2 0.460000 0.000000 0.460000 ( 0.456334)

james 0.410000 0.000000 0.410000 ( 0.405698)

jonas 0.480000 0.000000 0.480000 ( 0.486741)

fansipans 0.950000 0.000000 0.950000 ( 0.944716)


It looks like James is the winner, at least in terms of efficiency (as long as you don't count my C extension, which kind of breaks the Ruby spirit).

Here's that code, in case you're interested:


#include "ruby.h"
#include <signal.h>
#include <time.h>

static VALUE prec_c(VALUE klass, VALUE prec)
{
  VALUE str = rb_str_plus( rb_str_new2("%."), rb_funcall(prec, rb_intern("to_s"), 0) );
  VALUE str2 = rb_str_plus( str, rb_str_new2("f") );

  char s[20];

  sprintf(s, StringValuePtr(str2), NUM2DBL(klass) );
  return rb_funcall(rb_str_new2(s), rb_intern("to_f"), 0);
}

void Init_prec_c() {
  rb_define_method(rb_cFloat, "prec_c", prec_c, 1);
}


I'm sure someone can find some fallacies in my code that makes for unfairness in my benchmarking, but for the most part I think the data is fairly reliable.

3 Comments

Christian Neukirchen
2005-12-22 05:08:02
You should try to write that C implementation using sprintf and then returning only the first N chars (second parameter of rb_str_new), that should be even faster, I guess...
Patrick
2005-12-22 07:23:01
I would suggest that Jonas was on the right track for a math based solution; however, calculating the exponent twice is a mistake as is truncating the float (to_i).


Try something like:


class Float
def prec_hurley(x)
fact = 10**x
(self * fact).round / fact.to_f
end
end

On my (slower than your box :-) laptop I get the following times:

user system total real
prec_c 0.625000 0.000000 0.625000 ( 0.625000)
caleb1 0.672000 0.000000 0.672000 ( 0.687000)
caleb2 0.687000 0.000000 0.687000 ( 0.703000)
james 0.641000 0.000000 0.641000 ( 0.641000)
jonas 0.375000 0.000000 0.375000 ( 0.375000)
fansipans 1.953000 0.047000 2.000000 ( 2.000000)
hurley 0.328000 0.000000 0.328000 ( 0.328000)

This test was run on a WinXP box, I am guessing that in this environment there is more overhead to calling external C based libraries. Under a slower Linux machine the C code comes back into (very slight) favor. Would be even better if there was an implementation of round that did not force an integer (so we would not have to recast back to float).


Jonas
2005-12-22 16:49:04
I got a little surprised that the string conversion variants were that quick compared to my integer and float based one.


Thanks Patrick for improving on my attempt! :-)