Intrinsic Linked Lists for Static Construction

This is another excuse to make sure the blogger move to beta hasn't killed all m blogs. In the past I ranted about not being able to move to blogger beta (this blog moved, the others did not). Now I am happily united entirely on the beta blogger...web bliss is mine. (It would be nice if
the old posts listed the correct authors, but that's what we get for flirting with WordPress.)

A while ago I wrote a lot trying to explain how the hell global static construction works in C++.
The best simple summary I can give you is:

• It doesn't do what you think.
• Your code will explode in ways you didn't expect.

I also tried to explain the joys of intrinsic linked lists, that is structs that contain a next pointer. (Don't pass these up for the STL - sometimes the old-school technique works better, especially when the issue isn't O(n) but how good your implementation is. Are you sure your app isn't bottlenecked by memory allocation?)

Like peanut and chocolate, these two ideas go well together. That is...static construction problems can be fixed by using intrinsic linked lists. This code is guaranteed to make your life hell:

class foo {
static set all_of_me;
foo() { all_of_me.insert(this); }
~foo() { all_of_me.erase(this); }
// more tuff
};

The idea is that the foo class self-tracks all its members...this is all good until you do this in some other CPP file besides the CPP where all_of_me is defined.

static foo this_static_var_will_kill_me;

First the solution, then why it works. The solution is simply this:
class foo {
static foo * first_of_me;
foo * next;
foo() { this->next = first_of_me; first_of_me = this; }
// more stuff
};

Now foo uses an intrinsic linked list instead of an STL set and we can declare static global foo objects all the time!

Analysis:

• The problem with static construction is that C++ doesn't guarantee that static global objects will be initialized in any particular order.
• When a class has a static member variable that is in turn a complex class, that static member variable is effectively a static global object, and thus it will be constructed in no particular order.*
• In the case of our "foo" example, if the particular foo object is constructed before the set "all_of_me" is constructed, then foo's constructor will try to stick "this" into a set whose contents are probably entirely zero.
• If that doesn't crash then when the set is constructed (after the foo object) the set will be fully reinitialized, causing our object to be lost.

(For this reason we hope for the crash - unfortunately some STL containers like vector will often fail quietly when they are used before initialization, as long as they're zero'd out first.)

The beauty of intrinsic lists is: C++ guarantees it will do all of the static initialization (that is, zero-setting, etc.) before any functions or methods are called. So we can be sure our list head pointer is NULL, and that's all we need to get started.

One final note - as I define catagories for this post I see Chris has catagories for both "rants" and "IIS". I can't imagine that you'd ever want IIS without the rant tag.

* Okay, so there are some rules on construction order. Trust me, they won't help you do anything productive!

Returning an Array in C - the Least of 3 Evils

In C++ you can write things like this:

void get_some_strings(vector& out_strings)
{
out_strings.clear();
for (some loop)
out_strings.push_back(whatever);
}

Easy! How do we do this if our API has to be pure C? Well, there are three options.

First you could always allow the function to allocate memory that's deallocated by the caller. I don't like this option at all. To me, it's a walking memory-leak waiting to happen. You'll have to check for memory leaks every time you use the function and there are no compile-time mechanisms to encourage good programming technique.

A second option is to pass in some preallocated buffers. Hrm - I think I tried that once. Unfortunately as you can read here, the technique is very error prone and it took Sandy (the better half of the SDK) to clean up the mess I made.

The third option, and least evil IMO is to use a callback. Now we have something like this:

void get_some_strings(void (* cb)(const char * str, void * ref), void * ref)
{
for (some stuff)
cb(some string, ref);
}

If you can tollerate the C function callbacks (have a few Martinis - they'll look less strange) this actually provides a very simple implementation, which means less risk of memory-management bugs.

On the client side if you're using this library from C++ you can even turn this back into the vector code you wanted originally like this:

void vector_cb(const char * str, void * ref)
{
vector * v = (vector*)ref;
v->push_back(str);
}

Now I can use this one callback everywhere like this:

vector my_results;
get_some_stuff(vector_cb,&my_results);

What I like about the callback solution is that both the client code and implementation code can be written in a simple and consise manner, which translates into solid code.

Surprise - pthread_cond_timedwait takes an absolute time!

Whoever reads the man pages anyway? Turns out pthread_cond_timedwait takes an absolute time! In otherwords, if you want it to sleep for 1 second, you have to pass one second more than the current time, as returned by gettimeofday (yuck) and converted from a timeval to a timespec (double yuck).

As much as I gripe about this because most threading APIs take relative timeouts (as does select), there actually is a use for this.

When writing a thread-safe message queue you might write something like this to read the queue:

lock critical section.
increment waiting thread count.
while(we don't have a message)
 if(pthread_cond_timedwait(condition var, timeout)==ETIMEOUT)
    decrement thread count, unlock, return "timed out"
decrement waiting thread count
read message out of queue
unlock critical section

Now...you might wonder, why do we need a while loop? The answer is: it's possible that between the time that our thread is woken up (vai the condition variable wait) due to a message being queued and the time we actually run, get the lock, and continue execution, another thread could have come along and stolen our message. (Note that another thread can go through this code without ever calling pthread_cond_timedwait if there is already a message, which is good for performance. This is not a FIFO message queue!) Thus we have to while-loop around until we reach a point where we've woken up, acquired the lock, and the message is still there. Once we have that lock, the message isn't going anywhere and we can safely exit the loop.

This is where the absolute time is handy - we might go around the loop 6 times. But the "deadline" - the time after which there's no point in waiting, we should return to the user, is an absolute time, and can be invariant across the loop. Thus there is no need to measure how much time has gone by on each loop and decrement our wait time.

OpenGL Fogging Artifacts

Here's a video of a very very low visibility approach in X-Plane. Note how the "fog" (that is, the mixing of the runway and ground to gray) pulses in and out as we fly, and they don't do it at the same time. What's going on here?



What you're seeing is a defect in the fixed-function pipeline. The problem is two-fold:

1. OpenGL implementations are allowed to calculate fog colors at vertices and do a simple interpolation between the vertices.
2. The vertices that we interpolate between are not necessarily the corners of your triangle; they could be the vertices that OpenGL adds when it clips your triangle to the view frustum.
   

So we have two sets of artifacts at once. First consider the case of the ground and runways. Since the fogging "interval" (the distance between fog = 0% and fog = 100%) is quite small here, the same amount of fog is spread along the entirity of a runway triangle (about 50 meters deep) and a ground mesh triangle (at least 90 meters deep, but possibly up to 1 km deep). That means that we go from visible to fog much faster over the runway than over the ground.

As we fly, the actual size of the mesh triangles is changing, as part of each mesh triangle scrolls off screen. This in turn affects the gradient of how fast we fog and what the corner fog colors are.

The results are, well, that video: fog doens't match between the runways and the ground, and the particular strange results vary as we fly.

The solution is, like all things in life, to replace the fixed-function pipeline with a pixel shader. The pixel shader can then use a per-fragment value (like the depth value) to fog. This is more expensive (well, probably not really...we have the depth value around and it's the same number of DSP ops) but will produce consistent fog across the entire area.

VBOs, PBOs and FBOs

(The great is the enemy of the good - in preparing my 10-part series on why iostreams totally suck, I've been putting off blogging anything else.)

Apple has posted two very nice bits of sample code demonstrating PBOs and FBOs. Even though these are Mac-specific, as sample code they're good on any platoform because PBOs and FBOs are OpenGL extensions, not windowing system extensions.

So what are all these objects? Here's the situation:

Vertex Buffer Arrays (VBOs)

The VBO is the greatest thing to come to OpenGL since sliced bread. Basically it's a memory buffer containing geometry data that is managed by the driver. You can either tell OpenGL to copy data into the buffer, or temporarily memory map it and write to it. VBOs abstract as an "alternate memory space" - that is you tell OpenGL to read out of the VBO rather than your process's virtuall address space. (In practice the VBO may be in your process's address space too but this is hidden from your app.)

VBOs rule because:

• They allow OpenGL to act asynchronously. When you call client arrays, the driver has to copy all of your data immediately before the function returns. Because OpenGL owns the memory in a VBO it can schedule the VBO to be read later and be sure it won't be tampered with. (After all, the only way to "edit" the VBO is via OpenGL.)
• VBOs can be in VRAM or at least placed in memory that's easy for the card to get at. This means potentially much faster drawing.

It's important to note that VBOs as objects are unformatted...that is they are just a big chunk of bytes. OpenGL doesn't know or care whether they contain float data, what the ordering is, etc. until the instant you say "draw". (In fact it is an absurd example, but you could draw the same VBO using the data with multiple interpretations.)

PBOs (Pixel Buffer Objects):

The PBO extension doesn't really make a new kind of OpenGL object. It just says "we can use Buffer Objects for pixel operations, not just geometry operations." Normally a VBO can only be used to provide the data to something like glDrawArrays, that is, as vertex data. PBOs says you can also use a VBO as the memory buffer for glReadPixels (copy from framebuffer to memory) and glDrawPixels (copy from memory to framebuffer), glTexImage2d (copy from memory to a texture) and glGetTexImage (texture to memory).

There are some interesting applications for this (if the driver is clever):

• Read-pixels can be very slow because we have to finish drawing before we can read the memory. Since the memory in a PBO is owned by the driver and isn't accessed by the application without OpenGL's knowledge, a read-pixels from the framebuffer to a PBO can be asynchronous; the driver will schedule it for once drawing is done. (But see comments on timing below.) This is an important case when OpenGL's output will go to something other than the screen, like making a movie file.
  
• Texture upload can be slow; a PBO allows this to happen asynchronously, which could allow for some kind of fast threaded texture setup. This could also allow for more efficient processing when textures are changed every frame (e.g. playing a video file in an OpenGL scene).
  
• The case that Apple shows in their demo: PBOs and VBOs are not different OpenGL objects - they're using "buffer objects" (that is, untyped blocks of memory) for pixel or vertex data. So you can draw something to the screen, read it (using glReadPixels) into a PBO and then draw it (using glClientArrays) as a VBO. Since the buffer is never touched directly by the application, this "use an image as vertices" trick happens 100% on the graphics card and can be very fast, with no trips over the graphics bus.

One thing to note, however, is that a PBO is not a texture; you must copy from the PBO to a texture before you can draw with it. These are accelerated copies, but they are still copies.

Buffer Objects and Timing

Buffer objects can be used asynchronously until your application tries to use them. When you map them or try to read their data, OpenGL will have to block your thread until the execution of OpenGL commands has caught up. So in order to enjoy the benefits of asynchronous processing, you need to do "some other stuff" between a call to glReadPixels and a call to glGetBufferSubData or glMapBuffer.

(This is very similar to occlusion queries, where if you ask OpenGL how many pixels were drawn right after you draw them, you'll block until the pixels are really drawn. It's always best to assume OpenGL is lagging behind you. To get around this, X-Plane always asks about the number of pixels from the last frame before counting the number in this frame. This gives OpenGL an entire frame's worth of time to do the counting...by that point we can be sure the drawing has been done.)

FBOs (Framebuffer Objects) and, um, Renderbuffer Objects

Framebuffer objects represent places you can draw to other than the screen. This is the extension we've all been waiting for: with framebuffer objects you can draw directly into a texture.

An FBO is actually distinct from a texture - it represents all of the images you draw into at once. (Remember that when we draw we usually have an RGBA image buffer and a 32-bit depth buffer that is separate, and maybe other buffers too.) So the FBO lets us draw into an RGBA texture and a DEPTH-type texture at the same time, or even mix and match.

The FBO extension also lets us create buffers that are not textures for off-screen rendering.

FBOs represent one of the nicest ways to draw into a texture because they're simple and require no copying from the framebuffer to the texture. The FBO extension also has some functions to handle mipmap generation, so you can draw once and let OpenGL build the mipmap pyramid.

In some ways FBOs make PBOs obsolete: the most modern cards allow vertex shaders to read textures. This means that you can use a texture as geometry data directly. And with FBOs we can draw right to a texture. So rather than the old way (draw to the screen, read to a PBO, use it as a VBO, which involves one copy) we can avoid the copy (draw to a texture, then draw again using that texture for vertex data).

On the other hand I'm not sure that FBOs will replace PBOs that fast; PBOs are an older extension and thus more available, and vertex-shader-based texture reading is only available in 7th generation cards (6th for nVidia). So using FBOs avoids a copy but cuts out a whole set of graphics cards, including the very capable 9700-type cards from ATI (we see a lot of these in-field). It seems that a driver could do a reasonable implementation of PBOs even on older hardware, and with the wide to-computer bandwidth of PCIe even a bus transfer isn't the killer it used to be.

One last musing: I don't know how good the performance of texture-based vertex processing will be vs. streaming a VBO. With X-Plane we do occaisionally see a bottleneck trying to read texture memory...that is, the card can't get pixels from its own high-speed memory to its own high-speed shaders via its own high-speed bus fast enough. This is pretty amazing on its own because the memory controllers on a graphics card are extraordinarily fast. But the combination of high anisotropic filtering and full-screen anti-aliasing (combined with a healthy dose of overdraw by poorly behaved applications :-) can really stretch texture bandwidth. So I don't know whether using texture memory for vertex information will cause a further bottleneck.

(One guess is that for cards that can read from texture memory to vertex shaders, they're very new and have DDR3 memory, so texture memory is so fast that PCIe16x bandwidth isn't that important.)

Triple-Boot Mac (and MBR hell)

It only took about 8 hours of total time, but my MacBook Pro can now triple-boot into OS X 10.4.7, Windows XP Home SP2, and Ubuntu Linux (6.06 I think).

The install is actually not that bad once you've been through it once...the process is basically:

• Use diskutil to dynamically build two new partitions. The Mac comes with one "EFI" partition for boot control and one HFS+ partition. MBR gives you four max, so you build a Linux one followed by a FAT 32 one.
• Install Windows XP. Tedious and annoying but not complicated. Windows takes longer to boot from CD than an entire OS X install from scratch.
• Install Linux. This is the slightly dangerous part, as I found out.

So two things took a long time:

First, for some reason my brand new, genuine Windows XP CD-ROM doesn't work very well. Setup had at least two hangs, a failure to init a disk, a BSOD, and an assertion failure. Maybe all of those holograms on the disk play havoc with the optical drive? So the biggest single item was a 5 hour Windows install that mostly involved trying to boot setup over and over.

Windows XP asks questions during the install, so you have to sit there and watch it. Furthermore, if you are using rEFIt like I am, then you'll have to manually select Windows each time the installer reboots itself. The installer normally expects to reincarnate itself, so if your machine mysteriously reboots without warning be sure to keep reselecting to boot from the Windows install CD-ROM.

The other problem was that, almost certainly due to my own sleepiness this morning, I managed to splat LILO onto the boot block of the Windows partitiont. Ooops. Most tutorials online state that the only fix for this is a complete reinstall of both Windows and Linux, but fortunately I discovered this is not true.

It turns out that you can very gently run fixmbr on your Windows partition without disturbing triple-boot goodness. It's pretty much that simple...just launch the windows setup CD, wait 30 minutes for it to load every driver ever written, launch the recovery tool and use fixmbr on the appropriate drive. Linux and Mac continue to boot via rEFIt.

Now the only issue is: Windows can't understand Mac or Linux partitions, Linux can't understand Mac partitions, and while the Mac will figure anything out, it's not automounting.

Remote Debugging with WinDBG

This is not really a tutorial but rather a quick summary of how to do this so I can find this information quickly in the future:

On the "debugging server" (the PC with the problem)

1. Start WinDBG
2. Type .server npipe:pipe=pipename

On the "debugging client" (the one you're sitting at)

1. Start WinDBG
2. Go to File>Connect to Remote Session
3. For Connection String enter npipe:server=Server, pipe=PipeName [,password=Password] where Server is the hostname/IP and PipeName is the name that the server chose. The password section is optional.