encoding package's normalize_encoding() function is too slow

[malemburg]

BPO	11322
Nosy	@malemburg, @gpshead, @jcea, @abalkin, @vstinner, @ezio-melotti, @serhiy-storchaka
Files	encoding_normalize_optimize.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = None
created_at = <Date 2011-02-25.15:55:31.555>
labels = ['3.7', 'expert-unicode', 'performance']
title = "encoding package's normalize_encoding() function is too\tslow"
updated_at = <Date 2022-01-24.23:38:06.218>
user = 'https://github.com/malemburg'

bugs.python.org fields:

activity = <Date 2022-01-24.23:38:06.218>
actor = 'gregory.p.smith'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Unicode']
creation = <Date 2011-02-25.15:55:31.555>
creator = 'lemburg'
dependencies = []
files = ['45909']
hgrepos = []
issue_num = 11322
keywords = ['patch']
message_count = 10.0
messages = ['129386', '129389', '129460', '129463', '165517', '220630', '220633', '283266', '283271', '283333']
nosy_count = 8.0
nosy_names = ['lemburg', 'gregory.p.smith', 'jcea', 'belopolsky', 'vstinner', 'ezio.melotti', 'sdaoden', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = None
stage = None
status = 'open'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue11322'
versions = ['Python 3.7']

Linked PRs

• gh-55531: Implement normalize_encoding in C #136643

[malemburg]

I don't know who changed the encoding's package normalize_encoding() function (wasn't me), but it's a really slow implementation.

The original version used the .translate() method which is a lot faster and can be adapted to work with the Unicode variant of the .translate() method just as well.

_norm_encoding_map = ('                                              . '
                      '0123456789       ABCDEFGHIJKLMNOPQRSTUVWXYZ     '
                      ' abcdefghijklmnopqrstuvwxyz                     '
                      '                                                '
                      '                                                '
                      '                ')

def normalize_encoding(encoding):

""" Normalize an encoding name.

    Normalization works as follows: all non-alphanumeric
    characters except the dot used for Python package names are
    collapsed and replaced with a single underscore, e.g. '  -;#'
    becomes '_'. Leading and trailing underscores are removed.

    Note that encoding names should be ASCII only; if they do use
    non-ASCII characters, these must be Latin-1 compatible.

"""
# Make sure we have an 8-bit string, because .translate() works
# differently for Unicode strings.
if hasattr(__builtin__, "unicode") and isinstance(encoding, unicode):
    # Note that .encode('latin-1') does *not* use the codec
    # registry, so this call doesn't recurse. (See unicodeobject.c
    # PyUnicode_AsEncodedString() for details)
    encoding = encoding.encode('latin-1')
return '_'.join(encoding.translate(_norm_encoding_map).split())

[abalkin]

I don't think the normalize_encoding() function was the culprit for bpo-11303 because I measured timings with timeit which averages multiple runs while normalize_encoding() is called only the one time per encoding spelling due to caching.

[vstinner]

We should first implement the same algorithm of the 3 normalization functions and add tests for them (at least for the function in normalization):

• normalize_encoding() in encodings: it doesn't convert to lowercase and keep non-ASCII letters
• normalize_encoding() in unicodeobject.c
• normalizestring() in codecs.c

normalize_encoding() in encodings is more laxist than the two other functions: it normalizes " utf 8 " to 'utf_8'. But it doesn't convert to lowercase and keeps non-ASCII letters: "UTF-8é" is normalized "UTF_8é".

I don't know if the normalization functions have to be more or less strict, but I think that they should all give the same result.

[malemburg]

STINNER Victor wrote:

STINNER Victor <victor.stinner@haypocalc.com> added the comment:

We should first implement the same algorithm of the 3 normalization functions and add tests for them (at least for the function in normalization):

• normalize_encoding() in encodings: it doesn't convert to lowercase and keep non-ASCII letters
• normalize_encoding() in unicodeobject.c
• normalizestring() in codecs.c

normalize_encoding() in encodings is more laxist than the two other functions: it normalizes " utf 8 " to 'utf_8'. But it doesn't convert to lowercase and keeps non-ASCII letters: "UTF-8é" is normalized "UTF_8é".

I don't know if the normalization functions have to be more or less strict, but I think that they should all give the same result.

Please see this message for an explanation of why we have those
three functions, why they are different and what their application
space is:

http://bugs.python.org/issue5902#msg129257

This ticket is just about the encoding package's codec search
function, not the other two, and I don't want to change
semantics, just its performance.

[serhiy-storchaka]

I don't know who changed the encoding's package normalize_encoding() function (wasn't me), but it's a really slow implementation.

See changeset 54ef645d08e4.

[BreamoreBoy]

What's the status of this issue, as we've lived with this really slow implementation for well over three years?

[malemburg]

On 15.06.2014 15:02, Mark Lawrence wrote:

What's the status of this issue, as we've lived with this really slow implementation for well over three years?

I guess it just needs someone to write a patch.

Note that encoding lookups are cached, so the slowness only
becomes an issue if you lookup lots of different encodings.

[malemburg]

Thanks for the patch.

Victor has implemented the function in C, AFAIK, so an even better approach would be to expose that function at the Python level and use it in the encodings package.

[vstinner]

It seems like encodings.normalize_encoding() currently has no unit test! Before modifying it, I would prefer to see a few unit tests:

• " utf 8 "
• "UtF 8"
• "utf8\xE9"
• etc.

Since we are talking about an optimmization, I would like to see a benchmark result before/after. I also would like to test Marc-Andre's idea of exposing the C function _Py_normalize_encoding().

_Py_normalize_encoding() works on a byte string encoded to Latin1. To implement encodings.normalize_encoding(), we might rewrite the function to work on Py_UCS4 character, or have a fast version on char*, and a more generic version for UCS2 and UCS4?

[vstinner]

Oh, while reading Mercurial history, I found a note that I wrote:

"It's not exactly the same than encodings.normalize_encoding(): the C function also converts to lowercase."

IHMO it's fine to modify encodings.normalize_encoding() to also convert to lower-case.