Planet Ruby

In my earlier finite map benchmarks which compared several hash tables and functional maps (AVL trees and ternary trees), separate chaining (with $$\alpha = 0.47$$) beat double hashing ($$\alpha = 0.42$$) at unsuccessful searches (1% hit rate), but was slower at successful ones.

Theory predicts the following average number of probes for unsuccessful and successful lookups (expressions below):

Separate chaining looks much better here, but the graphs are misleading, because we don't actually care as much about the load factor as about memory usage, so we want to compare the collision resolution schemes when the latter is the same.

If we use a linked list for the collision chain, this represents one word of overhead per item compared to double hashing. For instance, if the load factor with separate chaining is 1, we can afford to have a table twice as big with double hashing for the same amount of memory and a load factor of 50%. In other words, $$N + n = N'$$ where $$N$$ and $$N'$$ are the sizes of the tables for separate chaining and double hashing, and $$n$$ the number of elements. The respective load factors are

The expressions for the average number of probes for unsuccessful and successful searches are (Knuth, TAOCP Vol 3, Section 6.4), for separate chaining

Read more...

I've added math typesetting support to Ocsiblog, which runs this site, using jsMath: (double-click on the equations to see the sources)

When jsMath is enabled, you'll see in the bottom right-hand corner a button that triggers a control panel allowing you to set several options such as the scale or the rendering mechanism (TeX fonts, image fonts or native Unicode fonts; you can pick the one that works best for you and save the configuration --- the best one is TeX fonts, if you have them, but Unicode fonts is quite decent). For best viewing, you can get the TeX fonts here (the page includes detailed install instructions for Windows, OSX and Un*x).

Here's what the above equations should look like with TeX and native Unicode fonts:

I just finished reading the inspiring The E-Myth Revisited, which like my own first book My Job Went to India suffers from an incredibly bad name.

This is definitely one of the most practically useful and potentially career-changing business books I’ve read. As I started getting toward the end, I realized that I should have been taking notes. The book is an excellent read, but at its core, it can be distilled into a clear outline of stuff to do after you read it. I was reading on my Kindle, which I’m still not good at using as a quick reference device. So, while I was excited about going back through the book and making myself a TODO list, I wasn’t sure how to best do it.

Then I remembered Derek Sivers’ book list. Derek has obviously spent a lot of time thoughtfully preparing a list of recommended books with reasons behind each recommendation. Not only that, he includes detailed notes on each book. I read his notes on E-Myth Revisited and was pleased to see that all of the important stuff is captured. Thanks Derek!

Speaking of Derek and books, don’t miss his book, How to Call Attention to Your Music. It might be titled for musicians but I think everyone will find something valuable inside.

This week I’m happy to tell you about a new set of articles which will be appearing here on the Rails blog called “Community Highlights”. This new series will feature people/projects/sites from the Rails community that may deserve a little extra recognition.

This week, we’re going to start with a few people who received awards on stage at Railsconf 2009, this years Ruby Heroes.

Brian Helmkamp

His Blog: http://www.brynary.com/ Twitter: brynary

Aman Gupta

Github: http://github.com/tmm1
Twitter: tmm1

Luis Lavena

His Blog: http://blog.mmediasys.com/ Twitter: luislavena

Pat Allan

His Blog: http://freelancing-gods.com/ Twitter: Pat

Dan Kubb

Github: http://github.com/dkubb
Twitter: dkubb

John Nunemaker

RailsTips: http://railstips.org/
Twitter: jnunemaker

Those are your six Ruby Hero’s for 2009. If you’re interested you can also watch a video of the award ceremony which talks more about the methodology about how they were chosen and see 5 of these guys receive their awards on stage at Railsconf 2009.

Matías Giovannini has been implementing purely functional data structures based on Bentley and Sedgewick's ternary search trees (TST) and pitching them against OCaml's imperative hash table (Hashtbl). In the interval between the initial results and his showing his first version (called Trie_map from now on), I made a functional TST ("Ternary") which compares favorably to both Trie_map and the revised implementation ("Trie_map_mod").

I also resuscitated a hash table implementation of mine that uses open addressing with double hashing (in contrast to Hashtbl's external chaining) and exhibits vastly improved performance.

I'll show the benchmark results first, to be followed by some code and analysis.

Benchmarks

I benchmark the following finite map implementations:

• imperative:

  • Fasthashtbl: hash table with open addressing and double hashing

  • Hashtbl: the hash table from INRIA's stdlib (external chaining)

  • Hashtbl_mod: Hashtbl with more aggressive resizing (lower load factor)

  • Hashtbl_hval: Hashtbl_mod with caching of the hash value

• functional:

  • Trie_map: TST with coalesced constructor for nodes with and without values

  • Trie_map_mod: TST with different constructors for leaves and inner nodes with/without a value

  • Ternary: TST with separate constructor for nodes with and without values but no leaf constructor

  • Map: the Map implementation from INRIA's stdlib (AVL tree)

All the finite maps are compared by

1. building a map with 98568 English words, which are added in (a) randomized and (b) lexicographic order

2. measuring the minimal lookup cost with constant lookups (so that everything is in the L1 cache)

3. timing successful lookups by looking for the 98568 words

   1. in the same (random) order the elements were added

   2. in randomized order

   3. in lexicographic order

   4. in reverse lexicographic order

   ... against the maps built in randomized and lexicographic order

4. timing searches against the previously generated maps (randomized and lexicographic order) using

   1. a larger set of English words (217625, 45.3% hit rate)

   2. a set of Spanish words (86016 words, 1.3% hit rate)

   ... in randomized and lexicographic order

For the sake of exhaustiveness, I measure the iteration and functor overhead and detract it from the lookup timings. The total size of the structures (including the size of the strings) is also measured. All the measurements are repeated 20 times, and the best time is retained. The benchmarks are performed in a single program execution to achieve steady state (major heap resized to required size). The set of words used in the map is large enough to ensure the structure (taking 5.7MB to over 12MB) doesn't fit in the 2MB L2 cache.

The full results can be found here (also includes hash table benchmark with integer keys).

This table shows the results for a map built in randomized order (refer to the full output for those in lexicographic order). Speed is measured in ops/sec, and size in bytes ("Find (hit, orig)" means that the lookups are performed in the same random order as the insertions).

Insertion (randomized order) and lookup

Implementation notes

The source code for all the containers and the benchmarks can be obtained here.

I modified Hashtbl first by changing its resizing policy so that the load factor is the same as in Fasthashtbl (Hashtbl_mod), and second by caching the hash value in the nodes (Hashtbl_hval), which makes successful lookups faster when there are collisions (since the key comparison can be bypassed when the hash values differ) and helps a lot with unsuccessful ones.

Fasthashtbl, Hashtbl_mod and Hashtbl_hval only allow the load factors to grow to 50% before resizing the underlying array to twice its former size; the average load factor is thus 37.5%. Hashtbl, on the other hand, allows it to grow to 2.0, which, theory predicts, would require 13.4 probes per unsuccessful search, and 4.6 per successful one (Knuth, TAOCP Vol 3, Section 6.4, page 524). For a 37.5% load factor, Hashtbl, Hashtbl_mod and Hashtbl_hval will require 1.1 and 1.2, and Fasthashtbl (which uses open addressing with double hashing) will need 1.6 and 1.25 --- double hashing is about as good for successful lookups but worse at unsuccessful ones.

Trie_map_mod and Ternary are very similar: the only differences are that the latter doesn't have a separate Leaf node type, and its code has undergone a few manual optimizations explained below.

Some observations

Functional vs. imperative

Read more...

As a young self-taught software developer, one of the first books I remember reading was Steve McConnell’s Software Project Survival Guide: How to Be Sure Your First Important Project Isn’t Your Last. Who knows why I picked that one of all the possible books but I somehow knew I wanted to learn something about the broad practice of software development instead of just focusing on how to make specific widgets appear on the screen in Delphi or VB or how to automate the shell on our VAX cluster. I probably happened upon the book while aimlessly thumbing through spines in the local book store and was drawn to the snazzy cover.

And so it was that one of my first experiences in learning software became project-focused. “How to be sure your first important project isn’t your last” indeed. This thing called software development was apparently all about doing projects.

I was not alone in this understanding of how software development worked. Most of the people I encountered in my professional life approached software work this way. When something needs to get done, the first step is to name it—sometimes with a silly code name and sometimes with a generic name like “the HR system project” and the next step is to start planning the project.

I’ve started to notice a bad habit. Whenever I need to do something I don’t want to do. Or, worse, something that I want to do but I am prone to procrastinate (according to The War of Art procrastinating something is a sign that it’s important). The bad habit is this: I turn it into a project.

Projects are lovely for procrastinators. As soon as you call something a project, you give it permission to not be completed right now.

Events such as the Rails Rumble have shown that it’s possible to finish software projects in two days that might take a corporate development team weeks or months in a normal project scenario. What’s the difference? Do the Rails Rumble participants throw quality out the window? Do their apps suck? Do they avoid testing and cut corners? Yea, sometimes. But so do most corporate development groups. That’s how things are.

I’ve learned over the course of my career that the amount of time I spend on something doesn’t positively correlate to its value or quality when finished. In other words, if I do something really quickly, it’s not likely to be less valuable than something that takes me a long time to do. Within obvious limits.

So if you want something to take a long time, call it a project. If you want it to get done, just get it done.

After reviewing the feedback on the two recent security announcements we’ve made a few minor changes to the Ruby on Rails security policy.

The first change we’ve made is to include more information on what to do if you don’t receive a response from the security team. In general reports to the security address should receive a response within 24 hours, however the sheer volume of spam to the address can, and has, lead to messages being caught in spam filters. In the event you don’t receive a response there are now two direct-emails to the people currently looking after security reports. That page will be kept up to date as responsibilities are reassigned.

The second change is to more clearly outline the announcement policy for rails vulnerabilities. In short, we notify vendor-sec ahead of the public notification to allow time for people distributing rails to prepare packages for their distributions. Then when the time has come for public notification an email is sent to the security announcement list. Finally the announcement is posted to this blog.

The security announcement list is extremely low volume and you’re strongly suggested to subscribe to it. This is the place which receives the first public announcements of all vulnerabilities in Rails, and also tends to receive additional notifications about vulnerabilities in ruby itself. We’ve been using this list for several years but judging by confusion and misinformed comments following the announcement of CVE-2009-1904, not enough people were aware of its existence.

If you have any comments on the security policy, please send them via email to security@rubyonrails.org.

I had a great time at Ruby Nation this weekend. After my presentation I got a number of questions asking about things I referenced during the talk. Here’s an attempt to point to some of them. If you weren’t there, you won’t have any context but feel free to follow the links anyway You might find something interesting.

My Book

Bureau of Labor Statistics Time Use Survey

Stockholm Syndrome

Karlheinz Stockhausen whose name I accidentally used when trying to refer to Stockholm Syndrome.

4d Database

John Coltrane

da Vinci Sketches

Eight Hour Burn

XP (Agile) Immersion

Pat Metheny – “Whenever young guys ask me what they should do to get better, I always say try to be the worst guy in whatever band you’re in. That’s the secret.”

I Will Teach You To Be Rich

Purple Cow

4-Hour Work Week

Wozzeck by Alban Berg

Drepung Gomang Institute (for whom we translated Hindi)

What Would You Rather Be Doing?

Ask Sunday – the company I mentioned that helped me with research

My exercise bike

Arduino – I used this to create the interface to my exercise bike

Gosu – The game library I used to write my exercise bike “game”

Building Games with Ruby – Andrea O.K. Wright’s presentation on game development in Ruby

You and Your Research – Richard Hamming at Bell Labs

Fixing Broken Windows: Restoring Order And Reducing Crime In Our Communities

The Pragmatic Programmer

Discussion Panel: Women in Rails

14 Worst Health Mistakes Even Smart Women Make – Referenced Harvard and University of Texas studies on the effect of the company you keep

How to Call Attention to Your Music – Derek Sivers free ebook

15 Things Kurt Vonnegut Said Better Than Anyone Else Ever Has Or Will

In my ongoing quest to keep myself honest, here's another piece of music I wrote. This one I started over a year ago, but then put down for a while. I think it really wants to be a lot longer piece—maybe one day.

I started in on the twice-yearly task of pruning our hedges today. So confronted with this task:

Which tool would you use?

I used both today, but realized I enjoy using the hand trimmers much more. With the electric trimmers, you can buzz through a lot of hedge quickly, but sometimes this happens:

With the hand trimmers, I can take my time and make precise cuts. The end result may take more time, but it turns out much, much better.

Software tools have similar feels to me. Java feels an awful lot like the electric trimmers. It’s heavy and powerful, but sometimes by the time you’ve finished with it, you’ve cut so far in that you may have missed a simpler, lighter solution.

Ruby feels like the hand trimmers. Precision, less code, more intent, and I can take my time to think through and arrive at a solution without leaving a huge trail of trimmings (code) behind me.

A Denial of Service vulnerability has been found and fixed in ruby. The vulnerability is due to the BigDecimal method mishandling certain large input values and can cause the interpreter to crash. This could be used by an attacker to crash any ruby program which creates BigDecimal objects based on user input, including almost every Rails application. This vulnerability has been assigned the CVE name CVE-2009-1904.

For upgrade instructions and information on affected ruby versions please see the ruby security team’s announcement.

All users are advised to upgrade their ruby installations immediately to avoid this problem. In the event that you are unable to upgrade your ruby installation, or are using an out-of-maintenance ruby version, there is a workaround available on github. You can either install it as a gem, or simply copy the file bigdecimal-segfault-fix.rb into config/initializers of your rails application.

NOTE: this workaround breaks valid formats supported by BigDecimal, users should not rely on this fix for an extended period of time but should instead immediately begin planning a migration to a supported ruby release.

The upcoming Rails 2.3.3 release will include some minor mitigating changes to reduce some potential attack vectors for this vulnerability. However these mitigations will not close every potential method of attack and users should still upgrade their ruby installation as soon as possible.

Thanks to Jose Fernández for reporting the vulnerability to the rails security team, and to the ruby security team for confirming the nature of the bug and handling the release process.

It’s just the beginning and a small milestone, but it’s a goal we set for ourselves by JavaOne last week that we reached: 10K registered users at http://kenai.com/. We were fortunate to be highlighted in the Tuesday afternoon keynote, which, to our collective relief, went off without a hitch. I also had a chance to speak a bit about Project Kenai behind the scenes in my technical session.

My slides are available and contain a decent overview of what we’ve been doing. One slide in particular seems to have surprised some folks: our codebase metrics.

• 12K lines of application code (everything in app/{controllers,models,helpers})
• 10K lines of views (HTML + template code in app/views)
• 1K lines of custom Javascript (public/javascripts excluding jQuery and plugins)
• 8K lines of test code (RSpec + plain text stories) (yes, we’re upgrading to Cucumber)
• 73.7% test coverage

If you’re doing Rails, you’re probably not all that surprised by these numbers; hopefully you’ve seen similar ones yourself. If you haven’t tried Rails, consider a site like kenai.com and ask yourself if you could build and maintain a production site like it with these numbers in your favorite language/framework.

Other takeaways from my talk:

• Use Java what it’s good for; in this case, long-running server apps. The downtime of the JRuby/GlassFish-deployed Rails application has been minimal for us; the few cases where we’ve had issues, they’ve usually been self-inflicted application problems. Instead of running Monit with a pack of Mongrels that need to be periodically recycled, we run a few GlassFish domains per server and only recycle them when we deploy new code.
• For the Java programmers out there, don’t be afraid to use stuff other than Java. We use Python, Django, Memcached, Perl, and anything that gets the job done.
• You can build cool stuff quickly with community Rails plugins like attachment_fu, geokit, and will_paginate. Not news to Rails programmers, but I’d be interested to hear of any equivalents for Java-based web frameworks.
• JRuby is a big win, allowing co-development on MRI and JRuby with deployment to GlassFish. JRuby’s java integration also allows for neat tricks like image_voodoo, a pure-Java imaging plugin for attachment_fu.

I’m reading Vagabonding: An Uncommon Guide to the Art of Long-Term World Travel by Rolf Potts. I’m only a quarter of the way through it and it’s already worth the price. In the third chapter, Rolf talks about the American reaction to the Exxon Valdez oil spill in the late 80s. The nation suddenly became, on the average, much more environmentally minded. So what did we do? We bought “environmental” products. Recycled products, energy-efficient this-or-that, health food, etc. What did we not do? Actually change our behavior.

Here’s a quote from page 29:

The more our life options get paraded around as consumer options, the more we forget that there's a difference between the two.

When I read this I recognized a pattern in myself and many people (everyone?) I know:

• You want to lose weight, get excited and buy a bunch of books, magazines, DVDs, etc. on weight loss. Join a fitness site where you can log calories and workouts. Buy a book about a diet with an enticing name.
• Want to learn a new technology? Get a bunch of books, sign up for a mailing list.
• Train for a triathlon? Tons of triathlon books, a bicycle, funny triathlon clothes, triathlete magazine, etc.
• Want to learn a (human) language? Buy some software and books, music, movies.
• Want to learn an instrument? Books, an instrument, a case for the instrument, various accessories.
• Get more organized? Productivity books, a PDA, PIM software.

I do this all the time. I decide I’m going to do something challenging, and my first step is to load up on stuff related to whatever it is I want to do. My second step is to continue to load up on stuff related to the topic. And so on.

Why do we do this? Because we know that we’re staring in the face of something that’s both very important and very scary. We want to feel like we’re doing something about whatever goal it is we have in mind. And the easiest way to feel like we’re doing something is to buy stuff.

What’s upsetting is to realize that in my case, simply buying the stuff is all I typically need to get enough of the feeling that I’m “dong something” to be satisfied. The end result? I’m fat, I still can’t program in Haskell worth a damn, I haven’t run the triathlon, I don’t know Spanish, I can’t play accordion very well, and I’m totally unorganized.

Experiment: next time a really important goal comes along, I’m not allowed to do any discretionary spending related to that goal.

My hypothesis is that unfunded life goals stand a better chance of being met.