kreynolds/cassandra-cql — pull request #43 by outoftime (2013-01-12 20:03:41+00:00)
Title: Precalculate a map of column names -> column indices

Hey Kelley,

We noticed some pretty poor performance when pulling back big wide rows (~a few thousand columns) with UUID headers, and tracked it down to the use of the `Array#index` method in the default proc in `@value_cache` on the `Row` class. This would end up doing O(N**2) comparisons between column headers, which ends up being a considerable performance bottleneck when there are lots of column headers.

This patch lazily generates a `@column_indices` Hash that maps column names to column indices, and uses that in favor of `column_names.index`. I did some benchmarking and it performs better at various row sizes, although the difference only becomes significant between 1K-10K columns in the row. As you can see, at that point it's quite stark:

Rehearsal ----------------------------------------------------------------------------
Array#index: 1 columns 0.000000 0.000000 0.000000 ( 0.001695)
Hash lookup: 1 columns 0.000000 0.000000 0.000000 ( 0.001645)
Array#index: 10 columns 0.000000 0.000000 0.000000 ( 0.003558)
Hash lookup: 10 columns 0.000000 0.000000 0.000000 ( 0.003279)
Array#index: 100 columns 0.020000 0.000000 0.020000 ( 0.014500)
Hash lookup: 100 columns 0.010000 0.000000 0.010000 ( 0.009414)
Array#index: 1000 columns 0.160000 0.000000 0.160000 ( 0.161603)
Hash lookup: 1000 columns 0.030000 0.000000 0.030000 ( 0.036212)
Array#index: 10000 columns 13.290000 0.000000 13.290000 ( 13.362359)
Hash lookup: 10000 columns 0.330000 0.000000 0.330000 ( 0.349780)
------------------------------------------------------------------ total: 13.840000sec

user system total real
Array#index: 1 columns 0.000000 0.000000 0.000000 ( 0.002420)
Hash lookup: 1 columns 0.000000 0.000000 0.000000 ( 0.002279)
Array#index: 10 columns 0.000000 0.000000 0.000000 ( 0.001562)
Hash lookup: 10 columns 0.000000 0.000000 0.000000 ( 0.003126)
Array#index: 100 columns 0.010000 0.000000 0.010000 ( 0.006003)
Hash lookup: 100 columns 0.010000 0.000000 0.010000 ( 0.004811)
Array#index: 1000 columns 0.160000 0.000000 0.160000 ( 0.162298)
Hash lookup: 1000 columns 0.030000 0.000000 0.030000 ( 0.037594)
Array#index: 10000 columns 12.870000 0.000000 12.870000 ( 12.947497)
Hash lookup: 10000 columns 0.320000 0.000000 0.320000 ( 0.345220)

I've gisted the benchmarking code and a modified `row.rb` for benchmarking purposes if you want to try it yourself:

https://gist.github.com/4520182

Unfortunately I'm using my old desktop right now and it can't seem to run the tests without Cassandra dropping out constantly, but hopefully Travis will confirm a clean patch : )