[bash,zsh] Reduce the number of fork & exec

[akinomyoga]

The current implementation of the shell function __fzf_list_hosts unnecessarily creates many processes to parse the files to list hostnames. The performance can be improved by simplifying the pipelines and reducing the number of forks. Each pipeline can actually be processed by a single AWK script. The number of forks for a single call of __fzf_list_hosts is reduced from 17 to 4 by this PR (I'd say 17 forks could be extremely slow up to several seconds depending on the system).

If the size of the processed data is megabytes or more and the system has many cores, one may expect a performance improvement by chaining the commands (which perform non-trivial tasks) in a pipeline and processing them in parallel. However, the ssh config, the known_hosts records, and /etc/hosts would never have the size of megabytes, so the fork & exec cost of the processes is much more expensive than the gain by parallelizing the tasks. Also, each task is very simple, so it is non-trivial whether the gain is really larger than the loss with the pipe I/O cost.

I confirmed that the output of __fzf_list_hosts is unaffected by this change in my environment (For example, one can check the result of __fzf_list_hosts | sha256sum before and after the change).

• One possible change by this PR would be that it now correctly processes a TAB separator in .ssh/config, which was not processed in the current master.
• Another thing is that, the current master uses \s in the regular expressions, but \s is the GNU extension and is not POSIX. This PR uses the POSIX bracket expression [[:blank:]] to avoid using non-portable features.

[junegunn]

Thanks.

extremely slow up to several seconds depending on the system

Do you actually notice a slowdown in practice? I'd assumed the difference would be negligible on modern systems. Maybe it's more apparent on embedded or resource-constrained devices? I have no experience with such systems.

The reason I'm asking is that I'm a bit concerned about the maintainability of the script, because there are more users familiar with the basic Unix tools than with non-trivial awk scripting.

[akinomyoga]

Do you actually notice a slowdown in practice? I'd assumed the difference would be negligible on modern systems. Maybe it's more apparent on embedded or resource-constrained devices? I have no experience with such systems.

I haven't experienced it with my daily sessions. To talk about the general situation, one of the systems that have a large fork & exec delay is Cygwin and the Cygwin-based systems such as MSYS2. MSYS2 is widely used in, e.g., Git for Windows, and fzf is available at /mingw/bin/fzf with the mingw-w64-x86_64-fzf package. Although I don't use MSYS2 daily, the result of time __fzf_list_hosts in my environment was about 0.5-0.7 secs. The time for fork & exec largely depends on the antivirus software activated in the system, so it can even be slower depending on the choice of the antivirus software.

The reason I'm asking is that I'm a bit concerned about the maintainability of the script, because there are more users familiar with the basic Unix tools than with non-trivial awk scripting.

Actually, the original reason I submit this change is that I would like to fix other problems in a subsequent PR I plan to submit (I wanted to separate PRs for changing the implementation style and for changing the actual behaviors). If we stick with the current style, an even larger number of simple commands need to be chained to fix the problems. I'm afraid that the pipelines will soon grow up to contain dozens of commands, so I think the current way isn't maintainable in another sense.

As the current implementation already uses AWK's for loop, I think what would be new in the AWK scripts in this PR would be the special variable NR, the keyword next, and standard functions tolower, match, gsub, and split. I think NR and next are pretty basic and common AWK constructs. I think what would be non-trivial is just the knowledge of standard functions, which one might search man awk or the POSIX standard.

[junegunn]

Although I don't use MSYS2 daily, the result of time __fzf_list_hosts in my environment was about 0.5-0.7 secs.

Thanks. That was what I wanted to know.

Actually, the original reason I submit this change is that I would like to fix other problems in a subsequent PR I plan to submit (I wanted to separate PRs for changing the implementation style and for changing the actual behaviors)

So what do you have in mind? I think it's okay to discuss it here as well, as long as you split the commits. But I'll leave it up to you.

I think what would be new in the AWK scripts in this PR would be the special variable NR, the keyword next, and standard functions tolower, match, gsub, and split

I was a little concerned because:

• I'm not an awk expert myself. Never really tried to use it other than in one-liners.
• I remember this pull request where I learned different awk versions implement things differently, which caused some headache. If we can be sure these constructs are standards and supported by all awk implementation, it's probably fine.

[akinomyoga]

Behavioral fixes to __fzf_list_hosts

So what do you have in mind? I think it's okay to discuss it here as well, as long as you split the commits. But I'll leave it up to you.

I have several fixes (see 4c1f1f8..ec526dc). I originally intended to submit these in a single PR later. I thought of pushing these to this PR, but the fixes for the AWK compatibilities became large (as explained below), and also, the number of changes for those fixes is not so small. I'm currently feeling like discussing the current refactoring and the fixes separately (in this PR and the next PR, respectively).

AWK compatibility

I was a little concerned because:

• I'm not an awk expert myself. Never really tried to use it other than in one-liners.
• I remember this pull request where I learned different awk versions implement things differently, which caused some headache. If we can be sure these constructs are standards and supported by all awk implementation, it's probably fine.

The functions used in this PR are all the standard ones defined by the POSIX standard. Thus, in principle, the AWK script in this PR should work in all the standard-conforming implementations of awk. However, as you worry about it, there are many historical bugs and quirks of the awk implementations, which failed to follow the POSIX standard. Here, a non-trivial question is "how much we should care about historical bugs and quirks?".

The error message awk: towc: multibyte conversion failure on: you saw in #3313 is a quirk of macOS awk. macOS awk is a fork of nawk; nawk hadn't supported the UTF-8 encoding, but Apple added a patch for the UTF-8 support. The problem is that the quality of the patch added by Apple was poor; i.e., it just doesn't do anything when there is any data in the input that cannot be interpreted by UTF-8. This annoyed me a lot in https://github.com/akinomyoga/ble.sh/issues/190 and https://github.com/akinomyoga/ble.sh/issues/515. This could be worked around by setting LC_CTYPE=C LC_COLLATE=C (or LC_ALL=C to force all locale categories altogether). However, this quirk affects regardless of the complexity of the AWK script. For example, this quirk also affects the implementation by the pipeline in the current master. This affects even the simplest one-liner awk '{print}', so one should not use awk at all if you worry about this.

Another incompatibility relevant to the present case is that some old mawk versions did not support the POSIX bracket expression [[:name:]] until 20090705 (which is still shipped with Ubuntu 18.04 LTS, unfortunately). This was https://github.com/akinomyoga/ble.sh/issues/335. However, the implementation by the current master also has a similar issue of using the GNU extention \s, so we can't say that rewriting the pipeline into the AWK script really increases the chances of the compatibility issues.

Solaris awk is also a problematic implementation. In Solaris by default, awk available in PATH is not a standard-conforming implementation of awk, but a version compatible with the ancient implementation of 1977 awk in the original UNIX. To use the standard-conforming implementation of awk in Solaris, one needs to explicitly call /usr/xpg4/bin/awk (or the user needs to prepend /usr/xpg4/bin to PATH). This also affects awk calls in the current master. For example, awk -v user="$user" used on the following line does not work with Solaris awk:

https://github.com/junegunn/fzf/blob/0a06fd6f633fdf07ec04b2a9e92a266207240fb8/shell/completion.bash#L503

If I remember correctly, !seen[b]++ appearing in the AWK script in key-bindings.bash added by the mentioned #3313 wouldn't work with Solaris awk either.

I tried to address the above AWK compatibility issue for this PR, but it turned out that all existing uses of awk are affected by those compatibility issues, and the code range affected by the compatibility workarounds became too large (see 4d7d118..4c1f1f8 for the change set). Also, I realized that we also need to apply the same changes to the Zsh integration codes. I'm now thinking of separating the PR for the AWK compatibility.

---

For now, I just simplified the AWK script not to use split() and force-pushed (commit 9c66ce28). I also added the same changes to the Zsh integration script. To do it I needed to include the similar changes to #4405 but for the Zsh integration (commit bf858493).

[junegunn]

Thanks for the detailed comment. I can feel the pain you had to go through :)

I'll take a closer look later today.

[junegunn]

Merged, thanks a lot!

[akinomyoga]

Thanks!