Substitution should not be really a relevant metric as it wouldn't influence the result much. Sed/Awk will still have to go through the whole file to find all occurrences they should substitute (and when they do find an occurrence, the substitution would take nanoseconds).

The size of the file is a better metric (e.g. how many seconds for that 800mb in total).

Also, whether you used regex in your awk/sed, and what kind. A badly written regex can slow down search very much.

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?