Steady as a rock

X does ‘weird’ things on this machine (trident chip), looks like a moire effect so I assume sync issues. Being an X noob, I can’t figure out how to fix this,  following hints found on the web (mostly involving modelines) didn’t work either. Is there anyone out there who reads this and can give me a hint? Please?

To my shock, I didn’t find a way to enumerate all permutations of a set of items in any reasonably standard python module. (aka installed when I found out on the train). Of course this has been implemented many times before but I’m sharing it anyway :)
A set of n items has n! permutations. Simple factorial implementation (seems also nowhere to be found in the standard python libs or numpy):

def factorial(x):
    if x < 0:
        raise ValueError("Factorial is only defined for x >= 0")
    y = 1
    while x >= 2:
        y *= x
        x -= 1
    return y

Permutations can easily be defined recursively, but that limits you to sets of 1000 items (maximum recursion depth). So better to make an iterative function. Even better: instead of returning a list, use a generator so you don’t have to copy an array many times. This is also a perfect example of writing obfuscated code in a clean language like python.

def permute(items, i):
    items = items[:]
    n = len(items)
    m = factorial(n)
    while n:
        c = (i%m) * n / m
        yield items[c]
        items.pop(c)
        m /= n
        n -= 1

Example:

>>> import permute
>>> items = [1,2,3]
>>> for i in range(permute.factorial(len(items))):
...     print list(permute.permute(items, i))
...
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Update: keybuk points out that this is pretty useless and that you should read documentation instead.

Every day, I travel about 80 minutes to work and 80 minutes back, by public transport. This is rather boring but fortunately I usually have my laptop with me, so I can do some work or experiments. Last week I started a little project I call traincoding: trying to accompish some small tasks while on the train. This is the first episode of the traincoding log.

Per-thread global variables

A simple way to make your library cumbersome to use in a threaded environment, is the use of global variables. They often have to be locked and unlocked, which costs quite a bit of time. If the global variables aren’t neccessarily global in the process but shared between functions (a good example is the infamous errno variable, which is thread-local by the way), the posix specification gives you something useful: pthread_setspecific. With this and some other functions from libpthread you can make an errno-like thread-local global variable.

In a modern glibc, errno is no longer an extern int errno; but a macro:

#define errno (*__errno_location ())

the __errno_location function finds out the thread-local address where errno is stored. This does not need pthread_getspecific since the C runtime allocates memory for errno explicitely. For our purposes we need to do our own allocation. Of course this is not limited to integers. The only thing we store is a pointer, the C runtime does not care what the pointer points to.

So, let’s define our macro first:

#define my_var (*(__get_my_var_location()))

The __get_my_var_location function now creates the key when it’s first called. It also allocates memory when it is first called in a specific thread:

pthread_key_t __my_var_location;
pthread_once_t __my_var_init;

void __init_my_var(void) {
    pthread_key_create(&__my_var_location, NULL);
}

int *__get_my_var_location(void) {
    void *ptr;
    (void) pthread_once(&__my_var_init, __init_my_var);
    ptr = pthread_getspecific(__my_var_location);
    if(!ptr) {
        ptr = malloc(sizeof(my_var_t));
        pthread_setspecific(__my_var_location, ptr);
    }
    return (int*)ptr;
}

That’s easy to use already, but having to type out 2 functions for every variable-like macro which you want to use this way is still a bit cumbersome, so why not let the C preprocessor do it for you? Here’s where it gets evil! You can download the code at the bottom as perthread.h and simply use the following in your code (here’s a full test):

#include
#include "perthread.h"

PER_THREAD(unsigned int, foo) /* NOTE: no semicolon! */
#define foo (*(__get_foo_location()))

static pthread_barrier_t barrier;
void *thread(void *arg) {
    foo = (unsigned int)pthread_self();
    printf("thread: %u foo: %un", (unsigned int)pthread_self(), foo);
    pthread_barrier_wait(&barrier);
    printf("thread: %u foo: %un", (unsigned int)pthread_self(), foo);
    return NULL;
}

int main(int argc, char **argv) {
    pthread_t t1, t2, t3;
    void *res;

    pthread_barrier_init(&barrier, NULL, 3);
    pthread_create(&t1, NULL, thread, NULL);
    pthread_create(&t2, NULL, thread, NULL);
    pthread_create(&t3, NULL, thread, NULL);
    pthread_join(t1, &res);
    pthread_join(t2, &res);
    pthread_join(t3, &res);

    return 0;
}

perthread.h contains the following PER_THREAD macro (you have to imagine a backslash at the endo of each line, wordpress messes it up):

#define PER_THREAD(type, name)
static pthread_once_t __ ## name ## _init = PTHREAD_ONCE_INIT;
static pthread_key_t __ ## name ## _location;
void __init_ ## name (void) {
    pthread_key_create(&__ ## name ## _location, free);
}
int *__get_ ## name ## _location(void) {
    void *ptr;
    (void) pthread_once(&__ ## name ## _init, __init_ ## name);
    ptr = pthread_getspecific(__ ## name ## _location);
    if(!ptr) {
        ptr = malloc(sizeof(type));
        pthread_setspecific(__ ## name ## _location, ptr);
    }
    return (type*)ptr;
}

This macro takes care of creating your initialization function and get_location function, all with the correct type and name. To see that it’s correct, run it through the C preprocessor.

That’s part one of traincoding. See you next time!