Once we knew what the source of the performance issues was, my mentor and I could begin optimizing. From our initial benchmarking, it was clear the get_pictures function needed some work. This is the function responsible for requesting photos with the given search term from Google’s image search API, then downloading them and reading them into memory. Here’s the function before optimization:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 #takes 59.405176 seconds

  def get_pictures
      @photo_tiles = ImageList.new
      limit = 50
      photos_per_query = 10
      api_key = API_KEY
      id = SEARCH_ENGINE_ID
      start = 1
      (1..limit).step(photos_per_query) { |start|
        source = "https://www.googleapis.com/customsearch/v1?q=#{search_term}&cx=#{id}&num=#{photos_per_query}&searchType=image&key=#{api_key}"
        data = JSON.load(open(source))
        (0...photos_per_query).each {|i|
            @photo_tiles.read(data["items"][i]["link"])
        }
      } rescue 'no more images found'
  end

  

The first thing we noticed by browsing through the links Google returned was that some of these images were huge! Since the images are being resized to be used as small tiles in a photo mosaic, the extra time downloading larger images is completely wasted. One option to resolve this issue would be to check the size of the photo before downloading it, but thankfully Google provides size range parameters to restrict the result set to small or medium photos so no checks are necessary. Since we settled on a photo tile size of 10x10 pixels, even the thumbnails worked for our purposes.

We also noticed as the function ran it would seem to get hung up on individual photos. Visiting those links sent us to non-responsive or slow pages. To combat that issue we added a rescue clause to the read statement, so the program would continue on in the case of a bad link.

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

  def get_pictures
      @photo_tiles = ImageList.new
      limit = 50
      photos_per_query = 10
      api_key = API_KEY
      id = SEARCH_ENGINE_ID
      start = 1
      (1..limit).step(photos_per_query) { |start|
        source = "https://www.googleapis.com/customsearch/v1?q=#{search_term}&cx=#{id}&num=#{photos_per_query}&searchType=image&key=#{api_key}"
        data = JSON.load(open(source))
        (0...photos_per_query).each {|i|
            @photo_tiles.read(data["items"][i]["link"])
        }
      } rescue 'no more images found'
  end

Running the whole search process with benchmarking now gives:

1
2
3
4
5
6

$ i.complete_search(10, 10)

=> Getting pictures took 14.296446
resizing pictures took 0.054123
getting picture colors took 0.007894
search took 14.361774

Simply changing the picture size and adding a rescue clause reduced the total time by 75%! However, this example is for a small number of total tiles. My mentor and I decided we could reduce the total time even further by adding more threads to the download process. That way, instead of waiting for each image to download completely before moving on to the next one, they can be downloaded concurrently. Since the download of one image doesn’t depend on any other one, there’s no need to download them one by one. Using more threads speeds up the amount of time the download portion takes.

However, reading the images once they’ve been downloaded has to be done one by one. In the original function the files are being downloaded and read in one line, so we need to separate the downloading from the reading in order to use threading.

For each photo, we create a new thread (Thread.new) to open the image from a link and read it into a temporary file. Then, since all the images need to be finished downloading before we read them, the threads need to be joined using thread.join. Finally, we loop through the temporary files we created and read each one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def get_pictures
  @photo_tiles = ImageList.new
  limit = 50
  photos_per_query = 10
  api_key = API_KEY
  id = SEARCH_ENGINE_ID
  timeout_in_seconds = 1
  threads = []
  start = 1
  (1..limit).step(photos_per_query) { |start|
    source = "https://www.googleapis.com/customsearch/v1?q=#{self.search_term}&cx=#{id}&num=#{photos_per_query}&searchType=image&start=#{start}&key=#{api_key}&imageSize=Medium&fileType=jpg"
    data = JSON.load(open(source))
    (0...photos_per_query).each {|i|
        threads << Thread.new { 
          open("tmp/image_#{start}_#{i}", 'wb') do |file|
            file << open(data["items"][i]["image"]["thumbnailLink"]).read rescue puts 'Cannot read image'
          end
        }
        
    }
  } rescue 'no more images found'

  threads.each do |t|
     t.join
  end

  (1..limit).step(photos_per_query) do |start|
     (0...photos_per_query).each do |i|
        @photo_tiles.read("tmp/image_#{start}_#{i}") rescue puts 'Cannot read image'
     end
  end
end

Now let’s check our performance:

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

$ i.make_mosaic(50, 50, 10, 10)

=> getting pixels took 0.959601
Getting pictures took 4.384112
resizing pictures took 0.055782
getting picture colors took 0.005212
search took 4.448468
matching pixels with image tiles took 0.087612
putting tiles in order took 0.089187
ordering photos took 0.007696
making mosaic took 0.290649
total time 5.883285

Dividing the work among multiple threads reduced the time the get_pictures function took from 14 seconds to 4 seconds. The whole mosaic operation now takes only 6 seconds, down from an original 69. However, this is still for only a small number of photo tiles. Larger mosaics with higher resolution tiles might require more performance improvements.

To learn more about threads in Ruby check out this tutorial from Sitepoint.

During my fellowship at Stack Exchange I’ve been working on a photo mosaic application using Rails and RMagick, a wrapper on ImageMagick for Ruby. The application takes an uploaded image and a search term from the user and returns a mosaic of that image created from google image search results for the given term.

The main issue I ran into when working on this application was how slow it ran. From start to finish the process of creating the mosaic took several minutes, even for a small number of photo tiles. My mentor at Stack Exchange helped me come up with several strategies to tackle this issue and speed up the application.

The first step to improving the performance of the application was discovering exactly which processes were causing it to be slow. This would also provide a baseline performance metric to compare against once we implemented optimizations. In order to do this we added in some simple benchmarks. Before and after each process that was run, I printed out a system timestamp.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def make_mosaic(photo_length, photo_width, tile_length, tile_width)
    time1 = Time.now
    self.get_pixels(photo_length, photo_width)
    time2 = Time.now
    puts "getting pixels took #{time2 - time1}"
    s = Search.new(self.search)
    s.complete_search(tile_length, tile_width)
    time3 = Time.now
    puts "completing search took #{time3 - time2}"
    self.match_pixels(s.photo_tile_colors)
    time4 = Time.now
    puts "matching pixels with image tiles took #{time4 - time3}"
    self.order_tiles(s.resized_photo_tiles)
    time5 = Time.now
    puts "putting tiles in order took #{time5 - time4}"
    m = Mosaic.new
    puts "ordering photos for mosaic"
    photos = m.order_photos(self.ordered_tiles, self.rows, self.cols, tile_length, tile_width)
    puts "making mosaic"
    m.create_mosaic(photos)
    puts "making mosaic took #{Time.now - time5}"
    puts "total time: #{Time.now - time}""
end 

Although writing out the puts statements was time consuming, it gave me great readable output:

1
2
3
4
5
6
7

=> getting pixels took 0.983399
search took 71.075624
matching pixels with image tiles took 0.134034
putting tiles in order took 0.16947
ordering photos took 0.046765
making mosaic took 0.202503
total time 72.611871

Initially I’d thought that assembling the photos into a mosaic has been taking the longest amount of time, but from this initial output, I was able to pinpoint the source of the delay to the photo search function. From there I put further benchmarks into the search function to get more information.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def complete_search(tile_length, tile_width)
  time = Time.now
  self.get_pictures
  time2 = Time.now
  puts "Getting pictures took #{time2 - time}"
  self.resize_pictures(tile_length, tile_width)
  time3 = Time.now
  puts  "resizing pictures took #{time3 - time2}"
  self.average_color_list
  time4 = Time.now 
  puts "getting picture colors took #{time4 - time3}"

end

=> Getting pictures took 59.405176
resizing pictures took 9.876595
getting picture colors took 0.031038
search took 69.316089

By far the slowest operation was downloading the photos and reading them into memory. This was taking 59 seconds out of a total 72 seconds! Now that I had a clear idea of how long the process was taking and which part was the bottleneck, I could begin to optimize. In part two of this post, I’ll show you my next steps.

Rickshaw is a really cool JavaScript graphing library by Shutterstock built on d3. I decided to create a realtime visualization of Citi Bike data from their JSON feed. (It’s still a work in progress, check it out here.)

To set up even a simple graph, you have to download the Rickshaw JavaScript and css files and reference them correctly. The more complicated your graph is the more of these there will be, so be sure you put everything in the right place. In my realtime graph there were many more, but for a basic line graph the links look something like this:

1
2
3
4
5
6
7
8
9

<link type="text/css" rel="stylesheet" href="../src/css/sample.css">
<link type="text/css" rel="stylesheet" href="../src/css/graph.css">
<link type="text/css" rel="stylesheet" href="css/lines.css">

<script src="js/d3.v3.js"></script>

<script src="js/rickshaw.min.js"></script>

<div id="chart"></div>

The next important component is getting the realtime data from the Citi Bike feed. I accomplished this using an AJAX request. The Rickshaw example realtime graph includes a helpful SetInterval function that will repeat the AJAX request at a specificed interval. Once the request is complete I send the data to a callback function that parses and adds it, and the graph.update() function displays the updated graph.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

setInterval( function() {
    newRemoveData(seriesData);
    jQuery.ajax({
        url: citibikeurl,
        type: 'GET',
        dataType: "jsonp",
        crossDomain: true,
        success: function(json){
            sortNeighborhoods(json);
        },
        error: function(){
        // repeats previous datapoint if bike feed request is unsuccessful
           newAddData([seriesData[0]], seriesData[0][seriesData[0].length - 1]["y"]);
           newAddData([seriesData[1]], seriesData[1][seriesData[1].length - 1]["y"]);
           newAddData([seriesData[2]], seriesData[2][seriesData[2].length - 1]["y"]);
        }
    });
    graph.update();

}, 2000 );

Looking at the data, I decided it would be interesting to graph the number of available bikes by area. The callback function classifies each station by its longitude and latitude and adds its bikes to the total count for its respective neighborhood.

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

function sortNeighborhoods(json){
    var midtownBikes = 0;
    var brooklynBikes = 0;
    var downtownBikes = 0;
       for(var i = 0; i < json.length; i++){
            if(json[i]["lng"] >= -73971000 || (json[i]["lat"] <= 40705311 && json[i]["lng"] >= -73999978)){
            brooklynBikes += json[i]["bikes"]
            }else if(json[i]["lat"] > 40740895){
            midtownBikes += json[i]["bikes"]
            }else if(json[i]["lat"] <= 40740895){
            downtownBikes += json[i]["bikes"]
            };
       };
    newAddData([seriesData[0]], midtownBikes);
    newAddData([seriesData[1]], downtownBikes);
    newAddData([seriesData[2]], brooklynBikes);
}

Once you have the data in the graph, Rickshaw has lots of options you can customize, from color palatte to annotations and hover detail. The syntax for these is pretty straightforward and can be found in the documentation and by looking at the example graphs provided on their website.

The next interesting problem I faced was seeding the graph with some recent data before the page rendered so the user didn’t have to wait for the graph to populate. I set up a Postgres database and created a simple rake task to grab the realtime data, just like in my graph, but write it to the database instead of rendering it. That way a rolling log of data would be available to populate the graph.

In order for the data to be current, the rake task needs to be run at regular intervals automatically, which is where the Heroku scheduler add-on comes in. This add-on is free and can be added to your existing heroku application using the command $ heroku addons:add scheduler:standard. Then, in your Heroku dashboard you can specify the rake task you want run and the interval, as often as every 10 minutes. Because I can’t have the task run as often as my data source updates, I added code to interpolate between the most recent points to make the graph smoother.

This post details how I made a simple tic-tac-toe game using Sinatra.

The first step is creating the code that contains the logic of the game. There are a ton of different ways to do this, and Sinatra doesn’t care which way you choose. I decided to make a game class, a board class, and a player class. The game class contains the logic pertaining to turns and the running of the game, initialized with an empty board and two players. The board class stores the gameboard as a 3x3 matrix, updates itself with every turn, and determines when the game has ended in a win, loss, or tie. The player class stores the player attributes like name and marker.

The next step is to move the Ruby logic into a Sinatra application. To make things a little easier, I used Ratpack, a Sinatra boilerplate by Ashley Williams with support for activerecord, sqlite, and twitter bootstrap (even though we won’t be using the database functionality for this application). In the Ratpack schema the models live in the lib directory.

Now we can ignore our tic-tac-toe logic for a little bit and get our pages set up. First we need to define a class that inherits from Sinatra so that we can use all of Sinatra’s functionality in our application. Next create the routes. Each page needs a route in order to render, which we establish here with get statements.

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

# app.rb

module TicTacToeProject
  class App < Sinatra::Application

    #routes
    get '/' do
      erb :index
    end

    get '/play' do
      erb :play
    end

The erb :filename statements are telling Sinatra what to render. In this case that’s the erb files from my views folder. In order to make a board show up in the browser, I need to display each square from my board in my html, which is easy to do using erb. I chose to format the board as three rows with three columns each, but you could just as easily use a table or some other method.

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

<!-- views/play.erb -->

<div class="board">
  <div class="row center">
    <div class="col-md-4">
      <h2><%= game.square(0,0) %></h2> <!-- returns the value in square [0,0] -->
    </div>
    <div class="col-md-4 v">
      <h2><%= game.square(0,1) %></h2>
   </div>
    <div class="col-md-4">
      <h2><%= game.square(0,2) %></h2>
    </div>
  </div>

The only problem is, this erb file has no idea what game is. I need to pass the instance of my game class in my route in order for my views to render it. That looks something like this:

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

# app.rb

module TicTacToeProject
  class App < Sinatra::Application
    @@game = PlayGame.new

    #routes
    get '/' do
      @game = @@game
      erb :index
    end

    get '/play' do
      @game = @@game
      erb :play
    end

Once I’ve created views and routes for all my pages I’m most of the way there, but how do I get input from the user to allow them to play the game? One simple way to receive input from a user and store it for access later is to include a form in the view.

1
2
3
4
5
6

<!-- views/play.erb -->

      <form action="/move" method="get">
        <input type="text" name="move">
        <input type="Submit" value="Play">
      </form>

The text input of the form, which I named “move”, is stored in Sinatra’s params hash automatically. I can access whatever the user typed elsewhere in my program using the params[:move] variable. Now I can update the board with the player’s move before loading the erb in my route.

1
2
3
4
5
6
7

# app.rb

    get '/move' do
      @@game.play(params["move"]) #updates the gameboard with the player's chosen move
      @game = @@game
      erb :move
    end

We’re almost done! Now we can get a move from the player, update the board, and render a page displaying the updated board. However, if you were to run the code using the Shotgun gem you’d soon discover a problem. Every time the player moves the board will update, but when the player goes to make a second move they’ll find their previous move has been erased and the board is blank! The reason for this is that every time Shotgun rereads the Sinatra application to refresh the content it generates a new instance of the class App. So every time it runs, it creates a new instance of the PlayGame class, making a new game rather than updating an in-progress game. Try using Rackup instead, and the game should work as intended.

And now we have a working game! Fix up the views with twitter bootstrap, and we’re all done. You can check out my finished version at amystictactoegame.herokuapp.com.

Ruby has a matrix library that can be used to do simple linear algebra. The Matrix class defines useful methods like transpose, rank, and determinant. This is nice, because a lot of practical problems can be formulated in terms of linear algebra. Say that we have the following data about recently sold homes:

The data has, for each house, the square footage, number of bathrooms, and the price that the house sold for. If you wanted to predict what price another house (not in this data set) might sell for, and you knew its size and bathroom count, you could use the Matrix class to perform a linear regression on the data.

In linear regression we attempt to express our dependent variable (in this case, housing price), as a linear combination of the independent variables (bathrooms and square footage) plus some constant.

For any given triplet of datapoints (square footage, number of bathrooms, and price), the difference between the actual price and the price predicted by our equation, squared is the pointwise error. In order to determine the values of a, b, and c that make the most sense, we choose the values that minimize the total average squared error. If the data can be expressed as an matrix X such that X^TX is invertible, there is an easy formula to get the right values:

where w is the matrix containing the coefficients a, b, and c, X represents the dependent variable matrix, and b represents the independent variable matrix.

With the Ruby matrix class these manipulations will be easy. Creating matrices in Ruby is simple. First add a line to require the matrix library, and you’re ready to get started. Ruby stores each matrix as an array of rows. Just like arrays, the indices of matrix rows and columns start at zero. Don’t forget that all the rows must be the same length for the matrix to be valid.

Here we enter the data from the table into two matrices. Matrices can be instantiated in a variety of ways. I chose to simply list out the rows as nested arrays, and unless specified otherwise that’s what Ruby assumes the input will be. Each row represents a house with square footage in column 1 (the second column since ruby indexes columns from 0) and the number of bathrooms in column 2. The constant value in column 0 is necessary for the calculation of the constant c from our previous equation. The second matrix contains the housing prices. These two matrices are all we need for our calculations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

require 'matrix'

housing_data = Matrix[[1,4000,3], 
                      [1,3000,2], 
                      [1,3800,3], 
                      [1,3200,2], 
                      [1,3542,4], 
                      [1,2348,2],
                      [1,2987,3],
                      [1,4300,4],
                      [1,3342,4],
                      [1,3000,3]
                      ]

housing_prices = Matrix[[400000],
                      [310000],
                      [375000],
                      [315000],
                      [350000],
                      [250000],
                      [300000],
                      [450000],
                      [360000],
                      [320000]
                      ]

So, to get started on our handy equation, let’s transpose X, our housing data matrix. Ruby has a useful function that will transpose a matrix for you, as you can see above.

1
2
3
4
5

x_t = housing_data.transpose

 => Matrix[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
          [4000, 3000, 3800, 3200, 3542, 2348, 2987, 4300, 3342, 3000],
          [3, 2, 3, 2, 4, 2, 3, 4, 4, 3]]

Next we multiply the trasposed matrix by the original housing data matrix. The standard operators of *, +, -, /, and ** perform the corresponding operations on matrices.

1
2
3
4
5

 x_t_x = x_t * housing_data

  => Matrix[[10, 33519, 30],
              [33519, 115320001, 103193],
              [30, 103193, 96]]

We can invert the resulting matrix using the inverse method.

1
2
3
4
5

 x_t_x.inverse

  => Matrix[[(421924847/108574934), (-61017/54287467), (-673863/108574934)],
            [(-61017/54287467), (30/54287467), (-13180/54287467)],
            [(-673863/108574934), (-13180/54287467), (29676649/108574934)]]

Finally, we can get the coefficients matrix with two more multiplication operations. Those fractions look pretty unwieldy, so let’s iterate through the matrix and change them to floating point numbers to get a better idea of what’s going on.

1
2
3
4
5

w = (x_t_x.inverse * x_t) * housing_prices

 => Matrix[[(1018615352500/54287467)],
          [(4850790000/54287467)],
          [(447540942500/54287467)]]

Matrix.each reads left to right, then down the rows by default, but you can also specify options, for instance only reading down the diagonal (row index == column index). Since here we only have a simple [3x1] matrix, the default method works just fine. Rather than initializing and returning a new matrix, we can also just use the collect method in place of each to return the new matrix automatically.

1
2
3
4
5
6
7

w.collect do |i|
  i.to_f.round(2)
end

=> Matrix[[18763.36],
          [89.35],
          [8243.91]]

And there we have the coefficients in a matrix. The constant, c, is in row 0, the square footage coefficient, b, is in row 1, and the bathroom coeffient, a, is in row 2 (note that this mirrors the column structure of the original data matrix). As we would expect, both a and b are positive since higher square footage and more bathrooms are both associated with a higher price. Additionally, the magnitude of the coefficient for square footage (row 1) is much smaller than the one for bathrooms, since square footage is a much bigger number than bathroom count. Let’s revisit our original example of a 3500 square foot house with 3 bathrooms and determine the predicted price.

1
2
3

f(x,y) = 8243.91*3 + 89.35*3500 + 18763.36

 => 356220.08999999997

Our equation predicts that this house would sell for $356,220, which makes sense compared to the other points in our data set.

For more information on using matrices in Ruby checkout the Ruby Documentation and this helpful post from RubyLearning Blog.