4 ms·

Reminds me of this evergreen tweet from ryg: https://mobile.twitter.com/rygorous/status/1271296834439282690 https://mobile.twitter.com/rygorous/status/127129683

Reminds me of this evergreen tweet from ryg: https://mobile.twitter.com/rygorous/status/1271296834439282690 https://mobile.twitter.com/rygorous/status/12712968344392826... if you made something 2x faster, you might have done something smart if you made something 100x faster, you definitely just stopped doing something stupid

hyperbovine 4y ago
Meh. This tweet is a lot less clever than it seems. Shave a factor of n off the complexity of your your algorithm, as happens regularly in CS and informatics, and have all the 1000x speedups you want.
- squeaky-clean 4y ago
  If you shave a factor of n off of your algorithm, it usually isn't the same algorithm anymore. That's what they mean, the previous algorithm choice was "stupid" and you've stopped doing something stupid.
  - whatshisface 4y ago
    With that kind of creative interpretation almost any statement can be true. :)
  - Ar-Curunir 4y ago
    That's like saying, everybody struggling to solve SAT problems is just being stupid; just prove P = NP and solve the damn thing!
    - squeaky-clean 4y ago
      It's just an idiom and not meant to be taken so literally. Basically if you're getting a 100x improvement, you're jumping from one paradigm to another. And those are probably already solved algorithms / invented datastructures. If you're doing something novel and "clever" to speed up your algorithm for your circumstances, it's probably going to be under a 5x improvement. Or to continue the SAT analogy, if you're doubling your SAT score (e.g. 700 to 1400) you're getting smarter. If your 100x'ing your SAT score, the best possible previous score you could have gotten is a 16. Which would mean you got about one and a half questions correct across both the reading and math SAT.
- jakeinspace 4y ago
  I think it’s fair to classify using O(n^2) sorting as stupid (if the input size is significant). In numerical computing, using a naive routine for computing eigenvalues in O(n^4) would equally be considered stupid, unless the input sizes are known to be small of course.
- quickthrower2 4y ago
  Just prove P = NP while you are at it
- yieldcrv 4y ago
  I love the quote, I’ll be using it the rest of my life
- dan-robertson 4y ago
  I don’t think it seems clever so much as pithy? I don’t think it’s necessarily about algorithms so much as it is a claim that the main way to be 1000x slower is by doing 999x times too much work or waiting. An example that is basically unrelated to complexity theory is something like talking to a distant service but keeping a small number of requests because eg you were worried about load or didn’t notice you were waiting for acks or create a new tcp connection for each request or have a small sendbuf or somehow send way too fast and get rate limited and need to retry.
- amscanne 4y ago
  I believe the underlying point is that the bigger the N, the more obvious it probably is. If you’re in 1000x territory, there’s a strong likelihood that the improvement is so obvious that doing the opposite might be called “stupid”.
canucker2016 4y ago
I recall the Programming Pearls article from the Sept. 1984 issue of the Communications of the ACM journal, which compared various algorithms to determine the max sum of a continuous subarray of an array. The article showed how a linear, O(N), algorithm running on a lowly 8-bit CPU can beat a cubic algorithm, O(N^3), running on a Cray supercomputer, when N is sufficiently large. see https://www.cs.rpi.edu/~moorthy/Courses/CSCI2300/p865-bentley.pdf https://www.cs.rpi.edu/~moorthy/Courses/CSCI2300/p865-bentle...
thatguymike 4y ago
Or, you started doing something stupid!
__turbobrew__ 4y ago
if you made something 100x faster you don’t understand how mmap works

hyperbovine 4y ago

Meh. This tweet is a lot less clever than it seems. Shave a factor of n off the complexity of your your algorithm, as happens regularly in CS and informatics, and have all the 1000x speedups you want.

squeaky-clean 4y ago
If you shave a factor of n off of your algorithm, it usually isn't the same algorithm anymore. That's what they mean, the previous algorithm choice was "stupid" and you've stopped doing something stupid.
- whatshisface 4y ago
  With that kind of creative interpretation almost any statement can be true. :)
- Ar-Curunir 4y ago
  That's like saying, everybody struggling to solve SAT problems is just being stupid; just prove P = NP and solve the damn thing!
  - squeaky-clean 4y ago
    It's just an idiom and not meant to be taken so literally. Basically if you're getting a 100x improvement, you're jumping from one paradigm to another. And those are probably already solved algorithms / invented datastructures. If you're doing something novel and "clever" to speed up your algorithm for your circumstances, it's probably going to be under a 5x improvement. Or to continue the SAT analogy, if you're doubling your SAT score (e.g. 700 to 1400) you're getting smarter. If your 100x'ing your SAT score, the best possible previous score you could have gotten is a 16. Which would mean you got about one and a half questions correct across both the reading and math SAT.
jakeinspace 4y ago
I think it’s fair to classify using O(n^2) sorting as stupid (if the input size is significant). In numerical computing, using a naive routine for computing eigenvalues in O(n^4) would equally be considered stupid, unless the input sizes are known to be small of course.
quickthrower2 4y ago
Just prove P = NP while you are at it
yieldcrv 4y ago
I love the quote, I’ll be using it the rest of my life
dan-robertson 4y ago
I don’t think it seems clever so much as pithy? I don’t think it’s necessarily about algorithms so much as it is a claim that the main way to be 1000x slower is by doing 999x times too much work or waiting. An example that is basically unrelated to complexity theory is something like talking to a distant service but keeping a small number of requests because eg you were worried about load or didn’t notice you were waiting for acks or create a new tcp connection for each request or have a small sendbuf or somehow send way too fast and get rate limited and need to retry.
amscanne 4y ago
I believe the underlying point is that the bigger the N, the more obvious it probably is. If you’re in 1000x territory, there’s a strong likelihood that the improvement is so obvious that doing the opposite might be called “stupid”.

canucker2016 4y ago

I recall the Programming Pearls article from the Sept. 1984 issue of the Communications of the ACM journal, which compared various algorithms to determine the max sum of a continuous subarray of an array. The article showed how a linear, O(N), algorithm running on a lowly 8-bit CPU can beat a cubic algorithm, O(N^3), running on a Cray supercomputer, when N is sufficiently large. see https://www.cs.rpi.edu/~moorthy/Courses/CSCI2300/p865-bentley.pdf https://www.cs.rpi.edu/~moorthy/Courses/CSCI2300/p865-bentle...

thatguymike 4y ago

Or, you started doing something stupid!

__turbobrew__ 4y ago

if you made something 100x faster you don’t understand how mmap works