Re: Performance Regression between sed 4.4 and sed 4.5+

[Jakub Martisko]

Another observation - I've tried to replace the 0-9 and A-Z (I'll call
these "enums") in the input program with their :digit:/:upper: (and I'll
call these "classes") alternatives and got following results (i've had to
use 2500 lines long version of the input file instead of 100 like in the
previous mails, sorry for being inconsistent):

When using C locale, both the "classes" and "enums" versions had a similar
run time, with both sed 4.4 and 4.5+ (both using their official upstream
tarball versions)

real 0m3.032s
user 0m2.319s
sys 0m0.697s

but for the US locale:

"enums" 4.4 (note that this is still significantly faster then the C locale
and/or sed 4.5):

real 0m0.082s
user 0m0.072s
sys 0m0.011s

"classes" 4.4:

real 0m9.167s
user 0m8.522s
sys 0m0.623s

"enums" 4.5+:

real 0m33.219s
user 0m32.056s
sys 0m1.006s

"classes" 4.5+:

real 0m8.207s
user 0m7.968s
sys 0m0.217s

On Mon, Jul 29, 2024 at 3:04 PM Jakub Martisko <jamartis@redhat.com> wrote:

> I've tried a bit more experimenting and I think this gnulib commit
> introduced the regression:
> https://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=commit;h=6afba02d78
>
> I've tried to build sed 4.5 with various versions of lib/dfa.{c,h}.
> Starting with the version from the commit above, the sed run times became
> significantly slower.
>
> On Mon, Jul 29, 2024 at 1:30 PM Jakub Martisko <jamartis@redhat.com>
> wrote:
>
>> The callgrind output files for the locales/versions mentioned in the
>> previous email
>>
>> On Mon, Jul 29, 2024 at 1:23 PM Jakub Martisko <jamartis@redhat.com>
>> wrote:
>>
>>> Hello,
>>>
>>> This still seems to be an issue as of sed-4.9. I've tried some tests
>>> using the  valgrind/callgrind+kcachegrind and using various locales (I'll
>>> try to attach to a next email the callgrind profile files but I am not sure
>>> whether they'll pass attachment size/spam filters).
>>>
>>> I've tested with sed 4.4 and 4.5. Sed 4.9 behaves the same as 4.5, but
>>> since the regression first appeared in 4.5 I'm using that. I've used the
>>> following two locales (I've always set both LANG and LC_ALL to the locale):
>>> C and en_US.iso88591 (calling this just as US). The program was the one
>>> from my first email, the input file was the head -n 100 input also
>>> mentioned in the first mail.
>>>
>>> Interesting observations:
>>>
>>> 1) In sed 4.4 there seems to be a difference between the C and US
>>> locales: (numbers in parenthesis correspond to the numbers of call reported
>>> by the kcachegrind):
>>> US: ...-> dfaexec_sb (100) -> dfaexec_main (100) -> build_state (449) ->
>>> insert (~1.9 mil)
>>> C: ...-> dfaexec_sb (100) -> dfaexec_main (100) -> build_state (~135
>>> 000) -> insert (~135 000)
>>>
>>> 2) The C locale seems to behave the same way both in 4.4 and 4.5
>>>
>>> 3)The US locale behaves differently in 4.4 and 4.5:
>>> 4.4: ...-> dfaexec_sb (100) -> dfaexec_main (100) -> build_state (449)
>>> -> insert (~1.9 mil)
>>> 4.5: ...-> dfaexec_sb (100) -> dfaexec_main (100) -> build_state (~130
>>> 000) -> insert (~220 mil)
>>> with the following run times (time sed...):
>>>
>>> 4.4:
>>> real 0m0.042s
>>> user 0m0.035s
>>> sys 0m0.007s
>>>
>>> 4.5:
>>> real 0m1.289s
>>> user 0m1.248s
>>> sys 0m0.037s
>>>
>>> On Thu, Nov 23, 2023 at 11:27 AM Jakub Martisko <jamartis@redhat.com>
>>> wrote:
>>>
>>>> Sending some statistics, I've tried to use LANG=C which helped a bit,
>>>> but the performance is still worse than when using sed 4.4
>>>>
>>>> These are with LANG=C.UTF-8
>>>> time ~/repos/Fedora/sed/sed-4.4/sed/sed -nf program.sed input >
>>>> output_4.4
>>>>
>>>> real    0m21.214s
>>>> user    0m20.641s
>>>> sys    0m0.510s
>>>>
>>>>
>>>> time ~/repos/Fedora/sed/sed-4.5/sed/sed -nf program.sed input >
>>>> output_4.4
>>>>
>>>> real    183m34.784s
>>>> user    179m23.097s
>>>> sys    3m51.128s
>>>>
>>>> These with LANG=C
>>>> time LANG=C ~/repos/Fedora/sed/sed-4.4/sed/sed -nf program.sed input >
>>>> output_4.4
>>>>
>>>> real    11m16.226s
>>>> user    8m39.261s
>>>> sys    2m34.840s
>>>>
>>>>
>>>> time LANG=C ~/repos/Fedora/sed/sed-4.5/sed/sed -nf program.sed input >
>>>> output_4.4
>>>>
>>>> real    9m17.259s
>>>> user    7m11.610s
>>>> sys    2m3.557s
>>>>
>>>> On Wed, Nov 22, 2023 at 11:28 AM Jakub Martisko <jamartis@redhat.com>
>>>> wrote:
>>>> >
>>>> > 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
>>>>
>>>