Did you use any quadratic or worse regex algorithm? Such as having more than one .* in a single regex. Did you set LANG=C before running sed, to bypass the UTF

Did you use any quadratic or worse regex algorithm? Such as having more than one .* in a single regex. Did you set LANG=C before running sed, to bypass the UTF-8 logic? Also, if you had a list of substitutions to perform, did you try writing them as a single sed script?