Subscribe!

• Colins Blog

• An Unexpected Fraction
• You Have To Admire Their Optimism
• Representatives Matter
• Pythagoras By Incircle
• A Puzzle About Puzzles
• How Not To Do Twitter
• Calculating 52 Factorial By Hand
• Small Things Might Not Be So Small
• Not If You Hurry
• Factoring Via Graph Three Colouring
• Another Proof Of The Doodle Theorem
• When Obvious Is Not Obvious
• Graph Three Colouring
• The Doodle Theorem
• Be Careful What You Say
• The Mutilated Chessboard Revisited
• A Mirror Copied
• The Other Other Rope Around The Earth
• Photocopy A Mirror
• The Point Of The Banach Tarski Theorem
• Sieve Of Eratosthenes In Python
• Fast Perrin Test
• Russian Peasant Multiplication
• FindingPerrinPseudoPrimes Part2
• FindingPerrinPseudoPrimes Part1
• The Unwise Update
• Miles Per Gallon
• Tracking An Item On Hacker News
• Hacker News User Ages
• Poking The Dusty Corners
• There Is No Time For This
• Publically Sharing Links
• Learning Times Tables
• Graceful Degradation
• Diagramming Maths Topics
• On The Rack
• Square Root By Long Division
• Beyond The Boundary
• Fill In The Gaps
• Software Checklist
• NASA Space Crews
• The Birthday Paradox
• The Trapezium Conundrum
• Revisiting The Ant
• The Ant And The Rubber Band
• Irrationals Exist
• Multiple Choice Probability Puzzle
• Random Eratosthenes
• Wrapping Up Square Dissection
• Dissecting A Square Part 2
• Dissecting A Circle
• Dissecting A Square
• An Oddity In Tennis
• Decision Tree For Tennis
• Decision Trees In Games
• A Matter Of Convention
• Do You Nourish Or Tarnish
• Binary Search Reconsidered
• Two Equals Four
• The Lost Property Office
• The Forgiving User Interface
• Setting Up RSS
• Withdrawing From Hacker News

• Random Writings.
• Colins Blog 2010
• Colins Blog 2009
• Colins Blog 2008
• Colins Blog 2007
• Colins Blog Before 2007

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.

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

Comments

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.