Friday, September 07, 2007

How does COM know?

If you call an a non-blocking method on a COM object that's in a different apartment and you need to receive callbacks, you need to sit in a message pump of some kind. That fact is written in a few different blogs, but what I didn't understand until today is: why does that work? How is COM connected to the message pump?

First let's pull apart that statement with some basics:
  • Single-Threaded Apartment (STA) basically puts boundaries around sets of objects that are similar to the boundaries around a process. When calling between the apartments (sets of COM objects) we use an RPC mechanism instead of a direct function call.
  • There is a 1:1 correspondence between threads and apartments, and a 1:1 correspondence between threads and their message queues. Thus there is an appropriate message queue for each apartment, and posting to that queue will assure which thread gets the message.
  • RPCs are thus implemented by posting messages to the queue of the thread we're trying to reach. We then poll our own message queue until we get some kind of "reply" indicating the RPC has done. This looks like a blocking function call to client code.
In order for this to work, the thread in the apartment we are calling into must itself be waiting on a message queue. This would be the case if it is either (1) really bored and just querying the message queue or (2) it is itself blocked on a method call into another apartment, and is thus polling its queue to find out if its own RPC is done.

If this all seems like insanity to you, well, it is.

Now when I say "non-blocking" method call, what I really mean is: a method call that returns really fast but starts some work to be completed later.

Normally when a thread is blocked because it made an RPC into another apartment, that apartment can call right back because the same polling of the message queue to discover that the RPC is over allows other methods to be called. This simply means that the flow of code between COM objects can ignore STA when all method calls are "blocking".

But as soon as we have a non-blocking call, there is no guarantee that the client code is actually listening for method calls into its apartment. (By the rules of STA, if the thread is doing stuff, no calls CAN happen, because one thread per apartment.)

Typically client code will make the async call, maybe make a few, and then do some kind of blocking until we're done..for example, we might call WaitForMultipleObjects.

In this case the right thing to do is MsgWaitForMultipleObjects (followed by GetMessage/DispatchMessage if we get woken up for a message). This way while our thread is doing nothing, other apartments can call us back.

This works because the thread, message queue, and apartment are all 1:1 relationships. So to say "this thread needs to be open to COM RPCs" all we need to say is "this thread needs to block on its own message queue", which is done with GetMessage.

Friday, July 20, 2007

gl_FragCoord + ATI = World of Hurt

Well we just had a bit of a firedrill when we learned that gl_FragCoord causes some ATI cards on windows to revert to software shading. I don't know if this is fixed in a driver upgrade - we used a simple workaround suggested by a user on gamedev.net:
  • We store the clip-space coordinate in a varying variable. (We have to compute that anyway, it's just the result of ftransform()).
  • We then perform a perspective divide and change the coordinate range in the fragment shader.
Fortunately we wanted the screen coordinate as 0..1 so having clip coordinates is almost what we want anyway. The perspective divide must be per-pixel - varying variables only interpolate in a perspective-correct manner in homogenous clip coordinates, not window coordinates. At least, I think. :-)

This is a case where "the Google" comes in really handy -- having confirmation from other users of a known bug gives us a lot more confidence in the workaround.

Friday, June 15, 2007

list.size() is slow

Ever wonder how the STL list works in GCC?



What? No? You haven't?

Where's your sense of curiousity about the way your code works?

What? You have a life?!? What are you reading this blog for then?

Anyway, it's pretty simple. It's a doubly-linked list, where the node has a previous and next pointer. The head and tail of the list are linked together, and the list itself keeps a pointer to the head node.

This means that begin() and end() are fast.

Unfortunately, the list doesn't keep a size counter. This means that size() is O(n). So you can find the back of the list easily but getting its index is expensive.

That's probably fine, as turning the index back into an iterator is O(n) and the iterators are stable. By comparison though, CodeWarrior's list caches the number of items.

Moral of the story: empty() is more efficient than size()==0, and, um, know what's in your STL.

(Insert rant about STL being like sausage here...)

Thursday, June 14, 2007

Virtual Memory Dumping for Fun and Profit

We're trying to answer the question: why did X-Plane run out of memory? To answer that, we need to look at the contents of virtual memory. Now dumping virtual memory isn't so bad.

On Windows you call VirtualQuery with a base address. Start at 0 and increment by the returned RegionSize. When you get to dwTotalVirtual (as returned by GlobalMemoryStatus) that's a good time to stop.

On the Mac call vm_region, starting at 0 and incrementing by "size" until it returns an error code. One tricky thing: vm_region will skip over unused virtual memory. To "see" these holes (this is address space that can be used later) compare the address you pass in to the one that's returned. If you pass in a pointer that's in an unused region, the address will be advanced to the next region.

What if you want to show the DLLs/dylibs that are mapped into a given region? I make no promise for the performance of this method but...

On Windows, use GetMappedFileName. Pass in your process handle and a base address from VirtualQuery and it fills in a buffer with a DLL name if possible. This is in psapi.dll so it isn't available on non-NT-derived Windows.

On Mac, use dladdr, passing in the base address of the region. You'll get a dylib file path and a symbol name, although the symbol name tends to be junk.

Enum tags - C vs C++

So you're minding your own business when you come across a gem like this:
typedef enum __MIDL___MIDL_itf_qnetwork_0082_0001 {
AM_EXSEEK_CANSEEK = 1,
AM_EXSEEK_CANSCAN = 2
} AMExtendedSeekingCapabilities;

It doesn't take much to bring out the inherent beauty of C...it rolls off the tongue like the name of a fine perfume. Anyway, this is legal in both C and C++, but the rules are a little bit different.

First of all, this is a typedef statement. __MIDL___MIDL_itf_qnetwork_0082_0001 is the enum tag and AMExtendedSeekingCapabilities is the defined type. (I know, those aren't the real C++ spec names...)

A few things are clear:
  • In C or C++ we can assign the enumerated values (AM_EXSEEK_CANSEEK, AM_EXSEEK_CANSCAN) to an integral type, and we'll get the values 1 and 2.
  • I have no idea how big one of these enums is...check your local compiler settings. It may be that this enum only takes up 8 bits or it may have been allocated a full 32 bits. (We use ints for our enums in the X-Plane SDK to be sure how big they are. We lose type safety but see below.)
Now here's where things get fun. C is picky: it requires the "enum" keyword when using the tag but not when using the typedef. In other words:
typedef enum tag { a, b } def;

enum tag var1; // legal - enum keyword and tag go together.
tag var2; // illegal - tag requires the enum keyword.
enum def var3; // illegal - enum keyword cannot be used with a typedef.
def var4; // legal - typedef is usable on its own.

By comparison, all 4 of those statements will compile correctly in C++. You can see C++ code like this:
enum letters {
a, b, c, d
};
letters my_var = a;

This won't work in C++.

But C++ is more strict than C when it comes to typing. Given our above example, we can do this in C:
def my_var = 5; // Illegal in C++
In C++ you'll get an error -- you can assign an int to an enum but not vise versa.

Tuesday, June 12, 2007

Dyamic Cast is Slow but...

...stupid code is slower.

In a performance tuning situation, sometimes you have to figure out:
  • Is the problem that I'm not doing each operation fast enough or...
  • Is the problem that I'm simply doing too many operations?
(Of course, the answer can be both.) This is particularly tricky because...if an operation is slow, that can help you realize that you're doing too many of them. If you then cut the number of operations, who cares if it's slow? And if it's not slow, is there any harm in doing too many operations?

(Typically I will leave the operation slow while I cut down the number of operations, because having slow primitives makes it easy to observe the effects of improving algorithm time in a profiler. Then once I fix the algorithm, I tune the operation itself, possibly even temporarily disabling the algorithm improvement to make it easier to "see" what's going on when profiling.)

For WED (the X-Plane scenry tool) I decided to "code first, tune later" -- given that
the design could change a lot while in progress, it seemed best to not spend a lot of
time on code that might get thrown out. I knew that the fundamental design (a group of airports, each spatially far apart) could easily be tuned to prevent major O(n) parts just using indexing and culling.

The resulting unoptimized code was, well, simply awful. What really surprised me was how much time was being spent in dynamic_cast - pretty close to all of it.

The solution was mostly to fix stupid code, but in some cases to not use dynamic_cast.
  • The biggest single problem was a lack of caching. If we have tree structure, the intermediate nodes can't ask the leaf nodes for information on every function call - the result makse time complexity worse, not better!
  • When dealing with a large dataset, pass counts matter. For example, avoiding iterating on the hierarchy of airports when drawing a layer that doesn't care was a big win - it takes a long time just to visit all of that data.
Like many programs, WED has the problem of needing virtual functions along two axes - we want to specialize the combinations of various data-model types with various UI constructs. (Runway for the selection tool, taxiway for the selection too, runway for the vertex tool, taxiway for the vertex tool.)

I'm not a big fan of visitor, so my original design simply used dynamic cast within the specific UI construct to figure out which datamodel construct it had. It turns out the performance problem with this isn't that we're double-dispatching, but only how we do it, and for a large number of objects, dynamic_cast is simply too expensive. Providing a virtual function to get some kind of "type info" on the generic object is much faster.

So if there's any lesson on dynamic_cast here, I think it's just "dynamic_cast does some serious work" ... don't use it unless you really have to, and don't use it inside a hot loop, or where N is large.

Monday, June 11, 2007

Cause and Effect

I have a tree-view (think like the tree of files in an Explorer or a Finder window). Since all of my rows are based on objects with integer IDs, I have something like this:

map mOpen;

bool Is_Open(int id)
{
map::iterator i = mOpen.find(id);
return (i = mOpen.end() ? true : i->second;
}


Note that if we don't have an ID in the map, we pretend its value is true. This "defaults" the hierarchy to open whenever we come upon a new ID - similarly "clearing" the map opens everybody.

So then I write this clever toggle routine:

void Toggle_Open(int id)
{
mOpen[id] = !Is_Open(id);
}


And it doesn't work. Why not? Well, it turns out that the l-value mOpen[id] is evaluated before the right-side expression. Thus we have already called mOpen[id] before we ever call Is_Open.

Here's the subtle bug: calling the array operator on a map creates a default entry (by the default ctor of the value type) if there is no entry for the key. So mOpen[id] on an id that isn't present in the map inserts a default 0 into the map.

Now Is_Open was modified to return "true" for unknown IDs, but this code is making the ID known and false.

The result was: the first time the user clicks on an open triangle, it stays open. This is because it is being set to closed by map::operator[] and then opened.

The correct code is

void Toggle_Open(int id)
{
bool old = Is_Open(id);
mOpen[id] = !old;
}


This forces the current open state to be evaluated before the array operator can make a default entry.

To quote from chapter 5 of the C++ spec:

"Except where noted, the order of evaluation of operands of individual operators and subexpressions of individual expressions and the order in which the side effects take place, is unspecified."


I knew the specification was good for something. :-)