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
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.
(Once more thing I might put in the list of "not a big-O improvement but a rearrangement that made new things possible" is an essentially economic observation Google and others made: once you're planning to serve enough queries/sec, putting unreasonable-sounding quantities of data into expensive storage (like much of your Web search index in RAM) starts to make sense. I saw it referred to as "online data-intensive" at https://perspectives.mvdirona.com/2012/03/power-management-o... and linked papers but don't know if it has a more common name.)
Yeah, looks like the answer to my question is their paragraph about "exact algorithm, exact solution" on page 8. Sadly their supplementary materials don't seem to be online yet, so we'll have to see how they're comparing, but it looks interesting.
Really depends on the baseline, it’s easy to accidentally write something that would take billions of years to finish on real data but is fine for a mock-up. Caching often seems like the first optimization simply because systems tend to already be optimized enough to be useful.
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.