Efficient Software (by alaric)
Getting back on topic, when it comes to writing a fast program, you can often make things a lot faster by just using algorithms with lower average run times. Unless you're dealing with particularly small lists of numbers, switching from Bubble Sort to Quicksort will usually produce a big speedup; and a bigger speedup the larger your data is.
However, there is still a fairly widespread idea that making a program faster is a matter of using a "fast" language like C rather than a "slow" language like Python, Lisp or Java. This is because C is quite closely related to the machine language of current CPUs, so the compiler has an easier job converting algorithms written in C into efficient machine code. The same algorithm written in C, Lisp, Python, and Java will typically result in the Lisp version running about half as fast, the Java version a fifth as fast, and the Python version a tenth or twentieth as fast, as very rough ballpark figures.
However, it's still the same algorithm. If you write an algorithm that takes time proportional to N squared in C, and to N times log N in Python, then when N becomes 10,000, the factor of 1,000 difference between N and log N means the Python version is still 50 times faster.
In other words, the choice of programming language isn't the biggest factor in making some software efficient.
The story doesn't end there, by a long distance.
The processing power and memory available on a desktop computer have grown immensely. I remember reading in a computer magazine that these new 486 computers were amazingly fast, with their 33MHz 32-bit architectures and inbuilt floating-point unit and so on, but that this kind of power wasn't worth the price for business users; a 386 would run any business app fast enough for anybody. The 486, it suggested, was more of a tool for those manipulating large graphics or other such especially intensive tasks.
Ha ha! How amusing that people thought a 16MHz 386 with 4MB of RAM would be more than adequate for business use.
But why not? What are business users doing these days that really requires 100 times the RAM and 100 times the CPU clock speed? Back in the days of 386es, people were... word processing, editing spreadsheets, messing about with databases and contact lists and calenders. We've only really added email, instant messaging, web browsing, more higher-quality graphics and video replay since then.
The modern desktop machine or Web application server still spends most of its time idle. Either waiting for a human to press a button, for a request or response to come in over the network, or for the disk to respond with the requested data.
And looked at from another perspective, as a user, how often am I forced to wait because my computer is too slow?
- It takes a long time to boot up and load all my applications before it's ready for use. This is mainly an issue of the fact that disks haven't gotten all that much faster over the past decades, but the software has grown a lot.
- If I have too many applications open, it becomes sluggish. This is because it runs out of memory and has to page stuff out to disk, which then needs to be paged in when I switch applications. This is mainly an issue of the fact that disks haven't gotten all that much faster over the past decades, but the software has grown a lot.
- If I'm actually processing a large data set (such as searching a database), then I often have to wait. The CPU isn't usually very loaded, the bottleneck is the disk.
In fact, the only times I crave a faster CPU are when I'm compressing or decompressing large files (which is rare) or playing 3D games. And thinking about other common applications of computers, bulk arithmetic in general is very CPU-intensive; I include computer games in that category, along with scientific data processing and audio/video processing. All of these tasks benefit from highly parallel supercomputer-style architectures.
Fri 20th Apr 2007 10:24 pm 
Subscribe
By woolstar, Thu 26th Apr 2007 @ 6:38 am
What I love is that shell sort beats quicksort every time, and its easy, and nobody can tell you precisely how it works. It just does. It doesn't always beat quicksort, but its consistent. Lovely thing.
Btw, the people who care about performance, now live in the land of the mobile phone. Year 2007: cpu 100mgz, memory 8mbs. Wow, seems like I was here before.