Showing posts with label complexity limits. Show all posts
Showing posts with label complexity limits. Show all posts

Tuesday, April 13, 2010

Dprocs

We have a rather interesting interpreted language in-game that can be used to perform actions on a handful of triggers; an example might be to add an arbitrary 'use' function to an object. As an example of this, I once built a vacuum cleaner object which could be used to suck up pretty much anything you pointed it at. Sucked up things ended up inside the vacuum.

One drawback of this language is that it didn't have any concept of global data. I added that feature today, using a surprisingly small amount of code.

A surprisingly small amount of code that took me about three hours to write.

Once again, software complexity rears its ugly head. I actually made two false starts on this problem, each of which I had to back out before finally getting a minimal solution to it. The interpreter isn't really that complicated or large by any real programming standard, but it's still larger and more complicated than I could easily wrap my brain around.

It took about two hours to really figure out the best way to handle it, then about an hour to implement it. Most of that time was just trying to understand what was already there and how it all worked. And this is code I wrote!

On the plus side, my actual implementation, when I finished, had 2 bugs in it, both trivial. It's good to know that thorough understanding up front does in fact result in far fewer mistakes.

Tuesday, October 20, 2009

Software Complexity Crisis

[This rather large post is almost entirely a personal rant. I complain a lot about wxWidgets in here, because it's fresh in my mind and a very good example of a specific type of software engineering crisis. Note that I'm still using the WX libraries for the Alter Aeon client project; clearly it has value to me in spite of its faults, and I appreciate the effort the WX team has put it. That said, if I could easily move to any another library that met my constraints, I would do it in a heartbeat.]

Various recent attempts on my part to use large software libraries have made me re-examine the issue of the general software-engineering crisis. I've run up against typical software crisis problems many times in the past, so I tend to keep my eyes open when I see material related to the topic. This is one of the reasons that Vernor Vinge's book "A deepness in the sky" caught my attention.

One of the basic premises of this book is that complexity failure can be sufficient to bring down entire societies. This was put very succinctly in a blog posting by Jeremy Bowers on his iRi Blog, part of which I quote here:

"One of the less well known concepts which informs his sci-fi writings is one possible fate of societies that do not or can not end in a "singularity", which is the eventual unavoidable collapse of the society in a cascading failure state brought on by excessive, uncontrollable complexity in the ever-more-sophisticated systems that drive the society. In this case, take "system" in the broad sense, including not just software, but business practices, government, and societal mores. A failure occurs somewhere, which brings down something else, which brings down two other something elses, and perhaps quite literally in the blink of an eye, you are faced with a growing complex of problems beyond the ability of any one human to understand or contain."

This relates to software in that I'm beginning to see more and more examples of how this can occur. Two software platforms in particular come to mind - IBM's WebSphere, which I was peripherally involved with a decade ago, and wxWidgets, which I am involved with today.

Both of these platforms are very complex. Both form an abstraction layer which builds on top of other layers - in the case of wxWidgets, there is a huge amount of API reuse from the lower layers of Windows, or GTK, or X, depending on which configuration it's built for. Each of these layers is built upon other layers, and other layers, sometimes with very deep call trees.

The most egregrious example of this kind of layering that I can recall was in WebSphere. A friend had asked me to take a look at a stack trace from a WebSphere crash; somewhere deep in Java land, a 'null object exception' had been thrown. (Thank god it wasn't a NULL pointer, that would have been much worse!) The exception handler that caught it was basically the main loop, because apparently no other layer could be bothered to check for failure conditions along the way.

There were over 160 stack frames to walk through. Not one of them was due to a recursive algorithm or function. I don't know about you, but that level of stack depth is quite frankly beyond my ability to manage or debug. I don't care what it does.

WxWidgets is clearly beginning to show stress of its own, of a different character: it's becoming more and more impossible to guarantee consistency across platforms. The WX guys have made tremendous progress in this regard, so that most of the core features work right, but there are simply too many details to keep track of and too many paths that will never be tested.

Here's a couple of examples of this, one of which I'm STILL fighting:

-------------------------------------------

When I first started switching the Alter Aeon client project over to WX, I initially used the wxTextCtrl class, which is built out of Microsoft system libraries in the Win32 world, or built on the GTK libraries in my development environment. I had hoped to use the class for both the input window, and for the main display; with a small amount of effort, I got the client running and working, but there were minor, very persistent issues.

The first of these was the input window. Various events, such as backspacing when empty, cause a system beep/bell under windows. They don't cause a bell under Linux. And further, there's no way to disable this. I don't know about you, but I'll be damned if I'm going to ship a product that beeps every time someone hits backspace.

I managed to take care of some of this by trapping out various keystrokes in the CHAR handler. It seemed like a poor hack at the time, but at least it helped. However it didn't help enough; a number of keystrokes simply don't generate CHAR events, yet they still fucking beep. I finally ended up writing a raw keyboard event handler, which tracks nearly all of the keyboard state, to trap out events that would generate a beep when passed to the lower layer. In the time it took me to disable beeping, I could have written and debugged a keyboard handler from scratch, with exactly the desired behaviour.

While beeping has largely been taken care of, other issues with this so-called standard class have not. The biggest one is that the color of text displayed in the class returns to black occasionally, and depending on the versions of the system DLLs for the particular Windows installation. My first attempts at fixing this were effective on all my development environments, but failed on about half of the release environments - text typed in the window would occasionally simply vanish.

By adding forced color setting in various places where it shouldn't be needed, I eventually managed to fix this problem for about 90% of my users. Out of sheer disgust at this point, I did some extremely vicious forced color setting in various event handlers, and this appears to have fixed 'most' of the problem. I still am receiving sporadic reports of it happening on current client builds, but at least the problem goes away now and seems to be triggered at random.

When attempting to use this same class for the main window display, I ran into what seemed to be minor issues regarding the scroll bars and scrolling of text in the window. No matter what I tried, I never did find a way to get reliable scroll positioning for this class across all platforms.

After fighting this off and on for several months, I became desperate. I finally wrote my own text display class from the ground up, using nothing more than bitmaps and font drawing routines. The total from-scratch implementation time was less than the time I had previously wasted trying to get the scrollbars to work properly. It's also faster, especially for very large data sets.

-------------------------------------------

This, my friends, is the software engineering crisis in action. Each layer, while hiding some of the problems of the lower layers, introduces its own; the overall result is a system with fewer catastrophic issues, but exponentially more minor issues.

Those minor issues are surely tolerable, are they not? To an extent, yes - but at what point do you die the death of a thousand cuts?

Catastrophic issues might be catastrophic and obvious failures, but that's one of the best things about them: they're catastrophic and obvious. They HAVE to be fixed. They must be understood, they must be cleaned up and dealt with. The minor problems on the other hand, can just keep accumulating. They just keep getting worse, they just keep getting more obscure, more complicated, more difficult to find and rectify. And worse, they compound each other.

In a good scenario over the long term, they become so prevalent that the system no longer becomes usable. In a bad scenario, the system becomes critical and unmaintainable. It's a swiss cheese of buggy modules and misunderstood patches.

Is that really what you want to build critical infrastructure out of? Is this where we're headed? I certainly hope not.

Sunday, March 1, 2009

Chaos seems to reign

The field of software arguably contains some of the largest and most complex functional systems ever created by man. Even relatively simple systems can demonstrate incredibly complex behavior, and can hide potentially major flaws through indefinitely long periods of use, only to demonstrate them at inconvenient times. The Alter Aeon server codebase is no exception.

Pretty much the most complicated discrete object in the server is the socket stack. It handles a huge number of protocols and a bunch of different filtering layers, with hooks in various places. The last major redesign of the socket stack was around 1998; it is a testament to the design of that module that it has required no major modification in that entire time period, though many minor modifications have been made to it.

Unfortunately, the server is not made of such lovely discrete objects. Often, obscure bugs lurk in the sea of wild code that makes up the substructure of the system. This weekend I had the incredible good luck to catch and haul two of these bugs to the surface.

For years, there have been a handful of issues that occurred seemingly at random. In the early, old days, some of these would even cause a server crash and reboot the game; but after being unable to find and fix them, the crashes were gradually protected against and ways were found to ignore these spurious events.

Examples of the two most common of these are deceptively simple: sometimes, the get_room function would be asked to find a room but be given no instructions on how to do so, and other times a character (a monster or player, it was difficult to tell) would die and simply 'get stuck'.

In reality, these are monstrously difficult. The get_room function lacking instruction was mindboggling - it happened perhaps twice a year, the reports were never the same, and there were thousands of places that could be calling the function. Even as our debug facilities improved, no progress was made - there just seemed to be no rhyme or reason to it.

The dead character bug was just as bad. The entire destruct and event handling process was revisited and inspected several times, but no holes were ever found. Until thursday.

---------------------------------------------------

In the course of trying to add some new restrictions to the 'charm' spell, I noticed that the destruct sequences for the charm, possession, and entangling roots spells looked a little goofy. We didn't check or clear certain important things, but there were comments indicating that we didn't need to because something else over there would take care of it. Keep in mind that this was entirely my code; I had written this well over a decade ago.

In the course of looking at this, I suddenly had a realization: there were no 'holes' in the logic for charm or possession, but maybe, just maybe, there was a hole in entangling roots. Entangling roots did come later, and quite frankly the code for it was a complete hackjob.

Within ten minutes, I had my answer. There was indeed a conflict between entangling roots and the 'special' code that made possession and charm work. The problem then became, how exactly do you fix such a mess? After about two hours of thinking about it and five more of carefully backing things out and reorganizing, I got what appears to be a stable fix. There's still some debug logging in it, but this bug appears to be properly killed. The new code is simpler, the checks are stronger, and we don't rely on obscure handlers to clean up messes. I hope.

---------------------------------------------------

I thought that was the end of my troubles in the short term, but then Glorida shows up with some obscure problem of his own. He's been working on mob programs, and had built something rather complex that simply was not working. Not only wasn't it working, but it was doing something weird, and it was doing it reliably.

This is another one of those 'fairly complex' pieces of the system. It took me about two hours off and on to get it loaded into my brain so I could really think about it. It then took me probably another hour to really understand what was going on, and figure out what was happening. And then it occurred to me:

This explains a lot of those debug log reports over the years!

The symptoms he uncovered showed up as a very unusual sort of 'doing things before other things have completed' recursive issue. One example of it is that a monster would 'say' something to trigger another monster, and the second monster would perform its action before the first monster could fully complete its 'say' command. In obscure cases, this chaining could be several layers deep.

For simple things like monsters talking to each other, the worst that can happen is that some things get out of order, and you might not understand why it works sometimes but not others. But monsters do substantially more than just talk to each other.

And this is where the problem arose. In the course of doing more complicated actions, those actions could be interrupted mid-stream by other monsters trying to complete their triggers. One such set of actions would cause the get_room function to be passed trash. Another such set of actions would damage one of the monsters so that it could never properly die. Both of these sets of actions, and a number of others with similar strange effects, were possible and implemented in monsters on the game; and they were sufficiently rare to explain the infrequent bug reports.

This bug was easier to fix than the first, taking only about three hours to really think about and put together a proper solution. This fix also appears to work, though it does break a dozen or so special monsters that relied on the old behaviour to function.

---------------------------------------------------

There are several morals to this story, which all software engineers worth their salt will immediately recognize:

1) Never assume you'll remember anything about code you've written. When you start working on objects so complicated that it takes you an hour every day to load it into your head so you can go to work, what makes you think you'll remember every detail after a year?

2) Think about the design of any halfway complex system and stick with it. The charm/entangling roots bug was caused entirely by undesigned/spaghetti code for the character destruct process. It was never properly designed because I wasn't experienced enough at the time to know how. It's better now.

3) Never underestimate the power of race conditions and call trees. When even simple/obvious actions can invoke arbitrarily complicated effects capable of invoking other effects, you're walking on very, very dangerous ground.

Software continues to become more complex as time goes on. It pushes at the limits of our minds, bringing programmers to the limit of what they can understand and then begging them to add one more thing. It allows arbitrary expression, but with that comes the cost that our comprehension is limited even for structured objects, to say nothing of more arbitrary and abstract ones.

Where does the future of software lie? Undoubtedly toward increasing complexity. But we will need either better tools, or better brains, to be able to manage it. We are such a young species.

Friday, February 27, 2009

Bugs, bugs, and more bugs

One nice thing about the (relatively) small userload we have right now is that reboots and the occasional crash aren't so much of a problem. Which is good, because today has been awful.

A confluence of factors served to get some really terrible code into the system, but by far the biggest one was my acceptance of pretty well untested code without thoroughly testing or reviewing it myself. This was the cause of several crashes and an almost-severe memory corruption fault (which was fortunately cleared by a crash in a different, unrelated section of code.) While my code was definitely not bug-free, it was at least not crash worthy material.

The only saving grace in this mess is that I found and fixed a bug that has been occasionally plaguing the system for over ten years: memory structs on players were not being properly cleared in an obscure scenario, resulting in use of mob structures after death. Were it not for the crash-resistant pooling memory architecture that we've been using since 1996, this would have caused major problems over the years. As it was, it simply cut warnings and bailed.

In exchange for this though, I now have a host of other plausible wierdnesses, including a bug that appears to corrupt the destruct timer on dead players. Again, the design of the codebase is happily tolerating this and simply cutting warnings, but it is disturbing nonetheless.

Thursday, November 6, 2008

Software Complexity and Human Limits

As you might have read from other posts here, I've been working on a gui client for Alter Aeon. Gui code is fundamentally different from what I'm used to working on, in that it has loads of function pointer handlers and 'virtual internal state' that is mostly held by which objects are instantiated and what they're presently doing. At its lowest level, this can of course be represented by a perfectly ordinary state machine, however these state machines are fairly large and the state it's currently in isn't always obvious.

[As a side note, I do work in FAX software in my off time, and this also has some pretty huge state machines. However, those state machines are really well defined in one central location, and it's much more obvious what's going on. Even saying that, I still have a hard time with those.]

While working on this client, I quickly lose track of what needs to be done and how the states work. The client itself is big enough that I can't remember everything that is in it; and after not working on it seriously for almost two years, I had a lot of trouble getting back up to speed.

A good part of this is that the code itself was basically built from the ground up, and then never cleaned up by a maintainer. Maintenance is more than just adding a button here or there and fixing minor bugs; maintenance of software means getting in there and saying "why the hell are these drawing functions intermingled with scroll locking?", then moving things around so it makes more sense. A good example of this is the button system, the entirety of which is contained in the main window implementation file. This serves only to clutter up the main window implementation, and further make the button code hard as hell to understand.

So I've been doing the proper thing and moving functions around, grouping them by functionality, and trying to make useful classes on the side where I can hide details. But even so, I can tell that my standard way of thinking about and writing code is showing signs of strain. Much like I'm having to retool my picking technique on guitar, I need to retool my brain to handle this kind of abstraction better.

I don't really need any advice or recommendations for books here; I know where to find that sort of thing if I need it, and I've done this enough to know when I'll need it. I even know conceptually how to approach this kind of problem; I think I'm just currently bad at it. Fortunately (or perhaps unfortunately), there's a lot of work left to do on this client, so I'll get lots of practice.