Slashdot Mirror
Progress In Algorithms Beats Moore's Law
Relic of the Future writes "Seen on the blog 'Algorithmic Game Theory,' a report to congress and the president about past and future advances in information technology notes that, while improvements in hardware accounted for an approximate 1,000 fold increase in calculation speed over a 15-year time-span, improvements in algorithms accounted for an over 43,000 fold increase."
And yet first posts never seem to get any faster
more bloated GUI libraries (bling), and comfier runtimes (different VMs).
Algorithmists have Moore's Law envy.
Take the cheese to sickbay, the doctor should see it as soon as possible - B'Elanna Torres, "Learning Curve"
Even in the 1980's it was recognized in avionics that algorithm improvement accounted for several orders of magnitude of speed in computing -- out performing hardware advances of the day. We highlighted that article in Avionics Weekly -- proudly displaying it outside our cubicles.
There should be an algorithm for that.
Thats an interesting figure because when the alpha came out DEC were predicting 1000 fold improvement in speed over about the same period. They split the improvement over factors of ten: clock speed, parallelism in the CPU and multiple cores were each expected to deliver a factor of ten improvement.
Now while our algorithms might be getting better our programmers definitely are not. A lot of those improved algorithms must be in our APIs. Like the way its easy to use a Hashtable in java now but in the last you might have just searched a linear array.
http://michaelsmith.id.au
What the Good Lord Algorithmic Efficiency Improvements giveth, the Evil Lord Real-Time-Virus-Scanner taketh away.
sed -e 's/Chuck Norris/Rajnikant/g' joke > fact
So how did they magically increase the number of transistors using software? Oh whait, someone didn't know what Moore's law was...
When hardware gets faster it applies more or less uniformly to all algorithms you run on that hardware. When an algorithm is improved it applies to just one specific problem. For some problems we already knew close to optimal algorithms 15 years ago, in those cases there was no way algorithmic improvements could have achieved such a speedup. And in fact the article mentions just one specific problem where algorithmic improvements made it about 43.000 times faster on one specific input. In other words, this number is not nearly as general as the summary makes it sound. The are algorithms that were not speeded up nearly as much, and for any algorithms that were bad enough to begin with, there could have been an even larger speedup - without anybody making a fuss about it.
Do you care about the security of your wireless mouse?
Moore's law is based more on economics than technology. He was just a hands on executive who had a clear vision of what the future would bring. Anybody who actually has read his original paper would realize this. The fact that his theory has held up this long is incredulous.
Moore's Law is that the number of transistors on a single integrated circuit would double - it has nothing to do with speedup.
//TODO: create a signature
Linear Programming is a reasonably obscure optimisation method used in operational research, where you describe a complex management problem in terms of a series of linear inequalities, then use an algorithm to evaluate all the possible solutions until it has found the optimal one. The algorithmic improvements here mean that we have found ways of cutting down the space faster, while still coming to the best solution. For one particular problem with just the right characteristics it's very possible that an improvement of 43,000 times could be achieved, but this is almost certainly an atypical case, and in general improvements due to algorithms are almost certainly going to be a lot smaller than improvements due to processing speed over a long period.
I'm not sure they know what Moore's law is.
Oh, a submission from tim? of course it's wrong.
nothing new here
Be seeing you...
Progress in Algorithms Beats Moore’s Law
Everyone knows Moore’s Law – a prediction made in 1965 by Intel co-founder Gordon Moore that the density of transistors in integrated circuits would continue to double every 1 to 2 years.
Fewer people appreciate the extraordinary innovation that is needed to translate increased transistor den- sity into improved system performance. This effort requires new approaches to integrated circuit design, and new supporting design tools, that allow the design of integrated circuits with hundreds of millions or even billions of transistors, compared to the tens of thousands that were the norm 30 years ago. It requires new processor architectures that take advantage of these transistors, and new system architectures that take advantage of these processors. It requires new approaches for the system software, programming languages, and applications that run on top of this hardware. All of this is the work of computer scientists and computer engineers.
Even more remarkable – and even less widely understood – is that in many areas, performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed.
The algorithms that we use today for speech recognition, for natural language translation, for chess playing, for logistics planning, have evolved remarkably in the past decade. It’s difficult to quantify the improvement, though, because it is as much in the realm of quality as of execution time. In the field of numerical algorithms, however, the improvement can be quantified. Here is just one example, provided by Professor Martin Grötschel of Konrad-Zuse-Zentrum für Informationstechnik Berlin. Grötschel, an expert in optimization, observes that a benchmark production planning model solved using linear programming would have taken 82 years to solve in 1988, using the computers and the linear programming algorithms of the day. Fifteen years later – in 2003 – this same model could be solved in roughly 1 minute, an improvement by a factor of roughly 43 million. Of this, a factor of roughly 1,000 was due to increased processor speed, whereas a factor of roughly 43,000 was due to improvements in algo- rithms! Grötschel also cites an algorithmic improvement of roughly 30,000 for mixed integer programming between 1991 and 2008.
The design and analysis of algorithms, and the study of the inherent computational complexity of prob- lems, are fundamental subfields of computer science.
As always, all IMO. Insert "I think" everywhere grammatically possible.
Looks like both Moore's Law and the improvement in algorithms together don't beat out Gates's Law: Software bloat doubles every 18 months.
Disinfect the GNU General Public Virus!
Remember when you were a youngster and you had to learn about O() ?
Well, over the years you lose sight of the importance of that.
Not too long ago, just for fun, I implemented a DFT naively, O(n^2), and as an FFT (O(n log n).
Try that and run it for 65536 points and see what happens, even on a fast machine...
Consider for example the humble matrix solver. Iterative solvers (only applicable for certain problem spaces) can get you n lg n sort of behaviors, as compared to n^3 for generalized gaussian elimination.
It's important to use the right algorithm !
Absolute statements are never true
Aww, jeez. There was a post saying they didn't know Moore's Law meant transistors, which I figured wsa ridiculous for a Presidential Commission, so I fetched the report and snipped it. Seemed to me the text must be buried a few link-layers or pages deep. It didn't occur to me it would be front dead center and about two thirds of the blog article. This is slashdot. I have no defense. .
As always, all IMO. Insert "I think" everywhere grammatically possible.
Without knowing about the "before" and "after" algorithm, it's hard to know if the "after" algorithm couldn't have been run earlier because there wasn't enough memory.
I've written a lot of stuff that runs a hell of a lot faster lately, but I use a lot more memory than I did 20 years ago.
Any realistic scenario will chalk up around a factor of at least 8000 to memory improvements, leaving, oh, maybe a factor of 5 to pure algorithmic improvements.
OPTIMIZE YOUR SHIT.
Because tons of hardware is useless if you can't push it to it's limits with efficient code and algorithms.
Game and OS designers, I'm looking right at you.
Still waiting on Serviscope_minor to wake up to fucking reality and realize that Jessica Price isn't going to fuck him.
i read a sci-fi story once, i forget who it was by, where some space travellers found themselves in a situation where their computer failed. so they taught themselves maths, plotted the stars, learned to do trigonometry in their heads, and over the course of many months, the 30 or so travellers managed to work in parallel to calculate an approximate but accurate enough path to get themselves within range of rescuers.
then, there is another sci-fi story, called "The End of Eternity", which dates back to when the title "Computer" was utilised in exactly the same way as "Professor" is utilised, now. the hero of the story was a human named "Computer Harkan". Computer. "one who computes".
the point of mentioning these two things is very very simple: prior to modern "computers", parallel "Computing" algorithms were commonplace, well known, and heavily relied on. Along came "computers" and - you know what's coming next - exceedingly rapidly, all that incredibly valuable "parallel" expertise was lost, in favour of single-step, single-process algorithms. i believe we're paying for that loss of expertise, somewhat.
Software is getting slower faster than hardware becomes faster
If enithin kan gow rong it whil. (Murfey)
oo - please post your ~/.fvwmrc online somewhere! *excited*. i run fvwm too, i run fvwm too!
I don't understand, how does it mean algorithm improvement of 43,000 fold? Who needs 43,000 fold when anyone can easily make 1,000,000 fold improvement!
Proof:
Let N=1000
O(N^2) = 1,000,000
O(N) = 1000
O(log N) = 3
O(1) = 1
O(N^2)/O(1) = 1,000,000 / 1 = 1,000,000
Wait till we made improvement in O(N!) problems like traveling salesman and see how huge improvement that's gonna be!
As it turns out, some very important problems are inherently hard to parallelize:
http://en.wikipedia.org/wiki/P_complete
Palm trees and 8
Most of the improvement may have finally come from general abandonment of bubble sort for quicksort.
While processing power has increased over the years, the amount of memory that can be built in to a given amount of space has grown at a similar rate. So while it's easy to account for pure processing performance increases, what about algorithms that improved due to the space-time tradeoff, which would allow more complex algorithms that use more memory in return for requiring less processing time?
It seems disingenuous to say that algorithm improvements beat Moore's Law if they're really just benefiting from Moore's Law by being allowed more memory. There's a distinct difference between "we can use a better algorithm because we have more memory" and "we've discovered a novel new & faster approach".
If you can make and algorithm 43000 times faster, that means the first version was utter garbage to begin with. By this standard, all a person needs to do is write an algorithm that is one million times less efficient than the hardware would permit. Then over 18 months, make the software progressively faster until it gets one million times faster and claim that you performed a miracle. I think this is the Montgomery "Scotty" Scott school of computer programing where you under promise a thousand fold but deliver a half ass effort to claim that you're a genius
The ugly reality is that mainstream applications and OSes have slowed down more than the hardware has improved. That's disturbing considering the fact that hardware these days is about 10,000 times faster yet modern OSes are more sluggish than ever. Fortunately, people are waking up to this fact from instant computing devices like smartphones and tablets and once they've used instant computing, waiting 5 minutes for a computer to boot or even 45 seconds on a lean fresh install just won't be acceptable.
Thats an interesting figure because when the alpha came out DEC were predicting 1000 fold improvement in speed over about the same period. They split the improvement over factors of ten: clock speed, parallelism in the CPU and multiple cores were each expected to deliver a factor of ten improvement. http://mybestpicksever.com/
... Murphy still holds the lead.
Have gnu, will travel.
The difference in between top notch programmer and the rest of the garden variety type is this -
Top notch programmers are ever enthusiastic over the things they have produced while the rest - they are just coders.
That's why top notch programmers keep on finding ways to optimize their algorithm while the rest ---> you know who you are and what you have been doing.
One thing that's happened to improve algorithms, besides having people study Computer Science and take advantage of the work other people have done in academia and open source systems over the past few decades, is that computers are enough bigger and faster that you can solve problems that weren't feasible in the past, because you didn't have enough RAM, or disks were too small and you needed to use tape, or CPUs weren't fast enough to bother using some techniques, and having those tools gives you more choices of algorithms than I had when I was an undergrad in the 70s, or than my professors had when they were learning CS in the 60s and 50s. 640KB wasn't enough for everybody, and I remember a Star Wars funded research project at Princeton in the late 80s that had a VAX with 128MB of RAM crammed into it so they could study what you could do if you really always had enough RAM. (They didn't think 128MB was really quite enough, but it was a good start and they could get it funded, and it was still extravagantly large - they even had a 450MB disk drive just for swap :-)
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
A similar thing has occurred over the last 30 years in the physics sub-field of quantum Monte Carlo. I forget what the numbers are, but it's something similar with the algorithmic improvements being like an order of magnitude greater than the CPU improvements.
Ah, I remember looking at the sorting algorithm in a low level graphics library. Tightly hand coded, packed to keep every pipeline stage filled and make optimal use of all the parallel units in a VLIW graphics processor, it was probably the most efficient bubble sort I'd ever seen.
I coded up a quicksort to about the same degree of tightness in a couple days, and, golly gee, a whole bunch of code suddenly got faster. Some MUCH faster... That was Lesson 1 for me. Optimize algorithms before optimizing implementations.
Given the conflict of interest in the report evidenced by:
It's amazing they didn't report a billion-fold increase in algorithms resulting from government funded R&D.
Seastead this.
When the phone reboots a few times a day, boot time matters. Yes of course, the phone (android) shouldn't crash but it does.
OSes on the other hand do need to be boot more, especially laptops if you don't want to lose charge in standby or you care about crypto which only works if you power off. In standby mode, people can freeze the memory and transplant it to another computer.
The other problem is that OSes that boot slow also tend to run slow. The user interface slowness is something developers and product managers neglect all too often. That has worked for traditional computing products, but the public clearly likes a fast feeling OS. That's why the iPad does so well.
The algorithms that we use today for speech recognition, for natural language translation, for chess playing, for logistics planning, have evolved remarkably in the past decade.
I for one am yet to see any major improvements in speech recognition in the last ten years. It seems that it plateaued around 1995-2000 and hasn't had any decent improvements since.
Meanwhile, speech recognition has seen an increase in deployments in things such as:
Speech recognition still has a long way to go me thinks.
Grötschel, an expert in optimization, observes that a benchmark production planning model solved
using linear programming would have taken 82 years to solve in 1988, using the computers and the linear
programming algorithms of the day. Fifteen years later – in 2003 – this same model could be solved in
roughly 1 minute, an improvement by a factor of roughly 43 million. Of this, a factor of roughly 1,000 was
due to increased processor speed, whereas a factor of roughly 43,000 was due to improvements in algo-
rithms! Grötschel also cites an algorithmic improvement of roughly 30,000 for mixed integer programming
between 1991 and 2008.
The prof is fibbing. The gains are mostly in the big on-die L2 cache with its fat, core clocked dedicated backside bus (thanks to Intergraph, and Intel for stealing it from them, then AMD, IBM, et al). The prof simply shrunk the code and data set to fit (mostly or wholly) in the 512KB/1MB cache of their 2003 era Athlon XP/Pentium IV. As with most apps, it's all in the ca$he baby, all in the ca$he.
When I started, we had 8 bit processors and no 32 bit arithmetic support. We had to code 32bit arithmetic ourselves. Today we have 64bit arithmetic, and shortly, 96 or 28 bit arithmetic will be common in a few years.
Leslie Satenstein Montreal Quebec Canada
Transistors and processing power help with all problems. Algorithms fall into two categories, generalized and specific. Generalized Algorithms help all problems that relate, but rely heavily on processing power. If you can identify a specialized problem, then a specific algorithm(s) can slash time to compute drastically. To achieve these 43,000 times improvements, one needs to know the data before computation. A better image compression algorithm, e.g. jpeg2000, is only useful if you have raster image data with large deployed color depth. If all images were compressed by competition between specific algorithms, such as gif, png, jp2000, then the server has to compute the compression of each, so that all users can enjoy the speed increase (network speed, drive storage space, ram storage, decompress time) that comes from smaller files. The server still has to compress the one file many times to select best outcome, which is not a speed increase at all for the server, even if all users of a website such as google would benefit from less bandwidth and processor speed. Specific algorithms need to be flawlessly implemented on all systems, taking considerable development time and money. Generalized algorithms combined with faster processors is how most net data will likely be transferred. The specific algorithms will likely live on servers where all data can be stored as highest quality data, e.g. jp2000, and then converted when needed to .jpg for end users, to maximize the number of users that can benefit from the service.