Pretty ugly hacks

Recently I've (re-)discovered the more hacky kind of programming. It started after that I implemented my first bloom-filter. Somehow I ended up reading about all kinds of bit twiddling hacks, and finally I found myself in the realm of xor double linked lists.

Doubled linked list is a data structure where each node in the list has two pointers; one to the next node, and one to the previous node. The size of each node is thus 3 pointers. An xor linked list has the same logical function, but a compress representation -- it only requires 2/3 of the size of a normal linked list. This is achieved by observing that the only way to reach a node in a double linked list is either from the back or from the front of the list. Thus, it's enough to store the xor-sum of the pointer to the next node and the previous node, since either of those pointers is known. Anyway, the linked Wikipedia article explains it much better.

Well, the neighboring country to xor-lists is Tagged Pointer-land. In Tagger Pointer it's ok to do all kinds of crazy things to pointers as long as you know what you're doing. For instance you can exploit that dynamically allocated memory on most systems are aligned to 16-bits, 32-bits, 64-bit or even 128-bits borders. What can this be used for? Distinguishing between native integer values and arbitrary-precision integers for instance, or for putting small data structures (e.g., short strings) in the "pointer" rather than having to dynamically allocating a few bytes of memory.

It's actually pretty useful stuff, although -- as the title says -- pretty ugly. That is, the pretty kind of ugly.

Best TED-talk ever

TED is an extremely good place to find interesting (short) talks about various topics. You can literally spend days there watching really high quality presentations ranging from musical performances to science talks. Today, though, I saw something that bets every other TED-talks I've ever seen before.

It was short and witty, it was science and humor, and it was refreshingly different. And best of all, you actually learnt something useful! Stop wasting your time here. Get over there and see it now!

Commodore 64 Live!

Do you remember those old arcade machines where, when no one played them, the "computer" would play the games? Kind of like a demonstration of the game instead showing some fancy graphics. I came across the übergeeky page C64 Longplays a few days ago and I feel that I must do my small part to spread the word through the world.

It's basic like those computer-played arcade machines, with the difference that it's actually someone who plays through the entire game. Didn't you solve the third level of Boulder Dash or did you think no one ever cared to finish Ghostbusters? Everything is on C64 Longplays for you to watch.

I personally liked the video of Yie Ar Kung Fu... some fights was really close... the energy bar was down to the last pixel!

How browsers work

A former colleague sent me this very sweet explanation of how browsers work today. Can you say awww?

Of banks and doorbells

This is an amusing kafkaesque story form real life by Niel Fraser at Google.