Use retained mode rendering for better performance

[jussi-kalliokoski]

Currently with large lists pick gets really slow on terminals that take a lot of time to render (I'm using iTerm2). Would be cool to avoid useless renders in between keystrokes in those cases, e.g. you type abcdefgh quickly and all of those are rendered and in some cases it can take seconds for the final list to be rendered.

[mptre]

Hi,
Could you provide some more info on the data you're passing along to
pick (number of lines) and the number of matches your query yields.
Ideally send the input as a gist here on GitHub (or whatever service) if
it does not contain any sensitive data and the query.

The slow rendering you're experiencing is most probably caused by the
search algorithm being slow. Delaying rendering completely while typing
the query gives the visual impression of a unresponsive UI. But, I have
a few ideas on how to speed-up the actual search.

[jussi-kalliokoski]

Could you provide some more info on the data you're passing along to
pick (number of lines) and the number of matches your query yields.
Ideally send the input as a gist here on GitHub (or whatever service) if
it does not contain any sensitive data and the query.

Unfortunately I can't share the data itself as it's a file listing on a private project, however the number of lines is ~3k and the number of matches decreases quite quickly after the first few keystrokes (about half the files start with the same prefix).

The slow rendering you're experiencing is most probably caused by the
search algorithm being slow.

I added some debug measurements and that doesn't seem to be the case, unless I'm a really fast at typing or rusty at timing stuff in C. It seems like most of the time is spent in printing stuff out to the tty, often taking around half a second to print, while input processing takes 0-10 (mostly 0) milliseconds for each keystroke, indicating that stuff is coming in faster than it can print. Which leads me to:

Delaying rendering completely while typing
the query gives the visual impression of a unresponsive UI.

I'm not indicating that there should be any added delay, just to keep reading the input and updating state until the tty has no more data buffered, and only then render the results. Can also be capped at a time limit (e.g. 1/60s) to allow intermediate renders when the dataset is huge and the search actually takes long.

[mptre]

Interesting, do you happen to have a large terminal window? What's the
output of:

$ stty size

[jussi-kalliokoski]

Yeah, I'm using a small scale on my MPB, so

113 364

[mptre]

Does the poll(2) call in filter_choices() ever return 1 while typing fast? You can fake fast typing by simply pasting your query. There's already a builtin mechanism to prevent unnecessary rendering but I vaguely recall some issues with poll and character devices on macOS.

[jussi-kalliokoski]

Yeah, it does return 1, but the rflags only have 0x20 (POLLNVAL) set. Well that's a bummer. :/ But I think it would be really nice to have this improvement on Linux at least, terminals tend to get really bad at rendering full screen at high resolutions on Linux as well, and just terminating the search won't help much with that since it does a flush after that anyways. But I nuked my Linux setup recently so I can't currently get any actionable metrics, so I'm ok with closing this for now, your call, thanks for the help. 👍 💪 ❤️

[mptre]

-v please!

I have to do some measurements first in order to verify that the changes
are actually worth performing first :-) In the process I found a
low-hanging fruit, see commit 1786606.

I'm unsure about the following "improvement":

I doubt this change would cause a noticeable increase in performance.

[mptre]

I'm ok with closing this for now, your call, thanks for the help.

I'd really like this to work on macOS as well. Does select(2) and
kqueue(2) suffer from the same limitation when it comes to character
devices?

[mptre]

Anyone runing macOS willing to look further into this? /cc @jussi-kalliokoski @calleerlandsson @mike-burns

[mike-burns]

Not running macOS but I might be able to find someone at thoughtbot NYC who is willing to try this.

For clarity, the experiment is: iTerm 2, 3500 lines of input, typing three characters should get it down to a few lines of input quickly.

yes | head -3500 > foo
echo no >> foo
echo no >> foo
echo no >> foo
cat foo | pick

?

[mptre]

Sorry I was referring to kqueue() and select() on macOS and if they
support character devices.

[jussi-kalliokoski]

Sorry, been pretty busy for a while, might have a moment next week to test kqueue() and select() on OS X next week if no one else has done it by then. :)

[mptre]

Ping @jussi-kalliokoski