4 ms·

How quickly do algorithms improve?

57 points by npalli 5y ago

afpx 5y ago
http://algorithm-wiki.org/wiki/Main_Page http://algorithm-wiki.org/wiki/Main_Page
vmception 5y ago
The is a great study showing the algorithms have improved faster than Moore's law and advances in computing in many cases, if only the abstraction allowed for frontend and end users to experience these gains more often.
- taeric 5y ago
  I'm torn. A lot of the advances in algorithms required advances in memory capacity. Such that it seems odd to claim they outpaced Moore's law. True, but they could really only do it with said law.
  - vmception 5y ago
    I think these concepts do not compete. The gains are not linearly related to the capacity or speed of memory. The memory improvements accomplish just the removal of a bottleneck. You remove a bottleneck and everything flows faster instead of pools. So the increase itself can be greater than the same as the increase in the size of the corridor.
    - taeric 5y ago
      They were somewhat linear with relation to capacity of memory, but they also might not have been possible with capacity from a decade ago. This is easily seen if you look at fun algorithms such as BDDs. If you have the memory for them, they are amazingly fast. But, if you don't have the memory for it, it gets you nothing. Edit: removed a "not" that I didn't mean to type. :(
dataflow 5y ago
I'm curious how they went about this. A lot of algorithms "improve" older ones through taking e.g. a probabilistic approach (thus introducing failure modes that weren't there previously), or by using mechanical techniques like SIMD, or by parallelizing previously sequential solutions. How do you measure and compare improvements like that? The first one is hard to compare fairly, and the other ones can easily depend on the hardware. Of course there are cases where two algorithms solve exactly the same problem and one is just plain faster too, but did they really evaluate hundreds of those?
- deleted 5y ago
  [deleted]
- twotwotwo 5y ago
  The statement more directly backed up by the graphs in the paper is "changes in big-O did more to speed up solving large instances of some problems than did increase in SPECint," and they seem to mean really the same problem. The paper is at https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9540991 https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=954... It loses any feeling of objectivity, but it'd be interesting to broaden the question to approximate or specialized solutions, or things that make larger problems practical to solve without improving big-O. For some examples: - probabilistic sketches have been very successful at approximately answering questions that took a lot more work to answer exactly - adapting algorithms to hardware like GPUs doesn't reduce how many operations are done, but can make the operations cheaper/faster for the right problem - similarly, a good parallel or distributed approach to a problem doesn't change the big-O, but is often what allows scaling up to big n in practice - the B-tree (1970) did not improve on the big-O of the AVL tree (1962), but it made databases as we know them a lot more practical - LSM trees and compressed columnar storage also don't improve big-O, but provide big benefits for write-heavy and scan-heavy workloads Generally that pushes me more towards "hardware isn't responsible for all the advancements". Also, there's a fun conversation (happening out there, I assume) about how to value the sort of work that's more pragmatic than improving on a complexity bound but also more fundamental than just tuning some asm or C.
  - 5y ago
oluckyman 5y ago
In section III B (p.8) the paper states that “in 1982…Gries[24] devised another linear algorithm” for the maximum subarray problem. I remember that. Jon Bentley visited Cornell, and posed the problem to me and Gries together. We thought on it independently overnight and presented a linear solution to Bentley the next day. Gries had a simpler invariant, and I had simpler code (using min). I never knew he wrote the paper until now, and am not one of the several people he mentions in the Acknowledgement, although he does say “Bentley…challenged US with this problem”.
- Jensson 5y ago
  There are a lot of trivial papers to be written when a field is young. Someone has to write them even if the discovery wasn't hard to make.
civilized 5y ago
> Algorithms are sort of like a parent to a computer One of the less illuminating analogies I've heard. People should stick to "recipe" or "assembly instructions" and don't try to get so creative.
- fnord77 5y ago
  recipe / assembly instructions are not quite right, either. more like a process in a factory - material handling, coordination, input, output
- OneTimePetes 5y ago
  Creativity pollutes the communication, but a lack of creativity pollutes the purpose.
ape4 5y ago
How quickly to business requirements cancel out algorithm improvements.
gandalfgeek 5y ago
Link to full paper: https://ide.mit.edu/wp-content/uploads/2021/09/How_Fast_Do_Algorithms_Improve.pdf https://ide.mit.edu/wp-content/uploads/2021/09/How_Fast_Do_A... If you prefer video, I've made a short summary video: https://youtu.be/R0k80fSRLts https://youtu.be/R0k80fSRLts
nayuki 5y ago
[2021-09-22] https://news.ycombinator.com/item?id=28621057 https://news.ycombinator.com/item?id=28621057
deleted 5y ago
[deleted]
Marcus0 5y ago
Nice and amazing post this one is, thanks for sharing… https://www.advancedmd.online/ https://www.advancedmd.online/

57 points by npalli 5y ago

afpx 5y ago

http://algorithm-wiki.org/wiki/Main_Page http://algorithm-wiki.org/wiki/Main_Page

The is a great study showing the algorithms have improved faster than Moore's law and advances in computing in many cases, if only the abstraction allowed for frontend and end users to experience these gains more often.

taeric 5y ago
I'm torn. A lot of the advances in algorithms required advances in memory capacity. Such that it seems odd to claim they outpaced Moore's law. True, but they could really only do it with said law.
- vmception 5y ago
  I think these concepts do not compete. The gains are not linearly related to the capacity or speed of memory. The memory improvements accomplish just the removal of a bottleneck. You remove a bottleneck and everything flows faster instead of pools. So the increase itself can be greater than the same as the increase in the size of the corridor.
  - taeric 5y ago
    They were somewhat linear with relation to capacity of memory, but they also might not have been possible with capacity from a decade ago. This is easily seen if you look at fun algorithms such as BDDs. If you have the memory for them, they are amazingly fast. But, if you don't have the memory for it, it gets you nothing. Edit: removed a "not" that I didn't mean to type. :(

dataflow 5y ago

I'm curious how they went about this. A lot of algorithms "improve" older ones through taking e.g. a probabilistic approach (thus introducing failure modes that weren't there previously), or by using mechanical techniques like SIMD, or by parallelizing previously sequential solutions. How do you measure and compare improvements like that? The first one is hard to compare fairly, and the other ones can easily depend on the hardware. Of course there are cases where two algorithms solve exactly the same problem and one is just plain faster too, but did they really evaluate hundreds of those?

deleted 5y ago
[deleted]
twotwotwo 5y ago
The statement more directly backed up by the graphs in the paper is "changes in big-O did more to speed up solving large instances of some problems than did increase in SPECint," and they seem to mean really the same problem. The paper is at https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9540991 https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=954... It loses any feeling of objectivity, but it'd be interesting to broaden the question to approximate or specialized solutions, or things that make larger problems practical to solve without improving big-O. For some examples: - probabilistic sketches have been very successful at approximately answering questions that took a lot more work to answer exactly - adapting algorithms to hardware like GPUs doesn't reduce how many operations are done, but can make the operations cheaper/faster for the right problem - similarly, a good parallel or distributed approach to a problem doesn't change the big-O, but is often what allows scaling up to big n in practice - the B-tree (1970) did not improve on the big-O of the AVL tree (1962), but it made databases as we know them a lot more practical - LSM trees and compressed columnar storage also don't improve big-O, but provide big benefits for write-heavy and scan-heavy workloads Generally that pushes me more towards "hardware isn't responsible for all the advancements". Also, there's a fun conversation (happening out there, I assume) about how to value the sort of work that's more pragmatic than improving on a complexity bound but also more fundamental than just tuning some asm or C.
- 5y ago

oluckyman 5y ago

In section III B (p.8) the paper states that “in 1982…Gries[24] devised another linear algorithm” for the maximum subarray problem. I remember that. Jon Bentley visited Cornell, and posed the problem to me and Gries together. We thought on it independently overnight and presented a linear solution to Bentley the next day. Gries had a simpler invariant, and I had simpler code (using min). I never knew he wrote the paper until now, and am not one of the several people he mentions in the Acknowledgement, although he does say “Bentley…challenged US with this problem”.

Jensson 5y ago
There are a lot of trivial papers to be written when a field is young. Someone has to write them even if the discovery wasn't hard to make.

civilized 5y ago

> Algorithms are sort of like a parent to a computer One of the less illuminating analogies I've heard. People should stick to "recipe" or "assembly instructions" and don't try to get so creative.

fnord77 5y ago
recipe / assembly instructions are not quite right, either. more like a process in a factory - material handling, coordination, input, output
OneTimePetes 5y ago
Creativity pollutes the communication, but a lack of creativity pollutes the purpose.

ape4 5y ago

How quickly to business requirements cancel out algorithm improvements.

gandalfgeek 5y ago

Link to full paper: https://ide.mit.edu/wp-content/uploads/2021/09/How_Fast_Do_Algorithms_Improve.pdf https://ide.mit.edu/wp-content/uploads/2021/09/How_Fast_Do_A... If you prefer video, I've made a short summary video: https://youtu.be/R0k80fSRLts https://youtu.be/R0k80fSRLts

nayuki 5y ago

[2021-09-22] https://news.ycombinator.com/item?id=28621057 https://news.ycombinator.com/item?id=28621057

deleted 5y ago

[deleted]

Marcus0 5y ago

Nice and amazing post this one is, thanks for sharing… https://www.advancedmd.online/ https://www.advancedmd.online/