I have cleaned up the changes and ensure the behavior remains the same, however there are still a few points I need input from @malemburg
(And as Benedikt said, should be their own issue)

• This function is documented as taking strings, but during the 2->3 conversion and undocumented, and untested change was made which allowed it to accept bytes. I have kept it this way (in Python, to make removal simpler), though I think this should either be documented and tested, or removed.
• The function has been documented as ascii only, and for bytes, it is. However, for strings, it has not been enforced with an error. What should we do?

Benchmarks:

import time
from encodings import normalize_encoding
import pyperf


def bench(loops):
    range_it = range(loops)
    t0 = time.perf_counter()

    for _ in range_it:
        normalize_encoding('utf_8')
        normalize_encoding('utf\xE9\u20AC\U0010ffff-8')
        normalize_encoding('utf   8')
        normalize_encoding('%%%~')
        normalize_encoding('UTF...8')

    return time.perf_counter() - t0


runner = pyperf.Runner()
runner.bench_time_func('normalize_encoding', bench, inner_loops=10)

Main branch:

normalize_encoding: Mean +- std dev: 173 ns +- 7 ns

This PR:

normalize_encoding: Mean +- std dev: 42.9 ns +- 1.1 ns

Sorry for the lack of response. I'm currently at EuroPython and pretty busy with other things. I'll have a look on Saturday during the sprints.

There are some subtle differences between Python and C code. We first need to decide what normalization is needed in Python and C code. It seems that excessive normalization caused problems (see #88886).

There are some subtle differences between Python and C code.

All of our tests pass, and from my further testing it also matches behaviour, can you please point out such cases?

These are long standing issues that have had no progress for quite a while, I propose, to keep this PR simple/organized and therefore focused on switching the implementation to the existing C code. This PR will become more complex and therefore harder to review if it has to rewrite the existing C code too. The existing issues, and yours from a few days ago, can be addressed in the C implementation, rather than both implementations.

I suggest holding this PR until we solve other issues. Otherwise it will make backporting other changes more difficult.

I have some comments about this PR, but it's too early to address them because in the end, everything could change radically.

A Python core developer has requested some changes be made to your pull request before we can consider merging it. If you could please address their requests along with any other requests in other reviews from core developers that would be appreciated.

Once you have made the requested changes, please leave a comment on this pull request containing the phrase I have made the requested changes; please review again. I will then notify any core developers who have left a review that you're ready for them to take another look at this pull request.

I have made the requested changes; please review again

Thanks for making the requested changes!

@malemburg: please review the changes made to this pull request.