rubendiazjorge.me

Roman Numerals: a tale of Ruby performance improvement

Posted on July 9, 2016 by Chipairon / 0 Comment

There are an infinite number of opportunities to learn and improve your skills as a developer. I like to take some time now and then to do it consciously, so I pick a topic and go at it.
The trigger this time was a Sandi Metz newsletter entry about the Roman Numerals quiz. (That drove me to take interest in Ruby refinements, but I digress).
I remember trying to solve that same problem some years back when first learning ruby. I found it here, as part of ruby quiz blog and the associated book.

This time, a part of the proposed solution got me thinking:

  def roman_table_original
    return @roman_table if @roman_table

    roman_map = {
      1    => "I",
      4    => "IV",
      5    => "V",
      9    => "IX",
      10   => "X",
      40   => "XL",
      50   => "L",
      90   => "XC",
      100  => "C",
      400  => "CD",
      500  => "D",
      900  => "CM",
      1000 => "M"
    }

    @roman_table = Array.new(3999) do |index|
      target = index + 1
      roman_value = roman_map.keys.sort { |a, b| b <=> a }.inject("") do |accumulator, div|
        times, target = target.divmod(div)
        accumulator << roman_map[div] * times
      end
      roman_value
    end
    @roman_table
  end

def roman_table_original

return @roman_table if @roman_table

roman_map = {

1 => "I",

4 => "IV",

5 => "V",

9 => "IX",

10 => "X",

40 => "XL",

50 => "L",

90 => "XC",

100 => "C",

400 => "CD",

500 => "D",

900 => "CM",

1000 => "M"

}

@roman_table = Array.new(3999) do |index|

target = index + 1

roman_value = roman_map.keys.sort { |a, b| b <=> a }.inject("") do |accumulator, div|

times, target = target.divmod(div)

accumulator << roman_map[div] * times

end

roman_value

end

@roman_table

end

Oh, this can be optimized! In different ways. So I tried.

First question: why is it needed to sort the same array 4000 times? Oh, because the ROMAN_MAP is in ascending order and we need it in descending order. Let’s put the original array in descending order to begin with, and then there is no need for reversing it each iteration:

  def roman_table_inverted
    return @roman_table if @roman_table

    roman_map = {
      1000 => "M",
      900  => "CM",
      500  => "D",
      400  => "CD",
      100  => "C",
      90   => "XC",
      50   => "L",
      40   => "XL",
      10   => "X",
      9    => "IX",
      5    => "V",
      4    => "IV",
      1    => "I"
    }

    @roman_table = Array.new(3999) do |index|
      target = index + 1
      roman_value = roman_map.keys.inject("") do |accumulator, div|
        times, target = target.divmod(div)
        accumulator << roman_map[div] * times
      end
      roman_value
    end
    @roman_table
  end

def roman_table_inverted

return @roman_table if @roman_table

roman_map = {

1000 => "M",

900 => "CM",

500 => "D",

400 => "CD",

100 => "C",

90 => "XC",

50 => "L",

40 => "XL",

10 => "X",

9 => "IX",

5 => "V",

4 => "IV",

1 => "I"

}

@roman_table = Array.new(3999) do |index|

target = index + 1

roman_value = roman_map.keys.inject("") do |accumulator, div|

times, target = target.divmod(div)

accumulator << roman_map[div] * times

end

roman_value

end

@roman_table

end

Is it better? How do I know? By how much? Let’s benchmark it with benchmark-ips (bigger is better :P):

       original_keys     25.252  (±23.8%) i/s -    112.000  in   5.032620s
       inverted_keys     37.760  (±37.1%) i/s -    140.000  in   5.056769s

1 2	original_keys 25.252 (±23.8%) i/s - 112.000 in 5.032620s inverted_keys 37.760 (±37.1%) i/s - 140.000 in 5.056769s

Ok, what else? roman_map.keys does not change and is called for every iteration. It can be put outside the loop:

    keys = roman_map.keys
    @roman_table = Array.new(3999) do |index|
      target = index + 1
      roman_value = keys.inject("") do |accumulator, div|
        times, target = target.divmod(div)
        accumulator << roman_map[div] * times
      end
      roman_value
    end

keys = roman_map.keys

@roman_table = Array.new(3999) do |index|

target = index + 1

roman_value = keys.inject("") do |accumulator, div|

times, target = target.divmod(div)

accumulator << roman_map[div] * times

end

roman_value

end

       original_keys     23.618  (±25.4%) i/s -    106.000  in   5.017655s
       inverted_keys     37.309  (±29.5%) i/s -    162.000  in   5.043760s
   keys_outside_loop     41.393  (±31.4%) i/s -    168.000  in   5.224296s

original_keys 23.618 (±25.4%) i/s - 106.000 in 5.017655s

inverted_keys 37.309 (±29.5%) i/s - 162.000 in 5.043760s

keys_outside_loop 41.393 (±31.4%) i/s - 168.000 in 5.224296s

Ok, not too big of an improvement. Now take a closer look at the behaviour implemented for each key (called ‘div’ in the code). If the div is greater than the target number, the division is always 0 and the accumulator does not change. We can make the comparison upfront, saving unnecessary division, modulus, multiplication by 0 and trying to add empty strings to the accumulator:

    keys = roman_map.keys
    @roman_table = Array.new(3999) do |index|
      target = index + 1
      roman_value = keys.inject("") do |accumulator, div|
        if div > target
          next
        else
          times, target = target.divmod(div)
          accumulator << roman_map[div] * times
        end
      end
      roman_value
    end
    @roman_table

keys = roman_map.keys

@roman_table = Array.new(3999) do |index|

target = index + 1

roman_value = keys.inject("") do |accumulator, div|

if div > target

else

times, target = target.divmod(div)

accumulator << roman_map[div] * times

end

roman_value

end

@roman_table

       original_keys     25.419  (±19.7%) i/s -    122.000  in   5.053339s
       inverted_keys     37.964  (±34.2%) i/s -    150.000  in   5.044594s
   keys_outside_loop     40.720  (±27.0%) i/s -    180.000  in   5.025812s
  no_unnecessary_ops     81.137  (±16.0%) i/s -    400.000  in   5.199823s

original_keys 25.419 (±19.7%) i/s - 122.000 in 5.053339s

inverted_keys 37.964 (±34.2%) i/s - 150.000 in 5.044594s

keys_outside_loop 40.720 (±27.0%) i/s - 180.000 in 5.025812s

no_unnecessary_ops 81.137 (±16.0%) i/s - 400.000 in 5.199823s

Not bad!
Still, a lot of calculations are being repeated over and over. For instance, for the number 324, the “24” part we already calculated when 24 was the target. Also, for 24, we already constructed the 4 part when 4 was the target. We can improve this code by not repeating calculations we already did. This caching should improve the performance significantly:

    keys = roman_map.keys
    @roman_table = []
    (0..3998).each do |index|
      target = index + 1
      roman_value = ""
      keys.each do |div|
        if div > target
          next
        else
          if @roman_table[target-1]
            roman_value << @roman_table[target-1]
            break
          else
            times, target = target.divmod(div)
            roman_value << roman_map[div] * times
          end
        end
      end
      @roman_table << roman_value
    end

keys = roman_map.keys

@roman_table = []

(0..3998).each do |index|

target = index + 1

roman_value = ""

keys.each do |div|

if div > target

else

if @roman_table[target-1]

roman_value << @roman_table[target-1]

break

else

times, target = target.divmod(div)

roman_value << roman_map[div] * times

end

@roman_table << roman_value

end

       original_keys     25.419  (±19.7%) i/s -    122.000  in   5.053339s
       inverted_keys     37.964  (±34.2%) i/s -    150.000  in   5.044594s
   keys_outside_loop     40.720  (±27.0%) i/s -    180.000  in   5.025812s
  no_unnecessary_ops     81.137  (±16.0%) i/s -    400.000  in   5.199823s
         with_memory    228.699  (± 7.9%) i/s -      1.144k in   5.036505s

original_keys 25.419 (±19.7%) i/s - 122.000 in 5.053339s

inverted_keys 37.964 (±34.2%) i/s - 150.000 in 5.044594s

keys_outside_loop 40.720 (±27.0%) i/s - 180.000 in 5.025812s

no_unnecessary_ops 81.137 (±16.0%) i/s - 400.000 in 5.199823s

with_memory 228.699 (± 7.9%) i/s - 1.144k in 5.036505s

And indeed it does speed up things!

The code is available on github.

This is about learning and improving. Not all the code in an needs to be super performant, and surely this method didn’t from the perspective of a beginner rubyist starting to grasp the language.
Learn to pick the right battles. Try to improve the parts that cause the most pain, that are used the most often. And remember that for the most part, performance tuning is a tradeoff between computation, memory and readability/maintainability.

Learning and Improving/Quick Tips

On React performance, shallowCompare and Javascript equality

Posted on May 29, 2016 by Chipairon / 0 Comment

While developing a complex ui with React I noticed that performance was being worse than expected. Following the official recommendations I started overriding shouldComponentUpdate and adding shallowCompare.

It turns out it was not enough to solve the problem. In a nested component that was rendering a list of items, adding a new element was causing the update for all of them (and not just them but their whole subtrees). Here it is a JsFiddle illustrating the problem. Look at the console when adding a new element.

The caveat is this:

{ "foo": "bar" } === { "foo": "bar" } // ==> false

1	{ "foo": "bar" } === { "foo": "bar" } // ==> false

If the prop is an object but the references are not the same, then equality fails and it gets re-rendered.

One simple solution is to use simple props instead of objects. With the help of the spread operator from ES6 this is quite easy:

Another solution is to use an external library like Immutable.js that has a method to query data equality:

const map1 = Immutable.Map({ foo: 'bar' });
const map2 = Immutable.Map({ foo: 'bar' });
console.log(Immutable.is(map1, map2)); // ==> true!

const map1 = Immutable.Map({ foo: 'bar' });

const map2 = Immutable.Map({ foo: 'bar' });

console.log(Immutable.is(map1, map2)); // ==> true!

But it can only go so far. If a property/value of the object is a complex object like an array, data equality will still fail:

const map1 = Immutable.Map({ foo: 'bar' });
const map2 = Immutable.Map({ foo: 'bar' });
console.log(Immutable.is(map1, map2)); // true!

const map3 = Immutable.Map({ foo: [1] });
const map4 = Immutable.Map({ foo: [1] });
console.log(Immutable.is(map3, map4)); // false! (╯°□°)╯︵ ┻━┻

const map1 = Immutable.Map({ foo: 'bar' });

const map2 = Immutable.Map({ foo: 'bar' });

console.log(Immutable.is(map1, map2)); // true!

const map3 = Immutable.Map({ foo: [1] });

const map4 = Immutable.Map({ foo: [1] });

console.log(Immutable.is(map3, map4)); // false! (╯°□°)╯︵ ┻━┻

Learning and Improving/Quick Tips

Do not crash the Agent!

Posted on September 12, 2015 by Chipairon / 4 Comments

In order to stress test our streaming infrastructure I have developed an Elixir application that manages several concurrent interactors and uses an Agent to maintain state.

The Agent abstraction is very potent but be careful about the code run in the Agent process. If this code crashes, the agent is terminated, losing all its data :/

To illustrate this, imagine you are launching several concurrent tasks and use an Agent to store partial results from each task. Later on, you want to do some computation for each partial result and decide to run the code on the agent process itself. In this code I am making the agent crash causing an arithmetic exception:

This can be prevented making the code run on the agent resilient to exceptions or running the code on the client instead of the agent, so even if the client process crashes, the agent is still healthy.
In this example, I am preventing the crash on the code run on the agent:

EDIT: As José Valim pointed out in the comments, try/catch should avoided whenever possible. My point (and my self-reminder) is: be careful with the code you run on an agent process, as the data will be lost if it crashes.

Learning and Improving/Open Source and Community

Faster Rails JSON responses removing JBuilder and View rendering

Posted on March 23, 2015 by Chipairon / 2 Comments

On some Rails JSON api calls listing collections of items, I have been using jbuilder and jbuilder view partials to DRY out the code and it has been working well.

But on collection views, specially if they are complex and require a big amount of data per item, it takes quite some time and I thought maybe there is an alternative approach. There is: use POROs (Plain Old Ruby Objects). And it is almost twice as fast. Let me show you an example:

Imagine an app about movie reviews. People can review movies and others can “like” the review. An API call has to return some aggregated data about recent reviews:

rating
headline of the review
likes count
Some info about the author (name, avatar)
Some info about the movie reviewed (title, year, img)
Latest 3 likers (users) (name, avatar)

Using Jbuilder as per the documentation, I would do something similar to this:

# reviews.jbuilder:
json.reviews @reviews.each do |review|
  json.partial! review
end

# _review.jbuilder:
json.(review, :id, :rating, :abstract, :likes_count)
json.author do
  json.partial! "users/minimal_user", user: review.user
end
json.movie do
  json.partial! "movies/minimal_movie", movie: review.movie
end
json.some_likers review.review_likes.take(3) do |like|
  json.partial! "users/minimal_user", user: like.user
end

# reviews.jbuilder:

json.reviews @reviews.each do |review|

json.partial! review

end

# _review.jbuilder:

json.(review, :id, :rating, :abstract, :likes_count)

json.author do

json.partial! "users/minimal_user", user: review.user

end

json.movie do

json.partial! "movies/minimal_movie", movie: review.movie

end

json.some_likers review.review_likes.take(3) do |like|

json.partial! "users/minimal_user", user: like.user

end

Note: minimal model representation consists of the minimum attributes necessary to show in listings, as opposed to what will return a call to “/show” the concrete resource with a lot more verbose response.

It is faster to achieve the same result using Ruby objects that build in a Hash the desired representation:

# Review json presenter:
class ReviewPresenter < JsonPresenters
  def self.minimal_hash(review)
    node = hash_for(review, %w(id rating abstract likes_count))
    node[:author] = UserPresenter.minimal_hash(review.user)
    node[:movie] = MoviePresenter.minimal_hash(review.movie)
    node[:some_likers] = review.review_likes.last(3).map do |like|
      UserPresenter.minimal_hash(like.user)
    end
    node
  end
end

#JsonPresenter (base class):
class JsonPresenters

  # A helper to extract attributes from an object,
  # calling getters on it.
  # Example:
  #   hash_for(user_instance, ["email"])
  #     -> calls user_instance.email
  #     The result will be: { email: "the email" }
  def self.hash_for(model, attributes)
    res = {}
    attributes.map do |attr|
      res[attr] = model.send attr
    end
    res
  end
end

# Review json presenter:

class ReviewPresenter < JsonPresenters

def self.minimal_hash(review)

node = hash_for(review, %w(id rating abstract likes_count))

node[:author] = UserPresenter.minimal_hash(review.user)

node[:movie] = MoviePresenter.minimal_hash(review.movie)

node[:some_likers] = review.review_likes.last(3).map do |like|

UserPresenter.minimal_hash(like.user)

end

node

end

#JsonPresenter (base class):

class JsonPresenters

# A helper to extract attributes from an object,

# calling getters on it.

# Example:

# hash_for(user_instance, ["email"])

# -> calls user_instance.email

# The result will be: { email: "the email" }

def self.hash_for(model, attributes)

res = {}

attributes.map do |attr|

res[attr] = model.send attr

end

res

end

Then the controller does not render a view, just converts to json the root component:

class ReviewsController < ApplicationController
  # Using jbuilder and partial views
  def popular_with_partial_views
    @reviews = Review.popular_fake(100)
    render :reviews
  end

  # Using Ruby hashes
  def popular_without_partial_views
    @reviews = Review.popular_fake(100)
    render json: ReviewPresenter.minimal_hash_for_collection(@reviews)
  end
end

class ReviewsController < ApplicationController

# Using jbuilder and partial views

def popular_with_partial_views

@reviews = Review.popular_fake(100)

render :reviews

end

# Using Ruby hashes

def popular_without_partial_views

@reviews = Review.popular_fake(100)

render json: ReviewPresenter.minimal_hash_for_collection(@reviews)

end

In the comparisons I have done I have used fake data constructed on the fly so the database access is left out of the equation.
You can find the full example rails application on my github repository and try for yourself.

Uncategorized

Phoenix framework with Twitter realtime demo

Posted on March 23, 2015 by Chipairon / 0 Comment

I have been working on a demo app to learn how Elixir works and how it would be to work on a Phoenix app. In particular its realtime capabilities using Channels, an abstraction on top of websockets.

The Phoenix Framework highlights its ability to scale and enables realtime connectivity so trying out a Twitter integration based on geolocation seemed a good fit to get my hands dirty.

It has been a good excuse to get to know better the fantastic Leaflet interactive map library.

You can find the demo here, where the implementation is described in more detail.

Uncategorized

Slimming my gulp seed: use CDNs to do their job

Posted on March 7, 2015 by Chipairon / 0 Comment

Developing front end applications with Gulp is delightful.

Some time ago I investigated how other people were configuring gulp projects and made a fork with my own opinions.
My seed used Backbone, Marionette, Underscore and jQuery and I had them added to the browserify build task.

Turns out, this is not so great because the size of the bundle is HUGE.

In this new version, I use those libraries from well known CDNs, so in most cases they will be already on the browser cache. This makes build times really fast and load times a breeze.

You can find my gulp seed on github.

Open Source and Community/Quick Tips

Configuring Nginx to work with websockets (Phoenix Channels)

Posted on March 2, 2015 by Chipairon / 0 Comment

I am learning a bit of Elixir lately and I am using websockets from the Phoenix web framework.
Everything worked on phoenix.server on localhost but I was unable to make it work when putting the app behind an Nginx proxy :(

400 Bad Request trying to connect to WebSocket server

I thought I did something wrong on the Elixir side because, you know, I am a newbie on that side.
Turns out nginx has to be configured with some extra information to work with websockets:

map $http_upgrade $connection_upgrade {
  default upgrade;
  ''      close;
}
server{
  listen 80;
  server_name <your.domain>;

  location / {
    proxy_pass http://localhost:<port>;
    proxy_set_header X-Real-IP $remote_addr;  # http://wiki.nginx.org/HttpProxyModule
    proxy_set_header Host $host;  # pass the host header - http://wiki.nginx.org/HttpProxyModule#proxy_pass
    proxy_http_version 1.1;  # recommended with keepalive connections - http://nginx.org/en/docs/http/ngx_http_proxy_module.html#proxy_http_version
    # WebSocket proxying - from http://nginx.org/en/docs/http/websocket.html
    proxy_set_header Upgrade $http_upgrade;
    proxy_set_header Connection $connection_upgrade;
  }
}

map $http_upgrade $connection_upgrade {

default upgrade;

'' close;

}

server{

listen 80;

server_name <your.domain>;

location / {

proxy_pass http://localhost:<port>;

proxy_set_header X-Real-IP $remote_addr; # http://wiki.nginx.org/HttpProxyModule

proxy_set_header Host $host; # pass the host header - http://wiki.nginx.org/HttpProxyModule#proxy_pass

proxy_http_version 1.1; # recommended with keepalive connections - http://nginx.org/en/docs/http/ngx_http_proxy_module.html#proxy_http_version

# WebSocket proxying - from http://nginx.org/en/docs/http/websocket.html

proxy_set_header Upgrade $http_upgrade;

proxy_set_header Connection $connection_upgrade;

}

I added this to the phoenix github project in case anyone is stuck with this problem.

Learning and Improving

Marionette.JS CompositeView example

Posted on November 28, 2014 by Chipairon / 1 Comment

I have been reading several posts from Deric Bailey lately. He is the creator of Marionette.JS and has good techie advice.

On my journey to learn how to use CompositeViews from Marionette.JS found a link on the official docs pointing to this post from Deric. It was no surprise to me that the samples there were not working. After all, it was posted more than two years ago.

The fix was tiny, but non-obvious to a novice like me: CompositeView inherits from CollectionView and it expects ‘childView’ to be populated instead of ‘itemView’. Another problem from the original fiddle is that it is using non-versioned dependencies so it is sure to be broken again in the future if they are not fixed.

Here is my version of the sample using the compositeView and fixed versions of the libraries:

Learning and Improving

Constant learning: Marionette.JS

Posted on November 20, 2014 by Chipairon / 2 Comments

I am starting to use Marionette.JS on some projects.
I have done some work with Backbone in the past and the reduction of boilerplate and ceremony on Marionette is a delight.

It has been cumbersome to find online examples that actually work. I am sure they fail due to little things and changes from version to version but from a novice perspective it is tough to figure out what the problem is. After all, if I am following an introduction tutorial I don’t have yet the knowledge to know how it is supposed to be properly used :)

So I have been learning in an extrange flow:

Find a tutorial/sample that does something interesting
Try to apply the directions to build a similar, custom sample
Bang my head because my custom sample fails
..try the original sample and realize it was failing on the first place (╯°□°）╯︵ ┻━┻
RTFM and learn from the official docs who it is supposed to do what the sample is trying
Fix both the original sample and my code :)

It is “a” way to learn and I am learning a lot, but I don’t think it is very smooth for newcomers.

Learning and Improving/Open Source and Community

Taming Apple Push Notifications with better error logging on Houston

Posted on August 19, 2014 by Chipairon / 0 Comment

I have been using Houston as a wrapper to send Apple Push Notifications.

It is a great gem but it wasn’t bubbling errors returned from the Apple Push Notification Server so it was difficult to know what was wrong when messages where not being sended to iOS devices.

I created a pull request to solve this and now the feature is available to anyone using the gem.

I love the ruby community <3