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...