« Previous | Next » 

Revision e0f470ac

IDe0f470acb66ce1fa998b13b430fef43beec13fc6

Added by Iustin Pop over 9 years ago

Fix job completion with big job queues

Accidentally stumbled upon this while testing unrelated code on a
machine with ~3K active jobs - the bash completion unittest was
hanging.

Upon investigation, it turns out that bash's ${var//pattern/repl/} is
probably quadratic in the size of input (or worse, even):

$ touch job-{1..500}
$ time ( a=$(echo job-*); echo ${a//job-/}| wc -c; )
1892
real    0m0.597s
user 0m0.590s
$ touch job-{1..1000}
$ time ( a=$(echo job-*); echo ${a//job-/}| wc -c; )
3893
real    0m4.654s
user 0m4.580s

We can easily fix this if we change to array-based substitution (once
per element):

$ time ( a=($(echo job-*)); echo ${a[*]/job-/} |wc -c; )
3893
real    0m0.028s
user 0m0.010s
$ touch job-{1..10000}
$ time ( a=($(echo job-*)); echo ${a[*]/job-/} |wc -c; )
48894
real    0m0.233s
user 0m0.220s

This means that exactly when the master node is busy processing many
jobs, we could accidentally start consuming lots of CPU in the bash
completion, which is not good.

Note: the code might have problems with filenames containing spaces (I
didn't reset the IFS, etc.), but the original code had the same issue,
I think.

Signed-off-by: Iustin Pop <>
Reviewed-by: Michael Hanselmann <>

Files

  • added
  • modified
  • copied
  • renamed
  • deleted

View differences