Wednesday, April 30, 2008

c/c++: switch vs. array of functions

As I promised I made some tests to compare switch statement and a map to functions. As I expected a map to functions works faster. Furthermore it doesn't depend on the amount of 'switch' conditions. I made a synthetic test:

unsigned long func(unsigned long acc)
    return acc*acc;

#define SWITCH

typedef unsigned long (*fd)(unsigned long);

int main(int argc, char **argv)
    unsigned long i, acc = 0;

    #ifndef SWITCH
        fd f[15] = {func,func,func,func,func,func,func,func,func,func,func,func,func,func,func};

    for (i=0;i<1000000000;++i)
        #ifdef SWITCH
            switch (i%15)
                case 0:
                    acc = func(acc + i); break;
                case 1:
                    acc = func(acc + i); break;
                case 2:
                    acc = func(acc + i); break;
                case 3:
                    acc = func(acc + i); break;
                case 4:
                    acc = func(acc + i); break;
                case 5:
                    acc = func(acc + i); break;
                case 6:
                    acc = func(acc + i); break;
                case 7:
                    acc = func(acc + i); break;
                case 8:
                    acc = func(acc + i); break;
                case 9:
                    acc = func(acc + i); break;
                case 10: 
                    acc = func(acc + i); break;
                case 11: 
                    acc = func(acc + i); break;
                case 12: 
                    acc = func(acc + i); break;
                case 13: 
                    acc = func(acc + i); break;
                case 14:
                    acc = func(acc + i); break;
            acc = f[i%15](acc + i);

    return 0;
Times w/o switch:
$for i in 1 2 3; do time ./a.out; done

real 0m11.114s
user 0m10.973s
sys 0m0.010s

real 0m10.968s
user 0m10.966s
sys 0m0.007s

real 0m10.904s
user 0m10.899s
sys 0m0.003s
and w/ switch
$for i in 1 2 3; do time ./a.out; done

real 0m12.378s
user 0m12.399s
sys 0m0.000s

real 0m12.410s
user 0m12.413s
sys 0m0.013s

real 0m12.417s
user 0m12.423s
sys 0m0.010s
A map to functions wins ~1 sec. That's not that much but if you are building a state machine with a lot of states it's better to use mapping rather than switch.

c++: friend classes in namespaces

You can declare friend class w/o declaration of it:

class A{friend class B;}
Here compiler doesn't have to know what is class B. But things go worth if you have class A defined in namespace N and class B in namespace M, or in other words A and B are in different namespaces. If you leave the things and you don't want to include header with declaration of class B, compiler will argue that class M::B doesn't have an access to private/protected members of N::A. You can't simply do
namespace N{ class A{friend class M::B;} };
Here compiler will raise an error that there is no B in namespace M, or even no such namespace 'M' if it hasn't achieved it during parsing. The solution here is to do a declaration of empty class B in namespace M:
namespace M{class B;}; namespace N{ class A{friend class M::B;} };
This will work and your compiler will be happy ;)

Wednesday, April 23, 2008

python: switch emulation

You know that python doesn't have switch statement. Guido says he doesn't want overload language python with statements to make it as much expressive as possible. But you can emulate 'switch' not only with 'if ... elif ... else' but with dictionary. Look:

    'one': lambda: 1,
    'two': lambda: 2
}.get('one', lambda: 0)()
You can create reusable 'switch' by creating dictionary that maps to callable objects and use it to call them by key. Also such 'switch' is mutable. This can be useful in some circumstances.

Monday, April 21, 2008

c/c++: arrays and pointers

Sometime programmers don't make a difference between pointers to memory and arrays. They pass easily array to function that wants pointer. It's dangerous if it changes the pointer target(reallocates memory for example):

void function(int *a)
        delete [] a;
        a = new int[3000];
This will cause Segmentation fault if you pass an array to the function. The reason is that you can't do some pointer routines with arrays. The other difference in the type of &array. For int array[1];: array, &array and &(array[0]) are the same. Almost. An array is just a sequence of variables. But there is a rule, that c++ looks arrays as if they were pointers. It means that if you write array, compiler takes it as &array[0]. The value of &array and array is the same (address of the first element). But their type is different. Here &array has type "pointer to the array of T". If you add one to &array, it will point to the address of the place right after the last element of the array(just like you skipped the array).

Wednesday, April 2, 2008

ext3: symlinks

Everybody uses symlinks in linux. Very interesting thing about the internals of symlinks I have recently discovered. Symlink may store path to original location in two ways. Symlink is represented as usual inode in ext3 filesystem. Its definition is in ext3_inode structure. The length of the string is given in i_size. If path to original location including terminating '\0' symbol is less than size of the i_block(EXT3_N_BLOCKS * 4 bytes = 60 bytes usually) array then the path is stored in the i_block. Otherwise i_blocks will be 1 and i_block[0] will point to a block containing the target name. When the string has to be contained in i_block[0], fs driver has to resolve the block and read its contents. This reduces performance a bit. You should be aware that lots of symlinks that point to the full path may get some extra cycles of your cpu. Solution: use relative paths for symlinks.