I had been struggling for a few weeks with some strange behavior I was getting from my dissertation project. I developed my software using the GPL'd Quake 2 engine, and I was surprised when it started crashing unexpectedly and displaying all sorts of weird artifacts. John Carmack and his cohorts are great programmers, and I knew there weren't bugs like this in the commercial game... but I also knew that I hadn't touched any of the code that was throwing me memory violations.
So I spent a few weeks debugging, and didn't get anywhere. I excised the entire collision system and reduced the frequency of fatal errors, but the system still wasn't stable enough to run for more than a few hours. Plus, I really want to use the collision system.
Most of my changes were to the standard data structures, particularly edict_s (which I use to represent my animats -- my artificial creatures). I added a three-dimensional array to keep track of each animat's world knowledge -- one dimension holds the "layers" of knowledge (like food locations, enemy locations, unexplored territory, &c.), and the other two dimensions represent the XY coordinate plane of the world. The world is a square 2048 units per side, and I didn't want the arrays to be that large, so I collapsed the XY plane into a 32x32 grid of "sectors", with each sector being 64x64 units in size; my knowledge array could then have 32x32 entries per layer (0 - 31 in each dimension), rather than 2048x2048.
Because of this granulation, however, I needed a routine to translate an animat's real coordinates into its sector coordinates, so I wrote the following:
#define GRIDX(x) ((int)x->s.origin[0]/C_GRIDSIZE)
#define GRIDY(x) ((int)x->s.origin[1]/C_GRIDSIZE)
Those macros take the X or Y coordinate of animat x and then divide it by C_GRIDSIZE, which is 64. No problem! Except... near the edges of the map it's possible for an animat to nudge itself slightly past 0 or 2047! The knowledge array in the animat structure only goes from 0 to 31, but occasionally these macros would return -1 or 32, or even worse! When I would then try to write to the array, I wasn't writing into the knowledge map at all, I wrote to other locations in the animat structure!
Sorry for all the exclamation points, but it's no wonder I was seeing strange behavior. I just changed the macros as such:
#define MIN(a, b) (a<b?a:b)
#define MAX(a, b) (a>b?a:b)
#define GRIDX(x) MIN(MAX(((int)x->s.origin[0]/C_GRIDSIZE),0),C_XMAX-1)
#define GRIDY(x) MIN(MAX(((int)x->s.origin[1]/C_GRIDSIZE),0),C_YMAX-1)
Everything seems to be quite stable now, and I'm going to leave it running overnight just to be sure. The lesson is: always bounds-check your arrays!
No, Michael. Never bounds-check your arrays. You cannot bounds-check that which you don't have. Arrays are inherently evil, and should almost never be used.
The array is implicitly a point of program vulnerability. Bounds-checking is only one of the ills its flesh is heir to. He who programs with arrays will inevitably come to grief, either through a bounds violation, or a fencepost error, or a size-rigidity problem.
Arrays are incompatible with the most important software-engineering breakthrough of our time, the principle that gave birth to object-oriented programming: Unite your data to the set of operations that can be validly performed on it, and forbid all others.
When programming in any language that supports the dynamic allocation of memory, I avoid arrays, you should pardon the expression, religiously. Instead, I use keyed linked structures: either forward-and-backward linked lists or binary trees that can be searched by content, and which are organized in a fashion that conceals their nature and size from the "higher" application.
Computer languages are shockingly inconsistent in their treatment of arrays. Whereas Pascal and Ada treat the array's dimensions as part of its data type, other languages do not. FORTRAN arrays start from 1; C and C++ arrays start from 0. BASIC arrays start from 0 and then throw in an extra element at the end, to the confusion of communications applications everywhere. And let's not discuss PERL arrays; my stomach simply isn't up to it.
Applications written around arrays have caused much destruction. I once had a matrix mechanics job, a twelve-hour program that ran on a supercomputer, fail in the ninth hour because of an array problem. The great continent-wide communications crash of a decade ago was caused by a mis-defined array. Two major stock market recording debacles occurred because an array was undersized -- the same array in both cases, ironically enough.
Our enemies know this. Soviet academicians pushed arrays right up to the end of the USSR. (Hoist on their own petard. Hah!) Stroll the streets of Paris and you'll see innumerable placards that say, L'arrai, c'est tres bon! Al-Qaeda has reportedly tried to popularize arrays in certain unnamed engineering colleges in Virginia and North Carolina, promising "extra virgins" to those who used them "effectively."
Arrays are not attractive. I've lost count of the number of times a flirtatious single woman has asked me, "are you a dynamic kinda guy?" (More than that was ultimately required, of course, but hey, we're talking principle here.)
Several (admittedly disputed) statements of Christ condemned the array. When Peter denied Him thrice, the third occurrence caused a protection violation. You know what happened after that.
Preserve the purity of your precious bodily fluids. Avoid the array at all costs. Don't let your friends bring arrays to your parties. If you see one coming toward you, cross the street. Make sure any candidate you support for public office has a firm anti-array stance.
Despite all of this, you might ultimately have to get involved with an array, if only for maintenance purposes. If so, your Curmudgeon will pray for you. And always remember the Golden Rule Of Indexing:
"Real Men Count From Zero."
The Register asks the question, What does C have in common with a scalding cup of coffee?
Congratulations, by the way, on finding the needle.
Francis, you're too funny.
But I'm not going to implement a 3D linked space just to store some doubles, especially not when I need to address them directly and will never need to insert or delete! Arrays are incredibly useful, because they're low-level. Just gotta be careful.
Very interesting analysis (and comments too). Now I'm ready to start my day of coding.