Archive for the ‘computer’ Category

Negative-overhead exceptions

Tuesday, May 1st, 2007

There are two schools of thought about how to handle errors in computer programs. By "errors" here I mean things that are out of the programmer's control, like "out of memory" or "file not found" rather than mistakes in the actual program (which is a whole other topic). Ideally we want programs which don't just crash when they hit such unexpected circumstances but rather tell the user exactly what the problem is and give them the opportunity to fix it and try again or do something different instead.

The first school of thought is that functions which fail should return some kind of "status code" (which may be "success" or one of several other values indicating different types of error). This is how most of the functions comprising the Windows API signal failure.

The problems with status codes are:

  1. Whenever you call a function you need to check it's status code or risk missing an error (which usually makes things worse). It's tedious and error prone (mistake prone) to write the code to do this and sometimes programmers forget.
  2. The information about an error you can return is quite limited - you can say "file not found" but you can't say which file wasn't found or what the program was trying to do at the time (you have to determine this from context).
  3. If you're using the return value of your function for a status code you can't use it for something more natural. For example, if you're writing a square root function that needs to return an error code when given a input that is negative, it can't also return the answer in a natural way.

The second school of thought is that failures should be indicated by "throwing an exception", which is technically rather more complicated. This involves looking at the function that called the failing function, and the function that called that one and so up the stack until you find a function that says "hey, I know about that exception - pass control to me and I'll deal with it". This eliminates the need for all the functions in between to know about the possible failure at all (other than cleaning up their resources).

Exceptions are new and spiffy and are generally considered to be the "right way" of doing things in new programs. Unfortunately, exceptions also have drawbacks:

  1. Your program is less "explicit" about what it actually does - certain controls paths are "hidden away" in the exception mechanism. Proponents of exceptions argue that this is a good thing.
  2. Certain programming styles cannot be used in the presence for exceptions. For example "do X, then do Y, then do Z, then do W if Y failed." Proponents of exceptions argue that these styles are mistake prone (it's all to easy to forget to do Z) and should be avoided anyway.
  3. While many programming languages in widespread use support exceptions, not everything does. In particular, certain "glue" for interfacing between different bits of code written in different languages generally doesn't support exceptions because they need to be compatible with languages which don't support exceptions (the old "lowest common denominator" problem).

Another criticism often made of exceptions is that they are slow. This may have been true in the past, but in practice it turns out that exceptions are no slower than status codes in the success case (they are slower in the error case, but that doesn't matter too much because errors should be pretty rare).

I think that it is possible to make programs that use exceptions even faster than programs that use status codes. With the right set of tables, the error case code can be completely separated from the normal case code. No code that deals with or tests for errors even needs to be loaded into memory until an exception is actually thrown. Then control passes to a "throw" function which loads the tables and error handlers into from disk and examines the stack to determine which functions the exception passes through and which function will actually handle the exception. The code is faster than the "status code" version because it doesn't have to have all those "if failed" tests sprinkled throughout.

I haven't tried implementing it, but as far as I can tell there are very few places where this scheme would have any overhead at all. One is this situation - State0::RunState() and State1::RunState() can't be folded together with my scheme because they have different stack unwinding information.

The other limitation is that the stack layout and set of constructed objects has to be completely determined by the instruction pointer in any given function. This is usually the case but does mean that functions can't allocate dynamically sized arrays on the stack. These don't tend to be used in practice because they have the serious problem that it is very easy to overflow the stack. If you do know in advance a maximum possible size for this array you may as well just allocate the maximum size.

Multiple scrollbars

Thursday, April 26th, 2007

Ever have a window which has so much text in it that the vertical scrollbar moves too coarsely to allow you to find the position you want? Like you have an entire dictionary loaded as a text file and you're trying to find the word "madrigal". You get to "machine" and (after some fiddling with the mouse) manage to move the scroller one pixel down only to find that you have overshot all the way to "magical". Then you have to scroll all the way back up to madrigal or go back to machine and scroll down. Either of which, depending on the size of the dictionary, may take quite some time. Most annoying.

Wouldn't it be good if, for long documents like this, you had two scrollbars side-by-side. These would work like the hour hand and minute hand on a clock. The rightmost one would set the position in the document coarsely and the leftmost one would be for fine-tuning it. Once you had got to the "early Ms" with the rightmost scrollbar you could quickly get to any nearby word with the leftmost one.

For best distribution of precision between the scrollbars, the region of the document corresponding to the entirety of the leftmost scrollbar (X) would be to the entirety of the document as the window would be to X (i.e. the pixel size of the two scrollers would be the same).

The scrollbars would be set up so that moving the scroller of the leftmost scrollbar one pixel scrolled the document by at most one line. If the document is too large, than a new scrollbar is added - particularly long documents might have 3 or even more scrollbars, each with the same virtual document size to virtual window size ratio.

Lensing editor

Wednesday, April 25th, 2007

One problem I'm always wrestling with while programming is how to see as much as possible of my program on screen at once. I tend to use a very high screen resolution (1600x1200 usually) and a very small font in my text editor (6x8) to see a large quantity of text at once. My coworkers despair that they can never read what's on my screen and say that I must have very good eyesight (I do at short distance - reading road signs while driving is another matter). But even 150 lines is not enough sometimes.

A while ago I had an idea for effectively increasing the number of lines even further. Vertically "compress" the lines that are further away from the cursor, while showing the closer lines at normal size. The further lines wouldn't be legible (unless the document is quite small) but you can see the overall "shape" of the document and easily navigate to different sections. The effect would be kind of like squashing the document vertically so that the whole thing fits on the screen and then looking at part of it with a horizontal bar magnifier centred on the cursor (although it would be a magnifier with an extended cross section so that even lines of text quite far away from the center were magnified a little bit, and there would be no obvious boundary between magnified and non-magnified text). Because of the similarity to a bar magnifier, and by analogy with the concept of a "folding editor" I call this idea the "lensing editor".

Sonic head tracking

Tuesday, April 24th, 2007

Here's an interesting idea I had a while ago. It involves using the microphone in a headset like this, a fixed set of speakers and a high-resolution sound card (like almost any modern sound card) to track the position of the head of the person wearing the headset.

The software works by sending sounds through the speakers and trying to pick them up through the microphone. Once it manages to synchronize the sent pulses with the received pulses it can calculate the exact delay from sending a pulse to receiving it. Part of this delay will be due to the hardware involved or the latencies in the operating system, but these delays should be fixed. The remainder of the time is caused by the finite speed of sound in the medium between the speaker and the microphone. To a fairly good approximation this speed will be constant (about 300m/s) so using the delay one can work out the distance between the microphone and the speaker. Do this for two speakers and you can triangulate the position to a circle in the plane normal to the line between the speakers. Two more speakers and you can determine the position of the user's head quite precisely, up to the resolution limit of the soundcard (most modern soundcards can do 192k samples/second, giving a positioning accuracy of about 1.6mm).

Why would you want to do this? Well, the position of the user's head is a particularly interesting datum because it can be used to move windows around giving a pseudo-3D view. Suppose you have two windows on the screen and one is partially covering another. Normally to see the hidden part of the lower window you have to use the mouse (or worse, the keyboard) to move the upper window or bring the lower window to the foreground. But with a pseudo-3D view each window has a "Z-position" in front of or behind the plane of the monitor. If the user's head moves left then the closer windows move right and the further windows move left, allowing you to "see around" the upper window by moving your head, just as you would do with real objects. I haven't tried it yet, but I think it would be quite effective, and a cheap way to make a user interface much more immersive. I thought of doing this years ago but with an infra-red gadget strapped to the forehead - it only recently occurred to me that this could be done less intrusively with the microphone that many people wear anyway for telephony purposes.

Embedded scroll bars

Sunday, April 15th, 2007

Many usability abominations have been inflicted on us in recent years, but I think one of the worst is embedded scroll bars in web pages. I usually scroll with my mouse wheel so it's especially annoying to be scrolling down and have a frame with a vertical scrollbar scroll under the pointer so that it starts sucking away the scroll events. It's also annoying if you're actually interested in the contents of the frame, since you have to cover up part of the text that you're reading with the pointer in order to be able to scroll the frame. Ban embedded scroll bars now! (Yeah, I know - I should use an open source browser and reprogram it myself to remove constructs that I dislike...)

Computer industry: complexity explosion

Thursday, April 12th, 2007

The enemy of software is complexity. The more complex a program, the slower it will run, the more likely it is to crash or have security holes, the longer it takes to write and test and the harder it is to modify.

I think that most software is much more complex than it really needs to be. I think that there are a few basic causes for most of the complexity we see in modern software. In no particular order:

  • Premature optimization. Programmers making changes to eliminate a perceived inefficiently without checking that there is a real inefficiency, that the change fixes that inefficiency and doesn't cause a slowdown in the system as a whole.
  • Legacy optimization. Optimizations which used to be important, but are not necessary with modern hardware design. This can be a tricky one because it's often difficult to justify removing old, fast, working code and replace it with something simpler but slower. I think MAME has struck a nice balance here.
  • Political considerations. Management decreeing "this project must be written in Java as it is the latest and greatest thing" when that might not be the best tool for the job.
  • DRM. Adding snake-oil to software to temporarily appease copyright holders. To be maximumally difficult to break, DRM must be extremely invasive so tends to cause complexity throughout entire systems. Windows Vista is probably the best example of DRM run horribly amok.
  • Hoarding. A company invents some spiffy new way of doing something and doesn't want that method to be available to their competitors, so they patent it or copyright it to force their competitors to solve the problem in a different way. The result is that there are multiple ways of doing any given task, rather than one canonical one. This has a much greater second-order effect as a lot of software needs to be compatible with many other pieces of software, so has to know about n different ways of doing things.
  • Refactoring debt. As code is added, removed and changed, the surrounding code should be modified so that the result is as simple as possible, or the resulting software will be an overly complex conglomeration of disjoint pieces and unnecessary duplication. Unfortunately this important step is often left undone (either because there isn't time, or management doesn't realize what an important investment it is, or because there isn't sufficient test coverage to be sure that the refactorings don't cause additional problems.
  • Excessively clever techniques. Sometimes somebody will happen on a technique which seems to be particularly powerful, but actually ends up causing more problems than it solves. For example, the preprocessor in C allows you to do all sorts of things which the language does not directly support (like generic programming and domain specific languages) but only in a way which does not integrate well with tools like source analyzers and debuggers, unless these are made much more complex.

I sometimes wonder if there is a great opportunity for someone who would dare to blow up the universe and build a whole new computing infrastructure with a serious case of Not Invented Here (though reusing the best bits of today's software), creating something much simpler and more reliable.

Disruptive technology

Wednesday, April 11th, 2007

I think Microsoft really missed an opportunity with the Zune. Creating an MP3 player with built-in ad-hoc wireless networking would have been a work of genius had it not been utterly crippled to satisfy content providers. If you "squirt" a song to someone else they can only play it three times and it goes away in three days. Suppose that they had ignored the wishes of the RIAA and instead created an MP3 player which squirted unencrypted songs at random to other MP3 players in the vicinity. It could even compare playlists with other devices in range and squirt songs it thinks the owners of other players are likely to enjoy (a la last.fm). This would be an absolutely killer application for an MP3 player - I'm sure lots of people would buy it just for the unlimited free music and it would make a fortune. Unlike using internet-wide sharing apps, it would be very hard for the RIAA to track down who is doing the sharing, since the networks would be geographically localized.

What about that pesky copyright problem, though? Well, with all the money they made from the hardware, I'm sure Microsoft could afford to fight (and win) a few copyright lawsuits. Saying "you may only use this player with music whose copyright is owned by someone who doesn't mind it being distributed in this way" ought to be enough to comply with the law (assuming no new anti-P2P laws are created in the meantime).

What about having the artists get paid? Well, the player could include software which says things like "Hey, I noticed you've been playing a lot of music by artist X lately, why not buy their new CD, buy tickets to their concert in your area or just donate some money to them so that they can continue to record" and provides convenient links to do any of those things. If those links worked for non-RIAA music as well as RIAA music, it would eliminate the need for the major recording labels altogether. The RIAA definitely wouldn't like that, so it would take someone as big as Microsoft to pull it off.

Computer industry: partners and competitors

Tuesday, April 10th, 2007

The software industry is quite unlike any other because (in principle at least) no problem needs to be solved more than once. Each piece of software can build on all the previous pieces.

This puts many companies (especially ones like Microsoft, who make platforms - software which is designed to be built upon) in the curious position of having their partners also be their competitors in many situations. On the one hand, we want to make things as easy as possible for our partners, releasing rich software frameworks to help them improve their time to market. On the other hand, we want to make things as difficult as possible for our competitors by keeping our product code secret.

How do you define the line between product and framework? The extremes are easy - low level functions which are applicable for just about any product (like those for copying a string or creating a window) are clearly frameworks. High level functions like the code in Visual Studio for performing common refactorings or manipulating the solution explorer window are clearly product code because they are really only applicable to Visual Studio (or equivalent products).

But there's a whole spectrum of functionality in the middle which makes it very difficult to draw a hard boundary. Take the command bar code for example. This is the code for manipulating menus, toolbars and commands and allowing users to customize the product by moving menu items and toolbar buttons around and adding new ones. It was invented (and is maintained) by the Office team but is also used by Visual Studio since we have many of the same problems to solve. Currently, command bar functionality is not made available to developers outside of Microsoft. If you want to have customizable toolbars and menus in your own product, you have to add it yourself. But this would be useful for all sorts of other applications, so perhaps we should make it a framework and let other companies use it. The Office team might disagree, since it could make it easier for their competitors to catch up with them.

I think that as a company, Microsoft is (very slowly and gradually) moving from being a "products" company to a "frameworks" company - we're gradually releasing more and more things in such a way that others can build upon them, as it becomes less of a strategic advantage to keep them to ourselves. If we released the command APIs now it probably wouldn't make much of a difference Office's competitors because:

  1. They all have their own, incompatible ways of providing equivalent functionality - it would be a very big job for them to switch to using command bars.
  2. Command bars only work on Windows and Office's competitors are all cross-platform.

I think we will continue to introduce new innovations in "product only" form (like the "ribbon" stuff in the latest version of Office) and then turn them into frameworks some years later, once it becomes strategically more favorable for us to do so.

I like this trend because it promotes the idea of "software as a science" (in the sense of creating things that others can build upon) and ultimately helps to advance the "automate everything" cause.

Brain implants

Monday, April 9th, 2007

If it were technically possible and safe, would you enhance your brain with electronic implants?

Some possibilities:

  • A clock, so you would always know what time it is without having to carry a watch, and never oversleep again
  • A calendar, so you always know what you have planned for any particular day and time
  • A calculator, so you could instantly do mental arithmetic on numbers many digits long
  • A computer, so you could perform complex calculations just by thinking about it, and amuse yourself when bored by playing games in your head
  • An internet connection, so you can instantly look up anything, send a message or check your email
  • A borg-style "hive mind" implant so you can participate in shared consciousness with anyone else who has a compatible implant

Delete your recycle bin!

Sunday, April 8th, 2007

Ever try to delete your recycle bin (if you use Windows) or Wastebasket (if you use a Mac)? In some sense it seems like it ought to work (since these are just objects in the system) but in some other sense it seems like it would cause a paradox and destroy the univese (or at least prevent you from being able to delete other things, or crash the machine). Computing brings us many other paradoxes like "compiling the first compiler" and "paging out to disk the code that pages code back in to RAM".