Code for Concinnity

Today I received a dump file from a client. I fired up WinDBG and met this dreaded error. If you stumble upon this post you have probably tried all the other Google solutions (such as updating to the latest WinDBG).

Here are what I tried, and failed:

Here is how I solved it:

• First, I run the .cordll command that everybody recommends

• The client was running Windows Server 2003 SP2. The mscordacwks.dll I have in my Windows 7 box was 2.0.50727.5448

• So, it looks like this DLL is actually missing on MS’s server.

• In a desperate atttempt, I tried to search the file in Google

• To my surprise, I found the file in a security update

• I downloaded the x86 file, opened the file in a zip and scavenged the required DLLs from there.

• I had to rename the DLL files. In particular, I needed to duplicate mscordacwks.dll to mscordacwks_x86_x86_2.0.50727.3625.dll to please WinDBG

• Load SOS manually .load C:\newly\downloaded\sos.dll

• .sympath+ C:\newly\downloaded; .reload

• (You may encounter an error if you have 2 SOS loaded at the same time. .chain, .unload should take care of stuff)

• Volia! Now the game begins

Well, I lied. This isn’t step by step but I believe this commented source code dump should be more illustrative than any tutorial I’ve read, here we go

// fun.cpp

extern "C"
{
#include <lua.h>
#include <lauxlib.h>
#include <lualib.h>
}

#include <iostream>
#include <sstream>

class Foo
{
public:
    Foo(const std::string & name) : name(name)
    {
        std::cout << "Foo is born" << std::endl;
    }

    std::string Add(int a, int b)
    {
        std::stringstream ss;
        ss << name << ": " << a << " + " << b << " = " << (a+b);
        return ss.str();
    }

    ~Foo()
    {
        std::cout << "Foo is gone" << std::endl;
    }

private:
    std::string name;
};

// The general pattern to binding C++ class to Lua is to write a Lua 
// thunk for every method for the class, so here we go:

int l_Foo_constructor(lua_State * l)
{
    const char * name = luaL_checkstring(l, 1);

    // We could actually allocate Foo itself as a user data but 
    // since user data can be GC'ed and we gain unity by using CRT's heap 
    // all along.
    Foo ** udata = (Foo **)lua_newuserdata(l, sizeof(Foo *));
    *udata = new Foo(name);

    // Usually, we'll just use "Foo" as the second parameter, but I 
    // say luaL_Foo here to distinguish the difference:
    //
    // This 2nd parameter here is an _internal label_ for luaL, it is 
    // _not_ exposed to Lua by default.
    //
    // Effectively, this metatable is not accessible by Lua by default.
    luaL_getmetatable(l, "luaL_Foo");

    // The Lua stack at this point looks like this:
    //     
    //     3| metatable "luaL_foo"   |-1
    //     2| userdata               |-2
    //     1| string parameter       |-3
    //
    // So the following line sets the metatable for the user data to the luaL_Foo 
    // metatable
    //
    // We must set the metatable here because Lua prohibits setting 
    // the metatable of a userdata in Lua. The only way to set a metatable 
    // of a userdata is to do it in C.
    lua_setmetatable(l, -2);

    // The Lua stack at this point looks like this:
    //     
    //     2| userdata               |-1
    //     1| string parameter       |-2
    // 
    // We return 1 so Lua callsite will get the user data and 
    // Lua will clean the stack after that.

    return 1;
}

Foo * l_CheckFoo(lua_State * l, int n)
{
    // This checks that the argument is a userdata 
    // with the metatable "luaL_Foo"
    return *(Foo **)luaL_checkudata(l, n, "luaL_Foo");
}

int l_Foo_add(lua_State * l)
{
    Foo * foo = l_CheckFoo(l, 1);
    int a = luaL_checknumber(l, 2);
    int b = luaL_checknumber(l, 3);

    std::string s = foo->Add(a, b);
    lua_pushstring(l, s.c_str());

    // The Lua stack at this point looks like this:
    //     
    //     4| result string          |-1
    //     3| metatable "luaL_foo"   |-2
    //     2| userdata               |-3
    //     1| string parameter       |-4
    //
    // Return 1 to return the result string to Lua callsite.

    return 1;
}

int l_Foo_destructor(lua_State * l)
{
    Foo * foo = l_CheckFoo(l, 1);
    delete foo;

    return 0;
}

void RegisterFoo(lua_State * l)
{
    luaL_Reg sFooRegs[] =
    {
        { "new", l_Foo_constructor },
        { "add", l_Foo_add },
        { "__gc", l_Foo_destructor },
        { NULL, NULL }
    };

    // Create a luaL metatable. This metatable is not 
    // exposed to Lua. The "luaL_Foo" label is used by luaL
    // internally to identity things.
    luaL_newmetatable(l, "luaL_Foo");

    // Register the C functions _into_ the metatable we just created.
    luaL_register(l, NULL, sFooRegs);

    // The Lua stack at this point looks like this:
    //     
    //     1| metatable "luaL_Foo"   |-1
    lua_pushvalue(l, -1);

    // The Lua stack at this point looks like this:
    //     
    //     2| metatable "luaL_Foo"   |-1
    //     1| metatable "luaL_Foo"   |-2

    // Set the "__index" field of the metatable to point to itself
    // This pops the stack
    lua_setfield(l, -1, "__index");

    // The Lua stack at this point looks like this:
    //     
    //     1| metatable "luaL_Foo"   |-1

    // The luaL_Foo metatable now has the following fields
    //     - __gc
    //     - __index
    //     - add
    //     - new

    // Now we use setglobal to officially expose the luaL_Foo metatable 
    // to Lua. And we use the name "Foo".
    //
    // This allows Lua scripts to _override_ the metatable of Foo.
    // For high security code this may not be called for but 
    // we'll do this to get greater flexibility.
    lua_setglobal(l, "Foo");
}

int main()
{
    lua_State * l = luaL_newstate();
    luaL_openlibs(l);
    RegisterFoo(l);

    int erred = luaL_dofile(l, "fun.lua");
    if(erred)
        std::cout << "Lua error: " << luaL_checkstring(l, -1) << std::endl;

    lua_close(l);

    return 0;
}

-- fun.lua

-- Because the metatable has been exposed 
-- to us, we can actually add new functions
-- to Foo
function Foo:speak()
    print("Hello, I am a Foo")
end

local foo = Foo.new("fred")
local m = foo:add(3, 4)

-- "fred: 3 + 4 = 7"
print(m)

-- "Hello, I am a Foo"
foo:speak()

-- Let's rig the original metatable
Foo.add_ = Foo.add
function Foo:add(a, b)
    return "here comes the magic: " .. self:add_(a, b)
end

m = foo:add(9, 8)

-- "here comes the magic: fred: 9 + 8 = 17"
print(m)

Last time I wrote about how to build Luabind on OS X. Well, it turned out that was only half the battle won. Building Luabind for iOS (ARMV7) architecture just plain doesn’t work. It seems like some people have managed to make it work but none of what I have found actually worked. If you are reading this, I suppose you are also tired of jumping through hoops just to compile the damn thing, well, Premake to the rescue.

Let me tell you, this is how building stuff in C++ is meant to work:

Just create a file premake4.lua

That is ALL THERE IS TO IT!

Boost Build whopping sucks. Premake is written by one guy and this turns out to be so trivial (as it should be).

Hope it helps.

A couple of years back I blogged about how I solved the frustrating and notorious “BOOTMGR is missing” error in Windows. Today I encountered it again and this time it seems to be more tenacious but I still tamed it after numerous trials. Here I document exactly what went wrong, why it happened and how to solve it.

Background information — how does Windows boot?

Here is a quick rundown. Every step below could possibly go wrong:

1. The BIOS loads the MBR of the booting disk by handing over control to the code residing there. MS’s MBR code will then load the boot sector of the active partition. (If something is wrong here, we need bootsect /nt60 X: /mbr).

2. The boot sector looks for \Boot\BCD and loads boot information from there. The BCD contains where BOOTMGR resides. If this step is wrong, you will see the infamous “BOOTMGR is missing”. To fix this, we need to correct the BCD by bcdedit (see below).

3. Finally BOOTMGR loads winload.exe. If the device or osdevice is set to the wrong partition, Windows may report that winload.exe is corrupt. Normally you fix this by bcdedit. In the rare events that winload.exe is really corrupt, you may need to do a Windows Repair.

Why did it happen?

The base case for this to happen is a multi-hard disk computer. Variations may include changing hard disks after installation, but the principle is the same.

Suppose we have a computer with 2 hard disks:

1. HDD1 (SATA 1/IDE 1)
2. HDD2 (SATA 2/IDE 2)

That is, HDD1 comes before HDD2 in BIOS.

Since Windows cannot determine your boot order from BIOS, it will always configures the MBR in HDD1, and configures the boot sector of the first partition of HDD1 and also put Boot\BCD in the first partition of HDD1. It will always be HDD1, no matter which disk you decide to install Windows on.

Suppose you have the following boot order in BIOS:

1. HDD2
2. HDD1

And suppose you have installed Windows so that:

• HDD1 — bootloader code
• HDD2 — actual Windows installation

Then booting will fail and you will see the notorious BOOTMGR is missing error. Another reason you may see this is that you remove HDD1 after some time, thinking that your Windows installation is nicely contained in HDD2.

Why is Windows Repair not enough?

If you use Winodws repair it will install the boot code in HDD1 and you are forced to adjust the BIOS to boot HDD2 through HDD1. For me, it was a purist’s reason to want to move everything to HDD2.

So here is how exactly I tacked it.

How to fix it

The following steps are assumed to be done in the Windows Recovery environment command line. Boot up your Windows CD and press Shift+F10 to call up the command prompt. We will assume:

• E: to be where Windows is installed.
• F: to be where BCD is set up.
• X: to be the Windows installation CD

 1. First, make sure you set the Windows partition as active. You can do this using various partition software or just Google how to do it. Here is an example session using diskpart. You need to replace 99 with the correct numbers:

 2. Now we gotta make sure the MBR of HDD2 is good to go:

 3. Now migrate BOOTMGR and Boot from F: to E:

 4. Now use bcdedit to fix up the BCD

 5. That’s it!

How to fix it from scratch (what I actually did)

If in the process you think you have screwed up so bad that you want to start over, you don’t have to reinstall Windows:

1. It is save to wife out both BOOTMGR and the Boot directory. You can find BOOTMGR in the Windows install CD.

2. To recreate the Boot directory, run bootrec /rebuildbcd. Windows will insist on creating it in the first partition in HDD1. You can apply the above techniques to patch up the newly created BCD and then move it to E:. Alternatively you can create BCD from real scratch by using the UUIDs from bcdedit /enum all.

3. You should be able to get Windows booted with just the two files E:\BOOTMGR and E:\Boot\BCD. If that worked you will find that Windows boots with Vista style’s green bar. To fix it:

That should be it. Enjoy!

I have been evaluating several 3D frameworks for cross-platform mobile game development lately. Here’s my findings. To stay objective, I am just going to state a couple of hard facts as conclusion:

• Irrlicht is smaller than Ogre. I did an actual experiment using both. I compiled both into static libraries (required for an iPhone deployment). A “Hello World” app with just one line of irr::createDevice (to get stuff statically linked) results in an 4MB executable; the same app with one line of new Ogre::Root results in an 6.5MB executable. The Ogre one is already heavily optimized by disabling FreeImage and some other components. (For the record, Cocos3D’s “Hello World” app demo is 2.5MB, but it is not cross platform at the moment).

• The Ogre-iPhone “branch” is official; the Irrlicht OGL-ES branch is not official (yet).

• Ogre-iPhone can do shader programming (OpenGL ES 2.0). There are OpenGL ES 2.0 files in the Irrlicht OGL-ES branch but I have not played with it and don’t know how mature it is.

That’s it. The size point might not be that relevant for desktop development but definitely is when it comes to small game developments. I actually prefer Ogre’s “more complicated” “syntax” (a much touted disadvantage by Irrlicht’s community) better but for this one I think I’m going with Irrlicht.

Most people compare Sencha Touch to jQuery Mobile. My general impression from reading the Web is that Sencha is more heavy-duty, faster than jQuery. My actual experience, however, reveals that they are actually vastly different.

I recently started using PhoneGap to do mobile development. The idea of using Web technology to write cross platform apps is just so great!

The natural thing to do with PhoneGap would be to use a framework. There are many, just to name a few that I tried:

• xui: Lightweight and fast, just as what you’d expect — jQuery on diet. I am not sure I am unlocking its real potential since examples/demos are non-existent at the time I write this. But this gets the job done.
• Senca Touch: Claims to be “the best HTML5 mobile Web app framework”. The demos are polished and attractive.
• jQuery Mobie: Good old familiar jQuery. The demos feel a little sluggish but overall still look good. It has less “widgets” than Sencha.

So let me get to the point of this post: I tried Sencha first and then tried jQuery. I will tell you that Sencha has slightly better performance but it’s approach really disappointed me.

Let me quote a snippet of Sencha Touch code from the PhoneGap tutorial on its Web site. This is how a typical Sencha Touch “class” look like:

Whew, that’s quite a lot of stuffs. Let me compare that with a selected part of a jQuery Mobile tutorial:

This looks so familiar. It’s just our good old jQuery. And the page was formatted with standard, vanilla HTML5.

The difference should now be apparent — jQuery Mobile is a real “moving the Web development experience to mobile platforms”, whereas Sencha is “moving ExtJS to the mobile platform”.

If you look at the code, you’ll find that the typical Sencha Touch application bears no resemblance to how a Web app looks like — it feels like writing Java view classes. Unless you were already an ExtJS expert, it’s like going to learn a whole different ecosystem. Maybe it’s just me, but I find that way more difficult to adjust the layout than HTML or using XIB GUI editor. Writing layouts in “plain text” feels like something from the 90′s, seriously. Every other GUI toolkit I know of has a GUI editor, and plain HTML has the advantage of being ubiqutous. I can already imagine tearing the manual while writing GUI in Sencha Touch — not particularly attractive.

Using jQuery Mobile, links are automatically “hijaxed” into AJAX-y links, without you having to define these ‘tap’ actions whatsoever. The other good thing about it is that it works in a desktop browser by default, whereas Sencha Touch’s tutorial app just gives me a blank page when viewed from Firefox.

My general feeling is that if I am going to use yet another framework, I may as well go native or use Titanium which gives me native performance. For the moment I am going to stick with jQuery Mobile.

You need to update all your packages. The latest MiKTeX package manager seems rather broken. If you use Task > Update Wizard, you’ll probably meet “The update wizard could not be found”

The solution is to open the Update program directly (type “Update” in Start Menu or find miktex-update.exe. I used both the normal variant and the “(Admin)” variant. A couple of updates later it’s finally working!

I launched a new site blog Illustrated Haskell where I experiment with a new approach to explain intermediate Haskell concepts, inspired by Khan Academy‘s style. I am not doing videos (yet?) but the style is intended to be narrative and easy to follow.

Check it out

I was doing ITA Software’s “Word Numbers” problem. Now there are various solutions on the Web. Reviewing those solutions tell us it’s a graph/grammar problem. Today we’re going to solve it brute-force.

Now let me give a quick recap of the problem:

A "word number" is defined as


wordNumber 1 = "one"
wordNumber 2 = "onetwo"
wordNumber 3 = "onetwothree"
...
wordNumber 12 = "onetwothreefourfivesixseveneightnineteneleventwelve"
...

Find the 51-billion-th letter of the wordNumber Infinity. Assume that letter is found for wordNumber x, also find the sum of 1 to x

(As someone noted in the StackOverflow comments, I actually misinterpreted the original problem. But that doesn’t affect our purpose here.)

A naive algorithm in C++

The idea seems simple: 2 counters, one for sum of numbers and one for length. We go from wordNumber 1 until the length meets 51000000000. Here is how I said it in C++:

// Brute force solver for the Word Number problem
 
#include <iostream>
#include <string>
 
int length_ones[10] = {0,3,3,5,4,4,3,5,5,4}; // "", one, two, three, ...
int length_tens[10] = {0,3,6,6,5,5,5,7,6,6}; // "", ten, twenty, ...
int length_teens[10] = {3,6,6,8,8,7,7,9,8,8}; // ten, eleven, twelve, ...
 
const char * ones[] = {"", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
const char * tens[] = {"", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};
const char * teens[] = {"ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteeen", "nineteen"};
 
std::string wordify(long n)
{
    if(n < 10) return ones[n];
    else if(n < 20) return teens[n-10];
    else if(n < 100) return std::string(tens[n/10]) + ones[n%10];
    else if(n < 1000) return std::string(ones[n/100]) + "hundred" + wordify(n%100);
    else if(n < 1000000) return wordify(n/1000) + "thousand" + wordify(n%1000);
    else return wordify(n/1000000) + "million" + wordify(n%1000000);
}
 
int word_length(long n)
{
    if(n < 10) return length_ones[n];
    else if(n < 20) return length_teens[n-10];
    else if(n < 100) return length_tens[n/10] + length_ones[n%10];
    else if(n < 1000) return length_ones[n/100] + 7 + word_length(n%100); // 7 for "hundred"
    else if(n < 1000000) return word_length(n/1000) + 8 + word_length(n%1000);
    else return word_length(n/1000000) + 7 + word_length(n%1000000);
}
 
int main()
{
    long sumNumbers = 0;
    long sumLength = 0;
 
    const long target = 51000000000;
 
    for(long i; i < 999999999; i++)
    {
        sumNumbers += i;
        long newSumLength = word_length(i) + sumLength;
        if(newSumLength >= target)
            break;
 
        sumLength = newSumLength;
    }
 
    std::cout << "Sum: " << sumNumbers << std::endl;
    std::cout << "The letter is " << wordify(i)[target - sumLength - 1] << std::endl;
 
    return 0;
}
 

OK, nothing surprising. It takes 45 seconds on my machine to execute (g++ -O3). We will use this as a baseline.

First attempt in Haskell

-- Original version
-- Can you spot how to improve this performance by 3 fold right away?

{-# LANGUAGE BangPatterns #-}
 
import Debug.Trace
import Data.Int
import Control.Monad
import Data.Array.Unboxed
 
ones = ["", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"]
tens = ["", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"]
teens = ["ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"]
 
lenOnes, lenTens, lenTeens :: UArray Int64 Int64
lenOnes = listArray (0,9) $ [0,3,3,5,4,5,3,5,5,4] -- "", "one","two", ...
lenTens = listArray (0,9) $ [0,3,6,6,5,5,5,7,6,6]
lenTeens = listArray (0,9) $ [3,6,6,8,8,7,7,9,8,8] -- first element is "ten" 3
 
-- potentially cleaner version
-- but I feared Haskell might do surprising things behind my 
-- back so I stuck with the above
-- lenBelowHundred = listArray (0,99) $ map (fromIntegral . length . wordify) [1..99]
 
-- wordify 123 = "onehundredtwentythree"
-- This is only used once in presenting the final result character
wordify :: Int64 -> String
wordify n
    | n < 10         = ones !! fromIntegral n
    | n < 20         = teens !! (fromIntegral n-10)
    | n < 100        = splitterTen
    | n < 1000       = splitter 100 "hundred"
    | n < 1000000    = splitter 1000 "thousand"
    | n < 1000000000 = splitter 1000000 "million"
    where
        splitterTen = let (t, x) = n `divMod` 10
                      in (tens !! fromIntegral t) ++ wordify x
        splitter div suffix = let (t, x) = n `divMod` div
                              in (wordify t) ++ suffix ++ wordify x
 
-- Optimized version of length (wordify n)
-- Used in number crunching
wordLength n = wordLength' 0 n
 
-- Tail recursive version
wordLength' :: Int64 -> Int64 -> Int64
wordLength' !pad !n
    | n < 10         = lenOnes ! n + pad
    | n < 20         = lenTeens ! (n-10) + pad
    | n < 100        = splitterTen
    | n < 1000       = splitter 100 7
    | n < 1000000    = splitter 1000 8
    | otherwise      = splitter 1000000 7
    where
        splitterTen = let !(!t, !x) =  n `divMod` 10
                      in wordLength' (lenTens ! t + pad) x
        splitter !d !suffix = let !(!t, !x) = n `divMod` d
                              in wordLength' (wordLength' (suffix+pad) t) x
 
-- Tail recursive
solve :: Int64 -> (Int64, Int64, Int64) -> [Int64] -> (Int64, Int64, Int64)
solve !n !acc@(!sumNum, !sumLen, !curr) (!num:nums)
    | sumLen' >= n = (sumNum', sumLen, num)
    | otherwise = solve n (sumNum', sumLen', num) nums
    where
        sumNum' = sumNum + num
        sumLen' = sumLen + wordLength num
 
solution :: Int64 -> (Int64, Char)
solution !x =
    let (sumNum, sumLen, n) = solve x (0,0,1) [1..]
    in (sumNum, (wordify n) !! (fromIntegral $ x - sumLen - 1))
 
main = do
    print $ solution 1234 -- Make sure we are sane
    print $ solution 51000000000

OK, I lied. It was not my first attempt. My initial version had space leaks which led to the program eating up 1GB RAM in several seconds. Using profiling techniques from Real World Haskell, I identified the space leaks and sprinkled Bang patterns everywhere.

So how well does that run?

Well, I don’t know.

As far as I remember, one version finished in 12 minutes, but I am not sure it is the version posted here. In short, the performance was not bearable.

Now if we were using Perl or Ruby, that might not have been too surprising. But for Haskell this seems something obvious is missing.

The solution

So there I went, I asked for help on StackOverflow and in Haskell-cafe.

There I got help from Bryan O’Sullivan who posted his version. Reiner Pope said that with -fllvm, it finishes in about 1.5 minutes. (OK, he did not exactly say that. He said Haskell version is half as fast as C++.)

But it did not work for me

So I downloaded Bryan’s code (we’ll call it RealWordNumber.hs from now on, sorry bad pun and off I went in excitement:

> ghc -O2 RealWordNumber.hs
> RealWordNumber
> Sum: 1
> Segmentation fault/access violation in generated code

Since RealWordNumber.hs uses Int, there is an integer overflow in his code. That’s also exactly the reason why I had to use Int64 in my original version.

(I was using Windows where GHC only has 32-bit)

So I patched his code to use Int64 and off I went. It never finished, I had to kill it.

Huh?

The culprit — 64-bit integers are slow in 32-bit programs

OK the major reason turned out to be this. To confirm, I compiled the C++ version to 32-bit using VC++ (cl /Ox WordNumber.cpp). It took 4 minutes to complete.

So I took RealWordNumber.hs to Arch Linux x64. It turned out that Int in GHC x64 is actually Int64, and the program completed in 5 minutes (ghc -O2).

Since the LLVM backend for GHC 7.0.3 seemed broken at the time I write this, and I did not want to go fixing it immediately, I trusted that it would really turn to 1.5 minutes if I ran it with -fllvm.

Now the fun part — breaking down performance improvements

“So,” I figured, “I just needed to take my original version and put it on Arch x64″. So I tried that, and it was still taking longer than my patience allowed (8+ minutes). The following will explain how I got my version up to the same league with RealWordNumber.hs, step by step.

First of all, I tuned the number down to 510 million (510000000) to avoid having to wait all day doing this.

Here is a base line using 510 million as an input:

RealWordNumber -- 1.94 seconds
K2WordNumber   -- 5.41 seconds

From here we see that if I had waited about 15 minutes, I could have seen my original version finish

Now on to how I got it up to speed:

1. Change divMod to quotRem

I think I heard it from #haskell, people say that quotRem is faster than divMod. So I simply changed all divMod to quotRem. Look at what we’ve got:

K2WordNumber-1 -- 4.48 seconds

OK, that was true. A surprising huge speed up.

2. Change Int64 to Int

Since GHC x64′s Int is actually 64-bit, I changed all Int64 to Int and removed the unnecessary fromIntegral calls.

K2WordNumber-2 -- 3.20 seconds

2 simple changes, we are already getting there

3. Change quotRem to separate quot and rem

Since quotRem returns a tuple of boxed Int64, which may need to be constructed and reconstructed. Max Bolingbroke suggested that using quot and rem separately might help. Here’s the experiment result

K2WordNumber-3 -- 3.13 seconds

It might have been an improvement, but might have just been experimental error. Unfortunately it seems like not much speed up was achieved.

4. Removed redundant parameters

It turned out in my original version, there were several redundant parameters being passed recursively in the function solve (the acc label, and curr). I used ghc -Wall to track them and removed them.

K2WordNumber-4 -- 3.16 seconds

No change. Since GHC figured out enough to warn me, it probably did the right thing and optimized them for me anyway.

5. Simplified parameter passing

The original solve function looked like this

To quote Bryan:

You’re passing parameters in three different ways: a regular Int, a 3-tuple, and a list! Whoa.

He is right. I also noticed that the n parameter does not change and does not need to be passed on. Johan Tibell blogged that GHC could in theory create this closure for us. But I did it manually to see what happens:

That resulted in

K2WordNumber-5 -- 2.87 seconds

Good.

6. Using unboxed integer types

I replaced quot and rem with these

K2WordNumber-6 — 2.77 seconds

Not as much as I had thought

7. Using Data.Vector.Unboxed instead of Data.Array.Unboxed

K2WordNumber-7 -- 2.50 seconds

8. Using Data.Vector.Generic.unsafeIndex instead of the (!) operator

K2WordNumber-8 -- 2.20 seconds

Wow, this one was huge.

9. Move the length vectors inside wordLength‘s closure

K2WordNumber-9a — 2.20 seconds

No improvement at all… But if I add bangs before the vectors…

K2WordNumber-9 — 2.00 seconds

WOW!! That was a large speed up. It turns out the reason for the speed up is related to strictness. wordLength is not strict in all lenOnes, lenTens and lenTeens, so they might be garbaged collected (?). Putting bangs on them allow them to stay alive. Since we need to use those arrays very frequently, it was better for them to be around all the time.

Haskell did not allow putting bangs on “global” variables, so I missed it in my original bang sprinkling exercise.

OK, so now we have transformed my original sloppy Haskell program to a “well-performing” Haskell program. Since it performs the same as Bryan O’Sullivan (casually) tuned version, I am going to assume it’s probably as fast as it should (before maybe resorting to serious hacks).

And here is the final version of the code:

-- Problem: Find the 51000000000-th character of the string (wordNumber Infinity)
-- where a wordNumber is defined as
--
-- wordNumber 1 = "one"
-- wordNumber 2 = "onetwo"
-- wordNumber 3 = "onetwothree"
-- wordNumber 15 = "onetwothreefourfivesixseveneightnineteneleventwelvethirteenfourteenfifteen"
-- ...
--
-- The answer should be presented as ( sum of all numbers up to that point
--                                   , the 51000000000-th character
--                                   )

-- This is a Haskell performance tuning exercise, trying to achieve C like performance.
-- Full guided story can be found at
-- http://cfc.kizzx2.com/index.php/in-search-of-performance-in-haskell/
--
-- (This Word Number problem is actually a misunderstood version of ITA's version)

{-# LANGUAGE BangPatterns, MagicHash #-}

import qualified Data.Vector.Unboxed as VU
import Data.Vector.Unboxed ((!))
import qualified Data.Vector.Generic as VG
import GHC.Base (Int(..), quotInt#, remInt#)

ones, tens, teens :: [String]
ones = ["", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"]
tens = ["", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"]
teens = ["ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"]

wordify :: Int -> String
wordify n
    | n < 10         = ones !! n
    | n < 20         = teens !! (n-10)
    | n < 100        = splitterTen
    | n < 1000       = splitter 100 "hundred"
    | n < 1000000    = splitter 1000 "thousand"
    | otherwise      = splitter 1000000 "million"
    where
        splitterTen = let (t, x) = n `quotRem` 10
                      in (tens !! t) ++ wordify x
        splitter d suffix = let (t, x) = n `quotRem` d
                              in (wordify t) ++ suffix ++ wordify x

-- Tail recursive version
wordLength :: Int -> Int
wordLength i = go 0 i
    where
        go !pad !n
            | n < 10         = lenOnes `VG.unsafeIndex` n + pad
            | n < 20         = lenTeens `VG.unsafeIndex` (n-10) + pad
            | n < 100        = go (lenTens `VG.unsafeIndex` (n//10) + pad) (n%10)
            | n < 1000       = go (go (7+pad) (n//100)) (n%100)
            | n < 1000000    = go (go (8+pad) (n//1000)) (n%1000)
            | otherwise      = go (go (7+pad) (n//1000000)) (n%1000000)
        (I# a) // (I# b) = I# (a `quotInt#` b)
        (I# a) % (I# b) = I# (a `remInt#` b)
        !lenOnes = VU.fromList [0,3,3,5,4,4,3,5,5,4] -- "", "one","two", ...
        !lenTens = VU.fromList [0,3,6,6,5,5,5,7,6,6]
        !lenTeens = VU.fromList [3,6,6,8,8,7,7,9,8,8] -- first element is "ten" 3

solve :: Int -> (Int, Int, Int)
solve n = go 0 0 1
    where
        go !sumNum sumLen i
            | sumLen' >= n = (sumNum', sumLen, i)
            | otherwise = go sumNum' sumLen' (i+1)
            where
                sumNum' = sumNum + i
                sumLen' = sumLen + wordLength i


solution :: Int -> (Int, Char)
solution x =
    let (sumNum, sumLen, n) = solve x
    in (sumNum, (wordify n) !! (x - sumLen - 1))

main ::  IO ()
main = do
    print $ solution 510000000

Moral of the story

• Haskell is a very fast functional language. But for tight areas like this, always consider giving plain old C a try — it may just save you days of profiling.
• 64-bit operations in 32-bit programs are slow (*)
• quotRem is faster than divMod
• Earlier I argued in #haskell that “if Integer vs Int matters for your performance, your program is probably written wrong”. Well, there are cases where it matters quite a lot. It turns out conversions are quite costly. (Though I still believe people should use Integer by default)
• Use the wrapper-worker pattern liberally.
• If you recurse, make sure every variable actually changes in each recursion. (For most cases this will benefit. If you only recurse several times maybe the closure’s overhead will be larger.)
• Don’t use a list or tuple just because infinite lists look smart.
• Data.Vector is a better “general case” container than Data.Array
• Try to reduce the scope of “global” variables. Put them in a closure so you can bang on it.

* This may be actually the suckage of Windows’ “WOW64″ (32-bit emulation layer). I have not tried to prove this on 32-bit Linux GHC)

Extra: the fastest indexing data structure — functions!?

I heard from #haskell that “pattern matching in Haskell is less than O(n)”. When I heard it, I didn’t really believe it. I have always thought that N pattern matches means translating into N if-then-else statements for the general case. He said something related to Church encoding but I did not see how it could be applied in the general case to avoid N if-then-else statements.

Just for fun, I tried changing the length vectors into functions:

K2WordNumber-10 — 2.00 seconds

Yes, pattern matching is as fast as unsafeIndex. WOW! wren nt thornton from the comments below give a more thorough explanation on this one. It turns out GHC is really darn smart and can figure out fast code given “primitive” definitions.