Premature Optimization

For many years I have believed (and still believe) in the following (quoted in Wikipedia) :

Tony Hoare first said, and Donald Knuth famously repeated, “Premature optimization is the root of all evil.” It is important to have sound algorithms and a working prototype first.

I’ve been finishing a molecular builder in JUMBO and it’s far more important to make sure that the right atoms are joined, rather than it joins the wrong atoms at lightning speed. So it’s nearly right and I applied it to larger systems.
It suddenly started to go very slow. Now there are lots of ways that programs can go solwly. In many cases the elapsed time is dependent on the size of the problem. Double the size, double the time.
But this had what is called “Quadratic Behaviour”. Double the size, quadruple the size. Joining 10 fragments was a few seconds, 100 fragments took 2-3 minutes. And in our apps we need to join this number.
So why was this? A typical example is adding unique items to a list. For small lists you can just run through the list and check for duplicates. But if you have 10 elements in the list it takes 10 operations. If you have 100, then 100 operations.
Isn’t this just linear? No :-(. Because to add 100 items you have to search the list 100 times and as it gets bigger it gets slower. The actual expression is something like n*(n-1) but that’s effectively quadratic.
Well I knew where the problem was so I didn’t need profilers or anything like that. I just went to the code and put in a few timings to check. Funny! didn’t seem to be there. Put in a few more timing statements. Still didn’t seem to find the problem. 3 hours later the code is covered with timing statements and I’ve found it:

CMLAtomSet atomSet = new CMLAtomSet(molecule);

What’s happening. All this is doing is iterating though the atoms in the molecule and adding them to a set. Sets in Java are optimised to avoid quadratic behaviour. Should be very fast.
The problem is that the atoms are being added one-by-one. After each one we update the XOM (which acts as the central storage for the problem). It’s safe. There is no way the XOM can get out of sync with the data. But each read and write from the XOM (which contained lists of strings) was expensive. Doing it 100 times was hitting the machine.
So I made this a lazy process. The XOM is not updated for each atom, only at the end. It now takes 1 sec for 60 fragments, not a minute. The trade-off is that you have to be careful to update at the end – so there is a function updateContent(). You MUST call it. I’ve now hidden all this from the developers so that the code above is both fast and safe (I hope – that’s where the unit tests are absolutely essential).
Some of you will have tutted that I should have run the profiler immediately. They’re right. I should have a profiler in my Eclipse. I’m off to get one. Any suggestions?
But that could take 15 minutes to install.
And the fix was only a 5 minute fix…

This entry was posted in programming for scientists. Bookmark the permalink.

One Response to Premature Optimization

  1. Jim Downing says:

    The profiler isn’t meant to save you the 5 minutes it took to fix, but the 3 hrs it took to find the problem 🙂
    There are *meant* to be profiling tools included in eclipse 3.2: If you enable the Callisto discovery site in eclipse, you should be able to install the TPTP profiling tools. The caveat is that I’ve never been able to get them working. YMMV and let me know if you do manage to get them going.
    An alternative would be to get a license for a commercial profiler. Most have free licenses for OS projects. I’ve enjoyed using YourKit before now and it boasts Eclipse integration too these days.

Leave a Reply

Your email address will not be published. Required fields are marked *