Binary Tree in Ruby

I've returned back to Dave Thomas's katas and picked up number 11: Sorting. Harking back to the reuse we saw in the data munging kata we must sort through a pair of unordered lists efficiently without using built in libraries. I chose to implement a binary tree and enjoyed reminding myself of this algorithm very much. As usual, source is at the GitHub.

    def insert(node)
      self.count_all = self.count_all + 1
      insert_left(node) if node.word < word
      self.count = count + 1 if node.word == word
      insert_right(node) if node.word > word
    end

Travel Itinerary Algorithm in Ruby

I've found a great new site for interesting and challenging programming exercises called TalentBuddy. Today I completed a fairly straight forward algorithm to reconstruct a travel itinerary from a pair of parallel arrays containing all the history departures and destinations. One of the neat things about TalentBuddy is that they expose your work to fairly large data sets (around 10,000 elements) and have a two second timeout, so implementations must be efficient.

My implementation begins by mapping the parallel arrays to a hash of destinations and departures. Then we calculate the first departure by getting the intersection of the two original arrays. Then a loop begins iterating through all destinations, retracing the history. This is made easy by the fact that no destination is visited twice. Finally, we have to handle the final case where the loop terminates when no additional destinations are found, printing the final destination. As always, full source is on GitHub

class PlaneTickets
  def get_journey(departure_ids, destination_ids)
    destination_for = map_departures_to_destinations(departure_ids, destination_ids)

    next_departure = (departure_ids - destination_ids).first

    while next_departure
      puts next_departure

      last_departure = next_departure
      next_departure = destination_for[next_departure]
    end

    puts destination_for[last_departure]
  end
end

Product Pricing Kata in Ruby

Continuing along with Dave Thomas's kata series, I'd like to share my implementation of the Product Pricing kata where we're asked to implement a checkout system that accepts rules for different pricing strategies. This immediately reminded me of my FizzBuzz implementation. In the end it was actually a fairly straight forward implementation of the Strategy pattern. The more challenging part of the exercise was extracting the actual pricing rules from the supplied test suite; a user story is often easier to read than a test of very specific behavior.

In the end, I was pleased with the rule set I implemented. For the full solution, please visit GitHub.

def rules
    [
        QuantityDiscountRule.new(sku: "A", quantity: 3, price: 30),
        QuantityDiscountRule.new(sku: "B", quantity: 2, price: 15),
        RegularPriceRule.new({
                                 "A" => 50,
                                 "B" => 30,
                                 "C" => 20,
                                 "D" => 15
                             })
    ]
end

Data Munging Kata in Ruby

Back in 2007, Dave Thomas posted a series of katas that continue to have an enduring appeal. The katas ranged from algorithm implementations to thinking exercises. This Data Munging kata had a particularly real world flare by focusing on data munging and algorithm reuse.

In short, the kata asks you to parse two data files and determine the minimum variance between two fields in each data set. The idea is to implement a solution for the first data set without reuse in mind. Next, implement a solution for the second data set and extract out the common, minimum variance algorithm between the two solutions. Nice!

I was pleased with my solution of passing in a data structure to my SpreadCalc class as well as the min_method and max_method the class could use to query the data structure to determine variance. This design would allow the class to be used on any data set that could respond to a method call and allow for the extension into all sorts of calculations related to minimums and maximums in a dataset.

class SpreadCalc
  def initialize(spread_data: spread_data, max_method: max_method, min_method: min_method)
    @spread_data = spread_data
    @max_method = max_method
    @min_method = min_method
  end

  def minimum
    min_index = 0
    min_spread = calc_spread(spread_data[min_index])

    spread_data.each_with_index do |data, i|
      spread = calc_spread(data)
      if spread < min_spread
        min_index = i
        min_spread = spread
      end
    end

    spread_data[min_index]
  end
end

I was also able to extract out a common algorithm for parsing the data files even though they were in slightly different formats. Although not intentional, I was in the mindset of extracting common functionality and the duplication was quickly obvious. I suppose that's the point of the kata! You can find the full source for my implementation on Github.

FizzBuzz in Ruby

FizzBuzz is a common and simple exercise in implementing the Strategy pattern. A brief synopsis of the Kata is as follows:

Print the numbers one through 100.
If the number is divisible by 3, print FIZZ.
If the number is divisible by 5, print BUZZ.
If the number is divisible by both, print FIZZBUZZ.

Using Ruby, the algorithm for this is quite straight forward using conditionals:

(1..100).each do |i|
  if i%3==0 and i%5==0
    puts "FIZZBUZZ"
  elsif i%3==0
    puts "FIZZ"
  elsif i%5==0
    puts "BUZZ"
  else
    puts i
  end
end

The kata only becomes interesting when you add an additional requirement; don't use conditionals. And of course, test drive your implementation. You can see my implementation on GitHub. I implemented two classes for processing a digit: Fizz and Buzz. These processors responded to process and processable? and were injected into a FizzBuzzRunner class along with the range. Additionally a default processor PassThrough was injected to the runner, which would be applied if no other processor was applicable and shared the same interface as the other processors.

The runner would query applicable_processors, asking each if the digit was processable?. If no processor was applicable, it would use the default, PassThrough. After collecting the applicable_processors, the results_from each processor were collected into an array. This allowed my final algorithm algorithm to read like well written prose.

class FizzBuzzRunner

  def initialize(range: range, processors: processors, default_processor: default_processor)
    @range = range
    @processors = processors
    @default_processor = default_processor
  end

  def as_string
    as_array.join(" ")
  end

  def as_array
    range.collect { |i| results_from(applicable_processors(i), i) }
  end
end

Rails transposing day and month after upgrading Ruby 1.8.7

If you're wondering why your month and day are being transposed when saved in your database, you're likely:

• Using a text field input for dates (likely with some JavaScript date picker)
• Using American style date formatting (mm/dd/YYYY)
• Upgrading from Ruby 1.8.7

If you meet these criteria you'll find that American style dates get parsed incorrectly in Ruby 1.9+ because of Ruby 1.9.x's new date parsing strategy. Unbelievably, this change effectively does away with American style date parsing in Ruby 1.9.x and Rails has happily followed suit!

american_date to the rescue!

After trying and failing to restore American style date parsing using timeliness, delocalize, and i18n_alchemy, I found american_date. If you look at the implementation, it is straight forward and restores backwards compatibility by simply adding a line to your Gemfile. Enjoy the return to sanity!

With Ruby 1.8.7 going EOL this month, and Rails 2.3.x and older losing support for even severe security issues, it's time to bust out your upgrade-foo for those old Rails apps. Of course, this is a tried and true topic, with many resources, most notably Railscast #225. Good luck with your upgrades!

Profile Ruby with ruby-prof and KCachegrind

This week I was asked to isolate some serious performance problems in a Rails application. I went down quite a few paths to determine how to best isolate the issue. In this post I want to document what tools worked most quickly to help find offending code.

Benchmarks

Before any work begins finding how to speed things up, we need to set a performance baseline so we can know if we are improving things, and by how much. This is done with Ruby's Benchmark class and some of Rail's Benchmark class.

The Rails guides would have you setup performance tests, but I found this cumbersome on this Rails 2.3.5 application I was dealing with. Initial attempts to set it up were unfruitful, taking time away from the task at hand. In my case, the process of setting up the test environment to reflect the production environment was prohibitively expensive, but if you can automate the benchmarks, do it. If not, use the logs to measure your performance, and keep track in a spreadsheet. Regardless of benchmarking manually or automatically, you'll want to keep some kind of log of the results keeping notes about what changed in each iteration.

Isolating the Problem

As always, start with your logs. In Rails, you get some basic performance information for free. Profiling code slows down runtime a lot. By reviewing the logs you can hopefully make a first cut at what needs to be profiled, reducing already long profile runs. For example, instead of having to profile an entire controller method, by reading the logs you might notice that it's just a particular partial which is rendering slowly.

Taking a baseline benchmark

Once you've got a sense of where the pain is, it's easy to get a benchmark for that slow code as a baseline.

1 2 3 4 5 6 7

module SlowModule   def slow_method     benchmark "SlowModule#slow_method" do       #my slow code     end   end end

Look to your log files to see results. If for some reason, you're outside your Rails enviornment, you can use Ruby's Benchmark class directly.

1 2 3 4 5

require 'benchmark' result = Benchmark.ms do   #slow code end puts result

This will tell you the process time in milliseconds and give you a precise measurement to compare against.

Profiling with ruby-prof

First, setup ruby-prof. Once installed, you can add these kinds of blocks around your code.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

require 'ruby-prof'   module SlowModule   def slow_method     benchmark "SlowModule#slow_method" do       RubyProf.start       # your slow code here       results = RubyProf.end     end     File.open "#{RAILS_ROOT}/tmp/SlowModule#slow_method_#{Time.now}", 'w' do |file|       RubyProf::CallTreePrinter.new(results).print(file)     end   end end

Keep in mind that profiling code will really slow things down. Make sure to collect your baseline both with profiling and without, to make sure you're doing apples-to-apples comparison.

By default ruby-prof measures process time, which is the time used by a process between any two moments. It is unaffected by other processes concurrently running on the system. You can review the ruby-prof README for other types of measurements including memory usage, object allocations and garbage collection time.

If you choose to measure any of these options, make sure your Ruby installation has the tools a profiler needs to collect data. Please see the Rails guides for guidance on compiling and patching Ruby.

Interpreting the Data with KCachegrind

At this point you should have a general sense of what code is slow having reviewed the logs. You've got a benchmark log setup with baseline measurements to compare to. If you're going to Benchmark while your profiling, make sure your baseline includes the profile code; it will be much slower! Remember we want an apples-to-apples comparison! You're ready to start profiling and identifying the root source of the performance problems.

After manually or automatically running your troubled code with the profiling block above, you can open up the output from ruby-prof and quickly find it not to be human friendly. Fortunately, KCachegrind turns that mess into something very useful. I found that my Ubuntu installation had a package for it already built, so installation was a breeze. Hopefully things are as easy for you. Next simply open your result files and start reviewing there results.

The image above shows what's called a "call graph" with the percentages representing the relative amount of time that method uses for the duration of the profile run. The CacheableTree#children method calls Array#collect and takes up more then 90% of the runtime. The subsequent child calls are relatively modest in proportion. It's clear we can't modify Array#collect so let's look at CacheableTree#children.

1 2 3 4 5 6 7

module CacheableTree   def children(element = @root_element)     full_set.collect { |node| if (node.parent_id == element.id)       node     }.compact   end end

Defined elsewhere, full_set is an array of Ruby objects. This is common performance optimization in Rails; collecting data looping through arrays works well with a small data set, but quickly becomes painful with a large one. It turned out in this case that full_set had 4200+ elements. Worse yet the children method was being called recusrively on each of them. Yikes!

At this point I had to decide how to optimize. I could go for broke and completely break the API and try and clean up the mess, or I could see if I could collect the data more quickly, some other way. I looked at how the full_set was defined and found I could modify that query to return a subset of elements rather easily.

1 2 3 4 5

module CacheableTree   def children(element = @root_element)     FormElement.find_by_sql(...) #the details aren't important   end end

By collecting the data directly via a SQL call, I was able to cut my benchmark by about 20%. Not bad for a single line change! Let's see what the next profile told us.

The above is another view of the profile KCachegrind provides. It's essentially the same information, but in table format. There were a few indicators that my optimization was helpful:

• The total process_time cost had dropped
• The amount of time spent in each function seemed to better distributed - I didn't have a single method soaking up all the process time
• Most of the time was spent in code wasn't mine!

Although, we still saw 66% of time spent in the children method, we could also see that 61% of the time was spent in ActiveRecord::Base. Effectively, I had pushed the 'slowness' down the stack, which tends to mean better performance. Of course, there were LOTS of database calls being made. Perhaps some caching could help reduce the number of calls being made.

1 2 3 4 5 6

module CacheableTree   def children(element = @root_element)     @children ||= {}     @children[element] ||= FormElement.find_by_sql(...) #the details aren't important   end end

This is called memoization and let's us reuse this expensive method's results within the page load. This method took another 10% off the clock against the baseline. Yay!

Knowing When to Stop

Performance optimization can be really fun, especially once all the infrastructure is in place. However, unless you have unlimited budget and time, you have to know when to stop. For a few lines of code changed, the client would see ~30% performance improvement. It was up to them to decide how much further to take it.

If allowed, my next step would be to make use of the applications existing dependence on redis, and add the Redis-Cacheable gem. It allows you to marshal Ruby objects in and out of a redis server. The application already makes extensive use of caching, and this page was no exception, but when the user modified the page in a way that expired the cache, we would hit this expensive method again, unnecessarily. Based on the call graph above, we could eliminate another ~66% of the call time, and perhaps, by pre-warming this cache, could help the user to minimize the chances of experiencing the pain of slow browsing!

Deconstructing an OO Blog Designs in Ruby 1.9

I've become interested in Avdi Grimm's new book Object on Rails, however I found the code to be terse. Avdi is an expert Rubyist and he makes extensive use of Ruby 1.9 with minimal explanation. In all fairness, he lobbies you to buy Peter Cooper's Ruby 1.9 Walkthrough. Instead of purchasing the videos, I wanted to try and deconstruct them myself.

In his first chapter featuring code, Mr. Grimm creates a Blog and Post class. For those of you who remember the original Rails blog demo, the two couldn't look more different.

Blog#post_source

In an effort to encourage Rails developers to think about relationships between classes beyond ActiveRecord::Relation, he creates his own interface for defining how a Blog should interact with a "post source".

1 2 3 4 5 6 7 8 9 10

# from http://objectsonrails.com/#sec-5-2 class Blog   # ...   attr_writer :post_source       private   def post_source     @post_source ||= Post.public_method(:new)   end end

The code above defines the Blog class and makes available post_source= via the attr_writer method. Additionally, it defines the attribute reader as a private method. The idea being that a private method can be changed without breaking the class's API. If we decide we want a new default Post source, we can do it safely.

The magic of this code is in defining the post source as a class's method, in this case, Post.public_method(:new). The #public_method method is defined by Ruby's Object class and is similar to #method method. In short, it gives us a way of not directly calling Post.new, but instead, referring to the method that's responsible for creating new posts. This is logical if you remember that the name of this method is #post_source.

Now let's look how he puts post_source into action.

1 2 3 4 5 6 7 8 9

class Blog   # ...   def new_post     post_source.call.tap do |p|       p.blog = self     end   end   # ... end

During my first reading, it wasn't clear at all what was going on here, but if we remember that post_source is responsible for returning the method need to "call", we know that post_source.call is equivalent to Post.new. For the sake of clarity-while-learning for those not familiar with post_source.call, let's substitute it with something more readable so we can understand how tap is being employed.

1 2 3 4 5 6 7 8

class Blog   # ...   def new_post     Post.new.tap do |p|       p.blog = self     end   end end

The tap method is available to all Ruby objects and serves as a way to have a block "act on" the method's caller and return the object called. Per the docs, "the primary purpose of this method is to 'tap into' a method chain, in order to perform operations on intermediate results within the chain". For some examples on using tap see MenTaLguY's post on Eavesdropping on Expressions. As he says in his post, "you can insert your [code] just about anywhere without disturbing the flow of data". Neat.

In this case, it's being used to tap into the process of creating a new blog post and define the blog to which that post belongs. Because tap returns the object it modifies, #new_post returns the post now assigned to the blog.

Brining it All Together

Avdi's approach may seem cumbersome at first, and it is compared to "the Rails way." But in general, that's the whole point of Object on Rails; to challenge you to see beyond a generic solution to a problem (in this case defining relationships between classes) so you can build more flexible solutions. Let's see some interesting things we might be able to do with this more flexible Blog class. We can imagine this same Blog class being able to handle posts from all sorts of different sources. Let's see if we can get creative.

1 2 3 4 5 6 7 8

class EmailPost < ActionMailer::Base   def receive(message)     @blog = Blog.find_by_owner_email(message.from)     @blog.post_source = EmailPost.public_method(:new)     @email_post = @blog.new_post(params[:email_post])     @email_post.publish   end end

With this little snippet, we're able to use the Blog class to process a different sort of post. We simply let the blog know the method to call when we want a new post and pass along the arguments we'd expect. Let's see if we can think of something else that's creative.

1 2 3 4 5 6 7 8 9 10 11 12 13

require 'feedzirra' # execute regularly with cronjob call like curl -d "blog_id=1&url=http://somefeed.com" http://myblog.com/feed_poster"   class FeedPostersController   def create     @feed = Feedzirra::Feed.fetch_and_parse(params[:url])     @blog = Blog.find(params[:blog_id])     @post.post_source = FeedPost.public_method(:new)     @feed.entries.each do |entry|       @blog.new_post(entry)     end   end end

We could imagine the FeedPost.new method being the equivalent of a retweet for your blog using an RSS feed! Try having the blog class doing this with an ActiveRecord association! Seems to me the Blog class might need to get a bit more complex to support all these Post sources which makes post_source.call.tap look pretty good!

Working with Constants in Ruby

Ruby is designed to put complete power into the programmer's hands and with great power comes great responsibility! This includes the responsibility for freezing constants. Here's an example of what someone might THINK is happening by default with a constant.

1 2 3 4 5 6 7 8

class Foo   DEFAULTS = [:a, :b] end   #irb default = Foo::DEFAULTS default << :c Foo::DEFAULTS #=> [:a, :b, :c]  WHOOPS!

As you can see, assigning a new variable from a constant lets you modify what you thought was a constant! Needless to say, such an assumption would be very difficult to track down in a real application. Let's see how we might improve on this design. First, let's freeze our constant.

1 2 3 4 5 6 7

class Foo   DEFAULTS = [:a, :b].freeze end   #irb default = Foo::DEFAULTS default << :c #=>  ERROR can't modify frozen array

Now we'll get very specific feedback about offending code. The question is how can we use our constant now as a starting point for array, and still be able to modify it later? Let's look at some more code.

1 2 3

Foo::DEFAULTS.frozen? #=> true Foo::DEFAULTS.clone.frozen? #=> true, this was my first guess, but it turns out we need... Foo::DEFAULTS.dup.frozen? #=> false

It's worth reading the docs on clone and dup to understand there difference, but in short, clone replicates the internal state of the object while dup creates a new instance of the object. There was one more question I needed to answer; what would happen when I wanted to append another frozen array to a non-frozen array? Let's look to the code again!

1 2 3

default = Foo::DEFAULTS.dup  #not frozen new_default = default + [:c].frozen new_default.frozen? # false

So it seems that the initial state of the object carries the frozen state, allowing you to append frozen arrays without having to dup them. The moral of the story here is don't make assumptions about Ruby! One of the best ways to challenge your assumptions is with unit tests.