Coder Corner

http://www.codercorner.com/Pictures/OpenGLConsideredHarmful.PNG

I’m not the only one with that kind of troubles

http://www.jwz.org/doc/censorzilla.html

Here’s an interesting new paper:

http://graphics.ewha.ac.kr/gSaP/

http://graphics.ewha.ac.kr/gSaP/gSaP.pdf

I’m not sure where they got that though:

“Moreover, [Terdiman 2007] hypothesized that parallelizing the hybrid SaP and subdivision may perform poorly”.

Did I? I just briefly explained how to do it but I don’t think I ever wrote “it may perform poorly”. Or show me where, because I don’t remember. In fact, I didn’t investigate this path well enough to know. But this is interesting and motivating, maybe I will now

“This algorithm may be considered as a parallel version of that proposed by [Terdiman 2007]”.

Hmm, but I already explained the parallel version in that paper, didn’t I? So it’s basically a parallel implementation of an MSAP, which I already detailled in 2007 (and it wasn’t even new at the time). No? Well ok, for GPU.

I should note that I’ve made the “ArraySAP” in that benchmark a bit faster than it used to be (especially insertions can now be 2X faster), but overall it doesn’t change their good results.

Oh, and I’ve used PCA to compute the best axis years ago already, in Z-Collide

SAP in 1999, SAP in 2010… I just can’t escape

Little trivia about empty classes…. Here’s the setup:

Question: what’s the size of Test0? What’s the size of Test1?

It’s a relatively well known fact that embedded empty classes are not actually free, and add 1 byte to the class containing them. So, knowing this, it shouldn’t be a surprise that sizeof(Test0)==2.

A more surprising fact, maybe, is that sizeof(Test1)==1. Yep, not free either, and a different size from Test0. It has to do with an obscure rule saying that the addresses of base classes must be different, or something. Can’t remember. Still, you need to keep this in mind if you don’t want to discover weird “ghost bytes” in your binary-serialized data.

Oh well.

The size of enums is compiler-dependent, and usually you don’t have any control over it. For example let’s have this simple enum for some types:

Then let’s check the size of the enum type:

With MSVC 2008, s = 4. This is clearly a waste of space in this case, since the type could be safely encoded on a single byte. So how do you tell the compiler about this? Well it turns out MSVC allows this nice syntax to control the size of the enum:

And that’s it! Compile with this, and s = 1. This is very useful when trying to save some bytes in a class while retaining the type safety provided by the enum. I think this notation is part of C++0x and will be supported in all compilers at some point. Right now though, it doesn’t seem to work with GCC.

For a portable solution, one probably needs to use templates, maybe something like:

A recent talk with a friend made me realize that the following declspec is not very well known. It’s used to avoid inlining a function (the opposite of what we’re usually looking for, which probably explains why it might have remained obscure for a lot of us).

With VC++:

__declspec(noinline)

With gcc:

__attribute__ ((noinline))

It’s very useful for example with templated arrays, to make sure things like the resize functions are never inlined.

http://www.youtube.com/watch?v=AtM3PGyiQUc

Woah! This reminds me of something…

http://channel9.msdn.com/shows/InsideXbox/Corrinne-Yu-Principal-Engine-Architect-for-Halo-Team-Microsoft-Part-Two/

In Ninja Blade on 360. No ninja coders there… But man, try to beat that score!!

Some time ago I mentioned the ICE kernel and somebody asked me about the source code. Well sorry, I’m not going to release this just yet. It’s not secret or anything, it’s just extremely ugly-looking source code. You have to realize: this is the first part of the engine I wrote, somewhere around 2000. I won’t release this without a serious cleaning / refactoring pass first.

However I can briefly describe what it does. It’s nothing special, really. To be perfectly honest I was just experimenting with random ideas, to see if they would work, etc. I never imagined I would still be using this stuff almost 10 years later. Also, even if I’m still using this at home, it doesn’t mean I would ever want to replicate this in a “real” engine at work, or on a console.

So anyway it all started as a reaction to the vanilla reference counting that we’d been using before, in “Irion“. In that engine we had manual, explicit “IncRef” and “DecRef” calls. You couldn’t delete an object directly (private dtor), instead you DecRef, and if the counter reaches 0 the object deletes itself. Standard stuff. But we had a lot of issues with that, people forgot to call “IncRef” or “DecRef”, unused objects that should have been deleted were found in memory alive and well, or quite simply we got many crashes from dangling pointers. Typical BS.

After the death of Irion I started my engine from scratch at home, and I really didn’t want to end up with the same mess (*). So I was looking for a solution to this, that’s the context. At the time the information about engine architecture on the Internet was scarce, or maybe I didn’t look well enough, in any case I don’t remember finding anything very useful online. So I started to build something, probably more out of boredom and curiosity than necessity.

First of all, it only works for objects inheriting a base class. For historical reasons, this base class is called “Cell” (why this is so is another, completely different story). Cell objects register themselves to the “kernel” in their ctor. They unregister themselves from the kernel in their dtor. The kernel is a singleton, for better or for worse (it was almost 10 years ago, I didn’t care about multiple threads).

Now when you create a “reference”, you still have an explicit function to call: “AddRef”. As the same suggests, it does not increase a simple reference counter (as “IncRef” was doing), it keeps track of the “owning object”, or simply owner, and the “referenced object”, or simply reference. Those couples of (owner, reference) are stored inside the kernel, in something called “reference tracker”.

If there is any intelligence in the system, it might be in the reference tracker. This is a somewhat creative data structure designed to keep track of those pairs efficiently, both in terms of speed and memory. A  (owner, reference) pair is simply a DWORD, made of two 16-bit IDs. The number of objects is limited to 64K, yes. The pairs are simply stored in a contiguous amount of memory, like a vector of DWORDs. Given an input Cell, the structure otherwise provides O(1) access to:

• its number of owners, and the set of owners
• its number of references, and the set of references

So, in a standard system you would get a Cell object and you could only do something like “GetRefCount”. It would return “3″, and you would know that this Cell is referenced by 3 other Cells somewhere. In ICE, you can easily ask for the “ref counter” (= the number of owners), but also who the owners are. That’s the first building block.

The second step is to investigate what happens when you actually delete an object. As we saw before, on deletion a Cell unregisters itself from the Kernel. The Kernel in turns tells the Reference Tracker about this deleted Cell. And since the Reference tracker knows what other Cells are still referencing the deleted one, well, from this point it’s easy to call the owners for notification. That function is called “OnInvalidReference”, IIRC.

So, for example:

• you have a Material, 3DS-MAX style
• it has a Reference to a Diffuse texture
• if you delete the texture (and I mean really, a savage “delete ptr” anywhere), the system calls Material::OnInvalidReference(), with the deleted Cell (the texture) as a parameter. From here, the Material can fix its dangling pointer (at least it was the original idea, but it evolved a lot afterwards)

There are a bunch of technical issues here with circular references and how to implement all this efficiently, but those are details “beyond the scope of the discussion”. The question was about containers, remember? Well it should be obvious what the next part was: of course I made a Cell-based container. Completely customized object, STL-Vector-style, that can hold Cell pointers, nothing else. The benefit, as you already guessed from the previous post and previous paragraph, is that if I ever carelessly delete a Cell object stored anywhere else in one of those containers, the kernel will know, it will call the container’s “OnInvalidReference”, and the container will remove the bad pointer from itself, automatically. Done!

This, unfortunately, was only the beginning of my weird architecture experiments.

Not long after that, I tried to fix the other main pain in the butt that had plagued Irion since the beginning: serialization. Oh man how I hated writing serialization code in Irion. In ICE, I really wanted to have an automatic mechanism to do that for me. IIRC the idea came from the Half-Life SDK: they had this great “offset of” macro that would give the offset of a member within a class. It’s pretty standard and well-known those days, but at the time, and for me, it was a mini revolution. The serialization code in Irion had to be written manually and painfully. Thanks to this single macro, suddenly it was possible to automate a large part of it. I’ll spare you the details as I’m sure you’re all aware of this stuff now, it’s used and over-used for serialization, meta-data, scripting, etc. The point to take home here is that the kernel suddenly knew about Cell classes’ members… and in particular, about other Cell pointers stored within Cell classes. Which opened a whole brand new Pandora’s box.

Remember, I was only toying at home. This was not production stuff. The ICE engine has never been used commercially or anything. No harm done.

Let’s face it: what’s the point of calling “OnInvalidReference” for a given Cell to clean its dangling pointers… if you can do it yourself? “If you want something done correctly, do it yourself”. Right. So that’s basically what I did. Provided you declared members with the correct serialization macros, the kernel does not call objects anymore to tell them to clean an invalid pointer. The kernel cleans the invalid pointer all by itself. It knows where it is! So it just clears it. Zero it. Nullify it.

That’s usually the point where type-safety zealots and other fans of “clean C++” (talk about an oxymoron) give up and start throwing rotten tomatoes at my indecent lack of concern for “proper OO ways”. (But then again, if “Boost” is the “proper” infant of the OO way, I’ll more than gladly remain a non-believing maverick. Boost! What a joke!)

But wait! I’m not done! I still have to tell you how discovering handle-based “weak pointers” changed the picture over again! And how the kernel can “remap” itself and move objects in memory under the hood to reduce fragmentation!

Come back! It’s fun!

Hello …?

(*) I failed