Surprisingly Quick

Recent changes
Table of contents
Links to this page


My latest posts can be found here:
Previous blog posts:
Additionally, some earlier writings:

2016/10/06 - Surprisingly Quick ...

In the 1990s I had a job at Liverpool University doing research into how we might make it possible for non-computing specialists to use parallel computers. Even today, over 20 years later, this is still an unsolved problem, and the machines now are designed to be easier to use. The machine I was using was a Parsys SuperNode with 96 T800 transputers, hooked together with a reconfigurable switch, cunningly designed so that any 4-regular network could be realised.

For the time it was quite an impressive piece of kit.

However, we wanted non-specialists to be able to use it, so it was decided that at a minimum we would need to have the NAG serial Fortran library available. We could worry about the idea of parallelising it later, but if the NAG library wasn't available at all, most serious numerical computing users wouldn't even consider the idea of looking at using it.

There were, in fact, a number of problems, not least was that on occasion, using system utilities in the documented fashion, I could crash the machine. There was one memorable occasion when I managed to wipe the disk just using the ls command.

It got to the point where whenever other users saw me coming (remote logins were disabled) they would back up their work across the network and logoff, such was my reputation.

Which persists to this day ...

So I was porting the NAG serial library, and I came across the problem that the compiler needed the modules to be presented in an order where if module A needed module B, then module B had been listed earlier. In short, I needed to do a topological sort on the module names.

These days this is easy, but back then the machines I was using didn't have a topological sort, so I wrote the simplest thing I could think of in AWK, instrumented it, set it running, and went away to make a coffee. The idea was that when I got back I could see how far it had got, and then decide whether to leave it running, put it on a faster machine, or write something cleverer.

I got back. It had finished.

In fact, it had probably finished even before I had got out the door. By not bothering to take the time to write something clever I had saved myself huge amounts of time - the first thing I'd thought of was fast enough.

So what is the lesson to take away from this? Is it that we should do experiments first to make sure we really understand the situation? That's certainly one lesson, but we can learn that from pretty much anything, and I had learned it decades earlier. It's a simple rule of thumb, never "optimise" before you measure.

So perhaps the lesson is that machines are faster than we think? Well, sort of, but not really. Machines certainly are fast (by some measure) but the machine I'd been using wasn't that special.

Perhaps the lesson is that a topological sort isn't actually that hard to write? Well, a good and fast topological sort is hard to write, but more likely the data I had wasn't sufficiently complex.

No, the lesson I learned that day was this:

  • Hash tables are an amazingly powerful tool.

You might not be surprised by that, but you might. Certainly in the early 1990s, hash tables, associative arrays, "maps", whatever you choose to call them, were comparatively rare, and were not offered as a standard feature in many languages. Having them instantly "to hand" in a language was unusual, and what became very clear was that there are times when they are exactly the right tool.

More, I would claim that even if they aren't exactly the perfect tool, they are a good place to start, a good tool to use to write that quick, first version, instrument it, and then let it run for a bit while you idly wonder whether it will be good enough.

Odds are, it's probably close.

<<<< Prev <<<<
An Unexpected Fraction
>>>> Next >>>>
Spikey Spheres ...

You should follow me on twitter @ColinTheMathmo


I've decided no longer to include comments directly via the Disqus (or any other) system. Instead, I'd be more than delighted to get emails from people who wish to make comments or engage in discussion. Comments will then be integrated into the page as and when they are appropriate.

If the number of emails/comments gets too large to handle then I might return to a semi-automated system. That's looking increasingly unlikely.



Links on this page

Site hosted by Colin and Rachel Wright:
  • Maths, Design, Juggling, Computing,
  • Embroidery, Proof-reading,
  • and other clever stuff.

Suggest a change ( <-- What does this mean?) / Send me email
Front Page / All pages by date / Site overview / Top of page

Universally Browser Friendly     Quotation from
Tim Berners-Lee
    Valid HTML 3.2!