Using NArray to crunch the Instagram Engineering Challenge

Recently Instagram put forward a challenge: Instagram Engineering Challenge: The Unshredder.

There are some solutions out there already:

That's just in the first page of Google hits.

Here at Centro, the team all challenged each other and shared our solutions. Here's mine: https://github.com/timgaleckas/instagram_challenge.

When I solved the problem, I was pretty proud of myself until one of the wiseguys here threw this image at my code: Shredded Mona Lisa.

Of course, my original code fell over. It took 21 seconds to to un-shred an image that large. It became a point of pride to see how fast I could get it running.

I tried:

  • Caching
    • This cut off 3 seconds for a speed up to 18 seconds.
  • Unrolling loops and skipping pixels
    • This cut the run time all the way down to 3 seconds.
    • It, however, cost me some resolution.
    • It failed if I started at the second pixel instead of the first.
  • Switching to NArray
    • This ran with comparable speed (5 seconds.)
    • This does not sacrifice any of the resolution.
  • Reducing the scope of the check
    • This reduced the time back to the blazing fast sub 3 second time.
    • This does not sacrifice any vertical resolution.

If you take a careful look at the code and do the math, you'll see that switching to NArray allowed me to go from only checking 100 pixels for each column to checking the full 1549 pixels while staying within one second of the time for the method that picks and chooses pixels to check.

Seems pretty powerful. That's why I'd like to give you a little explanation of how we're using NArray in this case and hopefully give you an incredibly powerful tool in your ruby tool box.

The loop we're trying to optimize is:

def percentage_pixels_that_are_edgelike(other_column)
  @percentage_by_other_column ||= {}
  return @percentage_by_other_column[other_column] if @percentage_by_other_column[other_column]
  # this line is doing all the work
  @percentage_by_other_column[other_column] = (0...pixels.size).select{|index|pixel_is_edgelike?(index, other_column)}.size.to_f / pixels.size
end

def pixel_is_edgelike?(index, other_column)
  (self[index+1] && (self[index]-other_column[index]).intensity > (self[index]-self[index+1]).intensity) ||
  (self[index-1] && (self[index]-other_column[index]).intensity > (self[index]-self[index-1]).intensity)
end

We know that creating that inner block that many times is inefficient and we know that using select{}.size is inefficient. That's why my first attempt at optimization was just to unroll the iteration into a simple loop.

What NArray allows us to do, on the other hand, is remove both iteration and math over arrays of data from ruby and push it down to a native extension.

So what used to be:

def add_arrays( array_1, array_2 )
  new_array = []
  array_1.each_index{ |index| new_array[index] = array_1[index] - array_2[index] }
  new_array
end

Turns into:

#we don't even need a method for this but,
def add_narrays( narray_1, narray_2 )
  narray_1 - narray_2
end

And the fact that NArray handles math between multidimensional arrays just as easily allows us to do stuff like this:

[
  [ 1, 3, 3 ],
  [ 2, 1, 3 ],
  [ 2, 2, 1 ]
] +
[
  [ 0, 1, 2 ],
  [ 3, 4, 5 ],
  [ 6, 7, 8 ]
]
->
[
  [ 1, 4, 5 ],
  [ 3, 5, 8 ],
  [ 8, 9, 4 ]
]

and even cooler:

[
  [ 1, 3, 3 ],
  [ 2, 1, 3 ],
  [ 2, 2, 1 ]
] * 2
->
[
  [ 2, 6, 6 ],
  [ 4, 2, 6 ],
  [ 4, 4, 2 ]
]

So instead of using RMagick's Pixel class and defining a custom :+ operator, we convert the array of pixels to a multidimensional array of color values:

NArray.to_na(pixels.map{|p|[p.red.to_f,p.green.to_f,p.blue.to_f]})

Which allows us to find the absolute difference between pixel columns by:

(pixel_array1 - pixel_array2).abs

And we multiply these pixel arrays by the function to convert to intensity:

def intensity_transform(narray)
  #http://www.imagemagick.org/RMagick/doc/struct.html#Pixel
  #The intensity is computed as 0.299*R+0.587*G+0.114*B.
  a = narray * [0.299,0.587,0.114]
  a[0,true] + a[1,true] + a[2,true]
end

This method multiplies each red value by 0.299, each green value by 0.587, each blue value by 0.114, and then adds the resultant arrays together to find pixel intensity.

Adding parallel arrays works naively for values that run horizontally across the arrays, but our formula needs to compare pixels to the top and the bottom of the current pixel.

Given the pixel map:

C1 C2
a0 b0
a1 b1
a2 b2
a3 b3
a4 b4

The formula to check that a2 is closer to the pixel above or below it than to the pixel next to it is: ( (a2 - b2) > (a2 - a1) ) || ( (a2 - b2) > (a2 - a3) )

To set up the data to allow us to use only operations across parallel arrays, we add shifted copies of the first array to our dataset like so:

C1 C2 C1[U] C1[D]
a1 b1 a2 a0
a2 b2 a3 a1
a3 b3 a4 a2

( Notice the removal of the top and bottom row from c1 )

So the formula for any given index i, becomes: ( ( C1[i] - C2[i] ) > ( C1[i] - C1_U[i] ) ) || ( ( C1[i] - C2[i] ) > ( C1[i] - C1_D[i] ) )

The actual NArray code looks like this:

def compute_percentage_pixels_that_are_edgelike( other_column )
  s = @pixels
  o = other_column.pixels
  # NArray[ range_for_dimensions, range_for_rows ]
  s1 = s[0..2,1..-2]
  column_difference = intensity_transform((s1 - o[0..2,1..-2]).abs)
  difference_up     = intensity_transform((s1 - s[0..2,0..-3]).abs)
  difference_down   = intensity_transform((s1 - s[0..2,2..-1]).abs)
  ((column_difference > difference_down).or( column_difference > difference_up )).where.total.to_f / s[0,true].total
end

Notice the 'where' method and the 'total' method.

'where' returns an array of the indices for which the predicate is true and 'total' is the same as the ruby array's size method ( but faster )

Hopefully this has been an enlightening introduction to NArray for some of you. It is a pretty cool library that can challenge the way you think about a problem and throw some pretty crazy speedup into the mix.

I'm not saying that NArray is perfect. Far from it. It has bugs (I ran into a couple just in this short exercise,) is difficult to use, lacking in documentation, and has an api that is far from desired. But what it lacks in frills and polish, it far makes up for in pure speed when it comes to crunching arrays and matrixes of numbers.

I hope it has made it into your ruby toolbox.

Using partials in SproutCore Handlebar views

Handlebars, like Mustache, support partials. And you can use this feature in a SproutCore app, but it takes a little bit of glue code.

We have established the convention that partial files have names that begin with an underscore, just as they do in Rails. We store them in resources/templates along with our other templates.

Add the following code to your app somewhere. We have it in a framework that holds a lot of our SproutCore extensions:

SC.ready(function() {
  SC.keys(SC.TEMPLATES).forEach(function(templateName) {
    var template = SC.TEMPLATES[templateName];

    if (template.rawTemplate && // we only want compiled templates
      templateName.substring(0,1) === '_') {
      Handlebars.registerPartial(templateName.replace('_', ''), template);
      delete SC.TEMPLATES[templateName];
    }
  });
});

Then, to render a partial in another template, use the standard syntax:

{{> partial_name }}

Don’t include the leading underscore in the partial name, and it should just work.

Starting up SproutCore Chicago

Although SproutCore has been around for several years, and we've been using it for projects for a year and a half, it hasn't achieved as much uptake or visibility as one might expect given its age. And while the community is generally helpful, it is fairly small and exists only in IRC and Google Groups (unless you're lucky enough to live in California).

At the beginning of the year we started a new project with SproutCore, and decided to see what we could do to help grow the community. We've now hosted two SproutCore Meetups in Chicago, and are looking forward to hosting more in the future.

Our first event was in March, and there were about 20 people in attendance. We're trying to have two presentations at each meetup, and at this one I talked about what was new in SproutCore 1.5 and Jeff O'Dell talked about using Lewbowski to test SproutCore applications.

Two weeks ago we had a second Meetup, and it also went well. Corey Burrows (one of our lead developers)  gave a really great talk on statecharts, the problems they solve, and how to use them in SproutCore applications. Then Tom Dale from Strobe gave a remote presentation on The Future of SprouteCore, where he announced the SproutCore 2.0 Developer Preview. As far as I know, we were the first people to learn of the release outside of Strobe.

I've been pleasantly surprised by the response to these events, and we're looking forward to hosting more! If you're in Chicago, join the group at Meetup and we'll let you know when the next event is happening.

Taking your test suite plaid

Hi, my name is Tim, and I too have a bloated and slow test suite. That’s the first step isn’t it? Realizing you have a problem.

Well, we have a problem. So we’ve decided to make it a big priority to get our test suite to run in a reasonable time frame. I’ve heard of stories, that may be only told to scare the new guys, of the full test suite taking over 35 minutes to run before I joined the team.

A key fact we just can’t get around is that we have a lot of code, both in our tests and our application. Here are the stats:

+----------------------+-------+-------+---------+---------+-----+-------+  
| Name                 | Lines |   LOC | Classes | Methods | M/C | LOC/M |  
+----------------------+-------+-------+---------+---------+-----+-------+  
| Controllers          |  4105 |  3333 |      59 |     423 |   7 |     5 |  
| Helpers              |  2073 |  1699 |       1 |     266 | 266 |     4 |  
| Models               | 15093 | 11668 |     218 |    1683 |   7 |     4 |  
| Libraries            |  4842 |  3723 |      64 |     477 |   7 |     5 |  
| Integration tests    |   676 |   506 |      17 |      29 |   1 |    15 |  
| Functional tests     | 14059 | 11496 |      92 |     547 |   5 |    19 |  
| Unit tests           | 31944 | 26450 |     195 |    1194 |   6 |    20 |  
| GoldStandard Tests   |   149 |   114 |       6 |      26 |   4 |     2 |  
+----------------------+-------+-------+---------+---------+-----+-------+  
| Total                | 72941 | 58989 |     652 |    4645 |   7 |    10 |  
+----------------------+-------+-------+---------+---------+-----+-------+  
  Code LOC: 20423     Test LOC: 38566     Code to Test Ratio: 1:1.9

There are obviously a lot of possible places to start. We didn’t want to get too far deep into a rabbit-hole, so we decided to have the initial work be a three-day time-boxed effort inside our sprint.

I dusted off my copy of ‘Grease Your Suite’ (http://grease-your-suite.heroku.com) and started to work on it. If you haven’t read ‘Grease Your Suite’, I highly recommend reading at least the fast_context section before you continue with this post.

Quezinart Speed

I decided to start with the unit test suite. We already use rvm, ree, and the gc environment variables to try to get us some more speed out of our suite and we still come in at just over 10 minutes (702 seconds) for just the unit tests.

First things first, I wanted to see which unit tests are hurting the most. I pulled down the rbtrace (https://github.com/tmm1/rbtrace) gem, ran our unit tests, and invoked rbtrace like so:

rbtrace --pid 15024 -c testunit | sort -n -k 2 -t'<' | tail -10

rbtrace comes with a predefined tracer to measure the run time of each of your test suites. I sort that list and chop off the worst 10 to tackle first:

Test::Unit::TestSuite#run(name="ManifestSearchTest", size=18) <18.094087>  
Test::Unit::TestSuite#run(name="SiteMarketTest", size=40) <19.251209>  
Test::Unit::TestSuite#run(name="ManifestTest", size=154) <21.322834>  
Test::Unit::TestSuite#run(name="CollaborationTest", size=144) <22.447253>  
Test::Unit::TestSuite#run(name="ProposalGeneratorTest", size=35) <24.215540>  
Test::Unit::TestSuite#run(name="PublisherOrderMailerTest", size=29) <25.795780>  
Test::Unit::TestSuite#run(name="PlanTest", size=165) <32.161778>  
Test::Unit::TestSuite#run(name="PublisherOrderTest", size=69) <32.693467>  
Test::Unit::TestSuite#run(name="PlanRowTest", size=155) <33.549538>  
Test::Unit::TestSuite#run(name="PlacementTest", size=144) <120.024747>

Holy slow code Batman! We have a specific unit test suite that takes 120 seconds. Two full minutes of our unit tests are in one test suite. Wow.

With a little bit more instrumentation and liberal use of Benchmark.realtime, I narrowed down a big part of our slowdown to the setup in a couple of our parent contexts. These were being called for just about every test down the line.

context "a placement" do  
  setup do  
    #this benchmark comes in at somewhere around 1 sec just to create this factory  
    #Benchmark.realtime do  
    @placement = Factory(:placement)  
    #end  
    @placement.stubs(:ordered_placement).returns(nil)  
  end  

  should "do the right thing" do  
    assert some_code  
  end  

  context "when it has some property" do  
    setup do  
      @placement.stubs(:some_property)  
    end  

    should "test further use cases with this property" do  
      assert @placement.some_property.something  
    end  
  end  

  ...

There are roughly 170 tests in this suite. If one of top contexts has a setup that takes about one second, and that setup gets repeated for everything underneath it, you can see how that time adds up. The reason it takes so long to create that factory is because it has a pretty deep dependency graph to get a usable object. Every test only tests a small slice of that object, but we still need the full, valid object around.

Light Speed

It would be nice if we could just set it up once and just access it in each test. This is where fast_context (https://github.com/lifo/fast_context) comes in really handy because that is exactly what it’s supposed to do. Unfortunately, when I implemented fast_context it required a LOT of code changes. For every change we made to the placement, we had to introduce a reverse change at the end of the should (teardown doesn’t work too well in fast_context land) to put the factory-built object back into its initial state. With all those code changes, this only brought the test suite down under 50 seconds and lets be honest, a 50 second test just isn’t going to cut it either. So I did some more instrumentation to find out where the rest of our time was going. It turns out fast_context only works within tests for a single context, e.g. the following code:

fast_context 'a placement' do  
  setup { @placement = Factory(:placement) }  
  should 'be placed?' do  
    assert_equal @placement.placed?  
  end  
  should "return its plan's name" do  
    assert_equal 'Plan One', @placement.plan_name  
    assert_equal 'Plan One', @placement.plan.name  
  end  
end

works fine and only calls the Factory(:placement) once. However, the following code:

fast_context 'a placement' do  
  setup { @placement = Factory(:placement) }  
  should 'be placed?' do  
    assert @placement.placed?  
  end  
  fast_context "plan delegation" do  
    should "return its plan's name" do  
      @placement.plan.expects(:name).and_returns('Plan One')  
      assert_equal 'Plan One', @placement.plan_name  
      #try to put it back to a pristine state for the next run  
      @placement.plan.unstub(:name)  
    end  
  end  
end

will run the Factory(:placement) twice. Once for ‘a placement’ and once for ‘plan delegation.’

Ridiculous Speed

The only way that I could think of to fix that with fast_context is to flatten out the contexts as much as possible and try to have a single level. When I did that, the test did get down to 24 seconds a run. The trade-off, however, was a pretty high price in less readability and more difficult maintainability. The constant work to set the factory-built object back to its initial state made for extremely verbose and error prone code. The flattening out cost us all of our contexts that we used for grouping and labeling.

Ludicrous Speed

I started thinking about different ways to cache the placement after it was first made and bring out copies of it for each test. I came up with PureFunction, named after http://en.wikipedia.org/wiki/Pure_function. If you look at the first bullet point from the wikipedia article, that’s pretty much exactly what I was looking for:

  1. The function always evaluates the same result value given the same argument value(s).

I wanted a mechanism that every time it is run in the same way, gives you the same thing AND since it’s going to give you the exact same thing, just cache it and return it. After all, why calculate it twice?

Here is the code (with a couple tests for good measure):

class PureFunction  
  @@cache = {}  
  def self.cache(&block)  

    #file/line number of the call to this function  
    calling_line = caller.first  

    #remove any cruft from being evaluated within a block/proc  
    calling_line = calling_line[0..(calling_line.index(':in')||0)-1]  

    #return the cache hit if it can be found  
    return Marshal.load(@@cache[calling_line]) if @@cache[calling_line]  

    #if it is unfound, run the actual code  
    ret_val = yield  

    #and store it by creating a serialized copy so that we can rehydrate  
    #it without any of the mutations it's gone through later  
    @@cache[calling_line]=Marshal.dump(ret_val)  
    return ret_val  
  end  
  def self.clear  
    @@cache = {}  
  end  
end  

if __FILE__ == $0  
  def assert(message, &block); puts "#{"%6s" % ((yield || false) ? '  PASS' : '! FAIL')} - #{message}"; end  

  assert "cache should return results" do  
    "hello" == PureFunction.cache do  
      "hello"  
    end  
  end  

  a = [1,2]  
  2.times do  
    assert "cache should return the same value whenever it's called at the same line" do  

      #we want the initial value to always come out of the block regardless of whether the object was mutated  
      [1,2] == PureFunction.cache { a }  

    end  

    #we mutate a  
    a << 3  
  end  

end

There are two really interesting parts I want to point out:

  1. You always get back an untouched copy of the return value of the block
  2. You don’t have to give an arbitrary cache key because I use the spot where you called the method from to key the cache

So now my test code looks like this:

context 'a placement' do  
  setup do  
    @placement = PureFunction.cache do  
      Factory(:placement)
    end  
  end  

  should 'be placed?' do  
    assert_equal @placement.placed?  
  end  

  context "plan delegation" do  
    should "return its plan's name" do  
      @placement.plan.expects(:name).and_returns('Plan One')  
      assert_equal 'Plan One', @placement.plan_name  
    end  
  end  
end

You can see here that now we don’t even have to use fast_context. The Factory(:placement) line get run once and only once no matter how many levels of context we have and we don’t have to try to undo any mutations that the placement has gone through in our shoulds.

A caveat: You can’t use this with unserializable objects. (We ran into instances where BackgroundJob was creating a ton of singleton classes and cases where we tried to serialize objects that we had mocked.)

So that is all fine and good, but the key question is how did we do with that 120 second test? Well after stripping out any setup that we didn’t need, and combining all the setup under a few as possible PureFunction blocks, we got it down to:

ruby -I"lib:test" test/unit/placement_test.rb   
Current PID<5494>  
Loading fast_context  
..........................................................................................................................................................................  
Finished in 7.278199 seconds.  

170 tests, 274 assertions, 0 failures, 0 errors

At the end of the three-day timebox, we had some pretty nice results. The worst unit test went from 120 seconds to under 7 seconds (a 94% reduction) and we have an approach to try with with the rest of the unit test suite. With all the changes, the unit tests now clock in at just under 7.5 minutes (446 seconds), so there is still room for improvement as we continue into the next sprint.

Running a SproutCore Development Server with Rack (and Passenger)

UPDATE: Please understand this is only for development mode. It should not be used in Production. SproutCore provides sc-build for deployment.

Here at Centro we maintain a SproutCore application that sits in front of a number of Ruby applications on the backend. Our project has evolved heavily over the last year or so: we started with the standard sc-server, eventually moved to Unicorn, and finally to Passenger. There doesn't seem to be a lot of discussion around the use of the SproutCore build tools and I hope this writeup proves useful to others looking to do something similar.

In the early stages of development we designed our Ruby services to make requests to http://localhost:4020, as sc-server generously provides a Buildfile that allows for easy proxy configuration. At the time it seemed like a great way to DRY up our configuration in development mode. Why bother to track everybody's port number in each project?

# ===========================================================================
# Project:   Transis
# Copyright: ©2009 Centro
# ===========================================================================

config :all, :required => [:sproutcore, :blueprint, :transis],
  :test_required => [:test_runner_extension]

config :examples, :load_fixtures => true
config :main, :theme => 'transis', :layout => 'lib/index.rhtml'

proxy "/id",        :to => "localhost:3002"
proxy "/planning",  :to => "localhost:3003"
proxy "/templates", :to => "localhost:3004"
proxy "/research",  :to => "localhost:3005"
...


We started running into issues pretty quickly with sc-server being single threaded. For example, when a user's browser makes a request to /research that app will make a request to /id to verify their authenticity. Since everything is running through a single threaded server timeouts quickly start piling up and the app ground to a halt.

We experimented with a teeny Rack based proxy server but quickly bailed. There had to be a better way. All of our Ruby services play nice with Rack (thanks to Sinatra and Rails), and we know the SproutCore development server is written in Ruby. We wanted to unify our development environment as the collection of scripts required was getting out of hand. The next approach was to replace the default Thin server used in sc-server with a cluster of Unicorns. This meant we had to dive into the SproutCore source and figure out how sc-server really works.

After a brief look around, it became clear the place to start is lib/sproutcore/tools/server.rb. Check out the code snippet below.

# get project and start service.
project = requires_project!

...

SC.logger << "SproutCore v#{SC::VERSION} Development Server\n"
SC::Rack::Service.start(options.merge(:project => project))

Since SproutCore is built around Rack, this should be pretty easy. The last line is pointing to SC::Rack::Service.start, so our next step was to see what's going on in there. Below are a few crucial excerpts from the start method (a lot of configuration has been removed).

# Guess.
if ENV.include?("PHP_FCGI_CHILDREN")
  server = ::Rack::Handler::FastCGI

  # We already speak FastCGI
  options.delete :File
  options.delete :Port
elsif ENV.include?("REQUEST_METHOD")
  server = ::Rack::Handler::CGI
else
  begin
    server = ::Rack::Handler::Thin
  rescue LoadError => e
    begin
      server = ::Rack::Handler::Mongrel
    rescue LoadError => e
      server = ::Rack::Handler::WEBrick
    end
  end
end

...

app = self.new(*projects)

...

SC.logger << "Starting server at http://#{opts[:Host] || '0.0.0.0'}:#{opts[:Port]} in #{SC.build_mode} mode\n"
SC.logger << "To quit sc-server, press Control-C\n"
server.run app, opts

Now that we've seen sc-server is nothing more than a simple Rack app, the only piece of this puzzle still unsolved was the projects. How does sc-server generate that array? Back in lib/sproutcore/tool/server.rb (see the snippet above) it seems SC::Tools implements require_project! which eventually relies on SC::Project to do all the dirty work.

Putting all this together we managed to to design a very concise config.ru file. Check it out.

require 'rubygems'
require 'sproutcore'

root = Pathname(Dir.pwd).expand_path
project = SC::Project.load_nearest_project(root, :parent => SC.builtin_project)
service = SC::Rack::Service.new([project])
run service

We ran Unicorn with 6 workers for a while and it was going pretty well, but as our dev tools matured we decided to start running our backends in Passenger locally. Converting from Unicorn to Passenger was easy, here's where the awesome nature of Rack really shines. The above config.ru file just works with Passenger, nothing had to change. All you need is a vhost similar to the example below.

<VirtualHost *:80>
  ServerName transis.local
  DocumentRoot "/Users/abloom/Sites/centro/transis-ui/public"

  ErrorLog /var/log/apache2/transis-error.log
  CustomLog /var/log/apache2/transis-access.log combined

  # Rails application URIs
  RailsBaseURI /planning
  RailsBaseURI /research
  RailsEnv development

  # Rack application URIs
  RackBaseURI /id
  RackBaseURI /files
  RackBaseURI /templates
  RackEnv development
</VirtualHost>

By moving our entire development system to Passenger we were able to more closely replicate our production environment as well as simplify our startup and shutdown scripts. No longer must we rely on PID files or the output of lsof. Simply touch tmp/restart.txt in any of the projects to get Apache to reload your code. Life is good when things are easy.

Our journey with SC.GridView and insertionOrientation

We're building an internal tool here to manage publisher organizations and their properties. We want to be able to choose which channels are associated with each property. I followed the instructions at http://wiki.sproutcore.com/w/page/28719873/Show-a-relation-as-a-checkbox-on-a... with some modifications to tie the selection to a SC.GridView and ended up with the code:

channelsEditView: SC.GridView.design({
  rowHeight: 22,
  columnWidth: 300,
  contentBinding: 'Gut.propertyChannelsController.channelsForSelection',
  contentValueKey: 'name',
  contentCheckboxKey: 'checkBoxValue',
  isSelectable: NO,
  exampleView: SC.ListItemView
})

Which produced:

Gridviewwrongorder
That's a great start but we really want the items to sort alphabetically down the page instead of across. Let's take a look at the source code of SC.GridView:

SC.GridView = SC.ListView.extend(
/** @scope SC.GridView.prototype */ {
  classNames: ['sc-grid-view'],
 
  layout: { left:0, right:0, top:0, bottom:0 },

  /**
    The common row height for grid items.
   
    The value should be an integer expressed in pixels.
  */
  rowHeight: 48,
 
  /**
    The minimum column width for grid items.  Items will actually
    be laid out as needed to completely fill the space, but the minimum
    width of each item will be this value.
  */
  columnWidth: 64,

  /**
    The default example item view will render text-based items.
   
    You can override this as you wish.
  */
  exampleView: SC.LabelView,
 
  insertionOrientation: SC.HORIZONTAL_ORIENTATION,

Wow, insertionOrientation. That's pretty much exactly what we want. So after changing channelsEditView to:

channelsEditView: SC.GridView.design({
  rowHeight: 22,
  columnWidth: 300,
  contentBinding: 'Gut.propertyChannelsController.channelsForSelection',
  contentValueKey: 'name',
  contentCheckboxKey: 'checkBoxValue',
  isSelectable: NO,
  insertionOrientation: SC.VERTICAL_ORIENTATION,
  exampleView: SC.ListItemView
})

Nothing changes. Lets take a look at what insertionOrientation does:

~/.rvm/gems/ree-1.8.7-2010.02/gems/sproutcore-1.4.1$ grep -r insertionOrientation *
lib/frameworks/sproutcore/frameworks/desktop/views/grid.js:  insertionOrientation: SC.HORIZONTAL_ORIENTATION,

The original author knew that we would need that configuration later on, but didn't get a chance to implement it. Here's where the pulling up your sleeves aspect of using an open source framework comes in. Time to implement it. Let's take a look at SC.GridView to see how the child views are laid out. The interesting code is in layoutForContentIndex:

/** @private */
layoutForContentIndex: function(contentIndex) {
  var rowHeight = this.get('rowHeight') || 48,
      frameWidth = this.get('clippingFrame').width,
      itemsPerRow = this.get('itemsPerRow'),
      columnWidth = Math.floor(frameWidth/itemsPerRow),
      row = Math.floor(contentIndex / itemsPerRow),
      col = contentIndex - (itemsPerRow*row) ;
  return {
    left: col * columnWidth,
    top: row * rowHeight,
    height: rowHeight,
    width: columnWidth
  };
},

When the view is rendered, SproutCore loops over all the items in the content collection and runs this method to determine where to lay out all the child views. As we can see, this completely assumes that the child views are laid out in rows down the page. So we need to add the case for laying them out in columns:

layoutForContentIndex: function(contentIndex) {
  var rowHeight = this.get('rowHeight') || 48,
      content = this.get('content'),
      count = (content) ? content.get('length') : 0,
      frameWidth = this.get('clippingFrame').width,
      itemsPerRow = this.get('itemsPerRow'),
      rows = Math.ceil(count / itemsPerRow ),
      columnWidth = Math.floor(frameWidth/itemsPerRow),
      isHorizontal = this.get('insertionOrientation') === SC.HORIZONTAL_ORIENTATION,
      row = isHorizontal ? Math.floor(contentIndex / itemsPerRow) : contentIndex%rows,
      col = isHorizontal ? contentIndex - (itemsPerRow*row) : Math.floor(contentIndex/rows);
  return { 
    left: col * columnWidth,
    top: row * rowHeight,
    height: rowHeight,
    width: columnWidth
  };
}

That works perfectly when all the items are on the screen, but as we scroll and resize, items start disappearing off of the end of the last column. After a bit of research we find that SC.GridView has a method contentIndexesInRect that determines which child views are inside the clipping frame at any time so SproutCore only needs to render items that are actually being shown. Let's take a look at it:

contentIndexesInRect: function(rect) {
  var rowHeight = this.get('rowHeight') || 48 ,
      itemsPerRow = this.get('itemsPerRow'),
      min = Math.floor(SC.minY(rect) / rowHeight) * itemsPerRow,
      max = Math.ceil(SC.maxY(rect) / rowHeight) * itemsPerRow ;
  return SC.IndexSet.create(min, max-min);
},

After we change that to incorporate the horizontal and vertical orientations we have:

contentIndexesInRect: function(rect) {
  var rowHeight = this.get('rowHeight') || 48 ,
      content = this.get('content'),
      count = (content) ? content.get('length') : 0,
      frameWidth = this.get('clippingFrame').width,
      itemsPerRow = this.get('itemsPerRow'),
      rows = Math.ceil(count / itemsPerRow ),
      columnWidth = Math.floor(frameWidth/itemsPerRow);
  if(this.get('insertionOrientation') === SC.HORIZONTAL_ORIENTATION){
    var min = Math.floor(SC.minY(rect) / rowHeight) * itemsPerRow,
        max = Math.ceil(SC.maxY(rect) / rowHeight) * itemsPerRow;
    return SC.IndexSet.create(min, max-min);
  }else{
    var indexSet = SC.IndexSet.create();
    for(var colIndex=0;colIndex<itemsPerRow;++colIndex){
      var colMinX = colIndex*columnWidth,
          colMaxX = colMinX + columnWidth;
      if( colMinX > SC.minX(rect) || colMaxX < SC.maxX(rect) ){
        var min = Math.floor(SC.minY(rect) / rowHeight) + (colIndex * rows),
            max = Math.min(Math.ceil(SC.maxY(rect) / rowHeight) + (colIndex * rows), (colIndex * rows) + rows);
        indexSet.add(min,max-min);
      }
    }
    return indexSet;
  }
},

And that works even without all items on the screen:

Gridviewcorrectorder
But when the view is resized diagonally, the left/right alignment gets screwed up:
Gridviewoutofsnc
After a TON of time trying to debug that, we see in the comments of the original contentIndexesInRect:

/** @private
  Find the contentIndexes to display in the passed rect. Note that we
  ignore the width of the rect passed since we need to have a single
  contiguous range.
*/
contentIndexesInRect: function(rect) {

'Note ... we need to have a single contiguous range'. I really wish I could tell you I have some insight into WHY we need the contiguous range, but I wasn't able to find it. So we change our new contentIndexesInRect to:

contentIndexesInRect: function(rect) {
  var rowHeight = this.get('rowHeight') || 48 ,
      content = this.get('content'),
      count = (content) ? content.get('length') : 0,
      frameWidth = this.get('clippingFrame').width,
      itemsPerRow = this.get('itemsPerRow'),
      rows = Math.ceil(count / itemsPerRow ),
      columnWidth = Math.floor(frameWidth/itemsPerRow);
  if(this.get('insertionOrientation') === SC.HORIZONTAL_ORIENTATION){
    var min = Math.floor(SC.minY(rect) / rowHeight) * itemsPerRow,
        max = Math.ceil(SC.maxY(rect) / rowHeight) * itemsPerRow;
    return SC.IndexSet.create(min, max-min);
  }else{
    var max = 0,
        min = count;
    for(var colIndex=0;colIndex<itemsPerRow;++colIndex){
      var colMinX = colIndex*columnWidth,
          colMaxX = colMinX + columnWidth;
      if( colMaxX > SC.minX(rect) || colMinX < SC.maxX(rect) ){
        min = Math.min(min,Math.floor(SC.minY(rect) / rowHeight) + (colIndex * rows));
        max = Math.max(max,Math.min(Math.ceil(SC.maxY(rect) / rowHeight) + (colIndex * rows), (colIndex * rows) + rows));
      }
    }
    return SC.IndexSet.create(min,max-min);
  }
},

What is basically going on here is we iterate over all of the columns and record the highest and lowest index of the items to display and return that in an IndexSet.

So the final code that monkey patches SC.GridView to make insertionOrientation work is:

SC.GridView.prototype.mixin({

  contentIndexesInRect: function(rect) {
    var rowHeight = this.get('rowHeight') || 48 ,
        content = this.get('content'),
        count = (content) ? content.get('length') : 0,
        frameWidth = this.get('clippingFrame').width,
        itemsPerRow = this.get('itemsPerRow'),
        rows = Math.ceil(count / itemsPerRow ),
        columnWidth = Math.floor(frameWidth/itemsPerRow);
    if(this.get('insertionOrientation') === SC.HORIZONTAL_ORIENTATION){
      var min = Math.floor(SC.minY(rect) / rowHeight) * itemsPerRow,
          max = Math.ceil(SC.maxY(rect) / rowHeight) * itemsPerRow;
      return SC.IndexSet.create(min, max-min);
    }else{
      var max = 0,
          min = count;
      for(var colIndex=0;colIndex<itemsPerRow;++colIndex){
        var colMinX = colIndex*columnWidth,
            colMaxX = colMinX + columnWidth;
        if( colMaxX > SC.minX(rect) || colMinX < SC.maxX(rect) ){
          min = Math.min(min,Math.floor(SC.minY(rect) / rowHeight) + (colIndex * rows));
          max = Math.max(max,Math.min(Math.ceil(SC.maxY(rect) / rowHeight) + (colIndex * rows), (colIndex * rows) + rows));
        }
      }
      return SC.IndexSet.create(min,max-min);
    }
  },
  
  layoutForContentIndex: function(contentIndex) {
    var rowHeight = this.get('rowHeight') || 48,
        content = this.get('content'),
        count = (content) ? content.get('length') : 0,
        frameWidth = this.get('clippingFrame').width,
        itemsPerRow = this.get('itemsPerRow'),
        rows = Math.ceil(count / itemsPerRow ),
        columnWidth = Math.floor(frameWidth/itemsPerRow),
        isHorizontal = this.get('insertionOrientation') === SC.HORIZONTAL_ORIENTATION,
        row = isHorizontal ? Math.floor(contentIndex / itemsPerRow) : contentIndex%rows,
        col = isHorizontal ? contentIndex - (itemsPerRow*row) : Math.floor(contentIndex/rows);
    return { 
      left: col * columnWidth,
      top: row * rowHeight,
      height: rowHeight,
      width: columnWidth
    };
  }
});

And since a lot of what we fixed is how the scrolling and resizing movement works, you can see a quick demo here:

(download)

Under the Hood of the LaunchPad Challenge

A few weeks ago we sponsored the 2010 ITA Fall Challenge. It was a great opportunity for both us and the students, but to sweeten the deal we gave out some pretty slick swag. (See the previous post on Something Unimportant for background on the puzzle.) Today's post will be a bit more in depth, including some code and a walkthrough for anyone who didn't finish it.

The instructions we gave out with the kits were very simple, "Plug in the USB cable to power the board up and see what happens." This is where the fun begins. The LaunchPad comes with two LEDs on the board. We preloaded some code they immediately started to flash. Decoding the pattern is the first step in the puzzle.

Did you figure it out? No? Alright, here's the deal, the red light represents the beginning of the sequence and the green light is printing out Morse code. If you take your time and write down the pattern you should have come up with VCC TO PIN 1.4

Launchpad_small

Don't worry, we didn't pass out bare boards. We put headers on and tossed a bunch of wires in each kit.

If you spend a minute looking at the board you'll notice both VCC and P1.4. Connecting these two pins with a wire causes the LEDs to start printing out a new message. Writing out the dashes and dots, you should have come up with TINYURL.COM/37C5S8E.

The tinyurl above should take you to a secret Github account that was created for the LaunchPad Challenge. Now that the contest has ended the ita2010 repository has been moved to the official Centro Github account.

If you followed all the instructions in the README you should now have a second binary running on your MSP430. The source for this new executable (prog2.elf) can be found here. It's really not much different than prog1.c, in fact, it's simpler. It doesn't watch any of the input pins and it's been stripped down to only contain one message. Now that you've got the source you've probably noticed the message is actually a phone number. This number is connected to a Google Voice account we setup with a pre-recorded greeting congratulating the winner and asking for their email address.

Ok, enough of the boring details of the contest and onto some of the code. The following C is about as simple as it gets. This was mainly due to the fact that I wanted anyone to be able to recompile these examples regardless of their platform. Initially I had written prog1.c to use the Interrupt Service Routine (ISR) to detect the connection on P1.4, but I knew the pre-processor on a Windows machine wouldn't handle this the same way the setup on my Mac does. Without the ISR the interaction for the user is less than desirable as it might appear slow or laggy depending on where in the code you are when the wire is connected. On the other hand but the code remains quite clean and is therefore much easier to follow. If you're up for it, try to modify prog1.c to work with the ISR. It's really not too hard, I promise.

The meat of both prog1.c and prog2.c can be seen in the Gist below. This is an excerpt from the main function and is responsible for continuously pumping out Morse encoded characters.

The "#" character isn't actually part of the message. It's used as a marker to make it easy to determine when to flash the "starting" LED. Hitting a null terminator (\0) tells the loop to reset the pointer and start over. The only catch is we need to reset the pointer one extra space back because the next operation immediately moves the pointer one space forward. Finally, the default, when we have a real printable character.

Also included in the never ending for-loop above (only in prog1.c) is the following snippet which is responsible for checking the state of P1.4 and appropriately switching out the messages.

The only catch is comparing the value of currentState with state. This is done to make sure we only switch messages when the state has changed. Without this check the message would end up being reset to the beginning on every iteration and the user would only see the endless blinking of the "starting" LED.

The one thing you may have noticed in the first Gist, and referenced elsewhere in the code is the delay function (implementation seen below). It should be noted that simply burning clock cycles to cause a delay is probably the worst possible route one could take. This was done here to help ensure the code could be compiled anywhere, under ideal circumstance a timer based around an interrupt would be used.

Check out the code on your own and see if you can figure out how the ASCII to Morse lookup table works. Feel free to fork this and make it better or even turn it into your own contest.

And as always, we'd love to see what kind of stuff you're doing with your MSP430's so post comments or send us an email.