Skip to content
  • Iustin Pop's avatar
    Fix job completion with big job queues · e0f470ac
    Iustin Pop authored
    
    
    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: default avatarIustin Pop <iustin@google.com>
    Reviewed-by: default avatarMichael Hanselmann <hansmi@google.com>
    e0f470ac