slow ssh host tab completion when many hosts

slow ssh host tab completion when many hosts

[Peter Palfrader]

Hi!

with a large ~/.ssh/config, ssh tab completion for hostnames can take a
long time.

I'm on zsh 5.8 in Debian 11, but for testing purposes I am using
Completion/Unix/Command/_ssh and Completion/Unix/Type/_ssh_hosts from
current git master.

As an extreme example, with this as my ~/.ssh/config:
  for i in `seq -w 1 10000 `; do echo "Host h$i"; echo "  PreferredAuthentications publickey"; done > ssh_config
"ssh h000<tab><tab>" takes about 20 seconds on my laptop to show me the
list of matching hosts.

I suspect, that one of the issues is in _ssh_hosts where it always pops
the first element of an array.  At a guess this causes quadratic
runtime behaviour.

The following patch improves the behaviour significantly (to about
2secs):


From bf4280bf4d9c6074fdb01b4817baafefb6d6e12f Mon Sep 17 00:00:00 2001
From: Peter Palfrader <peter@palfrader.org>
Date: Wed, 22 Sep 2021 10:25:08 +0200
Subject: [PATCH] Faster ~/.ssh/config processing

When iterating over the ssh config file, iterate over the array linearly
instead of always processing the first and then removing it from the
list.  This speeds up processing significantly.
---
 Completion/Unix/Type/_ssh_hosts | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/Completion/Unix/Type/_ssh_hosts b/Completion/Unix/Type/_ssh_hosts
index bd5366425..67416ab2e 100644
--- a/Completion/Unix/Type/_ssh_hosts
+++ b/Completion/Unix/Type/_ssh_hosts
@@ -20,8 +20,9 @@ if [[ -r $config ]]; then
   local key line host
   local -a lines=("${(@f)$(<"$config")}") 2>/dev/null
   local -a match_args
-  while (($#lines)); do
-    IFS=$'=\t ' read -r key line <<<"${lines[1]}"
+  local idx=1
+  while [[ $idx -le $#lines ]]; do
+    IFS=$'=\t ' read -r key line <<<"${lines[$idx]}"
     if [[ "$key" == ((#i)match) ]]; then
       match_args=(${(z)line})
       while [[ $#match_args -ge 2 ]]; do
@@ -35,7 +36,7 @@ if [[ -r $config ]]; then
     fi
     case "$key" in
     ((#i)include)
-      lines[1]=("${(@f)$(cd $HOME/.ssh; cat ${(z)~line})}") 2>/dev/null;;
+      lines[$idx]=("${(@f)$(cd $HOME/.ssh; cat ${(z)~line})}") 2>/dev/null;;
     ((#i)host(|name))
       for host in ${(z)line}; do
 	case $host in
@@ -43,7 +44,7 @@ if [[ -r $config ]]; then
 	(*) config_hosts+=("$host") ;;
 	esac
       done ;&
-    (*) shift lines;;
+    (*) idx=$((idx + 1));;
     esac
   done
   if (( ${#config_hosts} )); then
-- 
2.30.2


For your consideration :)
Cheers,
-- 
                            |  .''`.       ** Debian **
      Peter Palfrader       | : :' :      The  universal
 https://www.palfrader.org/ | `. `'      Operating System
                            |   `-    https://www.debian.org/

Re: slow ssh host tab completion when many hosts

[Bart Schaefer]

On Wed, Sep 22, 2021 at 1:31 AM Peter Palfrader
<zsh-workers=zsh.org@lists.palfrader.org> wrote:
>
> I suspect, that one of the issues is in _ssh_hosts where it always pops
> the first element of an array.  At a guess this causes quadratic
> runtime behaviour.

"shift" would imply a copy of the tail of the array, yes.

> The following patch improves the behaviour significantly (to about
> 2secs):

This looks OK, but it can be improved a bit further.  Firstly,
anywhere you are writing lines[$idx] you can just use lines[idx]
because everything inside the square brackets of an array dereference
is treated as a math expression.  Secondly:

> @@ -43,7 +44,7 @@ if [[ -r $config ]]; then
>         (*) config_hosts+=("$host") ;;
>         esac
>        done ;&
> -    (*) shift lines;;
> +    (*) idx=$((idx + 1));;
>      esac
>    done
>    if (( ${#config_hosts} )); then

Instead of the assignment idx=$((idx + 1))
you can use the statement ((idx++))