haskell’s lightweight threads

I’m continuing my experiments with Haskell (now it’s  the subject of my course project).

I had some concerns about the performance of Haskell’s lightweight threads, but Don Stewart‘s answer to my question on StackOverflow convinced me that multithreading in Haskell is awesome (thanks to the Control.Concurrent module). But just how awesome is it?

I tried to actually measure it with a benchmark. Here is what I did. I made two programs, one in C and one in Haskell, that create a bunch of threads and wait until all of them are completed. The threads don’t actually do anything, as we’re interested merely in the time it takes to create a new thread. The C program uses pthreads and the Haskell program uses Control.Concurrent.

Then I ran these programs a few times, took the arithmetic mean of the running time and plotted it. Here is what I saw.

On the X axis you see the number of threads that the program creates. On the Y axis you see the arithmetic mean of the run time over 10 runs. The green line is Haskell, the red line is C. Haskell is almost 10 times faster. Control.Concurrent kicked pthreads’ ass, leaving it no chances.

Some more information about the experiment: my computer is equipped with an Intel Core2Duo E6850 microprocessor, 2 Gb of RAM and runs Linux 2.6.38. I haven’t tried the same with Windows threads, but I think it would give similar results.

I know thre results are not really precise, because we actually measure time needed to load the program, create the threads, wait for them to finish and exit, but for big inputs the added time is negligible compared to the total amount of time spent on creating the threads, and overall the result must corellate pretty well with what we’d have if we measured only the time needed to create the threads.

The source code for the C program:

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>

void* thread_main(void*);

int main(int argc, char* argv[])
   int n,i;
    pthread_t *threads;
    pthread_attr_t pthread_custom_attr;

    if (argc != 2)
        printf ("Usage: %s n\n  where n is no. of threads\n",argv[0]);
       return 1;


    threads=(pthread_t *)malloc(n*sizeof(*threads));

    for (i=0; i<n; i++)
        pthread_create(&threads[i], &pthread_custom_attr, thread_main, (void *)(0));

    for (i=0; i<n; i++)

void* thread_main(void* p)
   return 0;

The source code for the Haskell program:

module Main (main) where

import System.IO.Unsafe
import System
import Control.Concurrent
import Control.Exception

children :: MVar [MVar ()]
children = unsafePerformIO (newMVar [])

waitForChildren :: IO ()
waitForChildren = do
   cs <- takeMVar children
   case cs of
      []   -> return ()
      m:ms -> do
         putMVar children ms
         takeMVar m

forkChild :: IO () -> IO ThreadId
forkChild io = do
   mvar <- newEmptyMVar
   childs <- takeMVar children
   putMVar children (mvar:childs)
   forkIO (io `finally` putMVar mvar ())

forkKids :: Int -> IO ()
forkKids 0 = return ()
forkKids n = do
   forkChild (threadMain)
   forkKids (n-1)

threadMain = return ()

main = do
   args <- getArgs
   forkKids (read (head args))

P.S. Here’s a good paper describing the runtime support of multithreading in GHC

my first (kinda) useful haskell module

Finally found some time to get to know Haskell a little bit more closely. So, here is the first practical thing I wrote in Haskell: a module for parsing .ini files.

It uses the Parsec library. Using Parsec for parsing ini files feels like shooting chipmunks from an M-20 bazooka. Which means, it’s fun.

If you’ve ever touched boost::spirit, you’ll understand what Parsec is.

In Parsec, a parser is a special kind of function (and therefore, a first-class object). A parser combinator is a function that takes one or more parsers and uses them to create a new parser. Parsec has a lot of built-in basic parsers and combinators. By using them, you can construct your own parsers, with blackjack and hookers, which of course, can also be used with combinators, and so on… Parsec can be used to deal with quite complex, non-trivial grammars, but in our case, it’s just an ini file. I could’ve written the parser by hand, but why bother when I have this awesomeness at my fingertips?

Anyway, here’s the code:

module IniFile (iniFileToMap) where

import Text.ParserCombinators.Parsec
import qualified Data.Map as Map
import Char

parseIniFile :: Parser ([(String, [(String, String)])])
parseSection :: Parser (String, [(String, String)])
parseSectionHeader :: Parser String
parseNameValue :: Parser (String, String)
parseComment :: Parser ()
parseNormalValue :: Parser String
parseQuotedValue :: Parser String
parseValue :: Parser String
parseName :: Parser String
parseInsideQuotes :: Parser String
parseCmtOrSpace :: Parser ()
iniFileToMap :: FilePath -> IO (Map.Map String (Map.Map String String))

parseCmtOrSpace = do{
   skipMany parseComment;

parseInsideQuotes = many (noneOf "\"")

parseQuotedValue = between (char '"') (char '"') parseInsideQuotes 

parseNormalValue = many1 (satisfy (\c -> isPrint c && not (isSpace c)))

parseValue = parseQuotedValue <|> parseNormalValue

parseName =  many1 (satisfy (\c -> isAlpha c || isDigit c || c == '_' || c == '.'));

parseComment = do{
   skipMany1 (char ';');
   skipMany (noneOf "\n");

parseNameValue = do{
   name <-  parseName;
   between (skipMany (oneOf " \t")) (skipMany (oneOf " \t")) (char '=');
   value <- parseValue;
   return (name, value);

parseSectionHeader = do{
   name <- between (char '[') (char ']') parseName;
   return name;

parseSection = do{
   name <- between parseCmtOrSpace parseCmtOrSpace parseSectionHeader;
   values <- endBy1 (parseNameValue) (parseCmtOrSpace);
   return (name, values);

parseIniFile  = do{
   result <- many1 (parseSection);
   return result;

list2Map list = Map.fromList (map (\e -> (fst e, Map.fromList (snd e))) list)

iniFileToMap path = do{
   result <- parseFromFile parseIniFile path;
      case (result) of
         Left err -> error (show err)
         Right xs -> return (list2Map(xs));

Note how every function beginning with “parse” is itself a small parser, and is used in conjunction with other parsers and combinators.

I probably made a bunch of newbie mistakes, but unfortunately I didn’t find anybody who could review the code and provide guidance. So, I guess, I’ll have to gradually improve it as I learn more about Haskell and Parsec.

opengl and texture-mapped text

I’ve been experimenting with OpenGL lately.  One of my experiments was rendering text in an OpenGL window.  Now, there are several libraries out there that do the thing, they can even handle TrueType fonts and stuff, but I wanted something simple and I wanted to do it myself.

So, the idea is the following: you have a picture with letters, numbers and special symbols, you load it into your OpenGL application and then render lines of text using the symbols provided in the picture.

The solution I came up with is to store the picture with symbols as an OpenGL texture and render the text as series of texturized quads – applying the relevant piece of the texture to each of them. To make things faster, instructions for rendering each character are put into a display list. Let’s see how the whole thing is done.

We start by declaring a class that will create the texture and display lists. Nothing particularly interesting here.

#include "SDL/SDL.h"
#include "GL/gl.h"
#include "GL/glu.h" // for gluOrtho2D
#include <iostream> 
#include <stdexcept>

class Font
   explicit Font(const char*);/* Builds a font from bitmap file */
   void render(const char*);

   SDL_Surface* surface; /* An SDL surface containing the characters */ 
   GLuint texture; /* OpenGL texture */
   GLuint dl; /* First of the 96 display lists used to draw printable characters */ 

Now let’s jump to the implementation of the Font ctor. It does several things:

  • Loads a bitmap from a file
  • Creates a new OpenGL texture, sets some options and sets image data for it
  • Generates display lists, one per character. Each display list draws a quad with a different piece of the texture applied to it, depending on which character it is associated with

To load a bitmap from file, we use the SDL_LoadBMP function. After that we create a new texture with glGenTextures. Then we need to set image data for our texture. OpenGL expects raw image data, which is contained in the “pixels” field of the SDL_Surface structure. It is important for us to know how this data is arranged, because we’ll need to pass that information to the glTexImage2D function, which is used to specify the texture image. Namely, we’ll need to know the width and height of the bitmap, number of color components and pixel format. Note that the width and height of the bitmap should be a power of 2. I don’t know the exact reason for this limitation yet, but I think it might have something to do with memory alignment issues.

In this particular example, the bitmap that we’ll be using is a 1024×8 image that looks like this. It has 3 color components (R, G, B, there is no aplha component), and the pixel format is RGB (not BGR). In this piece of code, we simply make those assupmtions to keep things short and simple, but in a real-world application you’d probably want to take this information from the “format” field of the SDL_Surface structure.

After we’ve set the image data for the texture, it’s time to create the display lists. Note: this example only supports ASCII printable characters in the range from space to tilde (~). Also, we know how the glyphs are arranged in the bitmap and that the width and height of each glyph is exactly 8 pixels. If I wanted to make things more generic, I’d add the possibility to supply a separate text file that would provide texture coordinates for each symbol. Also, some people on the internet have suggested to use vertex buffers instead of display lists (because they have better performance), but I don’t know what they are and how to use them yet :-)

 * Builds the font from a bitmap file.
 * The entire file is read as a texture and then we create display lists
 * for each printable character. Those lists just create a small quad, applying
 * the relevant piece of the texture to it.
Font::Font(const char* bitmap_file_name)
   if(NULL == (surface = SDL_LoadBMP(bitmap_file_name))) throw std::runtime_error(SDL_GetError());

   // Set up the texture
   glGenTextures(1, &texture);
   glBindTexture(GL_TEXTURE_2D, texture);
   glTexImage2D(GL_TEXTURE_2D, 0, 3, surface->w, surface->h, 0, GL_RGB, GL_UNSIGNED_BYTE, surface->pixels);

   // Now compile the glyphs into display lists

   dl = glGenLists(96);
   for(char c = ' '; c <= '~'; ++c){
      int idx = c - ' '; 
      glNewList(dl+idx, GL_COMPILE);
         glTexCoord2i(8*idx, 0);
         glVertex2i(0, 0);

         glTexCoord2i(8*idx + 8, 0);
         glVertex2i(8, 0);

         glTexCoord2i(8*idx + 8, 8);
         glVertex2i(8, 8);

         glTexCoord2i(8*idx, 8);
         glVertex2i(0, 8);

Now, let’s move on to the implementation of the render() method. The first thing we have to do is to make texture coordinates usable for our goal.  By default, the origin of the texture coordinate system is at the upper-left corner of the image (0,0) and the lower right corner has the coordinates (1,1). This is not what we want. We want the lower-right corner to have coordinates (1024, 8), so that we can use pixel coordinates. This can be accomplished by modifying the texture matrix with glScalef. Then we just iterate through the string, calling the appropriate display lists. Note how we preserve the modelview matrix between calls and restore the previous texture matrix at the end of the procedure.

 * Renders a string on the screen
void Font::render(const char* c)
   glBindTexture(GL_TEXTURE_2D, texture);
   glScalef(1.0/surface->w, 1.0/surface->h, 1.0);
   for(int i = 0; i < strlen(c); ++i)
      int idx = c[i] - ' ';
      if(idx < 0 || idx >= 96) throw std::runtime_error("Non-printable character encountered");
      glTranslatef(8*i, 0, 0);
      glCallList(dl + idx);

The rest is pretty straightforward. It’s the dtor for Font, a routine to set up SDL and OpenGL and main(). Note how we’re able to use glColor3f to set the text color!

void prepare(); /* Prepares the environment (set up SDL and OpenGL */

int main()
      Font fnt("font.bmp");
      glColor3f(1.0, 0.0, 0.0);
      glTranslatef(208, 200, 0);
      fnt.render("HELLO, OPENGL TEXTURE FONTS!");
   catch(std::runtime_error& e)
      std::cerr << "ERROR: " << e.what() << "\n";
      return 1;
   return 0;

 * Sets up SDL and OpenGL.
 * Sets a 640x480 32-BPP video mode
 * Sets a coordinate system for the OpenGL window, (0,0) being the top
 * left corner, (640, 480) being the bottom right.
void prepare()
   // Initialize SDL and set video mode
   if(SDL_Init(SDL_INIT_EVERYTHING) < 0) throw std::runtime_error(SDL_GetError());
   if(NULL == SDL_SetVideoMode(640, 480, 32, SDL_OPENGL | SDL_GL_DOUBLEBUFFER)) throw std::runtime_error(SDL_GetError());

   // Prepare OpenGL
   gluOrtho2D(0, 640, 480, 0);
   glClearColor(.0, .0, .0, .0);

 * Frees allocated resources (SDL surface, texture and dl's)
   glDeleteTextures(1, &texture);
   glDeleteLists(dl, 96);

If you want to compile it (and see this), don’t forget to link your executable against the SDL, GL and GLU libraries.

linux install fest in yerevan

There is a Linux install fest about to happen here in Yerevan. The event is planned for May 7. Here’s the deal: if you’re willing to try Linux, you attend the event with your computer (laptop or netbook, obviously) and we install one of the popular distros on it, of course, preserving all of your personal files and the existing Windows partition, if you wish. We’ll be happy to answer all of your questions regarding free software, use of Linux on desktop, etc.

I will attend the event as a volounteer.

о юных сталкерах

Дорога шла в гору. Три мелких пацана уверенно шагали по ней, хотя не знали точно, куда идут.

Нет, не так. Это был обычный летний полдень. Три мелких пацана слонялись по безлюдному двору унылой хрущевской пятиэтажки. Им надоело понарошку играть в нашествие пришельцев и стрелять из игрушечных пистолетов. Наблюдения за деятельностью больших черных муравьёв и устраивание апокалипсиса в муравейнике тоже почему-то больше не привлекали. Одним словом, им было скучно. Когда скука достигла своего апогея, один из них сказал: “А давайте пойдем искать приключения!” И они согласились. И они пошли. Искать. Приключения. Ага.

Они покинули свой двор и направились в сторону детской неврологической больницы. Сама больница, впрочем, их не интересовала. Их интересовало то, что было за ней. Потому что раньше они дальше этой больницы никогда не заходили.

Итак, дорога шла в гору. Три мелких пацана уверенно шагали по ней, хотя не знали точно, куда идут.  Одним из них был я.

Когда я был совсем мал – года три, наверное – я часто ходил по этой дороге. В эту самую больницу меня и водили. Лечить заикание. Дорога, помню, была вся в каких-то непонятных выбоинах, а на обочине росли лиловые колокольчики и еще такие большие цветы, похожие на зонтики. А еще, по левую руку стояло недостроенное здание. Только каркас и какие-то бетонные перекрытия. Даже стен не было. Оно мне запомнилось, потому что за все время, пока меня водили в больницу, его так и не достроили. Когда мы втроем проходили мимо этого здания, выяснилось, что оно осталось таким, как и прежде. То есть, недостроенным.

Но мы прошли и эту вечную стройку, и больницу, и наконец, мы перешли какую-то невидимую грань. Иначе я сказать не могу. Мы именно перешагнули невидимую грань между мирами.

По ту сторону росли маки. Много, много маков. Это было, конечно, не такое маковое поле, но все-таки цветов было много. Нам, как детям пыльного города, представлялось невозможным чтоб цветы где-то росли совершенно просто так, без клумбы или там горшка какого-нибудь. Мы рассматривали цветы, трогали их красивые восковые лепестки. Маки не пахли, но были приятны на ощупь.

В тот день мы не зашли слишком далеко. Но на следующий день мы взяли с собой бутыль воды, морковку, верёвку, положили это в какую-то сумку и двинулись в путь.

За маковым полем простиралось что-то вроде пустыни, в которой там-сям были разбросаны стройки. Некоторые из этих строек выглядели покинутыми, другие подавали признаки жизни в виде звуков, лязгов и голосов рабочих. Но в целом, место было довольно необитаемым. Иногда мы встречали островки маков. Иногда мы встречали даже пастухов со стадами. Один из них даже спросил у нас, который час.

Местность была довольно труднопроходимой: тут были какие-то овраги, на дне которых валялся мусор, крутые склоны, усыпанные камнями, росли колючки, которые цеплялись за шнурки ботинок и носки, коля кожу через ткань.  Шлялись какие-то собаки. Там было вовсе не безопасно.

Мы шли через всё это напролом.  До сих пор мне не известно, как ни один из нас не свернул шею, переходя очередной овраг и как нас не загрызла стая бродячих собак. Возможностей свернуть шею у нас было предостаточно, и мы ими с удовольствием пользовались.

Например, во время своего путешествия мы обнаружили странное сооружение, предназначение которого мне до сих пор неизвестно. Это были два огромных цилиндрических резервуара, за ними на высоте была небольшая кабинка, вроде той, что бывает на подъемных кранах. Я подозреваю, что это сооружение имеет какое-то отношение к бетону, так как я видел нечто подобное в бетонузле по соседству с нашим домом.

В кабинку можно было попасть поднявшись по хлипкой лесенке на маленькую площадку, причем середика у этой площадки отсутствовала: была просто дыра в полу и по бокам перила. Но нам на это было наплевать. Мы перешли на ту сторону, цепляясь за перила, чтобы рассматривать какой-то хлам в кабинке. Если бы кто-нибудь из нас упал, то двоим другим пришлось бы волочить бездыханный труп до дому. Наверное, нас кто-то  охранял, потому что в подобных опасных ситуациях мы оказывались не раз, но с нами ни разу ничего не случилось. А может быть, это такой закон природы: с безрассудными ничего не случается.

Наверное, наше возвращение можно сравнить разве что с возвращением космонавтов из межпланетного путешествия. На обратном пути мы нарвали маков – отнести домой. Но на потом я вспомнил, что дома придётся объяснять, откуда взялись маки. Выбрасывать их было жалко. Они были такие красивые, с блестящими красно-черными лепестками.

Решение быстро нашлось. Я подошел к первому попавшемуся прохожему – пожилой женщине – и протянул ей букетик со словами “Это вам”. Остальные последовали моему примеру. Так и вернулись домой ни с чем.

Сегодня я побывал в тех краях. Недостроенное здание так и осталось недостроенным, а детской неврологической больницы больше нет – теперь там налоговая инспекция.


how i implemented resource files in my game

A couple of months ago, the source code for my space shooter game was lost. That was probably the best thing that could happen to this project, since now I am forced to rewrite it from scratch – and I believe that if you are forced to redo your project all over again, you’ll write better code.

But this post isn’t about honing your code to perfection by constant rewrites. It’s about implementing a particular feature -  resource files.

Most of those who have played Quake 2 or Quake 3 have seen, for example, *.pk2 or *.pk3 files. The game stores its assets – models, textures, maps, everything – in those files. In fact, try installing OpenArena and replacing its pk3 files with original Quake 3 pk3′s: you’ll end up with Quake 3.

I wanted to have similar files in my game, too – to keep sprites and level descriptions in them. It is probably way simpler than Quake’s resource files, but I didn’t need anything really advanced.

To achieve my goal, I had to invent a format, write a packaging tool for it, and write some code that would allow other game components to access the contents of the resource file. Let’s review each of those steps…

File Format and Packaging

I wanted something that would be really simple and easy to use. So I decided to go with the following format: have a header section, describing file names, offsets and sizes, followed by a big blob of bytes. The offsets and sizes are in ASCII format, to avoid headaches related to integer encoding on different platforms. Then I wrote this really simple bash script to package resources (bitmaps, text files, etc.) into a single resource file.

echo -en "$BASH_ARGC "
let i=0
for file in "$@"; do
echo -en `basename $file`" "
let size=`du -b $file | cut -f 1`
echo -en "$i "
let i=$i+$size
echo -en "$size ";
echo -en "\x0A"
cat $@

It should be used this way:
./respacker.sh *.bmp *.txt > resources.pack
Basically, it prints the header and then dumps the contents of the supplied files.

There is no encryption or compression. I don’t think I’d ever need encryption for this game, and compression can be added later without modifying the basic format of a resource file.

Using the Resource Files in the Game

I was pondering this for a while and eventually decided to just memory-map the resource file, and write a wrapper around the memory-mapped buffer that would allow accessing files by filenames. You can have a look at the code. I don’t know if this is the approach used in real games, but it seems to work for me. Anyway, I hope to find time for more research on this subject and maybe I’ll find a better solution.

devmon pipemenu for openbox

devmon is a configuration-less bash wrapper script for udisks which automounts optical discs and removable drives. It can also selectively autostart apps or execute commands after mounting, ignore specified devices and volume labels, and unmount removable drives.

I made a pipemenu for Openbox that lists the currently mounted media, allows to open it in a file manager and unmount it via devmon. It’s basically a small bash script. Here it is:


echo "<openbox_pipe_menu>"
echo "<separator label=\"Media\"/>"
for i in `ls "$MEDIADIR"`;
   echo "<menu id=\"med_$i\" label = \"$i\">\
          <item label=\"Open\">\
           <action name=\"Execute\">\
            <command>$FILEMGR \"$MEDIADIR/$i\"</command>\
          <item label=\"Unmount\">\
           <action name=\"Execute\">\
            <prompt>Are you sure you want to unmount $i?</prompt>\
            <command>/usr/bin/devmon --unmount \"$MEDIADIR/$i\"</command>\

echo "<separator label=\"Devmon commands\"/>"
echo "<item label=\"Unmount all\">\
         <action name=\"Execute\">\
          <prompt>Are you sure you want to unmount ALL media?</prompt>\
          <command>/usr/bin/devmon --unmount-all</command>\
      <item label=\"Unmount optical\">\
         <action name=\"Execute\">\
          <prompt>Are you sure you want to unmount ALL optical drives?</prompt>\
          <command>/usr/bin/devmon --unmount-optical</command>\
      <item label=\"Unmount recent\">\
         <action name=\"Execute\">\
          <prompt>Are you sure you want to unmount the most recently mounted drive?</prompt>\
          <command>/usr/bin/devmon --unmount-recent</command>\

echo "</openbox_pipe_menu>"

Set the MEDIADIR and FILEMGR variables to appropriate values (directory in which the media gets mounted and your favorite file manager, respectively).