ldn11 @ LedakJitu Tower Defense as a Thread Model

I keep having the strangest reoccurring dream. In my dream, I’m playing a turret defense game. ¹ However, it is no ordinary tower game. It’s actually a thread process model. In the dream, each turret type represents a thread synchronization mechanism, generally some sort of atomic primitive. The units marching along the paths represent the threads that require synchronization. Most are worker threads calculating a result set, but some may be polling threads reading device updates or doing other jobs. The range circle of each tower and the position of the unit along the path represent states when it is appropriate for the thread to be accessed, either quiescent states or work states where the thread has completed some useful task and has a result ready to be read. If the unit\thread moves out of the turret\synchronization range circle, the thread result is lost or held and operation on the next work cycle begins. Shooting a unit\thread with a turret is a read\synchronization operation and gathers the result.

Yeah, I know, clearly I’ve had threads on the mind a little too much lately. 🙂 I’ve been working on a major refactor of the engine at work and thread synchronization problems are tricky.

Usually when I have dreams like this I wake up in the morning and have a good laugh wondering what the heck I was thinking. This time, however, I think there may be something to it. Now, I’m not suggesting a design built literally on the model exactly as it is in the dream but I think there are elements that could be useful.

The part that is intriguing about the turret defense thread model is that you can guarantee completion (all units hit) without guaranteeing really very much at all about either the turrets or the units. The units are not synchronized with each other; in fact, in many tower games faster units can overtake slower ones. A unit does not guarantee a minimum speed–it may even be allowed to stop entirely on occasion–although it does guarantee a maximum speed. The turrets are not synchronized with each other, nor do they communicate any information to each. A turret does not guarantee a specific number of units hit, only that it will hit units at a specific rate. A turret also does not guarantee what order it will fire at units in. A unit likewise guarantees nothing about when or by whom it will be hit except that it can be hit when it is within a valid range.

Yet, with a sufficient number of correctly placed turrets all the units will be hit with none escaping. More importantly, most of the time you can have far fewer turrets than units and still complete successfully. The number of turrets required is a simple function of the maximum speed of the turret, the maximum speed of the unit, and the number of times the turret must hit the unit for completion. Placement is trickier, but with a thread model you could surely replicate that with signals.

Fascinating, isn’t it?

I’m not sure yet where to go with all this, but it seems like there’s a useful idea to be gleaned. It’s not that different that a traditional worker pool, but the lack of communication seems important. I’m sure there’s something useful that can be done with this.

1. For anyone who cares, the specific game seems to be Crystal Defenders, but with some elements of Bloons Tower Defense 3.

gacormak @ LedakJitu memcpy_s

On Friday, an article ran on Slashdot making note that Microsoft is “banning” the C function memcpy in favor of the new memcpy_s. While memcpy_s has in truth been around for a while, the notion that it would now generate compiler warnings has created quite an uproar. Some people seem curious as to why so many people are upset by what seems a pretty innocuous change. The article author asked if was going to affect anyone’s creativity. I can assure you that’s not the concern.

In a nutshell: the problem is you can’t tape a cupholder to a formula one race car and declare it street legal. It still doesn’t have any bumpers, it’s too low to be safe around other cars, and if you aren’t an expert driver you still shouldn’t be driving it. A cupholder doesn’t change that.

So what? A cupholder is still an improvement… right? Who doesn’t want a cupholder? Imagine for a moment that having the cupholder suddenly disqualified you from a number of races. You couldn’t run that race if you have a cupholder. It also slowed down your car–not a lot, but a tiny fraction of a second. Maybe it doesn’t slow it down enough to matter, but in those few races won by hundredths… well, maybe it does. Suddenly that cupholder doesn’t seem so nice.

To be clear, I’m not suggesting giving up on attempts to improve memory management and prevent buffer overruns. I just question if this exact approach was the best one.

Memcpy_s is basically a race car with a cupholder. While memcpy_s will certainly prevent some bugs, the same people who got one parameter wrong are just as likely to get two parameters wrong… and cause all new bugs in the process. Garbage In = Garbage Out. It doesn’t matter what the calling convention is.

On two occasions I have been asked,—”Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?” … I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question.”

— Charles Babbage, 1864
discussing the first mechanical computer

The change also comes with a price: it breaks cross-compatibility with other compilers, including older compilers on the same operating system as well as other platforms. This means the same code can’t cross-compile anymore if you use memcpy_s. Someone with Microsoft suggested that GCC should pick up the change as well. Perhaps, but that assumes that GCC is the only other compiler that matters. Certainly, it’s the most popular other compiler that matters, but it’s far from the only one especially if you do embedded systems work or anything running on “exotic” hardware. And let’s be honest–if you’re not writing something that’s fast or exotic, you’re probably not writing it in C. The exception, of course, being legacy code… but surely that’s even less likely to be changed. The whole point of legacy code is that you don’t have the time\budget to update it, otherwise you wouldn’t be running it at all. These are the guys who will wrap memcpy_s in a macro named memcpy, defeating it entirely. Sigh.

As for that speed difference I mentioned? We’re obviously only talking about an extra comparison operator and perhaps a branch or two here. I know an extra comparison operator seems trivial, but if an extra comparison operator didn’t matter ASSERT macros wouldn’t exist. The speed difference is nominal, but it’s very, very real. On a lark I timed it. Copying 32 bytes 100,000 times with memcpy took on average 3952 counts, or about 0.001104 seconds, measured to nanosecond accuracy with QueryPerformanceCounter. Performing the identical operation with memcpy_s took on average 9706 counts, or about 0.002712 seconds. This was in “release mode” using Visual Studio 2008. (For the curious, in debug mode the difference averaged 8028 counts to 11340 counts, but you shouldn’t be shipping your code in debug mode anyway!)

Now hopefully you’ve done everything you can to avoid memcpy in your inner loop in the first place, but we all know there are rare occasions where it’s unavoidable. This all brings me back to my earlier point: if you’re not writing something that’s fast or exotic, you’re probably not writing it in C. Yes, you can write your own memcpy that’s probably faster than the system memcpy if you’re really worried about speed, but now we’re back to the portability issue. In short, I’m certain that to the people where the choice of language matters, those few clock cycles matter too. We’re talking folks writing device drivers here, not business applications.

Nobody is twisting anyone’s arm to use memcpy_s. You can easily disable the compiler warnings and continue to use memcpy all you like. But hopefully you see where I’m going with this: A lot of the reason that people continue to use C for certain projects has to do with performance and portability. This change sacrifices both for dubious return. If the change is not going to have tangible benefits that outweigh the problems, why do it at all?

Sooner or later, you need to trust that the programmer knows what they are doing. If the programmer can’t manage memory responsibly, you’ve got a bigger problem than an extra parameter is going to fix. To be honest, while a lot of people don’t like to admit it programmers sometimes leak or botch memory even in managed languages. There’s certainly a thesis paper or two in “possible alternatives” to the approach taken–perhaps checking the block size by querying the allocator instead of asking the programmer which would be even slower but more reliable, borrowing ideas from double entry accounting, etc, etc.–although the “real” fix surely involves more intelligent ways of thinking about memory, which realistically means a fundamental change in constructs, not a patched function.

As always, XKCD sums it up best (panel #2):

Ah, I wait for the day… 🙂

surgahoki99 @ LedakJitu Parallel Processing in a Nutshell

A friend sent me the link to this video, and I have to say, this is the most clear and direct explanation of the difference between linear processing and concurrent processing I’ve ever seen. …That, and it’s just darn cool to watch a 1100 barrel paintball gun get fired.

polar79 @ LedakJitu BioHacking

If you’re into reverse engineering biological systems–in my mind, one of the most fun parts about AI programming–this talk by Drew Endy is absolutely a blast. Also be sure to check out the BioBricks project at openwetware.org or download the actual “bricks” at the MIT Registry of Standard Biological Parts.

The BioBricks are sequences of DNA described in a standardized, open-source format where each sequence represents a single, interchangeable part or “device”. A data sheet is provided for each device that describes what it does and what its tolerances and parameters are, etc., similar to the data sheet for an electronics part. Like an electronic component, devices can be combined together to make more complicated structures. When you’re finished designing your device, the sequenced DNA can be inserted as a plasmid into a suitable host cell and used to make all kinds of cool stuff, like this biological film where the bacteria change color in response to light.

Hello World displayed by light-sensitive, color-changing eColi