Hi Ole,
Thanks for GNU parallel, we use it a lot! While debugging a slow startup we
ran into a performance issue and put together a patch for it. Details below,
and the patch is attached.
If you pass a big command template to parallel and it has lots of "{" in it
but nothing that actually matches a replacement string, building the job
takes
time proportional to the square of the template length. It all happens in
the
parent, single threaded, before the first job even starts, so --jobs doesn't
help at all. A realistic way to hit this is a big chunk of inlined bash on
the
command line (say a script with lots of functions and ${...} expansions),
where
all those braces look like possible replacements but none of them match.
You can see it with a simple synthetic example:
for n in 750 1500 3000; do
tmpl="true $(yes 'eval "${x:0:5}...."' | head -n "$n" | tr '\n' ' ')"
printf '%5d tokens: ' "$n"
{ /usr/bin/time -f '%es' parallel --dry-run "$tmpl" ::: 1 >/dev/null; }
2>&1
done
Here (GNU parallel 20260822, perl 5.40.1, one core), before and after the
patch:
tokens size stock patched
750 15 KB 1.30 s 0.15 s
1500 30 KB 4.82 s 0.17 s
3000 60 KB 18.55 s 0.16 s
Stock roughly quadruples for each doubling of the template; with the patch
it
stays flat. The ${x:0:5} bits are just an easy way to get lots of "{" with
no
match. In real life it shows up when you put a serialized bash payload
(typeset -p) on the command line.
What's going on: in replace_rpl_def(), the `if($rpl =~ /^\{/)` branch runs
two
loops like
while($s =~ s{ ( (?: ^|\177> ) (?: [^\177]*|[\177][^<>] )*? ) \{ ... \}
}...)
for every rpl. That leading "unchanged" capture, (?: [^\177]*|[\177][^<>]
)*?,
is a lazy quantifier whose first branch [^\177]* is unbounded. When the
{...}
part matches nothing (the usual case for {} on a template full of ${...}),
the
engine keeps retrying that split from every "{", and that's where the square
comes from.
The fix leaves those loops alone. When the rpl has no group regexp it does a
cheap pre-check first for the same body but without that expensive leading
capture: if that can't match anywhere, the loops can't either, so we skip
them.
The pre-check uses only the \Q-quoted literal prefix/postfix and the
existing
position/format syntax (no user sub-expression), so it is always safe.
If the rpl does have a group regexp we don't pre-check at all and just run
the
original loops. The loops wrap the group in an extra capture and precede it
with
the position and unchanged-prefix captures, so re-embedding it in the
pre-check
would change the meaning of things like a backreference, a (?(1)...)
conditional,
(?1) recursion or a scoped (?-s) modifier. Skipping the pre-check for
grouped
rpls removes the observed slowdown while leaving their handling exactly as
before.
One honest note: A lot of the digging and this patch itself were done with
an
AI assistant. We checked it pretty hard on our side: differential
testing against stock parallel over a bunch of hand written cases, 900
random templates
and 2500 nasty custom --rpl regexps, all identical in stdout, stderr and
exit
code, plus the benchmarks above and perl -c. We're happy enough with it to
send
it.
That said, this still needs a careful review. The tests give us some
confidence, but we can't rule out a regression in an obscure corner case.
We'd appreciate your assessment of the approach itself - there may be a
better way to address this.
Thanks for taking a look.
Regards,
Igor
diff --git a/src/parallel b/src/parallel
index ea5c289..3611688 100755
--- a/src/parallel
+++ b/src/parallel
@@ -14794,6 +14794,29 @@ sub new($) {
# Look for: { position prefix group postfix format }
# Look for: { 1.1 / (.*) '' :% 5d }
# --match '\.(.*)' echo '{1.1/3/6:% 5d}' ::: fooa.123
+ # The two while-loops below carry a leading unchanged-capture
+ # (?:[^\177]*|\177[^<>])*? whose nested quantifier backtracks
+ # O(n^2) when the {..} body finds no match. When the rpl has NO
+ # group regexp, do a cheap pre-check of the same body without
+ # that capture: if it cannot match anywhere, the loops cannot
+ # either, so skip them. The pre-check uses only the \Q-quoted
+ # literal prefix/postfix and the existing position/format
+ # syntax (no user sub-expression), so it is always safe.
+ #
+ # We deliberately restrict the pre-check to the group-less case.
+ # The loops wrap $grp_regexp in an extra group and precede it
+ # with the position and unchanged-prefix captures; embedding it
+ # here in a different capture context would change the meaning
+ # of backreferences (\1, \g{-1}), conditionals (?(1)...),
+ # recursion (?1), scoped modifiers (?-s), #-comments under /x,
+ # etc. Applying the pre-check only to group-less rpls removes
+ # the observed slowdown while leaving grouped rpls unchanged.
+ my $run_scan = 1;
+ if(not defined $grp_regexp or $grp_regexp eq '') {
+ $run_scan = ($s =~
+ /\{\s*(?:-?\d+(?:\.\d+)?\s*)?\Q$prefix\E\Q$postfix\E(?:$format_regexp)?\}/sx);
+ }
+ if($run_scan) {
while($s =~
s{( (?: ^|\177> ) (?: [^\177]*|[\177][^<>] )*?)
\{
@@ -14821,6 +14844,7 @@ sub new($) {
{
replacer_rpl($rpl, $1, $2, $grp_regexp, $3);
}gsex){}
+ }
}
} else {
my ($prefix,$grp_regexp,$postfix) =
