jtdaugherty / vty

A high-level ncurses alternative written in Haskell
BSD 3-Clause "New" or "Revised" License
319 stars 57 forks source link

perf: Improve performance for large bracketed pastes. #232

Closed iphydf closed 2 years ago

iphydf commented 2 years ago

Speedup is about an order of magnitude and change (as expected: 23 times faster for 300KB: 93s -> 4s).

The current algorithm has polynomial time complexity. The new algorithm runs in linear time and is generally much more efficient because it operates on packed byte strings instead of linked lists of Char.

Addresses part of https://github.com/jtdaugherty/vty/issues/231, but there is more to do.

Some timing:

image

As we can see, it's still O(n^2) overall, probably because of the calls to bracketedPasteFinished. I'll investigate that next. The constant factor overall is much lower now:

Before: 2.866E-6n^3  - 1.784E-4n^2 + 0.114n - 2.622
After:  -1.389E-8n^3 + 5.53E-5n^2  - 1.604E-3n + 0.273
iphydf commented 2 years ago

I tried to follow the style of surrounding code. Let me know if there's anything style-wise to fix.

Regarding start and end: if you're worried about performance of those being inside the function, don't be, they are lifted by the compiler. If style-wise it's not OK, I'm happy to lift them manually, though.

jtdaugherty commented 2 years ago

Thank you for your work on this!

jtdaugherty commented 2 years ago

This change is now released in 5.35.