Archive for the ‘ Lang ’ Category

The eventoriented programming model

Wednesday, January 12th, 2011

Eventoriented Programming which is sometimes called “evented programming” is a programming model used as an alternative to programming with threads.

Why does this matter

I think it was around 1998 when we first learned that the clock rate could not be increased and we where about to seeing the end of Moore’s law that the number of transistors that compounds a CPU will double every two years. The CPU clockrate at this time was slightly below 1 GHz. A few month later clever scientists discovered a way around that barrier and Moore’s law applied again. The computer industry was saved. I believe I was not the only one who did not take it seriously when in 2005 they announced that they really can not increase the clockrate any further. I was like “yeah, you will discover it within no time”. Now it is crystal clear that the only way to increase the computing power of a CPU is to give it more cores. Energy consumption/ cooling constrains the clockrate and we know today that energy efficient computing requires clock rates to drop again to below 1 GHz.

Today having more than one core on the CPU is yesterdays news because everybody already has at least a dual core CPU in his or her PC. The hardware is available but parallel computing this is still the hardest challenge we are today facing in the computer industry. At the moment our machines have multiple cores but we are not able to put them to effective use. Not being able to increase computing power in the PC is a serious thread for the industry because nobody will replace one unless it breaks. Besides the economic aspects there are a lot of topics desperately waiting for more computing power like speech, image recognition, and advanced computer interfaces.

What to do

What I think makes parallel computing really a hard problem is that there is currently and most likely there will be no general solution to the problem. Many computer scientists have spent their lives trying to find one. Among the most prominent is David Patterson who is Professor for Computer Architecture at Berkeley who worked on three separate projects on parallel computing. Many insights have been discovered but still the problem is far from being solved. On the other hand specific problems in this area have been addressed by today’s companies like Amazon, Facebook and Google. I think we can learn from them and look at the programming models used in their approaches.

I am convinced that there are at least to different kind of websites. There are sites that all people are using all the time like Amazon, Facebook and Google and on the other hand there are sites which are only use by some people some of the time. I am particularly interested in the later one so the rest of this piece is about the situation where you have less than 20.000 active connections at a time.

Programming with Thread vs. Eventoriented Programming

One of the strange things in Software Engineering is that people have strong opinions and you can get easily into a situation one starts a fight over like for example Emacs vs. VI, Windows vs. Mac, Ruby vs. Python. Same here in programming models. I believe that most software engineers think that threads are the way to go when using multicore CPUs. One the other hand there are strong indications that this is not always true. John Ousterhout who has been so far to one of the most influential Computer Scientist for my own career gave in 1996 a talk on “Why Threads are a bad idea” at the USENIX conference. When I found his slides I smiled since at that very second it occurred to me that I am on the right track. The slides (http://home.pacbell.net/ouster/threads.pdf) are freely available and you should definitely have a look. For this article I will only use his main argument that thread programming is extremely difficult to get right and a burden even for the best programmers.

Threads split the resources available to the operating system into pieces. Even if the resource consumption for a single thread is very small in total it sums up. For example a webserver which has 1GB available and splits it into 0.5 MB pieces for each thread is limited to 2.000 simultaneous requests. A recent example makes the issue very clear. The Apache webserver uses threads. Nginx is an Apache webserver clone where the threading mechanism was replaced by a event loop. It was successful and today Nginx by far outperforms Apache in terms of number of connections and memory utilization.

Eventoriented programming is a natural way and many programmers today prove to be comfortable using it.

Event oriented programming is often said to produce spaghetti code which is difficult to debug. I believe these are skill related issues and the event oriented programming model needs to be mastered like every other programming model. For example signal processing diagrams can help documenting programs following the event oriented model. Special debugging tools assign every callback a complete stack trace so that one can trace back the source of a given problem if he must.

Non-blocking I/O

Non-blocking, or asynchronous I/O allows the computation to continue while the input/ output operation is running. So it is for example possible to have multiple database queries running at a time. Input and output operations on the network or file can be extremely slow compared to processing of data in memory. Most of I/O operations involve disc access in some form and spinning of discs is orders of magnitude slower than read/ write operations on a electronic circuit.

There are different forms of non-blocking I/O like polling, signals and callbacks.

Greenlet

Greenlets or eventlets are an abstraction on top of an event loop. When using greenlets one is programming in a blocking way and the framework is using the event loop and a scheduler under the hood. The programming model is more like threads but avoiding the resource consumption.

Callbacks

A callback is a function, that is passed as an argument to I/O operation. Once the I/O operation is completed the part of the program which deals with the results of this operation is invoked. It is possible to use anonymous callbacks but this is considered a bad practice since it makes programs difficult to read. Therefore named callbacks are to be preferred over anonymous callbacks.

Event-loop

The event loop, also called message dispatcher is a programming construct that waits for and dispatches events or messages in a program. It works by polling some internal or external “event provider”, which generally blocks until an event has arrived, and then calls the relevant event handler (“dispatches the event”).

Ted Faison’s book “Event-Based Programming: Taking Events to the Limit” proved very helpful to me in understanding the ins and outs of event oriented programming. The book follows a structured approach and is very well written.

According to Fairson the event programming model is by far the superior programming model especially for large software systems. Dependencies between software parts make large software systems complex and difficult to maintain. Dependencies have the biggest impact on software quality since the most complex parts also have the most dependencies. The event oriented programming model helps you gain better modularization so development, testing and maintenance of parts of the system is easier. Fairson makes a point that by following the event oriented programming model complexity grows linear with the size of the system while you will experience exponential grows when following other models. If this proves to be true this will be the biggest discovery in software engineering for the last decade.

Message passing

An event loop is one of the methods used for implementing inter-process communication. Message passing is currently used in many software systems, including operation system kernels.

Actor model

The actor model is a programming model that treats “actors” as the universal primitive. The actor model is an abstraction on the message passing model where in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and determine how to respond to the next message received.

In programming network servers we try to avoid abstractions and rip out many of the layers of the current software stack so we can get done more on a single machine (green computing).

Implementations

As we have seen in this article the event loop is the superior programming model. Some remarkable implementations which support the event oriented programming model are available at the moment like Twisted and node.js.

Tags: , ,
Posted in Lang | No Comments »

The eight queens puzzle

Sunday, January 9th, 2011


Sample solution for the eight queens puzzle The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen moves. The queens must be placed on the board in such a way that no two queens threaten each other. Thus, a solution requires that no two queens share the same column, row, or diagonal. For the implementations below the generalized n-queens problem has been used.

Implementations using functional programming

I present the implementations of the n-queens puzzle in the order I have created them.

Common Lisp

The Lisp solution is the first I present here since I started learning functional programming languages with Lisp. I did some research on algorithms to solve the 8-queens puzzle before I cam up with this attempt to implement one. For the algorithm it is clear that per column only one queen can be placed. Once understanding the symmetric properties of the chess board it became clear that the search space can be easily split in half using only the first half of the first column. Then only 46 of the 8-queens puzzle solutions are found. The remaining 46 solutions are found by just mirroring the board.

As you all know in functional programming a different way to decompose the problem is being used. In the beginning it was a hard for me to wrap my head around that. As always in similar situations I started drawing diagrams and once I understood that map, filter, and foldr are the basic building blocks I figured it out.

Data flow graph for eight queens algorithm

I created the “multi” helper function to recurse 7 times over the map and filter. In retrospective the use of the compose macro might be more elegant.

#!/usr/bin/env clisp

"The eight queens puzzle is the problem of putting eight chess queens
on an 8x8 chessboard such that none of them is able to capture any other
using the standard chess queen moves. The queens must be placed on the
board in such a way thot no two queens threaten each other. Thus, a
solution requires that no two queens share the same column, row, or
diagonal."

(defun filter (predicate sequence)
    "(filter #'oddp? (list 1 2 3 4 5)) -> (1 3 5)"
    (remove-if-not predicate sequence) )

(defun enumerate-interval (low high)
    "create a list containing all numbers from low to high"
    (if (> low high)
        ()
        (cons low (enumerate-interval (+ low 1) high))))

(defun reflect (l n)
    "reflect a given solution from the upper half of the board to the lower half."
    (if (null l)
        ()
        (cons (- n -1 (car l)) (reflect (cdr l) n) ) ))

(defun safe (l)
    "check if the last queen in the list is threatened by its successors"
    ; threads from same column are impossible in the choosen data structure
    (if (null (cdr l)) ; not threatened by itself
        T
        (if (= (car l) (car (last l))) ; check same row thread
            NIL
            ; check for diagonal thread
            (if (= (- (length l) 1) (abs (- (car l) (car (last l)))))
                NIL
                (safe (cdr l)) ))))

(defun queens (n)
    "list the solutions for the eight queens problem"
    ; only solve for half of the first column to reduce search space
    ; use reflect on the solutions later
    (mapcan
        (lambda (x)
            (if (and (oddp n) (= (car x) (ceiling (/ n 2))))
                (list x) ; selective reflection for odd numbers of n
                (list x (reflect x n)) ))
        (multi (- n 1)
            (add-next-col (enumerate-interval 1 (ceiling (/ n 2))) '())
            (enumerate-interval 1 n)
             )))

(defun add-next-col (vs l)
    "add the next column to l (all possible values in vs)"
    (if (null vs)
        NIL
        (cons (append l (list (car vs))) (add-next-col (cdr vs) l)) ))

(defun multi (r l intrval)
    "helper to map my operators multiple times"
    (if (= r 0)
        l
        (filter #'safe (mapcan
            (lambda (v) (add-next-col intrval v))
                (multi (- r 1) l intrval) )))) 

(defun print-usage-info ()
    "Print usage hints for this script."
    (format t "Usage: queens <N>~%")
    (format t "Description: Print the solutions to the queens puzzle.~%"))

(defun main (args)
    "Main function that analyses command-line arguments."
    (if (or (/= (length args) 1)
            (null (first args)))
        (print-usage-info)
        (let ((arg1 (parse-integer (first args) :junk-allowed t)))
    (if (integerp arg1)
        (format t "~A~%" (queens arg1))
        (print-usage-info)))))

(compile 'multi)
(compile 'add-next-col)
(compile 'queens)
(compile 'safe)
(compile 'reflect)
(compile 'enumerate-interval)

(main *args*)

Haskell

My first contact with Haskell was really an eye opener. When it comes to type systems I experience people to get very opinionated. Either you belong the the one (right) fraction or you will be considered an idiot! While learning Haskell I experienced the first time that this topic has shades of grey. In Haskell the types used in your function help you to argue (think) about your program. The nice side is that the type system does not get into your way. Haskell has type detection so you do not need to write all that type related boilerplate code you have in other strongly typed programming languages. And Haskell provides type classes so you do not need Generics. It is said that one of the most important goals in designing Haskell was to make statements very compact. For example Haskell uses the space character ” ” to notate application. This leads to very compact programs. My personal summary is that I am looking forward to see a lot more of Haskell in the future.

#!/usr/bin/env runhaskell

-- Haskell solution to the n-queens problem using list comprehension

boardSize = 8

queens :: Int -> [[Int]]
queens 0 = [[]]
queens n = [ x : y | y <- queens (n-1), x <- [1..boardSize], safe x y 1]
      where
         safe x [] n = True
         safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)]

--main  = print $ queens 8
main  = print $ length (queens 8)

Erlang

Having deep roots in Prolog Erlang has no static typing. The current hype concerning Erlang is about its strong support for parallel computing. I did not use this feature in the following solution. As you can see the Erlang and Haskell solutions are very similar and it is easy to transform one into the other.

#!/usr/bin/env escript
-export([main/1]).

queens(0) -> [[]];
queens(N) -> [ [X|Y] || Y<-queens(N-1), X<-[1,2,3,4,5,6,7,8], safe(X, Y, 1)].

safe(X, [], N) -> true;
safe(X, [C|Y], N) -> (X /= C) and (X /= C + N) and (X /= C - N)
    and safe(X, Y, (N+1)).

main([X]) ->
    N = list_to_integer(X),
    Q = queens(N),
    % io:format("~w~n",[Q]).
    io:format("~w~n",[length(Q)]).

Python

Python has elegant support for List Comprehensions as well. Consequently there is not a huge difference to the Haskell and Erlang solutions besides that the Python solution it is a little bit more verbose.

#!/usr/bin/env python

"""The eight queens puzzle is the problem of putting eight chess queens 
on an 8x8 chessboard such that none of them is able to capture any other 
using the standard chess queen moves. The queens must be placed on the 
board in such a way thot no two queens threaten each other. Thus, a 
solution requires that no two queens share the same column, row, or 
diagonal."""

def queens(n):
    """Compute the solutions for the n-queens puzzle."""
    board_size = n
    def queens_intern(n):
        if n==0:
            return [[]]
        else:
            return [ [x]+y for y in queens_intern(n-1)
                for x in xrange(1, board_size+1) if safe(x, y, 1)]

    return queens_intern(n)

def safe(x, y, n):
    """Is the queen x threatened by the others (y)?"""
    if y==[]:
        return True
    else:
        return ((x != y[0]) and (x != y[0] + n) and (x != y[0] - n)
            and safe(x, y[1:], (n+1)))

if __name__ == '__main__':
    print len(queens(12))

Javascript

Javascript implementations which follow the Ecma 262 Standard do not support List Comprehensions. For example the V8 Javascript engine follows this 1999 standard very closely. But there is considerable hope that with the Harmony Project and the 6th edition of the standard the goodness implemented in Javascript 1.7 like List Comprehensions will be taken up.

Haskell has a strong support for mathematical reasoning about programs. So a side-effect of learning Haskell was that I also learned how to transform one expression into another. For example a list comprehension can be expressed as a composition of map and filter.

[ x * x | x \leftarrow [1..5], odd \: x] \equiv (map \: square \: \circ \: filter \: odd)[1..5]

Above an example for a equivalence transform of a list comprehension into a composition of map and filter. The function composed of map and filter is much less readable than the nested list comprehension.
The list comprehension is constructed in one pass whereas the application of the map and filter function takes two passes. However if one does the composition in the wrong order he is in deep trouble since he gets a program which still computes the correct solution but this tiny little difference has a huge impact on performance. In the 8-queens solution the queens_intern function is called nine times. If the order is wrong it is called 20 million times which results into a factor 1000x impact on execution time. I think these are strong arguments in favour of using list comprehensions.

var count = 0;

function queens(q) {
    var board_size = q;
    function queens_intern(n) {
        count += 1;
        if (n==0){
            return [[]];
        } else {
            // Javascript normally has no list comprehension so I had to 
            // transform it using map/ filter and consequently lost some readability
            // [ [x]+y for y in queens(n-1) 
            //        for x in xrange(1, board_size+1) if safe(x, y, 1)]    (Python)
            // the following commented out code invokes queens() 19173961 times
            // real	1m27.636s, user	1m27.933s, sys	0m0.296s

    /*        return _.reduce(_.map(_.range(1,9), 
                                  function(x) {
                                    return _.filter(_.map(queens(n-1), 
                                                          function(y) {return [x].concat(y);} ), 
                                                    function(f) {return safe(f[0], _.rest(f), 1);} );}
                                  ), 
                            function(c,d) {return c.concat(d);}
                            ); */
            return _.reduce(_.map(queens_intern(n-1),
                                  function(x) {
                                    return _.filter(_.map(_.range(1, board_size+1),
                                                          function(y) {return [y].concat(x);} ),
                                                    function(f) {return safe(f[0], _.rest(f), 1);} );}
                                  ),
                            function(c,d) {return c.concat(d);}
                            );
        }
    };
    return queens_intern(q);
};

function safe(x, y, n) {
    if (y==undefined || y.length==0){
        return true;
    } else{
        return ((x != y[0]) && (x != y[0] + n) && (x != y[0] - n)
            && safe(x, _.rest(y), (n+1)));
    }
};

var res = queens(8);
//_.each(res, function(x) {print(x);});
print(res.length);
print(count);

The underscore.js library provides the basic building blocks like map, filter, reduce which I needed. I downloaded the V8 Javascript engine and compiled it with the “sample=shell” option. Now I can run it on my machine “time shell underscore.js queens_map_filter.js”.

Finally, execution times

The solutions for the n-queens puzzle discussed above have not been optimized for performance. Focus of the solutions is on readability and experimentation with functional programming concepts. I currently work as a performance engineer and therefore I need to get some insights on execution time considerations, too.

Before you draw any conclusions based on the numbers below please be aware that this is not a comprehensive benchmark for real applications! If you think the problem is not a realistic one your applications are structured differently. Then I must say that I choose the problem purposefully since it resembles the kind of problem I am tying to solve and why I turned to functional programming in the first place. The eight queens problem is sufficient for me to get a feeling for the kind of work I am planning to do.

One can always argue that the comparison is not fair because of XYZ. I hope I did not hurt anybody’s feelings. If you think there is something wrong with a solution or the benchmark please let me know.
Since I tried to be fair I also included measurements of the compiled versions of the Erlang and Haskell solutions as well.

n-queens Common Lisp eight_queens_sussman.lisp eight_queens.lisp
8 0m1.024s 0m0.052s
12 ( stack overflow) 0m26.466s
Haskell queens_list_compr.hs compiled version
8 0m0.488s 0m2.668s
12 2m34.238s 0m12.353s
Erlang queens_list_compr.erl queens.erl compiled version
8 0m4.460s 0m12.213s 0m0.240s
12 72m57.726s 251m56.077s 0m58.552s
Python queens_list_compr.py queens_map_filter.py queens_conjoin.py
8 0m0.080s 0m0.116s 0m0.032s
12 0m56.384s 65m1.556s 0m10.021s
Javascript (V8) queens_map_filter.js using Rhino
8 0m0.100s 0m5.020s
12 13m19.194s 11m9.562s

I must say the results are a little different to what I had expected. For example I did not expect the Common Lisp solution to be so fast. On the other hand I am really disappointed about the performance of Erlang. Nobody promised something like that to me but there is so much hype lately about Erlang’s suitability for parallel computing so I assumed that it would be fast as well. I am also a bit disappointed by the V8 Javascript implementation. From the projects benchmarks I concluded that the n-queens solver would be much faster. I hope that the V8 team will take up list comprehensions soon similar to what Mozilla did in 2006. Also I did not expect this outcome I must say for me Python is the true winner. Especially since it is so often said to be slow.

I know that Javascript 1.7 (this is the Mozilla version) contains array comprehensions and I wanted to give it a try using Spidermonkey. So I tried to use Spidermonkey smjs on Ubuntu 10.10 but unfortunately the Spidermonkey-bin package is gone and I could not find a workaround. I will redo the Javascript test as soon as a suitable workaround is found to get smjs running on Ubuntu again.

Tags:
Posted in Lang | No Comments »