Performance Regression between sed 4.4 and sed 4.5+

[Jakub Martisko]

Hello,

there seems to be large performance regression starting in sed 4.5.
I've done most of the testing on sed 4.4 and 4.5 since this seems to
be the point where it was introduced, but it is present in 4.9 too.

Command I'm using:

 sed -nf program.sed input > /tmp/out

program.sed should be in the attachment, the input file is 355MB
large, so I am attaching only a head -n100 of the input file (can
share the rest somehow if needed). When running with sed 4.4 the run
ends in roughly a minute (with the full input file), however with the
newer versions, sed runs for several hours (~4h). Both versions were
built/run on the same machine. I am also attaching a gprof profiles of
the 4.4 and 4.5 runs.

Thanks,
Jakub

profile-4.4
Description: Unix manual page

input_very_short
Description: Binary data

profile-4.5
Description: Unix manual page

program.sed
Description: Binary data