From: Chuck Remes <cremes.devlist@...>
Date: 2011-09-19T04:06:27+09:00
Subject: Re: Ruby Speed Question


On Sep 18, 2011, at 10:51 AM, Kevin Anon wrote:

> Wrote my first Ruby program recently for a class assignment where we had
> to examine the speed of binary search on various array sizes in 3
> different languages. After a little debugging, I managed to get the code
> working, but the difference in run-time between this and the other 2
> languages is significant enough that I'm wondering if I did something
> wrong.
> 
> This takes 13-14 seconds total, while Java runs in just under a quarter
> of a second and C# runs in well under a hundredth of a second. I'm sure
> some of the slowdown for Ruby is that I'm doing it in JRuby on NetBeans,
> but even running it through a command prompt version of Ruby only
> knocked a second or two off the total runtime.

This general question has been answered quite a few times. Some of these links are a little out of date now but the gist is correct. BTW, JRuby is probably the fastest current runtime and the one with the best chances of reaching Java-like performance. Running it with NetBeans isn't slowing you down though you may want to see if you can configure NetBeans to run JRuby with the --server switch (more aggressive JIT'ing by hotspot).

http://stackoverflow.com/questions/1011460/what-makes-ruby-slow

http://stackoverflow.com/questions/2529852/why-do-people-say-that-ruby-is-slow

http://carboni.ca/blog/p/Another-Cool-Reason-Ruby-is-Slow-implicit-super

You can google for more links if you like.

That said, Ruby is probably never going to be as fast as Java or C#. It has advantages beyond speed such as no compile -> link -> run cycle, better ways to express thought (IMHO), a more English-like readability, etc.

I rewrote your example to take advantage of a few Ruby idioms. Your original was essentially a straight port of the C version (minus the memory management). This version is actually a little bit slower on JRuby (the calls to #not_found?, #found? and #left? add about 20% overhead). Interestingly, this rewrite is *faster* when run on Rubinius than your original code. That's one of the nice things about this ecosystem... there are 3 good choices for Ruby runtimes all with the various strengths & weaknesses.


class BinarySearch

  # main method, tests binary search speed on arrays of varying sizes
  # for each array size, program does the following:
  #    1) fills array with even numbers (index times two)
  #    2) performs 500,000 unsuccessful searches (odd numbers only)
  #    3) reports total time & average time per search
  #    4) brings the array out of scope to remove it from memory
  def initialize
    puts "Data Structures & Algorithms - Assignment 1 - Problem 5 - Ruby\n\n"

    @size = 32
    @list = []
  end

  def run
    while @size < 530_000
      @list.clear
      populate_with_even_numbers

      @check = 0
      elapsed_time = measure_elapsed_time do
        search_for_odd_numbers
      end

      puts "ERROR! Successful search! checksum = #{@check}" if checksum_failure?

      output_results(@size, elapsed_time)
      @size *= 4
    end
  end

  # recursive binary search
  # array = the array to be searched
  # target = what to look for
  # first = the first index of the range
  # last = the last index of the range
  # returns the index of target value, or -1 if not found
  def search(target, first, last)
    return -1 if not_found?(first, last)  # basis (not found)

    middle = (first + last) / 2
    if found?(middle, target)
      middle
    elsif left?(middle, target)
      search(target, first, middle - 1)
    else  # recur on right half
      search(target, middle + 1, last)
    end
  end
  
  def not_found?(first, last)
    first > last
  end
  
  def found?(middle, target)
    @list[middle] == target
  end
  
  def left?(middle, target)
    target < @list[middle]
  end

  def populate_with_even_numbers
    # fills the array with even numbers
    @size.times { |i| @list[i] = 2 * i }
  end

  def measure_elapsed_time(&blk)
    start = Time.now
    yield
    Time.now - start
  end

  def search_for_odd_numbers
    1.step(1_000_000, 2) do |j|
      r = search(j, 0, @list.length - 1)
      @check -= r
    end
  end

  def checksum_failure?
    500_000 != @check
  end

  def output_results(size, elapsed_time)
    puts "Performing 500k searches on an array of length " + size.to_s + " required " +
    elapsed_time.to_s + " seconds, an average of " + (elapsed_time * 2000).to_s +
    " nano-seconds per search"
  end
end



if __FILE__ == $0

  b = BinarySearch.new
  b.run

end


To my eye this reads much better and expresses the execution a bit more clearly.

We hope you stick around and learn more about the language.
 
cr