This post will describe the basics of a very powerful feature of the D programming language: the Compile-time Function Execution (CTFE), which allows complicated functions to be fully evaluated at compile-time, irrespective of the optimization levels.

C optimizations

If you are an average C programmer, you know that simple code can be trusted to be evaluated at compile-time thanks to optimizers. For instance, if you write something like:

void square(int x) { return x*x; }

void foo(void)
{
   int k = square(32);
   /* ... */
}

you trust your compiler to evaluate the square at compile-time, when optimizations are on. When things get more hairy:

int factorial(int x)
{
    int result = x;
    while (--x)
         result *= x;
   return result;
}

void foo(void)
{
   int k = factorial(8);
   /* ... */
}

C programmers get immediately less confident about what will happen at run-time. For instance, would you say that your compiler is able to expand the above code at compile-time or not? Actually, the answer is “yes” in this particular case (unless you are using a very old compiler), but the point is still valid: this is not C code that one would write if he wants to be sure that the whole calculation be folded at compile-time.

There is also another issue: since the language does not mandate that the value is folded (and in fact, it is not folded when optimizations are disabled), you cannot create a constant out of it, such as by assigning it to a const variable.

When things get hairy

Now, let’s try with a (very naive and simple) solution of problem #1 of Project Euler:

#include <stdio.h>

int euler1(int max)
{
   int i,res=0;
   for (i=1; i<max; i++)
   {
       if ((i % 3) == 0 || (i % 5) == 0)
           res += i;
   }
   return res;
}

int main()
{
   int r10 = euler1(10);
   int r1000 = euler1(1000);
   printf("%d %d\n", r10, r1000);
   return 0;
}

This program simply calculates the sum of all divisors of 3 or 5 below 1000. But if you look at the generated code with GCC under -O3, you will see that the actual results are not computed at compile-time, but rather calculated at runtime. I believe any average C programmer would agree that we should not expect this code to be folded at compile time.

Now, meet the equivalent D code:

int euler1(int max)
{
   int i,res=0;
   for (i=1; i<max; i++)
   {
       if ((i % 3) == 0 || (i % 5) == 0)
           res += i;
   }
   return res;
}

int main()
{
   int r10 = euler1(10);
   int r1000 = euler1(1000);
   printf("%d %d\n", r10, r1000);
   return 0;
}

Deja-vu? Yes, it is exactly the same, barring the initial include statement that is not required (actually, there is no preprocessor in D and modules refer to each other with the import statement, but printf is a builtin). Of course, the above example was hand-crafted to make it both valid C and D code, but being D an evolution of C, the basic syntax is the same.

Meet CTFE

And now the hattrick: in D, we can request the compiler to evaluate euler1 at compile-time by simply using the static keyword at invocation time:

   static int r10 = euler1(10);
   static int r1000 = euler1(1000);

Great, isn’t it? Now the result of the above function call are evaluated by the compiler, irrespective of the optimization levels. If the function cannot be evaluated at compile-time (usually because it has side-effects, like any kind of I/O), it will trigger a compile-time error.

We can verify that the above constants really do appear in the generated code by compiling with gdc -save-temps euler1.d and then inspecting euler1.s:

D6euler14mainFZi3r10i:
        .long   23
.globl _D6euler14mainFZi5r1000i
        .align 4
        .type   _D6euler14mainFZi5r1000i, @object
        .size   _D6euler14mainFZi5r1000i, 4
_D6euler14mainFZi5r1000i:
        .long   233168
        .section        .rodata
.LC0:
        .string "%d %d\n"
        .text
.globl _Dmain
        .type   _Dmain, @function
_Dmain:
.LFB3:
        pushq   %rbp
.LCFI3:
        movq    %rsp, %rbp
.LCFI4:
        movl    _D6euler14mainFZi5r1000i(%rip), %edx
        movl    _D6euler14mainFZi3r10i(%rip), %esi
        movl    $.LC0, %edi
        movl    $0, %eax
        call    printf
        movl    $0, %eax
        leave
        ret

Notice how the compiler has calculated the values 23 and 233168 (respectively, results of euler1(10) and euler1(1000)) and put them in the data section of the executable.

If you are curious of what happens when the compiler cannot do the whole evaluation at compile-time, it is sufficient to stick a printf() call somewhere in the euler() function. Since printf() does some I/O, it breaks CFTE, and the compiler will happily tell you about that:

euler1.d:9: Error: cannot evaluate printf("hello, world!\x0a") at compile time
euler1.d:15: Error: cannot evaluate euler1(10) at compile time
euler1.d:16: Error: cannot evaluate euler1(1000) at compile time

Closing words

CTFE is simple yet very powerful. The fact that it is triggered at the call site (rather than being an attribute of the function, like the inline keyword) is a very smart design choice: it makes perfectly sense for the same function to be used at both run-time and compile-time, depending on the inputs.

For the C++ guys reading, C++0x has grown a constexpr keyword that, while looking superficially similar, it is a lot less powerful, since it can only be used on very simple functions (basically, one-liners). In fact, the keyword is meant to be use while declaring a function, and not at the call-site, so it has to apply only on small functions which can be proved to always yield a constant value.

In the next weeks, I will post a more complete real-world example of the power of CTFE from BeRTOS. Stay tuned!

In the never-ending spam-fighting war, many different technologies are implemented to prevent users from wadingthrough a daily batch of pill discounts and lottery winnings. Two of them, which are both very effective, are greylists and RBLs (aka blacklists); they both operate at the SMTP level (even before the mail body is transferred). Usually, these technologies are deployed separately, but even better results can be achieved when combined. How? Follow me.

Greylisting

Greylisting is a very common anti-spam technology: whenever a potential spam arrives, our MTA replies with a temporary failure code (SMTP code: 4xx), and writes down the IP address of the sender MTA (the server that is sending the e-mail) in a DB; when facing a 4xx code, any RFC-compliant MTA will simply try to deliver the same e-mail again after a while, at which point our MTA will let the mail through (because the IP address is already present in the DB). On the other hand, most spammers do not follow the RFC (how bizarre): they would not bother retrying and would simply move on; this is because each retry is a memory/CPU cost for them (they need to note down the server which is temporary failing, keep a queue around, etc.); after all, if it was a real temporary failure, that server might still be failing for a few hours, and it would be a real waste of bandwidth to try again, just to stop at the same temporary failure.

What it is interesting about greylisting is that such a simple idea can achieve impressive results. If you google around, you will find enthusiastic people reporting at least 80% of spam blocked, with few of them citing numbers as high as 95%. All modern mail servers support greylisting either out of the box or through a plugin. For the famous open source server Postfix, the postgrey extension is easily available and widely deployed.

There obviously are some cons to greylisting:

• Since normally greylisting is applied to all incoming e-mails, regular e-mail delivery is delayed. In fact, a RFC-compliant MTA will eventually retry, but how soon is an implementation detail. It might be one minute or one day (even though most servers usually retry in a few minutes). Obviously, mature greylisting implementations will keep the IP address of a good server in the DB for a long time (eg: one day or one week), effectively whitelisting it; so, the delay only happens on one e-mail per server. Most people don’t see this delaying as a problem, but I do: I believe that a good anti-spam pipeline should never impact regular e-mails whatsover. I don’t want a very important e-mail to be delayed for an unknown period of time because I cannot fight spam in other ways.
• Some servers could be RFC-compliant and still fail to delivery e-mail to a server using greylisting. How & why? Simple: think of  large shop like gmail. They have dozens of SMTP servers. When a server tries to deliver an e-mail and it receives the 4xx code back, can you be absolutely sure that the same SMTP server will retry later? What if they have an unique queue of e-mail, and another server picks the same e-mail up and retries? This other server will also be greylisted.  Can you see the problem now? I won’t enter details, but many greylist implementations suggest using manually-compiled (and maintained) whitelists. Uh-oh. Less funny now.

RBLs

RBLs are blacklists of servers/zombies that deliver spam, listed by IP address, and queried through the DNS protocol. In short, if you want to ask super-blacklist.example if 1.2.3.4 is listed there, it is sufficient to try to resolve the hostname 4.3.2.1.super-blacklist.example; if it resolves to an IP address (any IP address, it doesn’t matter), it’s listed; otherwise it is not listed.

Blacklists can be deployed within a mail server at different levels. For instance, you can use them in a score system to increase the probability for a mail to be treated as spam. Or you can use them to simply reject the e-mail at the SMTP level, even before the body is transferred (since everything you need to query the blacklist is the MTA IP address, and you have this information as soon as the TCP connection is initiated to your MTA).

Of course, not all blacklists are equal. If you rely on them for rejecting your e-mails, you better be sure that the blacklist is well-maintained, has a good reputation and that you are using it correctly. For instance, if we analyze the famous Spamhaus Zen blacklist, we find out that it is made of three different blacklists, one of which is the PBL. The PBL is (quoting) “a DNSBL database of end-user IP address ranges which should not be delivering unauthenticated SMTP email to any Internet mail server except those provided for specifically by an ISP for that customer’s use”. Rephrasing: it is a list of all dynamic IP ranges in the world; all home ADSL users are listed here. That’s it. There is no connection with spam altogether, it is just a list of dynamic IP addresses. Now, while most dynamic IP addresses will never deliver an e-mail directly to your server (and instead go through their ISP’s MTA), are you ready to block these hosts at the SMTP level? What if someone (one in ten thousands) runs a legitimate MTA server on their ADSL line? They are not violating any RFC, so why should you blacklist them? In fact, SpamHaus itself suggests against using this list for outright rejection of e-mail.

So, is there anything we can do with PBL at the SMTP level, which is in the middle between outright rejection and a SpamAssassin-like score system? Yes we can: we can greylist!

Greylisting & RBLs together

There are many different anti-spam technologies that can be done at the SMTP level, by looking at the so-called SMTP envelope (the SMTP conversation that happens before the actual e-mail is delivered). For instance, some people configure their servers so that they will reject e-mails based on the HELO command, eg: if its argument is not a FQDN hostname, as required by the RFC. Others (including myself) consider an outright rejection too risky, because there might be misconfigured MTAs out there and it’s not their users fault (nor your users fault!). Traditionally, you could either choose to implement one of these enforcements or not. But there is an alternative: greylisting.

Let’s get back to the PBL example. Using PBL for filtering e-mails is attracting:

• Almost all regular e-mail will arrive from a non dynamic consumer IP address.
• Almost all e-mails that you get from dynamic consumer IP addresses will be spam (basically, zombie Windows PCs running malwares that deliver spam).

But almost is not always, and I don’t want to risk rejecting any regular e-mail, even if it happens once a year. I don’t want to impact regular e-mails whatsover. So, you can do like me and just greylist entries from IPs that are in the PBL. The worst thing that can happen is that those e-mails are slighly delayed, but given the unlikeness of such event, it is probably an acceptable compromise.

If you think of it, this is just a smarter alternative way of deploying greylisting. Instead of greylisting each and every e-mail and causing delays to all your users, you greylist only those e-mails that are very dark grey but not really black. And if you google around for SMTP anti-spam tricks, you can find many of them which follows in this dark grey area: they’re so dark that some mail admins reject e-mail altogether, but they’re not fully black, so other more conservative admins just punt. Don’t punt: greylist!

This is why I greylist all e-mails from IPs in the PBL. And I also greylist all e-mails whose HELO string is not a FQDN, so that the occasionally misconfigured server is just delayed a little while, but not rejected, and I still block lots of spam very early in the pipeline.

And now, give me the code!

As much as I find this kind of greylisting deployment so sexy, it is depriving to see that there is basically no support around in mail servers for such a setup. The abandonware spftware called gl4rbl is the best I could find around, and we succesfully deployed an enhanced version of it with qmail in Develer for a long time.

When we switched to Postfix, we had to reimplement this, because the existing postgrey plugin does not allow conditional greylisting.

In the next days, we will post our own Postfix Policy Server that implements greylisting on RBL. It is a very compact Python script, less than 200 lines including comments. We also have some ideas on making it more generically useful so that it can be used to implement other kinds of conditional greylisting, and I will discuss them in the same post.

In case you did not know, you can avoid missing it by subscribing to the RSS feed.

I generally like C++ and the way C++ feels, but there is one specific quirk which is caused by STL designers’ choice of data structures which cannot be implemented with a copy-on-write (aka COW) semantic. Curious about which quirk? Keep on reading! COW might look like an implementation detail, but it can really change the way you design your APIs.

What is a COW?

An object with COW semantic (sometimes also called “implicit sharing”) has an interesting property: whenever you copy it, it does not really do a “deep copy” but simply shares the underlying data between the original object and its copy, and increments a reference counter to track this. Only at the moment that any of the copies is further modified (written to), the deep copy is really performed.

Now, it is important to realize that the overhead imposed by the COW semantic is usually very tiny: the object just needs to bookkeep a counter at every copy, and check it before any modification. The latter is even lighter than it sounds because the compiler can strip off many checks thanks to constant propagations.

But what are the advantages of using COW? The first and foremost advantage is the possibility to have a clean API with respect to return values.

Returning a COW

If you have programmed C++ long enough, you know that all C++ functions that should return a complex data structure (anything which is larger than a small structure, like a container, a memory buffer, and so on) will instead accept a reference or a pointer to an object that the caller must provide and that will be “filled in” as return value. This is absolutely awful. If you don’t see it as awful, it’s about time you take a break from C++ and switch to other languages for a while. For instance:

std::vector<Node> nodes;
cur_node.children(nodes);
printf("Number of children: %u\n", nodes.size());

The Node::children() function, in any other language, would have returned a vector of Nodes. But idiomatic C++ says that you should not impose the overhead of doing an additional copy of the vector onto your user, and thus ask him to pass you the container to fill. This is really unreadable because it breaks the common syntax of functions by intermixing return values to arguments. Moreover, it imposes additional troubles to the API; eg: what happens if you call Node::children() with a non-empty vector? Will the function just append its data to the vector? Or would it clear it at the beginning?

Now, think of a world where std::vector is a COW data structure. All these problems suddenly disappear because returning the vector would not cause a copy anymore. Bam, problem solved! And when you have a clear API, where return values really are return values, you get all the benefits from it:

printf("Number of children: %u\n", cur_node.children().size());

Three lines merged into one. No more temporary named variable. And if Node happens to internally store its children as a vector, this code is even faster than the non-COW version, because there is no copy performed at all: you get the same speed as if children() returned a reference to the internal vector, even though it does not.

COWs to the rescue

Other advantages of COW data structures:

1. You can nest COW data structures without overhead. Think of a vector<vector<int>>. Without COW, whenever the outer data structure resizes, the inner data structures will all be reallocated and copied. With COW, there is no copy at all: the internal data structures are basically moved over in constant time.
2. You can stop abusing const references everywhere. In C++, most functions will receive arguments by const references instead of simple values. Again, this is to save the overhead of a copy, and again this is almost useless with COW data structures. Const references are also nasty because they represent a first leak of const-correctness in your code (I also hate the whole const-correctness in C++, but this is for another day; if you like it, you can still make your functions accept const values if you feel too).

Norwegian COWs

Nokia’s Qt has designed all objects and data structures with COW. They even made them reentrant (for multithreading purposes) by using atomic reference counting through native CPU instructions. Finally, they expose the guts of COW through a simple QSharedData template that you can use to reimplement your own COW objects.

I could not agree with Qt’s designers more.

This is another example of how COW can positively influence API design:

QByteArray fileHash(QString fn)
{
   QFile f(fn);
   QCryptographicHash h(QCryptographicHash::Sha1);
   while (!f.atEnd())
        h.addData(f.read(16*1024));

   return h.result();
}

See how I can simply pass the buffer returned by QFile::read() to addData() without having to worry about memory copying.

Counting COWs

So, the next time you design an API which asks for a return value among the arguments, think of a C++ world where COW is everywhere. And dream on.

Do you want to see how PyInstaller magically handles usages of ctypes, whilst py2exe/py2app would simply fail? Follow me in this in-depth tutorial!

PyInstaller comprises many advanced features to make your life easier when packaging a Python program. In my opinion, its main advantage over py2exe/py2app (besides the obvious fact that it is a multi-platform tool) is that it includes many workarounds and quirks necessary to make applications work after packaging. What py2exe “fixes” by adding a page to their wiki, PyInstaller implements it properly, for everybody’s pleasure.

A very good example of this philosophy is the support for ctypes. I am sure most of you are familiar with this little gem, which allows a programmer to dynamicall bind to a shared library and invokes its functions without writing a binding. For instance, let’s say you have some existing and very complicated C code like the following:

/* foobar.c */
#include <stdio.h>

void fooize(int a)
{
   printf("Fooized %d!\n", a);
}

Which is compiled to a shared library:

$ gcc -shared -fPIC -o foobar.so foobar.c

Now, you can access this from Python by simply doing something like:

#!/usr/bin/env python
# example.py

from ctypes import *
foobar = CDLL("foobar.so")
foobar.fooize(4)

which obviously produce the following output when executed:

$ LD_LIBRARY_PATH=. python example.py
Fooized 4!

ctypes handled all the magic for me: it called dlopen(3) to access the dynamic library, it called dlsym(3) to access the symbol fooize, and it even handled marshalling of arguments. This is great.

But what happens if I want to package this application? Well, with py2exe/py2app, it wouldn’t work. In fact, they would totally miss the dependency of the example program on the foobar.so file. This obviously happens because they support only the simplest forms of dependency: a plain Python import statement or dependencies between shared librarys (eg: foo.dll that depends on bar.dll).

Now, watch PyInstaller in action:

$ python ~/src/pyinstaller/Makespec.py --onefile example.py
wrote /tmp/ct/example.spec
now run Build.py to build the executable

$ python ~/src/pyinstaller/Build.py example.spec
checking Analysis
building Analysis because outAnalysis0.toc non existent
running Analysis outAnalysis0.toc
Analyzing: /home/rasky/src/pyinstaller/support/_mountzlib.py
Analyzing: /home/rasky/src/pyinstaller/support/useUnicode.py
Analyzing: example.py
Warnings written to /tmp/ct/warnexample.txt
checking PYZ
rebuilding outPYZ1.toc because outPYZ1.pyz is missing
building PYZ outPYZ1.toc
checking PKG
rebuilding outPKG3.toc because outPKG3.pkg is missing
building PKG outPKG3.pkg
checking EXE
rebuilding outEXE2.toc because example missing
building EXE from outEXE2.toc
Appending archive to EXE /tmp/ct/dist/example

$ ./dist/example
Fooized 4!

$ ls -la ./dist
totale 2927
drwxr-xr-x 2 rasky rasky      72 2010-03-19 03:33 .
drwxr-xr-x 4 rasky rasky     344 2010-03-19 03:33 ..
-rwxr-xr-x 1 rasky rasky 2991835 2010-03-19 03:33 example

It simply worked. What PyInstaller behind the hood is:

• Scan the bytecode of example.py, looking for usages of ctypes
• Collect all the shared libraries used by ctypes calls. Notice that it can’t infer all filenames potentially used by the source code (how would you handle the case where the library named is specified interactively by the user?), but it handles all simple cases (see this page for more details).
• Resolve pathnames using the OS’ library search path.

Notice how foobar.so was also included within the single-file package produced by PyInstaller. And how can this possibly work? Let strace show us the trick:

$ strace -ff ./dist/example 2>&1 | grep foobar.so
stat("/tmp/_MEIDG0H9t/foobar.so", 0x7fff92f09480) = -1 ENOENT (No such file or directory)
open("/tmp/_MEIDG0H9t/foobar.so", O_WRONLY|O_CREAT|O_TRUNC, 0666) = 4
[pid 13942] open("/tmp/_MEIDG0H9t/foobar.so", O_RDONLY) = 6
stat("/tmp/_MEIDG0H9t/foobar.so", {st_mode=S_IFREG|0700, st_size=7985, ...}) = 0
unlink("/tmp/_MEIDG0H9t/foobar.so")     = 0

What happens at runtime is that foobar.so is extracted in a temporary directory, so that ctypes can find it.

So: PyInstaller is designed to do everything required to package an application. If you like this philosophy and you are tired of chasing workarounds in wikis, you should give it a try!

So there is much chatting going on about the new IE9 and the fact that this time Microsoft tried to adhere to web standards much more than it used to do in the past. Namely:

• HTML5 for videos (H.264), which means that we will be holding a Adobe “Flash For Video” funeral pretty soon now. I notice that most geeks don’t care about usages of Flashes besides videos, but there are still many of them (both filling gaps in HTML standard, like in the case of multi-file uploads, and for animations/interactions/games where HTML5 Canvas+JS is still too slow).
• Fast JavaScript engine: aka JIT. Given how slow IE8 is in benchmarks, this is very good news for development of rich web applications on the Internet.
• CSS3, DOM, SVG: they are really supporting a lots of new features available in nowadays standards. I think the support for SVG will make many people wonder if Christmas came for Easter this year. And yes, it is indeed coming.

A very interesting news is that Microsoft is announcing GPU Acceleration for IE9. Now, we are a little short on details (and I’m not at MIX10 where IE9 is being presented) but I still see legends floating around.

First, there is absolutely no way that IE9 (or any browser, for that matter) could offload to the GPU the whole Javascript engine (and not even the compilation step required by the JIT). Modern GPUs are massively paralleled calculators. They are very good at executing a 100-lines mathematical function at the same time in 4096 cores, which is exactly what you need to do graphics (2D, 3D, whatever) and heavy calculations like physics, simulations, and so on; but they can’t really go beyond this. Moreover, there is a measurable overhead in starting each GPU task (use DMA to fill internal memory, upload the task) and fetching results (DMA the results off the video memory into main RAM).  So there is basically no way to use such a horse for running custom Javascript code.

In fact, what Microsoft is saying is that it will recompile Javascript in a different thread/process, offloading it to a different core of the CPU. This is probably a step forward in the right direction. IE8 already had a multi-process architecture much like Chrome does, and offloading the JIT itself to another process looks like a very good idea. I wonder what Chrome developers think of it.

So, what about GPU acceleration? It will be used in these main areas:

• Video decoding: Modern video cards have hardware support for H.264 decompression. This is already supported by Windows drivers, and if you use a Windows system to watch a H.264 HD video, you will see that the CPU usage is indeed pretty low. Alas, since H.264 is a patent encumbered format, this acceleration is not supported in Linux and probably will never be. The most Linux can achieve is YUV HW compositing, which is nothing like offloading the whole H.264 decoding to hardware.
• HTML5 Canvas: through the new Direct2D API, it will be easier to leverage hardware acceleration within Canvas. Notice that Direct2D, to the best of my understanding, is just a better API (both at the user-space level and driver level) to access the existing programmable graphics hardware. It is not different from what Cairo or Qt’s QPainter already offer, but it is fully accelerated. If you use Firefox on Linux, you get cairo -> xlib -> xrender, and then you’re doomed.
• Font rendering: rendering text is a big part in a browser, and the new DirectWrite API will take care of hardware acceleration for fonts. DirectWrite is a whole font-rendering stack that has been designed with hardware acceleration in mind. It is like Freetype of the next millennium. I believe there is absolutely no equivalent for DirectWrite in the OSS world.

I plan to do a quick benchmark of IE9 this week. I will specifically be focusing on HTML5 canvas rendering, since that is the part where it is meant to shine, even compared to Chrome.

Stay tuned!