Some years ago I helped diagnose an O(n²) bug in readline.
For years, I had problems pasting many lines of SQL in a psql session. It would slow down as it worked through the characters. One day the same happened in another shell, and it dawned on my that this was probably a problem with readline.
So I fired up a profiler and sure enough, something inside readline was recalculating something upon each character input with the work done proportional to all the characters already input.
I sent my findings to the mailing list, and Chet Ramey fixed it.
In the process, I discovered that wonky editing of long lines when resizing a terminal window was also fixable. When you resize, you change the line width, so readline needs to take that into account when it wraps the long lines. I think it did have code to do that at the time, but it just didn't kick in for some reason. Can't remember the details, but it does seem to work fine in psql today. That was another multi-year annoyance.
For years, I had problems pasting many lines of SQL in a psql session. It would slow down as it worked through the characters. One day the same happened in another shell, and it dawned on my that this was probably a problem with readline.
So I fired up a profiler and sure enough, something inside readline was recalculating something upon each character input with the work done proportional to all the characters already input.
I sent my findings to the mailing list, and Chet Ramey fixed it.
In the process, I discovered that wonky editing of long lines when resizing a terminal window was also fixable. When you resize, you change the line width, so readline needs to take that into account when it wraps the long lines. I think it did have code to do that at the time, but it just didn't kick in for some reason. Can't remember the details, but it does seem to work fine in psql today. That was another multi-year annoyance.