Using Moore’s Law to solve program inefficiencies

As the processing ability of computers becomes faster, we sometimes forget that some devices have limitations. Mobile devices have to contend with processors that draw minimal power, in a device with minimal space. Washing machines and fridges also have minimal embedded systems within them. And then there are devices such as Mars Rover Curiosity. The Curiosity has less processing power than an iPhone 5, but it also had to contend with a 253-day, 352 million-mile flight to Mars. Its memory is radiation hardened to withstand radiation from space. The RAD750 processor can withstand 200,000 to 1,000,000 rads, temperature ranges between –55 °C and 125 °C and requires 5 watts of power. It’s software is 2.5 million LOC written in C.

– Processors: Curiosity’s is 132MHz; the iPhone 5’s is 1.3 GHz.
– Memory: Curiosity’s has 128 MB; the iPhone 5 has 1 GB.
– Storage: Curiosity holds 4 GB; iPhone 5 holds 64 GB.

Writing code for devices with limited resources is intrinsically more challenging than those with abundant resources, and requires a working knowledge of making programs more efficient. In Knuth’s 1974 paper “Structured programming with go to statements” [1] he states: “we should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil”. But with CPUs such as the IBM zEC12, with a clock rate of 5.5 GHz, we may have forsaken the task of writing efficient code altogether. Why? For the simple reason that as time has progressed we have relied on Moore’s Law to solve program inefficiencies – a slow algorithm can be made more efficient by having it run on a faster CPU. Now machines process things so quickly it is hard for students to garner the difference between various algorithms – they end up designing code which is inefficient because they assume machine speed-ups will make up for any inefficiencies in the code.

In the 1970s it was commonplace to do comparative studies of algorithms running on various platforms, to optimize inefficiencies and produce leaner, more compact code. For example, compare a Bubble-sort algorithm with a Quick-sort algorithm by sorting 1000 random integers. The result – both return immediately, with run-times of 0.0 seconds. A common problem – algorithms that had different run-times 20 years ago, now seem equally efficient. Now run the algorithms with 100,000 random numbers: 0.01 seconds for Quick-sort, approximately 40 seconds for Bubble-sort. What sort of person would wait 40 seconds for an app to run? Likely no one. That’s why designing the best program involves knowing something about algorithm efficiency. If both algorithms seem to have the same efficiency, the novice programmer will choose the code that is shortest, i.e. the Bubble-sort. The experienced programmer will realize that the Quick-sort is more efficient, even though it relies on recursion, which uses more stack resources. Maybe an Insertion-sort running at 6 seconds?

Bottom line – We cannot rely on faster CPUs to fix inefficient programs. Nor can we forsake the fact that many devices have limitations that prevent them from running algorithms in the same manner as they would on devices with limitless resources.

[1] Knuth, D.E., “Structured programming with go to statements”, Computing Surveys, 6(4), pp.261-301 (1974).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s