Erik McClure

So I’m rewriting my 2D culling kd-tree for my graphics engine, and a strange bug pops up. On release mode, one of the images vanished. Since it didn’t happen in debug mode, it was already a heisenbug. A heisenbug is defined as a bug that vanishes when you try to find it. It took me almost a day to trace the bug to the rebalance function. At first I thought the image had simply been removed from a node accidentally, but this wasn’t the case. It took another day to finally figure out that the numimages variable was getting set to 0, thus causing the node to think it was empty and resulted in it deleting itself and removing itself from the tree (which caused all sorts of other problems).

Unfortunately, I could not verify the tree. Any attempt that so much as touched the tree’s memory would wipe out the bug, or so I thought. Then I tried adding the verification function into an if statement that would only activate if the bug appeared - it did not. The act of adding a line of code that was never executed actually caused the bug to vanish.

I was absolutely stunned. This was completely insane. Following the advice of a friend, I was forced to assume the compiler somehow screwed something up, so I randomly disabled various optimizations in release mode. It turned out that disabling the Omit Frame Pointers optimization removed the bug. I didn’t actually know what frame pointers were, only that I had turned on this optimization in many other projects for the hell of it and it had never caused any problems (no optimizations ever should, for that matter). What I discovered was astonishing. Frame pointers couldn’t be omitted from a function if it got too complicated or needed to unwind the stack due to a possible exception. On a hunch, instead of adding the verification function to the chunk of code that was only executed if the error occurred, I instead added a vestigial 'throw "derp";' line.

The problem vanished.

I knew instantly that either the problem was caused by the omission of frame pointers, which would indicate a bug in the VC++ 2010 compiler (unlikely), or when the frame pointers were included, it masked the bug (much more likely). But I also had another piece of knowledge at my disposal - exactly how I could modify the function without masking the bug. I considered decompiling the function and forcing VC++ to use the flawed assembly, but that didn’t allow me to modify the assembly in any meaningful way. A bit more experimentation revealed that any access of the root node, or for that matter, the 'this' pointer itself (unless it was for calling a function) caused the inclusion of the frame pointer. I realized that a global variable would be exempt from this, and that I might be able to get by this limitation by assigning the address of whatever variable I needed to the global variable and passing that into the function instead.

This approach, however, failed. In fact most attempts to get around the frame pointer inclusion failed. I did, however, notice what appeared to be a separate bug in another part of the tree. A short investigation later revealed an unrelated bug in the tree caused by the solve function. However, what was causing this bug (duplicated parentC pointers) still threw up errors after solving the first bug, indicating that it was possible this mysterious insane compiler induced bug was just a symptom of a deeper one that would be easier to detect. After more hunting, a second unrelated bug was found. Clearly this tree was not nearly as stable as I had thought it was.

A third bug was eventually found, and I discovered the root cause of this bug to be an #NaN float value in the tree. This should never ever, ever happen, because it destabilizes the tree, but sure enough, I finally found the cause.

Casting from a float* that was previous cast from a float[4] causes read errors at totally random times, despite this being completely valid under the circumstances. My only guess is that the compiler somehow interpreted this cast as undefined behavior and went crazy. I will never know. All I know is that I should never, ever, ever, ever, ever cast to that data type ever again, because guess what? After removing all my debug equipement and putting the cast back in, I was able to reliable reproduce the bug that started this whole mess, and removing the cast made the bug vanish.

This entire week long trek through hell was because the compiler fucked up on a goddamn variable cast. It wasn’t a memory leak, it wasn’t a buffer overrun, it was just a goddamn miscast variable.

Lesson: Re-validate every inch of your data structure the instant you realize you have a heisenbug, and make sure your validation function properly checks for all things that can screw things up.

While reconstructing my threaded Red-Black tree data structure, I naturally assumed that due to invalid branch predictions costing significant amounts of performance, by eliminating branching in low-level data structures, one can significant enhance the performance of your application. I did some profiling and was stunned to discover that my new, optimized Red Black tree was… SLOWER then the old one! This can’t be right, I eliminated several branches and streamlined the whole thing, how can it be SLOWER?! I tested again, and again, and again, but the results were clear - even with fluctuations of up to 5% in the results, the average speed for my new tree was roughly 7.5% larger then my old one (the following numbers are the average of 5 tests).

Old: 626699 ticks New: 674000 ticks

//Old
c = C(key, y->_key);
if(c==0) return y;
if(c<0) y=y->_left;
else y=y->_right;

//New
if(!(c=C(key,y->_key)))
return y;
else
y=y->_children[(++c)>>1];

Now, those of you familiar with CPU branching and other low-level optimizations might point out that the compiler may have optimized the old code path more effectively, leaving the new code path with extra instructions due to the extra increment and bitshift operations. Wrong. Both code paths have the exact same number of instructions. Furthermore, there are only FOUR instructions that are different between the two implementations (highlighted in red below).

00F72DE5  mov         esi,dword ptr [esp+38h]  
00F72DE9  mov         eax,dword ptr 
00F72DEE  cmp         esi,eax  
00F72DF0  je          main+315h (0F72E25h)  
00F72DF2  mov         edx,dword ptr [esp+ebx*4+4ECh]
00F72DF9  lea         esp,[esp]
00F72E00  mov         edi,dword ptr [esi+4]  
00F72E03  cmp         edx,edi  
00F72E05  jge         main+2FCh (0F72E0Ch)  
00F72E07  or          ecx,0FFFFFFFFh  
00F72E0A  jmp         main+303h (0F72E13h)  
00F72E0C  xor         ecx,ecx  
00F72E0E  cmp         edx,edi  
00F72E10  setne       cl  
00F72E13  movsx       ecx,cl  
00F72E16  test        ecx,ecx  
00F72E18  je          main+317h (0F72E27h)  
00F72E1A  inc         ecx  
00F72E1B  sar         ecx,1  

00F72E1D  mov         esi,dword ptr [esi+ecx*4+18h]  
00F72E21  cmp         esi,eax  
00F72E23  jne         main+2F0h (0F72E00h)  
00F72E25  xor         esi,esi  
00F72E27  mov         eax,dword ptr [esi]  
00F72E29  add         dword ptr [esp+1Ch],eax

00F32DF0  mov         edi,dword ptr [esp+38h]  
00F32DF4  mov         ebx,dword ptr 
00F32DFA  cmp         edi,ebx  
00F32DFC  je          main+31Dh (0F32E2Dh)  
00F32DFE  mov         edx,dword ptr [esp+eax*4+4ECh]  

00F32E05  mov         esi,dword ptr [edi+4]  
00F32E08  cmp         edx,esi  
00F32E0A  jge         main+301h (0F32E11h)  
00F32E0C  or          ecx,0FFFFFFFFh  
00F32E0F  jmp         main+308h (0F32E18h)  
00F32E11  xor         ecx,ecx  
00F32E13  cmp         edx,esi  
00F32E15  setne       cl  
00F32E18  movsx       ecx,cl  
00F32E1B  test        ecx,ecx  
00F32E1D  je          main+31Fh (0F32E2Fh)  
00F32E1F  jns         main+316h (0F32E26h)  
00F32E21  mov         edi,dword ptr [edi+18h]  
00F32E24  jmp         main+319h (0F32E29h)  
00F32E26  mov         edi,dword ptr [edi+1Ch]  
00F32E29  cmp         edi,ebx  
00F32E2B  jne         main+2F5h (0F32E05h)  
00F32E2D  xor         edi,edi  
00F32E2F  mov         ecx,dword ptr [edi]  
00F32E31  add         dword ptr [esp+1Ch],ecx

I have no real explanation for this behavior, but I do have a hypothesis: The important instruction is the extra LEA in my new method that appears to be before the branch itself. As a result, it may be possible for the CPU to be doing branch prediction in such a way it shaves off one instruction, which gives it a significant advantage. It may also be that the branching is just faster then my increment and bitshift, although I find this highly unlikely. At this point I was wondering if anything I knew about optimization held any meaning in the real world, or if everything was just a lot of guesswork and profiling because what the fuck?! However, it then occurred to me that there was an optimization possible for the old version - Move the if(c==0) statement to the bottom so the CPU does the (c<0) and (c>0) comparisons first, since the c==0 comparison only happens once in the traversal. Naturally I was a bit skeptical of this having any effect on the assembly-rewriting, branch-predicting, impulsive teenage bitch that my CPU was at this point, but I tried it anyway.

It worked. There was a small but noticeable improvement in running time by using the old technique and rewriting the if statements as such:

c = C(key, y->_key);
if (c < 0)  y = y->_left;
else if(c > 0) y = y->_right;
else return y;

Optimized: 610161.8 Ticks

The total performance improvement over my failed optimization attempt and my more successful branch-manipulation technique is a whopping 63838.2 Ticks, or a ~10% improvement in speed, caused by simply rearranging 4 or 5 instructions. These tests were done on a randomized collection of 500000 integers, so that means the optimized version can pack in 10% more comparisons in the same period of time as the bad optimization. That’s 550000 vs 500000 elements, which seems to suggest that delicate optimization, even in modern CPUs, can have significant speed improvements. Those of you who say that toying around with low level code can’t infer significant performance increases should probably reconsider exactly what you’re claiming. This wouldn’t directly translate to 50000 extra players on your server, but a 10% increase in speed isn’t statistically insignificant.

This is completely insane. First, Microsoft has rendered its new Windows Live Messenger (previously MSN messenger) almost completely useless.

• No more handwriting
• No more setting your name to anything other then your first and last name.
• All links you click on redirect you to a page from Microsoft warning you about the dangers of the internet, requiring you to click a link to proceed.
• All photosharing is now incompatible with previous versions of messenger, and instead of actually just sending the file, it will instead fail completely.
• Any youtube video, image, or any other link you copy paste into the window will automatically trigger a sharing session whether you like it or not.
• It will, at times, randomly decide none of your messages are getting through.
• You can no longer have a one-sided webcam session. WLM will simply leave your webcam as a giant, useless blank image underneath your conversation partner, demanding that you buy a webcam.
• It’s new emoticons must have been influenced by H.R.Giger (you can’t turn them off and leave custom ones on).

Naturally I wasn’t able to put up with this for very long and moved to pidgin. Pidgin has many issues of its own, including an ass-backwards UI design and this really annoying tendency to create a new popup window to confirm every single file transfer, among other truly bizarre UI design elements. I was willing to put up with these, because honestly pidgin is designed for Linux and just happens to work on windows too, and their libpurple library is the basis of almost all open-source IM clients.

Pidgin, however, has now stopped working as well. It now spastically refuses to connect to the MSN service because the SSL certificate is invalid. I can appreciate it trying to protect my privacy, but there is no way to override this. So, pidgin is now out of the question.

Well, how about Trillian? During its installation, Trillian informed me that “The Adobe Flash 9.0 plugin for Internet Explorer could not be found. This plugin is required for some of Trillian’s features.”

Trillian is no longer on my computer.

After digging around on wikipedia, I came up with Miranda IM, which seemed to be my last hope for a multi-protocol service that didn’t suck total ass. It supported WLM, AIM, and… not google talk? Not XMPP, the most useful extensible open source protocol? Um, ok. Its UI design is more compact then Pidgin but arguably even worse, and it doesn’t support custom emoticons or hardly ANYTHING on the WLM protocol. It served its purpose by at least letting me log the fuck in like I wanted to, though.

This is driving me up the wall. If anything else happens, I’m going to snap and simply make time to work on my own IM client implementation that doesn’t have glaring design flaws like every single other one. Honestly, requiring the Internet Explorer flash plugin to run everything? What the fuck are they smoking? What the hell is wrong with these developers?!

If only D had a good development environment, then I could write my IM client in it.

Due to Bandcamp’s sudden threat to turn all of my free downloads into paid ones, I decided to go ahead and start selling my music properly. Renascent is now available for $3, or about as much as a gallon of milk costs. It contains remastered, super high quality (lossless if you choose to download in FLAC format) versions of all 14 songs, in addition to the original FLP project files used to create them. If you have ever wondered how I made a particular song, this might be another incentive to purchase the album. Note that these FLPs are released under the Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license, so you can’t go running off with them like free candy.

Track List:

1. On The Edge (2:56)
2. Renascent (4:06)
3. The Boundless Sea (6:49)
4. Duress (2:40)
5. Seaside Lookout (4:54)
6. Sapphire [Redux] (2:20)
7. Absolutia (3:04)
8. The Plea (3:46)
9. Now (2:34)
10. Alutia (4:10)
11. Rite (5:20)
12. Crystalline Cloudscape (4:04)
13. All Alone (3:06)
14. SunStorm (4:12)

Total Time: 56:44

Listen and Buy It Here

There is a documented bug in windows 7 that has pissed me off a few times and recently crippled a friend of mine, where a .wav file with corrupted metadata causes explorer.exe to go into an infinite loop. My friend has a large collection of wavs that somehow got corrupted, so I wrote this program to strip them of all metadata. Due to the nature of the bug, the program can’t delete them (you must use the command prompt to do that), but rather creates a folder called “safe” with all the stripped wav files inside of it.

Hosted in case anyone else has corrupted wav files they need to save. Just stick it inside a folder and run it - it’ll automatically strip all wav files in the same folder as the executable.

WavSaver