oolib gets notifications

Apple's Cocoa API has an interesting feature named the Notification Center. It enables UI components to communicate by posting messages to whomever is interested. I suppose it's a bit like Twitter in the insides of a computer program; objects may blurt out messages regardless of who is listening, and objects may show interest in receiving messages from other objects.

Notifications allow for loose coupling between objects. Suppose you have two classes A and B, and you want to make a state change in an instance of class A known to an instance of class B. The traditional way of doing that is to have A call a method in B. Now, A depends on B, and they are tightly coupled.
With notifications, the situation changes. A announces its state change to the world. B listens to state change messages, so it picks up the state change. There is no interdependency between the two, they are just handling messages. You can add a third class C that reacts to the message in another way, without touching class A.

This is particularly useful for GUI widgets; for example, a button announces it's been pressed, a scroll bar announces it's been moved, and a movie player announces it's finished playing.

For oolib, my personal C++ framework, I wanted to have this functionality too. It basically works like this: an object may register itself as an observer of certain messages. Whenever that message is sent, the observer will be notified.

class MyObserver : public Observer {
public:
    void notify(const char *event) {
        print("observer: %s", event);
    }
};

const char *Event1 = "This is event #1";
const char *Event2 = "This is event #2";

int main(int argc, char *argv[]) {
    MyObserver o;
    add_observer(o, Event1);
    add_observer(o, Event2);

    notify(Event1);
    notify(Event2);
    return 0;
}

The global notify() function will see to it that observer->notify() will be called for all registered observers.

There is one big difference between oolib's notify() and Cocoa's NSNotificationCenter: Cocoa works with Objective-C, and allows you to supply a selector—which is a function pointer, so it's essentially a callback mechanism.
With oolib, you are required to inherit from Observer and implement the virtual method notify(), which is more like ‘the C++ way’ of doing things.

Finally, I should mention the Qt framework. Qt has a feature called slots and signals, which allows you to connect a slot (class method) to a signal, which can be emitted by some object. It looks like Qt works by virtue of pointers to methods... which is peculiar because C++ does not deal well with pointers to methods. The Qt folks actually use a meta-compiler that generates the code needed to make it work.

This programming trick is also known as the observer pattern.

Starry, starry night

The holidays are nearing, and it always makes me ponder the universe. Maybe it's because the stars come out in the cold and clear dark winter evenings, or maybe it's because of the unusually bright star in the Christmas story. Anyway, it gave me the idea of creating something like a classic 3D star field. What if you used actual star positions for this star field, and would you see something like you do on Star Trek if you flew through it at warp speed?

I started out by searching for star catalogs. These are plain text databases with lots and lots of scientific data about the stars.
Star databases are a bit of an annoyance; each has its own format, and they all contain different fields. Some contain parallax data (which is needed for calculating the distance of stars), but most don't. Some contain the visible color of stars, others don't. But most annoying of all, they don't use the same unique identifiers; star Procyon A is named HIP-37279 in the Hipparcos catalog, HD 61421 in the Henry Draper catalog, Gliese 280 in the Gliese catalog, while it's Bayer Flamsteed designation is 10 Alpha Canis Minoris.
The Tycho-2 star catalog contains over 2.5 million stars, but unfortunately it is worthless for making a 3D model because it lacks parallax data. So I took the HYG database, which is a modified version of the Hipparcos database, and combined it with usable data from the SKY2000 star catalog, plus a short list of well-known brightest stars. This involved some awk and Python scripting to cross reference the databases and calculate the 3D positions.

Star positions are usually given in right ascension (RA) and declination (Dec). These are angles, like latitude and longitude, but are often described in hours, minutes, and seconds. Given the angles and the parallax, you can calculate an x,y,z position in space, and this is what we need for a 3D star field. These coordinates have the earth at its origin. You might want to use galactic coordinates instead, which puts the Sun at the origin.
Now, because all of this stuff is turning, turning in outer space, the positions of stars change (unlike what I was told as a child). Star databases contain the position at a point in time (referred to as the epoch) and you can adjust the position using the proper motion of stars. Frankly, I didn't bother, but if you want to know the correct position of a star as it is today, you are going to have to do some extra math.

The constellation Orion

At a distance of 4 kpc

So, I put all coordinates into OpenGL and the result is pretty neat. In the left image you can clearly see Orion. The red star in the top-left of Orion is Betelgeuse. All the way to the left from Betelgeuse is Procyon. The image on the right shows what you see from a distance of 4 kiloparsecs. It's like a bubble with a disc through the center. This is just what the data set looks like though; in reality, it probably does not have this shape as we are part of a much, much larger Milky Way.

This is what almost 220 thousand stars look like on a computer screen, and you can look around and point at stars in real-time.

Fun facts:

• The furthest bright star, just outside the bubble, is Deneb at 4754.8 light years.
• Most stars around us are red dwarfs. Hence the pinkish color of the bubble.
• When you travel to another star, the night sky looks different.
• OpenGL vertex buffer objects (VBO) kick ass.

I was amazed that my (now three years old) computer had no problems whatsoever in dealing with this data. Once again, I find that the modern PC is an amazingly powerful computer. Although I'm no scientist and no astronomer, it enabled me to put together a pretty realistic 3D model of our stellar neighborhood in my attic.

A Pool Allocator or The (un)importance of Code Optimization

In school I learned to use dynamic memory allocation, and to use linked lists to keep track of dynamically allocated objects. The idea was that arrays are static and fixed-size, while linked lists can virtually limitless continue to grow dynamically. The linked list also doesn't use memory that it doesn't need, and there are some nice performance characteristics when inserting and removing items from a linked list.

The malloc() library function takes memory from the heap, which is a region of memory. Whenever malloc() runs out of heap space, it will call sbrk() to grow the heap by asking the operating system kernel for extra memory pages. Modern operating systems actually use mmap() instead, which works by virtue of virtual memory and demand paging. It's all pretty sophisticated.

How different were things for classic arcade game machines, tiny computers with very small system memory. There was practically no operating system at all, it was just the game code itself running on the bare metal. Arcade games like Space Invaders and Galaga did not have the luxury of a malloc() library function. They were not even written in C, but in the machine's assembly language. The way to allocate monsters and bullets was to use an array in the bss segment—an area of system RAM memory sitting just outside where the program code was loaded, or rather, copied from eeprom to RAM when the machine was switched on.

Things were so much simpler then, but even today I like allocating monsters and bullets from a ‘free’ list backed by a statically allocated array. Such a pool allocator gives a very clear picture of what is going on and how things work.

Even though the pool allocator has a hard maximum on how many objects may be allocated, it will never deny you memory if you stay within that limit. No other task in a multitasking operating system can steal this memory away from you, making it a very robust memory allocator.
In terms of performance, the pool allocator always completes in a fixed time, which is important for games that need constant performance.

Discussions about memory usage and performance are becoming pointless in this day and age, when we have massive amounts of memory and CPU power at our disposal even on mobile devices. As computers before were frustratingly slow machines, you had to push the limits to get the most out of it. Writing efficient code was the challenge, and every time you managed to squeeze out a few cycles more it was an achievement well earned.

Nowadays this hardly applies anymore. Although I have to say, lately I had some scripting code for doing large data processing. I rewrote it in C++ with multi-threading, and boy, did that make a difference in run time.

File wrapper class in C++ (2)

Last time I showed how to implement a File class. In the solution Brian (pictured on the right) and me used a second class as a wrapper around a standard FILE pointer. The two classes worked together by means of a shared_ptr. The shared_ptr ensured that the file would not be closed until there were no more references to the file wrapper object. Reread the last post to see what I'm talking about.

A reader of this blog pointed out that there is another solution, one that turns out far more idiomatic. The constructor of shared_ptr accepts an instance of a functor, named a Deleter. This functor will be called when the reference count drops to zero, and the object will be destructed. The resulting code looks like this:

#include <cstdio>
#include <tr1/memory>

class File {
public:

    // conversion constructor
    File(FILE *f) : stream_(std::tr1::shared_ptr<FILE>(f,
        FileDeleter() )) { }

    // copy constructor copies the shared_ptr
    File(const File& f) : stream_(f.stream_) { }

private:
    std::tr1::shared_ptr<FILE> stream_;

    // local functor closes the FILE upon destruction   
    class FileDeleter {
    public:
        void operator()(FILE *f) const {
            if (f != NULL)
                std::fclose(f);
        }
    };
};

Right here I inlined the FileDeleter class. You may also choose to put it outside the enclosing class, or it can even be implemented as a struct with operator()().

All in all, this solution is more elegant and more idiomatic than the previous one.