Optimize finding the max character width

[pitrou]

BPO	13155
Nosy	@pitrou, @vstinner
Files	find_max_char.patch find_max_char2.patch find_max_char3.patch find_max_char4.patch find_max_char5.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 = <Date 2011-10-12.22:08:58.441>
created_at = <Date 2011-10-11.23:14:18.792>
labels = ['interpreter-core', 'performance']
title = 'Optimize finding the max character width'
updated_at = <Date 2011-10-12.22:08:58.429>
user = 'https://github.com/pitrou'

bugs.python.org fields:

activity = <Date 2011-10-12.22:08:58.429>
actor = 'pitrou'
assignee = 'none'
closed = True
closed_date = <Date 2011-10-12.22:08:58.441>
closer = 'pitrou'
components = ['Interpreter Core']
creation = <Date 2011-10-11.23:14:18.792>
creator = 'pitrou'
dependencies = []
files = ['23379', '23380', '23381', '23382', '23392']
hgrepos = []
issue_num = 13155
keywords = ['patch']
message_count = 12.0
messages = ['145372', '145373', '145374', '145375', '145376', '145377', '145378', '145427', '145428', '145432', '145437', '145438']
nosy_count = 3.0
nosy_names = ['pitrou', 'vstinner', 'python-dev']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue13155'
versions = ['Python 3.3']

[pitrou]

This patch optimizes scanning for the max character width in an unicode buffer.

Micro-benchmarking some worst case situations:

$ ./python -m timeit -s "x='é'+'x'*100000" "x[1:]"
-> before:
10000 loops, best of 3: 74.9 usec per loop
-> after:
100000 loops, best of 3: 15.5 usec per loop

$ ./python -m timeit -s "x='\U00010000'+'x'*100000" "x[1:]"
-> before:
10000 loops, best of 3: 138 usec per loop
-> after:
10000 loops, best of 3: 71.3 usec per loop

[pitrou]

I hadn't noticed the STRINGLIB_SIZEOF_CHAR constant. Reuse it instead of adding STRINGLIB_CHAR_SIZE.

[pitrou]

Slightly cleaned up patch after Victor's comments in private.

[vstinner]

find_max_char() returns 0x10000 instead of 0x10FFFF, which may be wrong (or at least, surprising). You may add a max_char variable using other macros like MAX_CHAR_ASCII, MAX_CHAR_UCS1, ..., which will be set at the same time than mask. Or restore your if (ret >= 0x10000) return 0x10ffff; else return ret;.

Constants look inconsistent:

+ const STRINGLIB_CHAR *unrolled_end = begin + (n & ~ (Py_ssize_t) 7);
+ p += 4;

You may use STRINGLIB_CHAR in:

+ Py_UCS4 bits = p[0] | p[1] | p[2] | p[3];

[pitrou]

Ok, updated patch.

[vstinner]

Ok, updated patch.

"ret = ~mask + 1;" looks wrong: (~0xFFFFFF80+1) gives 128, not 127. I don't see why you need:

+ if (ret < 128)
+ return 127;
+ if (ret < 256)
+ return 255;

#undef ASCII_CHAR_MASK should be #undef UCS1_ASCII_CHAR_MASK

#error Invalid STRINGLIB_SIZEOF_CHAR (must be 1, 2 or 4)
should be
#error Invalid STRINGLIB_SIZEOF_CHAR (must be 2 or 4)

Why do you need these forward declarations? It's maybe related to another patch?

 static PyObject *
+unicode_fromascii(const unsigned char *s, Py_ssize_t size);
+static PyObject *
+_PyUnicode_FromUCS1(const unsigned char *s, Py_ssize_t size);
+static PyObject *
+_PyUnicode_FromUCS2(const Py_UCS2 *s, Py_ssize_t size);
+static PyObject *
+_PyUnicode_FromUCS4(const Py_UCS4 *s, Py_ssize_t size);

(You kept Py_UCS4 for "Py_UCS4 bits", but Py_UCS4 is maybe just fine.)

By the way, your function rocks :-) Use bit masks is a great idea, especially your "bits = p[0] | p[1] | p[2] | p[3]" "hack".

[pitrou]

> Ok, updated patch.

"ret = ~mask + 1;" looks wrong: (~0xFFFFFF80+1) gives 128, not 127.

That's on purpose, since the mask has just matched. If 0xFFFFFF80
matches, then the max char can't be 127, it has to be at least 128.

I don't see why you need:

• if (ret < 128)

•    return 127;
  

• if (ret < 256)

•    return 255;
  

Because otherwise you're returning 0xFFFF in the following line:

if (ret < 0x10000)
    return 0xFFFF;

#undef ASCII_CHAR_MASK should be #undef UCS1_ASCII_CHAR_MASK

Ha, funny that gcc doesn't say anything.
I also forgot to #under MASK_*.

#error Invalid STRINGLIB_SIZEOF_CHAR (must be 1, 2 or 4)
should be
#error Invalid STRINGLIB_SIZEOF_CHAR (must be 2 or 4)

Well, no. 1 is a legal value, even though it's handled elsewhere, so the
error message is right.

Why do you need these forward declarations? It's maybe related to another patch?

It's because I'm moving the stringlib #includes up in unicodeobject.c,
and stringlib calls these functions.

[vstinner]

Without the patch:

python3.2 -m timeit 'x="é"+"x"*10000' 'x[1:]'
100000 loops, best of 3: 2.18 usec per loop

python3.3 -m timeit 'x="é"+"x"*10000' 'x[1:]'
100000 loops, best of 3: 6.68 usec per loop

[vstinner]

With find_max_char4.patch:

python3.3 -m timeit 'x="é"+"x"*10000' 'x[1:]'
100000 loops, best of 3: 1.96 usec per loop

[vstinner]

find_max_char5.patch:

• don't use adjusted ~mask+1: "precompute" the right max_char
• rename findwidth.h to find_max_char.h
• add some #undef

[python-dev]

New changeset 9c7d3207fc15 by Antoine Pitrou in branch 'default':
Issue bpo-13155: Optimize finding the optimal character width of an unicode string
http://hg.python.org/cpython/rev/9c7d3207fc15

[pitrou]

find_max_char5.patch:

• don't use adjusted ~mask+1: "precompute" the right max_char
• rename findwidth.h to find_max_char.h
• add some #undef

Thank you, I've committed this version.