Bring It On

I just ran into an interesting old post from Eric Lippert about How Not to Teach Recursion. I don’t necessarily agree that calculating Fibonacci numbers is a bad example, but I might have a good one.

When I was a second year CS student I had a crush on a girl. I don’t remember any more, but I think we were already dating then. She asked me to help her with the written exam for the first year programming course. At that time they teach you Pascal as a language and a bit about algorithms in general. So I faked my way in and did the test for her (hey, I was young, stupid and horny).

As a geek, I decided to go with the hardest problem out of four we were presented. This problem carried the most points so I figured if I solve one more she’ll barely pass (I didn’t want to overdo it). The easiest (assuming you’re not afraid of it) way to solve the problem involved recursion.

Here’s the problem: imagine a chess board of arbitrary dimensions. Some of the “positions” are occupied and cannot be used. Your “figurine” is at arbitrary position Xs, Ys and can move only horizontally or vertically to the adjacent positions, unless the new position is occupied. Elsewhere on the board at the position Xt, Yt is a goal. You need to find the shortest path from the start to the goal position.

If there were no occupied positions this could have been solved semi-manually and iteratively. But there are potentially many, so the recursive solution that essentially exhausts all of the possible paths worked just fine.

I’m not sure if this is a good way to teach recursion, but it sure is a better motivation example as the backtracking can easily be visualized.

It turns out Joel’s primary product FogBugz is written in Wasabi. Wasabi is a custom language rooted in VBScript with added coolness like lambdas, closures, LINQ-like embedded SQL etc. Wasabi does not compile into native code nor is it interpreted – it compiles to VBScript or PHP. Wasabi compiler is written in C#, but this fact is mostly irrelevant.

To say that this generated a lot of controversy would be a huge understatement. The problem was that just a bit prior to this post, Joel ranted on and on about Language Wars. Executive summary – Joel’s friend asked for an opinion on which Web development language to choose for an enterprise level application. Joel’s response was to go with the safe approach – with the languages and frameworks that have been confirmed in practice, like Java, .NET or PHP.

Combined with the Wasabi post, many accused Joel of “do as I say, not as I do” attitude. Further, because Rails and Ruby were not among the recommended frameworks/languages, Rails fanboys decided to retaliate. Even Rails creator David decided to chime in with the post Was Joel’s Wasabi a joke?.

I’d like to draw your attention to a typical and reasonable comment from joe to the David’s post:

C# is cross platform (with mono). Java is cross platform. Python, lisp, perl, ruby, haskell, and a thousand other languages are cross platform. Some of them are even "enterprisey". Given all of the above why would you waste time writing a compiler in c#? Why not just rewrite your app in c# and call it a day? Why cross compile to php AND VB? PHP runs fine on windows and it supports IIS and SQL server, why don't you just write it in PHP and call it a day?. If you want to distribute your app then why not have your compiler spit out a C apache module? I can't believe Joel would be so stupid as to write a compiler which spits out PHP and Vbscript. It just doesn't make sense. It's ridiculus on the face of it. He is just messing with you guys and you guys are falling for it.

Basically, joe wonders about the same thing as I did in my previous post – wasn’t it also possible to rewrite FogBugz into a platform independent language at the time it was decided to make it multi-platform?

The answer is not a simple yes or no. If you’ve read Joel since “the beginning” you know that he is against most rewrites (and he’s right). If the circumstances are such that there’s no other way, sure – but otherwise keep the codebase and keep patching it. So it makes more sense to make a compiler that will transform VBScript to PHP than to rewrite the whole codebase in PHP. This might have been the only reasonable decision, if the codebase was larger than most of us think. Without Wasabi, all of Joel’s developers would have to suddenly become top-notch PHP developers, which would cost money in training and increase the risk of bugs introduced just because the developers didn’t know the language well.

Once they had their own compiler they realized that they could now start improving the language as long as the new constructs can be compiled into the constructs of the languages they compile into. Soon they ended up with a language in many ways superior to the average scripting language like VBScript, yet they incurred almost zero training cost and zero risk. That sounds quite good to me.

This does not mean that the rewrite was out of question. It just means that Joel is not nearly as “stupid” as joe would imply.

Personally, if Rails showed up sooner and matured some time before FogBugz was supposed to become multi-platform, I wouldn’t be surprised if Joel switched to it. But the timing was not right and now it’s too late.

There was a lot of discussion about the Joel’s post Ruby Performance Revisited. I guess this was just a flamebait, but I’ll bite. Here’s the relevant quote (bold emphasis mine):

Even though our product, FogBugz, seems like something that should be perfect for Ruby on Rails, we have several parts of code where performance is extremely important. In FogBugz 6 there's one place where we need to do literally millions of calculations to display a single chart on a single web page. We have gotten it down to 3 seconds or so in our current development environment with a lot of optimization, but frankly with a duck-typed function call I really don't think we could do it before the web browser gave up and timed out and the sun cooled down a couple of degrees.

So the problem is that there are millions of calculations for a single chart. And Joel’s VBScript based application can handle this in 3 seconds? I don’t think so.

The chance is extremely high that the chart generation is offloaded to a COM component written in C or C++. There’s just no way VBScript could handle this problem any better than Ruby. Ruby can easily call native code too, so why this argument then?

Like I said, I think part of this is deliberate – Joel needs people linking to him (notice the irony; I am aware of that yet I am linking). The second part might be inability to admit that there was an alternative solution to Wasabi (more on this in the next post) and that FogBugz 3/4/5, whichever was the first multi-platform version, could have probably be written in a singe common codebase in PHP/Ruby/Python.

Joel is extremely cool, but this post stinks. Most of the Web applications that do not need to scale “indefinitely” (think Amazon or IMDB) can be equally well written in Ruby, Python, Perl or VBScript/JavaScript. There are other reasons why FogBugz should not have been rewritten in one of these languages, but speed sure isn’t one of them.

I realized quite late in the game (pun intended) how cool the console gaming is vs gaming on the PC. For years, ever since the early Doom days I’ve been gaming on a PC. But then the graphics cards’ prices increased so much that I could usually buy the whole console for the price of a mid-class 3D card.

I got my Xbox at the very end of 2004. It was holiday season, Halo 2 just got out with rave reviews around the ‘net… My wife and I were walking around Carrefour (very roughly speaking an European equivalent of Wal-Mart) shopping groceries and discussing Christmas/New Year presents. It was actually her that suggested that I buy myself an Xbox. On a whim, something I rarely do when electronics are in question, I just put one in the trolley.

Couple of months later I was pleasantly surprised how good the decision was and have never looked back – I’m a “console guy” now.

Jumping in so late has its advantages – there were plenty of games to choose from and most were cheap (launched months ago). The platform was already mature so new games coming out would often use the hardware to its maximum.

When Xbox 360 launched, I did not rush to buy one. I still had almost dozen games to play on my “old” Xbox and I knew that buying a revision 1 hardware was never good idea anyway, so I waited. I also saw the games running on a HDTV LCD and decided to only go with the next-gen console with the next-gen TV.

Finally the starts aligned – in the next couple of weeks, I am getting a new LCD TV, a new PC (with a relatively low end graphics card, just enough to run Vista ) and a shiny new Xbox 360 (ordered it yesterday).

I got a great deal. Xbox 360 Premium with the best game so far “Gears of War” is only 434€. Since the console is officially 399€ that means I get the game for only 35€ (retail price usually around 60€!). On top of this, I get 50€ coupon from Microsoft (trivially easy to cash in) and a 40€ voucher from Amazon. The Amazon voucher sucks for general public because you only have 30 days to use it, you must buy over 80€ worth of goods from Amazon to cash it in, but I’m buying a new monitor on Amazon anyway so for me it’s a non-issue. Microsoft’s coupon is a lot better deal – you don’t have to buy anything extra, you have several months to cash it in and they will put the money on your account directly.

So let’s see – with 90€ discount, I get my console for 309€! On top of that, I save 25€ on the best game for the Xbox 360 until now.

I’d say it’s hard to pass this up, especially in the light of the new 1 year warranty for the console (US only for now, but should trickle down to Europe soon hopefully).

I’ll post a couple of pictures when I get the new TV. Unless I change my mind at the last moment, I’m going for 32” Samsung LCD TV LE32R73BD.

I am having trouble with the mastervac which is a pump that assist breaking in my Peugeot 206. When the pump does not function correctly, it takes more force to break. The problem is easily detected – you can hear a hissing sound coming from the general direction of the break pedal – it’s the air escaping when it shouldn’t.

So I took an appointment with local Peugeot service which was supposed to take place today early in the morning at 8:15. They did not have the part in stock when I called last week but they ordered it immediately. However it’s a holiday season now and everything takes a lot longer than usual…

The cool thing is that around 7:30 (?!?) this morning, I got an SMS from Peugeot service notifying me that the part is not available yet and that they’ll let me know as soon as they have it.

This is one of the few rare cases when I did not mind getting unsolicited SMS from someone

I don’t know who started it first, but now every top blogger is thinking (some are acting already) about providing a job board. I first noticed it when Joel Spolsky did it. In his case, it was only natural – highly focused “blog” like his is read by thousands of developers who pride themselves of being, well, better than the average. Presumably, on a job board where his readers would apply, there will be much higher percentage of good candidates than elsewhere. To balance things, Joel imposed some rules on the job providers too, effectively cutting out the middle man (hiring agencies), trying to make the whole experience good for both sides.

It appears that he, at least financially, succeeded. Based on the numbers for just the first week, the job board earned $40K (the numbers are smaller as the novelty wore off and amount to less than $10K now). That’s a lot of money for something that an intern hacked up with Joel over a few weeks, part time. Naturally, it’s not the site’s technical merits that attract job seekers and providers to Joel’s site but his reputation (and by extension “reputation” of his readership), something he has built up over the years.

Before Joel, I knew of one other company that did this, but in their case it made even more sense – 37signals, the authors of the Ruby On Rails framework, have a job board for RoR jobs – even more targeted than Joel.

The last one I encountered just a few days ago is Guy Kawasaki’s job board. Guy is a cool guy but not a developer – you could say that he is a marketer. His blog is a lot younger, but he worked fiercely to capture as much readership as possible  and appears to have succeeded. His logic is the same - come to my site, my readers demographics are here, my readers are entrepreneurial… He does charge a lot less than Joel though and won’t make a lot of money IMHO. But it may end up paying rent, or something like that, which is not bad at all.

For me these are one of the few completely legitimate business moves enabled by the Web. There’s no hype here and the boards provide a real value, the business model is sound and clean.

If only I had tens of thousands of readers…

Yesterday I mentioned the strange way the thread pool was described and implemented in the (most excellent) book Ruby Cookbook. I’m not sure if I’m allowed to “re-print” portions of the source code, but the code snippet in question is easily accessible online. Go to the site above and click on Tests column for the chapter 20, section 7: Limiting Multithreading with a Thread Pool. To make the test more interesting, change the end of the test to run 100 threads, and sleep for only 1 (one) second (I do the same in the code that follows).

Reacting based on instinct acquired while developing with C++ and C#/.NET, it does not seem smart creating all those threads. The classic definition of a thread pool is a small group of threads that you schedule the work to. But threads in C++ and C# are native threads whereas Ruby threads are green threads, so my instinct could be wrong.

Yesterday’s small test that brute-force opens hundred threads hints at one obvious cost to spawning all those threads – higher memory consumption, but the only way to confirm this suspicion is to implement a classic thread pool and compare. Here it is:

require 'thread'

class ClassicThreadPool
  def initialize(num_threads)
    @blocks = []
    @mutex = Mutex.new
    @cond = ConditionVariable.new
    
    @threads = []
    1.upto(num_threads) do
      @threads << Thread.new do
        run
      end
    end
  end
  
  def dequeue
    @mutex.synchronize do
      @cond.wait(@mutex) if @blocks.empty? 
      @blocks.shift
    end
  end
  
  def enqueue(&block)
    @mutex.synchronize do
      @blocks << block
      @cond.signal
    end
  end
  
  def run
    while(true)
      blk = dequeue
      break if blk.nil?
      begin
        blk.call
      rescue => e
        puts "Exception #{e} during job processing" 
      end
    end
  end
  
  def shutdown
    1.upto(@threads.length) { enqueue }
    @threads.each { |t| t.join }
  end
end

#Now test it

pool = ClassicThreadPool.new(3)

1.upto(100) do |i|
  pool.enqueue do
    print "Job #{i} started.\n"
    sleep(1)
    print "Job #{i} complete.\n"
  end
end

pool.shutdown

The code is very much alike the original code, except that for the pool of size P, only P threads are created. Each code block (job) scheduled to run is saved in an array and then executed on the first free thread from the pool. Threads in a pool run an efficient loop that waits for the available jobs and then executes them. When it’s time to shutdown, the pool schedules P nil blocks, allowing the infinite thread loops to exit, then the pool just joins the threads waiting for all of them to exit.

The result is very clear: this approach is far more efficient memory-wise. It starts and ends consuming about ~3.1MB of memory. Comparable example from the book starts with ~7.3MB dropping to ~3.7MB at the end.

Moral of the story: creating threads is never cheap, even on systems that implement green threads. You don’t incur the cost of setting up the real OS thread, but you do waste memory. Just because it’s easier to spawn a thread in Ruby doesn’t mean you should do so lightly.

On the other hand, if there are no bursts of activity, so there are only a few more threads than the pool would normally execute at any given point in time, then the difference between these two approaches is academic. Still, I’d rather use the solution that scales well under all circumstances than the one that only works well under specific conditions

The raw speed of the processor hasn’t significantly increased in years. The efficiency increases, slowly, but there’s no “free lunch” as it was before – getting a 200MHz processor used to get you twice the speed of the 100MHz processor. If you want better performance today, you go for a multi-core processor (Intel has recently launched a consumer-level four core processor).

For an app twice as fast as before, without a double-clock-speed at your disposal, you resort to parallelism, which is a hard topic. If I have a four core processor, I’d want to run my code on all four cores at once, if possible (note that not all problems can be parallelized). The way programming languages and processors expose parallelism is through threads.

Now, we are all used to working with threads in this way or another. Me, I’ve been doin’ some threadin’ mostly in C++ and C#. In C++, it was a major PITA if you did not have at least boost at your disposal. With C#/.NET, it’s mostly been a completely transparent experience. In some cases, you could be using threads and thread pools even without knowing it (asynchronous delegates are a great example).

Having this kind of background, I expected no real surprises in the chapter 20 of the very good Ruby Cookbook. But there were quite a few .

First of all, if you know some Ruby, but would like to improve your knowledge and you like to learn by example, get this book. It’s chock full of code snippets for almost any kind of real-life scenario. You don’t have to read it in order and can jump straight to, well, chapter 20 if you like

Section 7 talks about the thread pools. Thread pools are relatively easy beasts to comprehend, having in mind the following facts:

• running T threads on a single core processor will not make your code faster
• running T threads, where each is blocked most of the time (waiting for something, like file read or a database access) assuming each threads takes about X seconds to complete will in general execute in X + overhead seconds (overhead is relatively small), compared to T times X seconds if the code was run sequentially
• starting a thread is generally cheap, unless you do it all the time – there is a cost to setting the thread up
• therefore, it’s beneficial to pre-create P threads, keep them in a pool (just a fancy name for a group of threads) and then schedule work to each of the threads in a pool

The classic use case for a thread pool is a Web server. Most of the time, there will be either less than P requests (where P is the size of the thread pool) or, during short bursts, at most N times P requests (N relatively small). Usually, the requests will be I/O bound, most threads will wait for the disk, and the tasks will eventually execute.

Having all this in mind, I was shocked to see the thread pool example given in the book (source code is freely available from the web site above). In short, the scheduling looks like this:

class ThreadPool
  # ...
  def dispatch(*args)    
    Thread.new do
      # Wait for space in the pool.
      # ...
    end
    # ...
  end
  # ...
end

I omitted most of the code for clarity. What’s wrong with this picture? Well, for each new task/job/work item (names are used as synonyms in most threading texts), the class first creates a new thread, then waits for the “space in the pool”. For a 10 thread pool, if there is a short burst of activity, and you have 100 tasks to schedule, 100 threads will be created, of which only 10 at most will execute at any point in time.

This is obviously a different definition of a thread pool. Any programming book will tell you not to go overboard with threads and to create as few as is necessary. Why is the example written this way then? It’s definitely not because the book authors are incompetent as many great code examples from the book clearly show. I must be missing something…

Suddenly I realized that I recently read about Ruby providing green threads. Green thread is a term used to describe a “fake” thread, something that does work as a thread but does not use underlying OS thread facility. Note that in .NET for example, it is not guaranteed that a .NET thread will correspond to a real OS thread, even though it does at this point in time. Some Java JVMs allow you to choose between native and green thread approaches.

Ruby apparently provides green thread model only. This is very easy to confirm with the following short code snippet:

require 'thread'

def spawn(*args)
  Thread.new do
    yield(*args)
  end
end

1.upto(100) do |i|
  spawn(i) do
    puts "Running thread #{i}..."
    sleep(10)
    puts "Finished thread #{i}"
  end
end

sleep(15)

(I simplified the code by putting a longer sleep at the end, what you should do is join each of the threads and wait for their completion). Run this and if you are on Windows, have a look at the number of threads of this small script in Process Explorer. It’s 1 (one)!

This could imply that thread creation is cheap, which would explain the approach as given in the book. But it still goes against my instinct as a developer – it can’t be that cheap, at least you’d waste some memory, right? I don’t have fancy memory profiling tools, but assuming that Ruby’s garbage collector runs between the time all of the threads finish and the last sleep finishes (5 seconds gap) you should see the rough memory cost of the creation of 100 threads. Let’s see…

When all 100 threads are running, the working set of the process is 4904KB (running on Windows XP, on a 32bit Intel processor). When all of the threads exit, the memory consumption drops to 3464KB. The numbers are identical over many runs of the test. If I increase the number of threads significantly, both numbers increase significantly (for a 1000 threads, before and after numbers are ~20MB and ~9MB respectively).

So 100 threads cost you 1440KB, roughly. Note that there are many blocks created and it’s quite possible that it’s the block creation that costs memory, not threads. The testing methodology is obviously not scientific

Tomorrow, I’ll build a traditional thread pool and we’ll see if it makes any difference. To reiterate, in a traditional thread pool, only P threads are created and then work is queued and scheduled to run on one of the threads in a pool.