Paul Dix Explains Nothing

Serializing data speed comparison: Marshal vs. JSON vs. Eval vs. YAML

Last night at the NYC Ruby hackfest, I got into a discussion about serializing data. Brian mentioned the Marshal library to me, which for some reason had completely escaped my attention until last night. He said it was wicked fast so we decided to run a quick benchmark comparison.

The test data is designed to roughly approximate what my stored classifier data will look like. The different methods we decided to benchmark were Marshal, json, eval, and yaml. With each one we took the in-memory object and serialized it and then read it back in. With eval we had to convert the object to ruby code to serialize it then run eval against that. Here are the results for 100 iterations on a 10k element array and a hash with 10k key/value pairs run on my Macbook Pro 2.4 GHz Core 2 Duo:

                 user      system     total       real
array marshal  0.210000   0.010000   0.220000 (  0.220701)
array json     2.180000   0.050000   2.230000 (  2.288489)
array eval     2.090000   0.060000   2.150000 (  2.240443)
array yaml    26.650000   0.350000  27.000000 ( 27.810609)

hash marshal   2.000000   0.050000   2.050000 (  2.114950)
hash json      3.700000   0.060000   3.760000 (  3.881716)
hash eval      5.370000   0.140000   5.510000 (  6.117947)
hash yaml     68.220000   0.870000  69.090000 ( 72.370784)

The order in which I tested them is pretty much the order in which they ranked for speed. Marshal was amazingly fast. JSON and eval came out roughly equal on the array with eval trailing quite a bit for the hash. Yaml was just slow as all hell. A note on the json: I used the 1.1.3 library which uses c to parse. I assume it would be quite a bit slower if I used the pure ruby implementation. Here's a gist of the benchmark code if you're curious and want to run it yourself.

If you're serializing user data, be super careful about using eval. It's probably best to avoid it completely. Finally, just for fun I took yaml out (it was too slow) and ran the benchmark again with 1k iterations:

                 user      system     total       real
array marshal  2.080000   0.110000   2.190000 (  2.242235)
array json    21.860000   0.500000  22.360000 ( 23.052403)
array eval    20.730000   0.570000  21.300000 ( 21.992454)

hash marshal  19.510000   0.500000  20.010000 ( 20.794111)
hash json     39.770000   0.670000  40.440000 ( 41.689297)
hash eval     51.410000   1.290000  52.700000 ( 54.155711)

Gotcha with cache_fu and permalinks

This is an issue I had recently in a project with cache_fu. Models that I found and cached based on permalinks weren't expiring the cache correctly when getting updated. Here's an example scenario.

Say you have a blog with posts. However, instead of using a url like http://paulscoolblog.com/posts/23 you want something that's more search engine friendly and readable for the user. So you use a permalink (maybe using the permalink_fu plugin) that's auto-generated based on the title of the post. This post would have a url that looks something like http://paulscoolblog.com/posts/gotcha-with-cache_fu-and-permalinks.

In your controller's show method you'd probably find the post like this:

@post = Post.find_by_permalink(params[:permalink])

However, you'd want to do the caching thing so you'd actually do this:

@post = Post.cached(:find_by_permalink, :with => params[:permalink])

The problem that I ran into, which is probably obvious to anyone familiar with cache_fu, was that when updating the post, it wouldn't expire the cache. That part of the post model looks like this:

class Post < ActiveRecord::Base
  before_save :expire_cache
  ...
end

Do you see it? The issue is that when expire_cache gets called on the object, it expires the key Post:23 from the cache (assuming 23 was the id of the post). However, when the post was cached using the cached(:find_by_permalink ...) method, it put the post object into the cache with a key of Post:find_by_permalink:gotcha-with-cache_fu-and-permalinks.

Luckily, it's a fairly simple fix. If you have a model that is commonly accessed through permalinks, just write your own cache expiry method that looks for both keys and expires them.

Non-greedy mode in regex

I was writing a regular expression yesterday and this popped up. It's just a quick note about greedy vs. non-greedy mode in regular expression matching. Say I have a regular expression that looks something like this:

/(\[.*\])/

In English that says something roughly like: find an opening bracket [ with 0 or more of any character followed by a closing bracket. The backslashes are to escape the brackets and the parenthesis specify grouping so we can later access that matched text.

The greedy mode comes up with the 0 or more characters part of the match (the .* part of the expression). The default mode of greedy means that the parser will gobble up as many characters as it can and match the very last closing bracket. So if you have text like this:

a = [:foo, :bar]
b = [:hello, :world]

The resulting grouped match would be this:

[:foo, :bar]
b = [:hello, :world]

If you just wanted the [:foo, :bar] part, the solution is to parse in non-greedy mode. This means that it will match on the first closing bracket it sees. The modified regular expression looks like this:

/(\[.*?\])/

I love the regular expression engine in Ruby. It's one of the best things it ripped off from Perl. The one thing I don't like is the magic global variable that it places matched groups into. You can access that first match through the $1 variable. If you're unfamiliar with regular expressions, a good place to start is the Camel book. It's about Perl, but the way they work is very similar. I actually haven't seen good coverage of regexes in a Ruby book.

Storing many classification models

One of the things I need to do in Filterly is keep many trained classifiers. These are the machine learning models that determine if a blog post is on topic (Filterly separates information by topic). At the very least I need one per topic in the system. If I want to do something like boosting then I need even more. The issue I'm wrestling with is how to store this data. I'll outline a specific approach and what the storage needs are.

Let's say I go with boosting and 10 perceptrons. I'll also limit my feature space to the 10,000 most statistically significant features. So the storage for each perceptron is a 10k element array. However, I'll also have to keep another data structure to store what the 10k features are and their position in the array. In code I use a hash for this where the feature name is the key and the value is its position. I just need to store one of these hashes per topic.

That's not really a huge amount of data. I'm more concerned about the best way to store it. I don't think this kind of thing maps well to a relational database. I don't need to store the features individually. Generally when I'm running the thing I'll want the whole perceptron and feature set in memory for quick access. For now I'm just using a big text field and serializing each using JSON.

I don't really like this approach. The whole serializing into the database seems really inelegant. Combined with the time that it takes to parse these things. Each time I want to see if a new post is on topic I'd need to load up the classifier and parse the 10 10k arrays and the 10k key hash. I could keep each classifier running as a service, but then I've got a pretty heavy process running for each topic.

I guess I'll just use the stupid easy solution for the time being and worry about performance later. Anyone have thoughts on the best approach?