3 ms·
There used to be a quadratic algorithm in character input in readline, the library that many common shells are using to parse commands. So if you copy-pasted a
by olau 6y ago
There used to be a quadratic algorithm in character input in readline, the library that many common shells are using to parse commands. So if you copy-pasted a somewhat long list into something like Postgres or the Python shell, it would take a lot of time because it had to check a couple of things on each input, and that somehow involved checking the existing characters in the input (I've forgotten the details).
I think that's a really classical case of O(n^2). You have a linear algorithm (n), and then run it on each instance you insert (n) so n^2.
It bothered me for several years, until I eventually did some profiling and contacted the readline (and bash) maintainer who fixed it.
This is about 5 years ago.
There's also another readline-related problem in several shells that they don't discover if you resize the terminal window. I can't remember if I raised that too. It sometimes amazes me that very few people appear to ever look at or debug our common infrastructure.
- jeffbee 6y ago`java` used to have quadratic command line parsing, which nobody much noticed as long as unixes had fixed ARG_MAX, but it wasn't very long after Linux got arbitrary-length arguments that the first person discovered that java might take a week to parse a really big command line. I personally reported this defect and I don't know if they ever fixed it. https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6728845 https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6728845
- btilly 6y agoThere are a lot of such. When Larry Wall wrote the map operation for Perl, he just took the grep operation, added the function call, and added a resize if it was needed. The result is that the common "turn a list into a hash with map" operation was quadratic because it did the resize on every input element. I fixed that. I later noticed that unshift did the same thing for a different reason and fixed that. And then I looked at Ruby's source code and saw all the same performance mistakes. Exactly as the blog says, n^2 is fast enough to make it into production and slow enough to fall over once there. We focus on making it right, and only return to making it fast when there is need. And most of the time the cause is a hidden n^2 that we never thought about.
- MagerValp 6y agoIs that related to checkwinsize sometimes becoming unset? I’ve never managed to find a pattern to when it happens.