GeeCON 2012 registration is open!

If you would like to attend one of the biggest Java conferences in Europe and hear some renowned speakers like Adam Bien, Isabel Drost, Bruce Eckel, Ivar Jacobson or Simon Willnauer live, you are welcome to register at http://2012.geecon.org/. It's a great place to share your thoughts and experiences with some most passionate Java experts from all over the world. It would be great to see you on 16th-18th May 2012 in Poznań, which is also one of the host cities of the UEFA 2012 European Football Championship.

Gomemcache with multiget support

It's my pleasure to announce that gomemcache already has six contributors that have supplied changes and fixes to the original code base. A recent patch by Arbo von Monkiewitsch adds GetMulti() function that allows fetching values for multiple keys with one function call.
As a side note, one thrid of patches, as well as a few of my commits, are purely compatibility fixes for subsequent Go releases. I think that at the moment frequent changes to the standard libraries and the language core are the main blocker preventing wide adoption of Go by the IT industry.

Human factor

Having recently moved to a netbook, I realized again how important performance is for software development. I realized it even more when my Android phone became almost unusable after another software upgrade. As a kid I was a big fan of a computer demoscene where gifted coders showed to the world how to make the hardware do things unimaginable even by its creators (like a famous Commodore 64 FLI graphic mode). Now when the number of small devices connected to the Internet exceeds the number of computers and laptops wired to the global network, writing efficient software is a must: Facebook develops HipHop for PHP (written in C++), Google releases Native Development Kit for Android and makes Go the first compiled programming language available for the Google App Engine platform.

It is commonly argued that ANSI C is the "fastest programming language" that exists. No it's not. The language itself is neither slow nor fast, it's the implementations that are (compare Ruby and JRuby for example). However, it's true that software written in C can be usually compiled to the most efficient executable code (excluding pure assembly). No wonder that the most efficient pieces of software, like operating system kernels (Linux, BSD, Solaris, Windows, etc) or programming language VMs (Common Lisp, Python, PHP, Ruby, and even Java) are all written almost exclusively in C (not even C++).

Out of curiosity I started to look around for web software written in C and found a wonderful web server called G-Wan. It's very small and its performance looks really amazing as compared to other web servers - some enthusiastic reviews even call it The Future of the Internet and wonder why such a brilliant software is not popular. Well, G-Wan is not popular, because there is a problem. A big problem. And the name of the problem of G-Wan is Pierre Gauthier, its author. If you browse through the G-Wan's website and forum you can learn that he is a man with a really huge ego (he calls himself one of the best engineers available), who loves to criticize other people's work (like Poul-Henning Kamp's, the author of Varnish). But at the same time he does not want to publish his own source code nor make it open source, because he perceives other developers as inferior idiots, who would surely break it or at least bring nothing interesting to the existing code base. Moreover, evil government agents will try to introduce backdoors into his software and you are more secure when Pierre hides his code deep under his bed and tells you that you should trust him. And of course you do, don't you? And if you invest your time and money in G-Wan you don't have to worry at all about future development and maintenance, because even though the source code is closed, Pierre also gives you his word that he will not drop the software, and that he will never get hit by a bus (I'm not exaggerating, just read this post). I will not go deeper into his paranoia of his website being constantly attacked by Microsoft and NSA servers, because you already should have an idea about the way the guy thinks.

Edit: On the contrary to the information provided by its author, some security problems have actually been found in G-Wan. The affected version 2.10.6 is no longer available, and the issue was addressed by Pierre in his usual manner (one of the most funny claims is that nobody ever tried to confirm the bugs, while there is no archive of older G-Wan versions to verify it). Also, any links leading to the report are being actively removed from Wiki pages (see the comments to this post for details).

On the other pole there is a true pearl called Tiny C Compiler created by Fabrice Bellard. It's so insanely fast (it can compile the typical Linux kernel in less than 15 seconds!) that it can be used to write scripts or servlets in ANSI C (guess what is used internally by G-Wan to compile the servlets). With another open source project, libmicrohttpd, it can become a good alternative if you want to build a small, fast web server that can use ANSI C servlets (for example as an embedded router software). Libmicrohttpd is fully HTTP 1.0 and 1.1 compliant, and it offers several threading models, so you can tune your software and choose which one suites you best in your environment. If I was supposed to build a tiny embeddable web server, I would definitely choose open source libmicrohttpd + tcc + some personal coding over G-Wan.

P.S. G-Wan's author deleted forum from his website, also ensuring (with carefully crafted robots.txt file) that none of its contents is archived by search engines. The forum contained many important information for G-Wan users, but user support is obviously less important than invalidating links in this and other unfavourable posts. Of course you are still welcome to believe in "source code insurance", and that the same will never happen to G-Wan.

Another one bites the dust

A few days ago I found an interesting post on Ken Shirriff's blog, entitled Why your favourite language is unpopular. It summarizes a talk by Erik Meijer who provided a simple, yet very accurate, explanation why some programming languages gain popularity, while some other (often better in many aspects) don't. I thought about this formula in context of Reia, a very promising language for Erlang platform I mentioned about back in 2008 in my post Scripting Erlang. The author of Reia has just announced that he drops development of Reia in favour of Elixir. It seems that with the amount of software existing today there is very little space for another programming language, even if it addresses problems hard to solve with mainstream languages. With existing army of programmers at its disposal, the IT industry can deal with most of its problems using existing tools, without the need of inventing another language to rule them all. A good example of such philosophy is Cilk Plus, which originates from Cilk and allows to scale C/C++ code easily on multicore CPUs. With Cilk you can improve your existing software without rewriting it from scratch with a new computer language, which in the long run can create more problems than it actually solves.

Running Scala via Nailgun

Recently a friend of mine got me interested in Scala, a modern programming language for JVM. Scala reached a wide audience in 2009 when Twitter announced that they use Scala in the most critical elements of their backend. It became popular for its efficiency and scalability, and for joining in a very pragmatic manner the concepts of functional and object oriented programming. It also implements some very powerful constructs, like foldLeft, which allows you to compose your own reduction methods operating on lists (see this page for some very interesting examples).

I decided to give it a try on my Acer Aspire One netbook, which I use often to do some daily tasks. Unfortunately, with 1.6 GHz Intel Atom and 1GB RAM running Fedora 14 it took Scala REPL almost 20 seconds to start. I was wondering if I could make it faster and found out that some people recommended Nailgun for this task. In short, Nailgun preloads the whole JVM into the memory and than uses its own bootstrap loader to connect your programs to it, so that they load much faster, without JVM startup overhead. However, besides some good advice I couldn't find any working example how to do it, so I decided to do it myself. Fortunately it turned out to be a quite easy task. First, I copied nailgun-0.7.1.jar to Scala's lib directory, then I took the original bin/scala script and created a modified version. I changed line 161 from

scala.tools.nsc.MainGenericRunner  "$@"

to

com.martiansoftware.nailgun.NGServer  "$@"

and line 113 from

CPSELECT="-Xbootclasspath/a:"

to

CPSELECT="-cp "

The last change was necessary for Nailgun to load properly. Then I started regular Scala REPL through

ng scala.tools.nsc.MainGenericRunner

just to learn that it still takes 20 seconds to start. Conclusion? Modern JVM loading overhead is so small that reducing it further makes little sense, even on slow machines.
Lessons learned:
1) Using Nailgun to speed up Scala won't get you anywhere.
2) Don't listen to forum "experts" who recommend solutions which they have obviously never tried in practice.

Scale up your skills, not the hardware

It is not a big secret that good programmers keep their saws sharp all the time. If you want to improve your mental skills a good place to start is Project Euler. I found it while browsing other programmers' blogs and immediately got hooked up. Project Euler is a place where you can challenge yourself (and others) in solving various mathematical and computer programming problems. The collection of problems is constantly growing and you can find them ranging from very easy to really difficult. When you provide the correct solution to a problem, a forum dedicated to it becomes revealed and you can see how other people managed to solve it. Sometimes you can also get a bonus in a form of paper explaining the problem and the best known solutions in details. You can learn a lot from these forums since people share there both their ideas and source code written in different programming languages; some of them don't even use a computer, all they need to find a solution is paper and pencil.

What I particularly like about Project Euler is that most of the problems cannot be solved by brute force. They can make you check hundreds or thousands of possible combinations, but still require a more clever approach. A classic example are problems 18 and 67, where you need to find a path from the top of the number pyramid to the bottom, so that the total sum of numbers on the path is the largest. While the pyramid in problem 18 is rather small and you can find the solution by trying every of 16384 possible paths, it is impossible to solve problem 67 the same way. To solve it you need to turn the problem upside down - literally, since you can easily get the correct solution if you start searching for the best path from the bottom of the pyramid to the top, reducing the number of combinations with every step.

You may wonder how mathematics can help you in facing every day challenges as a programmer. Imagine you work for an on-line store with millions of CD records on stock, and you provide a browser with a dynamic list of products based on different criteria, such as genre, year and price. Now you want to show to your customers the most popular product within the range they choose. Getting all items satisfying the selected criteria from a database and finding the most popular one every time someone browses the list will quickly kill your back-end. On the other hand, it is impossible to generate such data in advance for every possible combination of search parameters. You can either expand your server farm (and possibly move to the cloud to reduce costs) or you can use some statistical tools to help you do the job. The trick is to find a representative sample size for a given population of products. Assuming that N is a total population, z is a statistical factor for desired confidence level, p is an estimated proportion of a given variable within the population, and d is admissible error level, we can get sample size n with the following formula:

x = z^2 * (p * (1 - p))
n = N * x / ((N - 1) * d^2 + x)

The z factor is constant and equals 1.96 for the 95% confidence level and 2.58 for the 99% confidence level. Assuming that a selected range of CD records contains one million uniformly distributed products and you can tolerate a 5% error, it turns out that in 95% cases you get the most popular one correctly by analysing only 385 randomly chosen items from the list, since:

x = 1.96^2 * (0.5 * (1 - 0.5)) = 0.9604
n = 1000000 * 0.9604 / ((1000000 - 1) * 0.05^2 + 0.9604) =~ 384.013

To be 99% sure that no more than 1% results are incorrect, you'd need to analyse 16369 records.

You can learn more about calculating sample sizes from this article at Quirks - I took the above formula from it. And remember: while it's true that machine cycles are cheap and people cycles are not, never forget that people cycles are worth billions of machine ones.

MapReduce with Gambit Scheme & Termite

Termite is a library that runs on top of Gambit Scheme and implements concurrency model inspired by Erlang (there is also a Chicken Scheme port, but it's so far incomplete). Since I have already posted about Termite some time ago, I will not go into details how to write distributed applications with it. Instead, I want to show you how to use Termite to implement a simple MapReduce algorithm.

A trivial implementation uses a simple worker process that executes some code, and a pmap function which spawns multiple workers and collects the results:

(define (worker)
  (let* ((msg (?)) (pid (car msg)) (fun (cadr msg)) (arg (caddr msg)))
    (! pid (fun arg))))

(define (pmap fun lst)
  ; spawn workers
  (for-each 
    (lambda (x) (let ((p (spawn worker))) (! p (list (self) fun x))))
    lst)
  ; collect results
  (let loop ((i (length lst)) (result '()))
    (if (= 0 i) (reverse result) (loop (- i 1) (cons (?) result)))))

So far it works similar to its Erlang equivalent. However, this version does not guarantee (just like the Erlang one) that you get the results in the same order as the arguments passed to pmap. Let's consider function f, which holds execution of the current thread for a given number of seconds:

(define (f x) (thread-sleep! x) x)

If you run the following code:

(pmap f (list 1 2 3 2 1))

The result will be:

(1 1 2 2 3)

Since the first results on the list will come from the processes that finished first.

A solution to this problem is to make a single worker process using a sequencer to mark spawned threads. Numbers generated by the sequencer are then used to sort the results to achieve the correct order of the result list:

(define (worker)
  ; init sequencer
  (let loop ((n 0))
    (let ((msg (?)))
      ; terminate worker on request
      (if (not (eqv? 'exit (car msg)))
        (let ((pid (car msg)) (fun (cadr msg)) (arg (caddr msg)))
          ; start a new thread
          (spawn (lambda () (! pid (cons n (fun arg)))))
          ; increase sequencer
          (loop (+ n 1)))))))

(define (pmap fun args)
  ; start worker
  (let ((p (spawn worker)) (result '()))
    ; send data to the worker
    (for-each (lambda (x) (! p (list (self) fun x))) args)
    ; collect results
    (let loop ((i (length args)) (lst '()))
      (if (= 0 i)
        (set! result lst)
        (loop (- i 1) (cons (?) lst))))
    ; terminate worker
    (! p (list 'exit))
    ; sort results
    (let loop ((in (qsort result <)) (out '()))
      (if (null? in)
        out
        (loop (cdr in) (cons (cdar in) out))))))

You can use any function you wish to sort the results. I used a modified version of quicksort found at Rosetta Code:

(define (qsort l gt?)
  (let q ((l l))
    (if (null? l)
      l
      (let ((s (split-by (cdr l) (lambda (x) (gt? (car x) (caar l))))))
        (append (q (car s)) (list (car l)) (q (cdr s)))))))

(define (split-by l p)
  (let loop ((low (list)) (high (list)) (l l))
    (if (null? l)
     (cons low high)
     (if (p (car l))
       (loop low (cons (car l) high) (cdr l))
       (loop (cons (car l) low) high (cdr l))))))

Now when you run the test again, you get the result list in the same order as the argument list, no matter what the execution time of single processes was:

(pmap f (list 1 2 3 2 1))

(1 2 3 2 1)

You can download the pmap library here.