Re: [PATCH 3/3] completion: improve shell expansion of items

From: Jeff King <peff@peff.net>
Date: Sep 27, 2012, 06:43 UTC
Message-ID: <20120927064338.GA4789@sigill.intra.peff.net>
In-Reply-To: <20120927062855.GA22890@sigill.intra.peff.net>

On Thu, Sep 27, 2012 at 02:28:55AM -0400, Jeff King wrote:

Show 25 quoted lines

> Thanks for reminding me to time. I noticed your a31e626 while digging in
> the history, but forgot that I wanted to do a timing test. Sadly, the
> results are very discouraging. Doing a similar test to your 10,000-refs,
> I get:
> 
>   $ refs=$(seq 1 10000)
> 
>   $ . git-completion.bash.old
>   $ time __gitcomp_nl "$refs"
>   real    0m0.065s
>   user    0m0.064s
>   sys     0m0.004s
> 
>   $ . git-completion.bash.new
>   $ time __gitcomp_nl "$refs"
>   real    0m1.799s
>   user    0m1.828s
>   sys     0m0.036s
> 
> So, a 2700% slowdown. Yuck.
> 
> I also tried running it through sed instead of iterating in bash. I know
> that some people will not like the fork, but curiously enough, it was
> not that much faster. Which makes me wonder if part of the slowdown is
> actually bash unquoting the result in compgen.

Ah. The problem is that most of the load comes from my patch 4/3, which does a separate iteration. Here are the numbers after just patch 3:

  $ time __gitcomp_nl "$refs"
  real    0m0.344s
  user    0m0.392s
  sys     0m0.040s

Slower, but not nearly as painful. Here are the numbers using sed[1] instead:

  $ time __gitcomp_nl "$refs"
  real    0m0.100s
  user    0m0.084s
  sys     0m0.016s

So a little slower, but probably acceptable. We could maybe do the same trick on the output side (although it is a little trickier there, because we need it in a bash array). Of course, this is Linux; the fork for sed is way more expensive on some systems.

Still, I'd be curious to see it with the callers (e.g., __git_refs) doing their own quoting. I'd worry that it would become a maintenance headache, but perhaps we don't have that many lists we feed (there are a lot of calls to gitcomp_nl, but they are mostly feeding __git_refs).

-Peff

[1] For reference, that patch is:

diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index 1fc43f7..5ff3742 100644
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash
@@ -225,16 +225,15 @@ __git_quote()
 fi
 fi
 
-# Quotes each element of an IFS-delimited list for shell reuse
+# Quotes each element of a newline-delimited list for shell reuse
 __git_quote()
 {
-	local i
-	local delim
-	for i in $1; do
-		local quoted=${i//\'/\'\\\'\'}
-		printf "${delim:+$IFS}'%s'" "$quoted"
-		delim=t
-	done
+	echo "$1" |
+	sed "
+	  s/'/'\\\\''/g
+	  s/^/'/
+	  s/$/'/
+	"
 }
 
 # Generates completion reply with compgen, appending a space to possible