Wednesday, August 29, 2007

unlikely() & likely()

This week wasn't really productive. No preparations for sessionals yet. Stayed up last night so missed the college today. And some idiot classmates must be thinking now that I was preparing hard for sessionals. Poor kids, ;-)

Actually, I tried my hands with Linux Kernel Development. And its such an amazing thing!!

For starting out, I downloaded the source of latest kernel as linux-
I unpacked it, and started reading code. And as some of you must have guessed it, it was beyond my limits of understanding.

Its quite difficult to start actually. Including the comments, the whole kernel code (latest) is about 7.3 million lines. Too much, na? The first version, 0.0.1 had about 10000 lines. I read somewhere that lately they've not been adding much to this code, but refining it and fixing bugs.

The Linux kernel is one of the best (or the best as they say) kernels around. It has got a great mix of good algorithms, and it has refrained from bad policies and poor design. Its monolithic and still quite modular.

Its well commented, and the code gives me a feeling that it can be understood, given time & patience. Well I've got some books too, notably Linux Kernel Development 2nd Edition, which will help me as I go.

There are some interesting things when writing kernel code. First, you can do everything and anything. Nobody will trap you or accuse you or kill you. No memory protection (as userspace has got), no faults and error trapping. You need to behave responsibly.

Second, you don't have the standard C library. No printf (though a printk is there). No great time saving functions. But fortunately, most useful ones are there in kernel headers (like string comparison etc.)

Third, you have a small, fixed-size stack. Unlike userspace applications, you just cannot allocate tons of variables! So every byte counts here.

Fourth, no floats in kernel code. No floating point arithmetic here. Because kernel has a do-it-yourself overhead. So, just integers and chars.

Finally, the one I found most interesting is about predictability. Conditional branches can be optimized as either very likely or very unlikely by GCC. The macros likely() and unlikely() do this work.

/* file is almost never NULL */
if (unlikely(file == NULL)) { .. }

/* the two sizes are almost always equal */
if (likely(new_size == old_size)) { .. }

Compiler will optimize these branches as the programmer has predicted. If prediction was good, it will improve performance. Otherwise it can degrade performance, too. You'll find unlikely() a lot in kernel code.

Its an intelligent piece of code. And so it requires a lot of time to study. Well, I am prepared for anything! Let's tame the beast!

No comments: