Coder Corner

I found a link in Charles Bloom’s rants, about “intro sort”. The author claims it is faster than STL’s version. Long story short: it is.

Once in a while I get doubts about how fast a radix sort is, compared to a vanilla STL sort, so I ran the good old tests again. Any news? Nope, radix is still faster in cases that interest me.

While I was at it, I quickly put together a “multithreaded radix sort” where half the list of items is sorted in a different thread, and then there’s an extra pass to merge the results. Result: faster than the single thread version on my dual core - at list for large amounts of elements to sort. Cool

Below are the results when sorting various numbers of floats.

• Radix: single thread radix sort, 3 passes
• Radix MT: multi thread version
• IntroSort: sort whose source code was given in the link above
• std::sort: your vanilla STL sort

See for yourself. The source code is here.

Quite often you can amortize the cost of two pieces of code in different parts of the engine by merging them together, reusing the results from one part in another part. For example, say you have:

• a character controller (CCT) moving your characters in the world
• old style projected shadows below your characters
• a portal engine using a downward raycast per character to find in what region they are
• a sound module using a downward raycast per character to find what footstep sound to play

It’s rather obvious but you can easily optimize away the 3 last parts. The CCT module already knows what triangles each character is touching. If you set it up correctly, those triangles can be the same as the ones you want to render your projected shadows on. And the same triangles already tell you in what region you are, what material you’re touching, and what sound is associated with them.

It may sound obvious but it’s not always done…

Well. I still have viruses here. The Globat guys don’t bother answering anymore. I’ll drop those clowns ASAP.