26 Jan 2002 wnewman   » (Master)

programming programming programming

Today I had occasion to write three dozen lines of code which deserved a hundred or so lines of comments containing explanation, several examples, and a DANGER UNEXPLODED MINDS header. Generally I believe that too many comments strongly suggest that something is wrong with the code. In this case I did it anyway. The new code is tricky because it's generalized in at least three ways (over maximization and minimization, over upper and lower bounds, and over BOOLEAN, REAL, and an application-specific domain which is only partially ordered). Thus, the alternative is twelve (two extremization operations times two bounds times three domains) more straightforeard functions, four of which already existed at the time that I discovered the need for the third generalization and started writing the all-in-one generalized version. Exploding my mind once and only once has got to be better than feeling my brain atrophying at superluminal speed as I try to proof-read twelve different fundamentally equivalent variant functions. And it's not *that* complicated, anyway, it's just that most humans, including me, tend to have trouble thinking accurately about double negatives and triple negatives, even whan as in alpha-beta search it's really fundamentally simple. (Rationalize, rationalize, rationalize?)

Also I think I may have figured out why some related code is so astonishingly slow. It's a menagerie of objects sending a storm of "I've changed, update yourself" messages. I've spent quite a lot of time off and on trying to understand the problem. Now I think I see a way for a cascade of update events to require a number of operations which grows exponentially in the length of the cascade, even though there are efficient, reasonably obvious update sequences which are nearly linear in cost. I suspect that this kind of pathological update mis-ordering is actually happening in my ridiculously long problem cases. I hope so, since it should be easy to fix by replacing my old trivial obvious eager update scheme with a few dozen lines of code (a FIFO queue, some flags, and perhaps some heuristics).

I wish I knew a better way of debugging things like this mis-ordering. It seems as though it should be easy to spot exponential growth! But it's obscured by a thicket of other polynomially large stuff. By the time that the test case is big enough that the exponentially large misbehavior would dominate, the number of operations the system is doing is so large that it's really hard to see any pattern at all. Hmm.

I also wish I had known what I was doing before I started. I suspect I might be rediscovering and reimplementing what practitioners in another specialty (truth maintenance systems?) consider to be the basics. I doubt, though, that these basics are universally known, or at least that they were universally known in the late '80s. SBCL's compiler is very slow, and when I use a debugger to follow what it's doing, I see it transforming code and inferring types and updating this because that thing upstream has changed over and over again. It's rather reminiscent of what I seem to have stumbled over in this unrelated code. As I've gone over the SBCL code (mostly looking for bugs, not performance issues) I've seen plenty of signs of serious effort (in, I think the late '80s and early '90s) to make it run faster, but no sign of any attempt to analyze and rationalize this kind of update scheduling. Hmm again.

In another kind of update problem, my dark engines of computation are grinding out and testing sbcl-0.7.1, and I hope it will not have an undetected severe bug as sbcl-0.7.0 did...

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!