Whither Moore's law's application to everyday computing?

An interesting article: Where have my cycles gone?.

This article asks the question I've asked myself for the longest time.

Nowadays, it's not as bad, because I run Linux on my home computer. I have, therefore, a good idea where my cycles have gone. The computer is pretty snappy at this time (well, it is an AMD Athlon XP 2000+, but there's a mere 256 MB of RAM), despite how much resolution I drive it with, how much anti-aliasing I've added, and how many background services I run.

But whenever I use a Windows XP computer, a Java application, or even some Linux desktops (those with GNOME or KDE come to mind... I use XFce which avoids much of the madness), I really wonder: given Moore's law, how come many tasks appear to be slower than they ever have been?

The author cites some understandable reasons. Here's my take on reasons I do not understand.

  1. Incorrect algorithms: somewhere, programmers have gotten really sloppy. Trying to sort linked lists with a classical quicksort (hint: don't!), running through data structures many times in an effort to work on the data where a single pass would work, doing all sort of really stupid things to help performance (such as adding cache to an O(n2) algorithm that could really be done in O(nlog2n)), and so on and so forth. I'm always suprised (in a bad way) at how many things are done with such sloppy algorithms. If the programmer would just think for a few seconds, it would avoid such problems. Complexity problems like this are usually trivial on small data sets, but what if your small data set is the set of pixels in the GUI blit routines that get used all the time, hmmm?
  2. Wrongheaded ideas: some OSs and applications have patently bad ideas at their core. Like searching stuff frequently that is not indexed. Like putting files all over the disk and expecting the filesystem to have an efficient lookup algorithm tailored to your application. Like opening multiple database transactions where everything should be done in one (this is bad for performance, but also for data integrity). The list goes on. I see this in commercial software all the time. I can think of no fundamental reason why system applications would be in a better state, given that they are marketed nearly the same way as user applications (which, IMHO, is really wrongheaded!). User applications, of course, have all those problems. Yuck.
  3. Speed/memory tradeoffs: for some reason, everybody got drilled into them that you should always save cycles in priority to memory. So people read the whole file in memory and cursor through it with pointer operations. So they put stuff in sparse hash tables where a sorted array would do and give significantly similar performance characteristics. So they introduce lots of caches to gain a small 5% increase in performance. It doesn't work, and here's why. Today's systems are usually starved for IO time or for memory; CPU is rarely running at 100% while you work (take a look at a system monitor or at the Windows Task Manager during the day; you may be very surprised at what your computer is doing). As people try to run several programs at once and get them resident, the problem worsens. Once physical memory is exhausted, the system becomes starved for IO time as the OS needs to swap stuff. If you get in this situation, it will always be much slower than the "slower" algorithm that uses almost no memory. There's also an interesting effect I've seen in some cases: due to CPU cache effects and the importance of keeping a working set small so it's most effective, larger uses of memory may be detrimental for performance in many situations, even if the OS isn't starved for RAM.
  4. Memory/resource leaks: they're everywhere. Garbage collected languages are great, but they shouldn't be taught as the first language. People who learned on garbage collected languages tend to think that the garbage collector takes care of all resource allocation. Hate to break it to you, kids: it only takes care of memory allocation, and on top of that, if you keep references to an object too long (like in caches...that thing again!), it never gets collected. Garbage collection is no excuse to be sloppy about object ownership. See previous point on why resource leaks eat up time.
  5. Freakin' objects everywhere and the lack of stack allocation: this is mostly a problem for language like Java, which couples an asinine lack of stack allocation for simple objects with a really slow allocator and garbage collector. Mix in a really high per-object allocation overhead (all object get a condition variable and a vtable, whether they need it or not!) and you've got a recipe for high temporary memory usage. That would be OK if the Java VM contracted its memory use once in a while. But NOOO! I sometimes think those who wrote the JVM have disregarded 30 years of computing, both in VM design and in garbage collection algorithms. I can think of no other reason that would explain how they could deliver such a ridiculous JVM 1.0. And I still don't understand how many of my Python scripts have more predictable performance than many of my Java programs, despite the JIT and the fact that the Python programming model does not lend itself to much optimization.
  6. Buzzword mania: why is it that we need EJB? Do you do transactions across multiple databases? Do you really need to distribute your objects (remember the first law of distributed computing: don't distribute your objects)? Replace EJB and related questions with buzzword of the month. Many products are built with technologies that don't really fit the problem, increase complexity, memory use, and decrease performance, for no visible gain in capabilities. This is really dumb. See my earlier article on why software projects fail.

Is that it? Probably not. But I think it covers a lot of things. If you're studying in CS or Comp. Eng., I really recommend that you do the following:

  1. Study algorithms. Know the main ones. Know which data structures have what complexity guarantees. This will help you choose the right structure and algorithm for the right job.
  2. Pay attention to the more low-level classes. Assembly looks like pre-history, but the principles of how machines work will always remain useful. C and C++ feel like nailing your toes to the desk in an awkward position, but you'll learn to be careful about resource ownership, and that's a valuable skill regardless of the language.
  3. Remain skeptical of those who claim your designs aren't "elegant" enough. There's always a sweet spot; but in any case, a design with less code will almost always be more elegant from a maintainability, understandability, and from a performance point of view as well. In my experience, university "elegant" means "complicated". It's cool looking, full of design patterns and objects and inheritance. But when 60% of what you typed is syntactic and semantic sugar, you'll end up with a mess sooner or later. And that will make it harder to figure out whether you picked the right algorithm. Don't misunderstand: elegant design does exist. But you'll have to develop your own sense of it. The understanding of elegant design in academic circles varies widely. Be especially wary of teachers who don't code, or instructors who never had to maintain any of their projects. Design sense mostly comes from learning what not to do by having done it and being stuck maintaining it.
  4. Remain humble when you're about to do some task. You may be smart enough to implement the equivalent of a database by hand; but why take the chance? And even if you're smart enough, keep in mind you don't really have the time anyhow. Solved problems may be fun to solve again, but good commercial-grade code is always developed with time pressure. Time you spend on your fun problem will be taken away from time you should spend making the overall system design maintainable.
  5. Try to understand what you're doing. Try to understand the libraries you're using, at least in a general way. Otherwise, it's going to be very hard to pick a given routine (or even a given method overload!) over another.

Well, that's my advice, for what it's worth. I just realized that a lot of it applies to people who already program professionally, and I can think of a few people who don't follow this advice. I know I try to follow it carefully, and it served me well so far. I've been programming commercially for nearly 5 years, and as a hobbyist since I'm 14, so I like to think that I've learned a few things at this point. I'm sure there are other things programmers should be careful of, but those I've noted in this post are supposedly 'obvious' and people still don't do it.

Hence this rant.

Hopefully, if people apply those, Moore's law's application to everyday computing, in the form of faster, more capable computers with the ability to do more for their users, will become reality.

No comments: