awk vs. Python performance

There are a lot of debates where people (try to) compare the relative performance of programming languages. These conversations range from producing extensive benchmarks to coming up with esoteric metrics about code complexity/maintainability to deriving even more esoteric metrics from (perceived) language/platform popularity.

I thought I would put my two cents into this game by describing a microbenchmark inspired by an actual task of mine: convert a file of delimited values to LIBSVM's data format. That is transform each line of

num1 num2 num3 num4 ...

to

num1 1:num2 2:num3 3:num4 ...

I'm omitting details about (LIB)SVM here, but this isn't relevant now. The point is that the first field is kept in the output, but the rest of them are prefixed with 'number of field in line minus one' and a colon. Note that columns may be omitted in the output, but field indexes must be ascending within a line (this is the so-called sparse matrix format).

Of course my first solution is in Python:

for line in file:
    cols = line.strip().split()
    print " ".join(["%i:%s" %(i, x.strip()) 
                    for (i, x) in enumerate(cols)])[2:]

For a file with 100k lines and 128 columns, this runs in 38 seconds on my WINDOWS box.

Not too bad, but there is an itching disturbance, which does not let the urge to rewrite it in awk escape me. I never wrote a single line in awk, so this should be a good start.
And lo, my first awk program:

{
    printf("%s", $1)
    for (i = 2; i <= NF; i++) 
    {
        printf(" %i:%s", i-1, $i)
    }
    printf("\n")
}

Let's run it on my WINDOWS box, under CYGWIN, with the same 100k/128cols file as above.

...

Ouch, this took more than 5 and a half minutes!! Shame for awk, go Python. Still it sounds like nonsense. Let's see. Both Python and awk are interpreted, so iterations are supposed to be slow(?) The Python code iterates over the columns with a library string function (join), which is implemented in C so it's blazing. awk uses 'for' extensively, so let's optimize it by unwinding the loop:

{
    print $1, "1:"$2 , "2:"$3 , "3:"$4 , [...]
    [...] , "125:"$126 , "126:"$127 , "127:"$128
}

This is a common technique used in compiler optimization, see how it works in this case. It WORKS, it runs MUCH faster. Same test file, same WINDOWS box and CYGWIN, 45 seconds. Wow, a 7-fold speedup, but still slower than Python. Is this for real? I don't think so.

Enter GNU/Linux, just for kicks, another box. The Python program runs in 31 seconds, and hey, wait a minute, we didn't have to wait a minute: the awk program is done in 17 seconds. I say, wow...

In a problem this little the use of Python was not too justified. In awk you even get mixable standard input / file handling for free, whereas in Python you must implement it by yourself. But when script portability is a concern, you still should consider Python even for a trivial task like this, because you could get more balanced performance. Of course you could give a try to Psyco, the Python optimizer, but you will have another dependency, and it may as well turn out that you're performance will even be much worse! More on this later.

Right tool for the right task, but know you environment too.

Shake Ya Tailfeathers (A Haskell Puzzle)

Deciding that the Scala bandwagon is far too hot right now (in the sense that I should wait a bit till I'll be eligible to late-adopt it) I've started learning Haskell instead.

After reading and processing the first some chapters of YAHT and still not getting CPS, I nevertheless wanted to produce something, so came up with this:

It's a puzzle I've learned a long time ago called Tailfeather.
Tailfeather is a number-sequence, where the very first element is lress than the last one, the second element is lress than the second to last element and so on.
The task is to write a function with the specification:

tailfeather :: Int -> Int
{- tailfeather n = b
    where 'b' > 1 is the smallest radix in which
    the digits written of 'n' 
    form a Tailfeather sequence of numbers 
-}

A very nice, very entry-level stuff. And the very beauty of it all is that implementing this solution was absolutely straighforward: I was able to focus on the actual problem without worrying about the underlying details (like how to represent a number-sequence -- is that an ArrayList or and array?)
Actually there are two sub-problems: A) rewriting a decimal number to another radix and B) determining whether a sequence is a Tailfeather.

Starting with the latter subtask, all you have to do is break a list into three parts, and solve the task recursively, like so:

tailfeather0 (x:xs) = 
    (x < last xs) && 
    (tailfeather0 (init xs))

First we check if the Tailfeather property holds for the first and the last elements, then cut those elements from the list (that is take the init of the tail) and check the remaining part.

Of course the recursion must be terminated (and this next code MUST appear before the previous fragment):

tailfeather0 [] = True
tailfeather0 [x] = True

DONE.

Let's see problem A. If you don't know the proper algorithm for converting from decimal to another radix, it is given here (if the site is down use Wikipedia).
My first naive rewrite of the example provided on the linked page yielded the following:

convert2base2 0 = []
convert2base2 n = (mod n 2) : convert2base2 (div n 2)

Looks tight, the only problem is that it returns the digits in reverse order (starting with the least significant bit). Reversing the list after the whole computation would be an option, instead I do it in place:

convert2base2 n = convert2base2 (div n 2) ++ [mod n 2]

Generalizing the converter to accept any base (don't use this one with b <= 1):

convert2base _ 0 = []
convert2base b n = convert2base b (div n b) ++ [mod n b]

Now that we have our building blocks, let's combine them:

tailfeather n = tailfeather1 2 n

tailfeather1 b n = 
        if (b == n)
            then b+1
            else if tailfeather0 (convert2base b n)
                then b
                else tailfeather1 (b+1) n

That's it.

Scala: Tail-Recursive Higher-Order Function

Last time I showed a simple handbook tail recursion solution. Digging deeper into Scala and functional programming, I've bumped into more interesting stuff. Introduce some new terminology:

1. A higher-order function is a function which takes other functions as parameters or returns another function. For example

  def sum(f: Int => Int, a: Int, b: Int): Int =
    if (a > b) 0 else f(a) + sum(f, a + 1, b)

defines a higher-order function which takes a function f plus two integers, and returns the sum of every f(x) in the interval (a, b).

2. An anonymous function is simply a function with no name. It's really just syntactic sugar but comes in handy when fiddling with higher-order functions, see:

  sum(x => x * x, 10, 20)

is a call to the above-defined function, with the (unnamed) square-function as the first argument.
Watch how the compiler automagically infers the type of x here.

3. Currying is another interesting concept, nicely described here. Currying lets you decompose argument lists arbitrarily, hence serving a nice ground to refactoring. Taking the sum example, we could rewrite it in a way that we factor out the interval-parameters from it's argument-list, and make it just pass back another function, which in turn deals with the intervals. Like so:

  def sum(f: Int => Int): (Int, Int) => Int = {
    def sumF(a: Int, b: Int): Int =
      if (a > b) 0 else f(a) + sumF(a + 1, b)
    sumF
  }

Try it out:

  sum(x => x*x)(10, 20)
  def s = sum(x => x*x)
  s(10,20)
  s(20,30)

Putting it in a more concise form, we are currying:

  def sum(f: Int => Int)(a: Int, b: Int): Int =
    if (a > b) 0 else f(a) + sum(f)(a + 1, b)

This is just a more compact form, but means the same as the previous one, you can still go

  sum(x => x*x)(10, 20)
  def s = sum(x => x*x) _ // note the underscore!
  s(10,20)
  s(20,30)

To wrap it all up, take exercise 5.2.1 from Scala By Example: rewrite sum (the curried version) to use tail-recursion.
Converting linear recursion to tail-recursion shouldn't be too hard: instead of recursively calling your method and then applying the iterating function in every step, you accumulate and recursively call on the partial results. Looking at the previous solution you would find it's really easy, and it goes like this:

  def sum(f: Int => Int)(a: Int, b: Int): Int = {
    def sum1(a: Int, result: Int): Int = {
      if (a > b) result
      else sum1(a + 1, f(a) + result)
    }
    sum1(a, 0)
  }

Scala: Tail-Recursive Factorial

Scala By Example has a smallish exercise (4.6.1) to desing the tail-recursive version of the following function:

 def fact(n: Int): Int = if (n == 0) 1 else n * fact(n - 1)

Tail-recursion means that the recursive call is the last call in the body of the function. In other words, the last operation computed is a recursive function application. In this cited example, the last expression is a multiplication, which renders the body non-tail-recursive.

To make the implementation more efficient, we have to turn the body inside-out and accumulate each step's result of the multiplication. This can be nicely done with the great nested function feature, see:

 def fact(n: Int) = {
   def fact1(n: Int, acc: Int): Int = {
     if (n == 0) acc
     else fact1(n - 1, n * acc)
   }
   fact1(n, 1)
 }

Notice how in this version I didn't mention the return type. The compiler can infer it, but I would consider it good practice to explicitly declare the intended type. However, recursive methods must always declare their return type (you get a neat compiler error should your forget it).

Shale, Struts, Spring, Tapesty, Stripes, Wicket, Whatever, Rails

I believe I've stated my dislike regarding web applications before. And again. I'm not being Luddite here. I like interesting and exciting stuff, as I told.

But taking J2EE and Java as an example, well, web development really can be painful. There are a helluva lot of frameworks, and you really have to learn a stack of stuff before you even can start working. And you really have to figure out the best way to go. As for me, I wish I hadn't gone with Core J2EE Patterns: Best Practices first, but J2EE Best Practices instead -- or better yet, with J2EE Design Patterns. Those worked out the best in may case, at last. For the learning part. As for the Getting The Job Done part, well, I'm still not convinced I went for the best route. I had to create a very simple web app: very little functionality, no persistence, very lean state-machine. KISS being one of my two main principles I've gone with implementing all of it on top of JSP/JSTL: no frameworks attached. DRY being the other principle I came to the conclusion I had to implement the Composite View pattern. Dug up the aforementioned (and a lot of other) books, read everything back and forth, and never got it.

And that's when I realized why we see a ploriferation of opensource Java web application frameworks: Because nobody ever understood what the fuck people were talking about when describing the J2EE patterns, so newcomers had to roll their own framework. Then they had to identify some design considerations in the new framework, so they just simply invented some new patterns, and which started everything all over again. As long as there is no general mindset about which framework(s) to use, people are doomed to the framework-boom. This is why Rails being the de facto web-framework for Ruby is doing so good for the Ruby community.

Event handling in C# for the Java developer

For months now I've been working on a C# WinForms project. Things are supposed to be easy for me, cause C# is just a copy of Java, right? Well sure, ok, I'm using C# 2.0, so I'm not supposed to see so much divergence from Java. True enough. There are grave differences however in a lot of areas, generics and events for example. Right this time, I've to delve into the latter.

Event-based programming is a powerful mechanism to enable two-way and multiplexed communication between interested parties. Event-based programming is main usage of the Observer pattern. Events are used extensively in GUI programming. That's why in Java, the events-mechanism is part of the AWT package of the standard library. In .Net world however, it's part of the core framework, which makes it a tad harder to comprehend -- although it allows for more diverse usage of them. For advanced examples check the very useful Pro C# 2005 and the .NET 2.0 Platform, Third Edition book from Apress. For a simple, Java-C# side-by-side comparison see Dare's post.

Why 3-tier is easier than 2-tier?

I really hate webapps. I'm not talking about fun and hip things like JRuby on Rails or (more) exotic and interesting things like Seaside. Pure "enterprise" pretty-graphical-decorations-over-a-relational-database class of stuff makes me cringe really. It's repetitive, unexciting, dull. I hate the way AJAX tries to reinvent the wheel, by relaying logic to the client, once again. More on this later.
There is one strong benefit on theserverside tho: web architecture forces you to use some kind of layering. However good you might be in mingling presentation logic with business logic, you will be always given contextual boundaries between the DB the webserver and your client. You can't just grab something from a backend, parse it into an object, and drag it around your 2-tier app as long as the user turns off her machine before Winter Holidays. Endulging yourself into saving a few hours by not caring about immutability, proper encapsulation et al. Not good.
Take your webdeveloper hat and present users a real interface.