sonylin.net / computer
O O O O

What makes a fast computer?

Sneak peak: its not the hardware, but the software!

This article was intended to show the audiences the effect of how a properly written software can make a computer do a task much faster than a fast hardware.

  • When I was a kid, I used to think that the way to accelerate a computation is by using a faster computer.  Yes, its true.  A faster computer will logically make software runs faster.  However this perception is all changed when I realised this fact in year 2000.  Now I wanted to share with all of you,

  • I had two software that I write for calculating the shortest distance and finding the shortest path between two cities.  The first program was written back in 1997/1998 when I was studying programming, and the second program was written in 2006.  Then in today, I decided to compare the performance of the first program - recompiled with current compiler and running on the latest quad core AMD Phenom with 2GB of ram - versus the the second program running on a slow 10 years old Pentium II machine. 

  • Disclaimer: this is not a shoot-out death-match between Intel and AMD.  The AMD Phenom is completely different to Pentium II.  They are 10 years apart and from different generation, Pentium II is a Generation 6 x86 proccessor, while AMD Phenom is a Generation 10 x64 processor.  This article is intended to show how does a smart algorithm compare to dumb algorithm.

  • The task is to find the shortest distance and shortest path between city A and city B on an island.  There are 1000 cities and a million of connecting roads between them.  Guess, which one is the fastest?  A guided bruteforce running on a machine with at least 40 times of computing power compared to Pentium II or a heavily optimised dynamic programming running on a 10 years old Pentium II?

  • OK, I admit that I did not finish test of the first program.  The first program first find the shortest distance between city A and B - which would help to finding the shortest path - and then bruteforcing to get the shortest path.  It took around 35 seconds to find the shortest distance, then I don't continue to find the shortest path, which I estimate would take more than one day.  I have no luxury of waiting that long. 

  • The second program is written using entirely different algorithm.  The process took 49 milliseconds - blink of an eye - to complete in the Pentium II to find both the shortest distance and path.  A 10 years old Pentium II just beats a state of the art quad core AMD Phenom!

  • This is the list of computers starting that runs a smart algorithm, all capable beating AMD's quad core Phenom running stupid algorithm.  Pentium II 266 MHz: 49 ms, Pentium !!! 550 MHz: 10 ms, starting from AMD Turion, Pentium 4, Celeron 2.13 GHz, Core Duo and above, it is almost immeasurable: 0 ms!

  • How about the accuracy of the 2nd algorithm?  Theoretically, the 2nd algorithm produces the same results compared to the first algorithm.  On testing, the 2nd algorithm produces 100% same result on every test case as the first algorithm.

  • The conclusion is the choice of algorithm and skill of programming is the one that make software run much-much faster by exponential degree.  It took years of training to find the best and fastest algorithm to solve a problem.  While changing hardware only increases computer performance by tiny margin.  E.g., upgrading 2 GHz single core Pentium 4 to 2 GHz dual core Core2 Duo increase its performance by two folds, or 3 folds at most.  However changing stupid algorithm to a clever algorithm will make a 10 years old computer beats new computer by significant margin, which means the performance is improved thousand times folds!

  • The algorithm for 2nd program was proposed for next generation network routing protocol, e.g. find the most efficient way of transferring your packet over the internet.  I invent the algorithm back in 2004/2005 while I was studying at Curtin University, and simulation shows that this algorithm was highly efficient in doing its task, including managing severed connection and damaged nodes.  Then I adept that algorithm for the 2nd program, it was the single computer version of that algorithm.  I hope on one fine day I could find that algorithm in the computer I've bought.

  • Unfortunately this is not how our world works.  There are 3 factors that determine a software's speed

    • Software programmer tends to create a resource hogging software due to faster and better hardware.  The hardware company is also happy with this, since people will kept buying newer and faster hardware to be up to date.  OR...  might be there was a conspiracy behind this, to make people kept buying newer and better hardware?  I don't know!

    • Not every problem can be solved with highly efficient algorithm like this.

    • More feature packed software leads to more calculation that overload the system.

  • Recommendation: for manager who contract software engineer to write a software for you.  Please make sure that your software engineer is writing a highly efficient software that will not cost you hardware upgrade or at least minimal upgrade.

  • All that I've written above comes from my experience of using computer the last 22 years.  I use computer heavily - other than meeting clients and meeting my staffs - all of my works is in front of a computer everyday for more than 5 hours.  When the toddler on my age was learning to write, I learn to type and operate a computer!  That is why my writing is so bad.

That is, hopefully this article could enlighten the audiences!

<expand