ble.sh:Perf: menu-complete chokes on directory with 6k+ files

[banoris]

In vanilla bash, it will warn user for many files:

$ vim somedir/
There are 3038 rows, list them anyway? [n/y]

Takes ble.sh ~30s to display files in menu-complete. Investigate further.

[akinomyoga]

I'm interested in this issue. May I ask what is your operating system, ble.sh version and Bash version?

This must be a general performance issue of ble.sh which is written in Bash script, but if I can identify the bottleneck maybe I can improve the performance. If you are using ble-0.3, I recommend you switch to the devel version (master branch) because there are several performance improvements in the devel version thanks to the reports from several other users.

I now have tried 10k files in a directory with the latest version of ble.sh and bash-4.4, 5.0, and 5.1 in Linux. In my environment, it seems to take about 15s to display the menu when bash-completion is enabled. When bash-completion is not loaded, it just takes about 3s. Since it doesn't block the user inputs, the bottleneck must be somewhere in the ble.sh code for the postprocessing of bash-completion output. I'll later investigate in detail.

[banoris]

I haven't check much details, maybe later once I got more info I'll file an issue to the main ble.sh repo.

take about 15s to display

Yes, I can reproduce this multiple times now. Not sure how I got ~30s last time, maybe one of those rare case, or I didn't check the clock properly.

Version info:

$ echo $BLE_VERSION 
0.4.0-devel3+a6b4e2c

$ echo $BASH_VERSION
4.2.46(2)-release

$ lsb_release -a
# RHEL 7.9

[akinomyoga]

OK! Thank you!

[akinomyoga]

I have investigated the bottleneck in the directory with many files. It turned out that there are several reasons that make the menu completion slow. The fixes and workarounds for some bottlenecks are in the mater branch of ble.sh, so you can update ble.sh by ble-update. The workarounds for the other bottlenecks need some user configuration as described below.

1. Delayed initialization for menu items did not work (~ 8 secs)[Fixed]

I have fixed it in commit akinomyoga/ble.sh@acc9661. ble.sh calculates the sizes of menu items in the terminal to determine the layout of the items. I intended to calculate the sizes of only the necessary items for the first page of the menu, but ble.sh actually had been calculating the sizes of all the items due to the bug in an expression to calculate some position. The fix reduces the time to about 1--3 seconds.

2. Old _filedir from /etc/bash_completion.d/redefine_filedir (~ 4 secs)

There is a shell function _filedir defined by bash-completion. It turned out that the implementation of _filedir in a certain version of bash-completion was very slow. I am using the latest version of bash-completion, but somehow the latest version of _filedir is overwritten by an older version defined in /etc/bash_completion.d/redefine_filedir by Fedora 31 distribution. This caused the second bottleneck in my environment.

I'm not sure if the same happens in your environment, but if you find the following lines in your bash-completion (probably /usr/share/bash-completion/bash_completion if you are using bash-completion from the RHEL distribution), you can instead download and use the latest version of bash-completion:

_filedir()
{

...

    x=$( compgen -d -- "$cur" ) &&
    while read -r tmp; do
        toks+=( "$tmp" )
    done <<< "$x"

...
} # _filedir()

-----[ Edit: I have suggested the following change in the upstream scop/bash-completion#667 ]-----

In addition, if /usr/share/bash-completion/bash_completion contains the above lines and there is also a file /etc/bash_completion.d/redefine_filedir from the RHEL distribution, you need to disable the setting somehow. I don't know what is the most proper way to disable this, but probably you need to edit your own bash_completion in the following way:

diff --git a/bash_completion b/bash_completion
index 697e7e2b..733c16a2 100644
--- a/bash_completion
+++ b/bash_completion
@@ -39,7 +39,7 @@ fi

 # Blacklisted completions, causing problems with our code.
 #
-_comp_init_blacklist_glob='@(acroread.sh)'
+_comp_init_blacklist_glob='@(acroread.sh|redefine_filedir)'

 # Turn on extended globbing and programmable completion
 shopt -s extglob progcomp

I think I'll later open a discussion in bash-completion about this issue.

3. Quoting the completion candidates depending on the grammatical context (~ 2 secs) [Optimized]

The third bottleneck was the calculation of the quoting of the completion candidates. For example, if the candidate contains special characters such as (, $, etc., they need to be quoted in the inserted text as \(, \$, etc. Since ble.sh needs to obtain the common prefix of the inserted texts of candidates, it needs to calculate the quoting of all the candidates. This quoting for 10k files took about two seconds in my environment.

In commit akinomyoga/ble.sh@a0b2ad2, I have re-implemented the quoting in awk (which is faster than Bash implementation). Now ble.sh switches to the awk implementation when the number of candidates is greater or equal to 500.

4. Layout and displaying of menu items (~ 3 secs)

After solving all the bottlenecks above, it still takes about four seconds until the menu is shown when I use the full screen (see below).

If we want to show this many items on one page, the three-second delay is inevitable (as far as it is written in slow Bash script). If you would like to reduce this delay, you can decrease the number of items shown on a single page using the settings bleopt complete_menu_maxlines and bleopt menu_align_min (I have added this new option menu_align_min in commit akinomyoga/ble.sh@22a2449):

# blerc

# Example
bleopt complete_menu_maxlines=10
bleopt menu_align_min=12

The setting complete_menu_maxlines controls the maximal number of lines used by the menu page. The setting menu_align_min controls the minimal horizontal spacing between the menu items. After this setting, the number of items on a single page reduces as in the following example, so that the delay would be shorter.

[banoris]

This is very good findings! I will duplicate this to ble.sh repo for documentation purposes.

[akinomyoga]

OK! Thanks!