homepage

As strange as it may seem, but using a simple trick was made UTF-8 decoding even more speed up.
Here are the benchmark results.
On 32-bit Linux, AMD Athlon 64 X2:
 vanilla patched
utf-8 'A'*10000 2061 (+3%) 2115
utf-8 '\x80'*10000 383 (-7%) 355
utf-8 '\x80'+'A'*9999 1273 (+1%) 1290
utf-8 '\u0100'*10000 382 (+47%) 562
utf-8 '\u0100'+'A'*9999 1239 (+1%) 1253
utf-8 '\u0100'+'\x80'*9999 383 (+47%) 562
utf-8 '\u8000'*10000 434 (-6%) 409
utf-8 '\u8000'+'A'*9999 1245 (+1%) 1256
utf-8 '\u8000'+'\x80'*9999 382 (+47%) 560
utf-8 '\u8000'+'\u0100'*9999 383 (+44%) 553
utf-8 '\U00010000'*10000 358 (+4%) 373
utf-8 '\U00010000'+'A'*9999 1171 (+0%) 1176
utf-8 '\U00010000'+'\x80'*9999 381 (+44%) 548
utf-8 '\U00010000'+'\u0100'*9999 381 (+44%) 548
utf-8 '\U00010000'+'\u8000'*9999 404 (+0%) 406
On 32-bit Linux, Intel Atom N570:
 vanilla patched
utf-8 'A'*10000 623 (+0%) 626
utf-8 '\x80'*10000 145 (+15%) 167
utf-8 '\x80'+'A'*9999 354 (+2%) 362
utf-8 '\u0100'*10000 164 (+10%) 181
utf-8 '\u0100'+'A'*9999 343 (-0%) 342
utf-8 '\u0100'+'\x80'*9999 164 (+11%) 182
utf-8 '\u8000'*10000 175 (+5%) 183
utf-8 '\u8000'+'A'*9999 349 (+0%) 349
utf-8 '\u8000'+'\x80'*9999 164 (+11%) 182
utf-8 '\u8000'+'\u0100'*9999 164 (+10%) 181
utf-8 '\U00010000'*10000 152 (+11%) 168
utf-8 '\U00010000'+'A'*9999 313 (+0%) 313
utf-8 '\U00010000'+'\x80'*9999 161 (+11%) 179
utf-8 '\U00010000'+'\u0100'*9999 161 (+11%) 179
utf-8 '\U00010000'+'\u8000'*9999 160 (+11%) 177

I see a slight increase under 64-bit Linux with gcc 4.5.2, too:
 vanilla patched
utf-8 'A'*10000 7857 (+4%)	8210
utf-8 'A'*9999+'\x80' 5392 (+8%)	5843
utf-8 'A'*9999+'\u0100' 2119 (+3%)	2173
utf-8 'A'*9999+'\u8000' 2121 (+2%)	2172
utf-8 'A'*9999+'\U00010000' 2248 (+2%)	2293
utf-8 '\x80'*10000 1015 (+1%)	1021
utf-8 '\x80'+'A'*9999 2747 (+5%)	2877
utf-8 '\x80'*9999+'\u0100' 868 (+0%)	869
utf-8 '\x80'*9999+'\u8000' 857 (+2%)	870
utf-8 '\x80'*9999+'\U00010000' 877 (+0%)	881
utf-8 '\u0100'*10000 1016 (+16%)	1181
utf-8 '\u0100'+'A'*9999 2506 (+3%)	2592
utf-8 '\u0100'+'\x80'*9999 1015 (+16%)	1179
utf-8 '\u0100'*9999+'\u8000' 1015 (+16%)	1182
utf-8 '\u0100'*9999+'\U00010000' 875 (+13%)	992
utf-8 '\u8000'*10000 836 (+18%)	985
utf-8 '\u8000'+'A'*9999 2508 (+3%)	2588
utf-8 '\u8000'+'\x80'*9999 1015 (+16%)	1182
utf-8 '\u8000'+'\u0100'*9999 1014 (+17%)	1182
utf-8 '\u8000'*9999+'\U00010000' 767 (+17%)	894
utf-8 '\U00010000'*10000 730 (+0%)	732
utf-8 '\U00010000'+'A'*9999 2542 (+2%)	2599
utf-8 '\U00010000'+'\x80'*9999 1013 (+17%)	1182
utf-8 '\U00010000'+'\u0100'*9999 1013 (+17%)	1181
utf-8 '\U00010000'+'\u8000'*9999 727 (+0%)	728

It seems the patch relies on a two's complement representation of integers. Mark, do you think that's ok?

> It seems the patch relies on a two's complement representation of integers. Mark, do you think that's ok?
Yes, the patch depends on two facts -- 8-bit bytes and a two's
complement representation of integers. That's why I call it a trick.
However, today CPython will not work on other platforms. However, we can
wrap macro definition in #if/#else/#end and provide the traditional form
(but I don't remember how to test a two's complement representation in
compile time).

The C standard says, in 6.3.1.3/3
Otherwise [*], the new type is signed and the value cannot be represented in it; either the result is implementation-defined or an implementation-defined signal is raised.
[*]: the value cannot be exactly converted, and the target type is not unsigned.
We shouldn't be using unsigned->signed conversions where the source value is out of range for the signed type.

Yes, this is an implementation-dependent behavior (and on the supported platforms it is implemented well in a certain way).
However, if the continuation byte check to do the simplest way ((ch) >= 0x80 && (ch) < 0xC0), this has the same effect (speed up to +45%) on AMD Athlon.
 vanilla patched
utf-8 'A'*10000 2061 (-2%) 2018
utf-8 '\x80'*10000 383 (+9%) 416
utf-8 '\x80'+'A'*9999 1273 (+3%) 1315
utf-8 '\u0100'*10000 382 (+46%) 558
utf-8 '\u0100'+'A'*9999 1239 (+0%) 1245
utf-8 '\u0100'+'\x80'*9999 383 (+46%) 558
utf-8 '\u8000'*10000 434 (-6%) 408
utf-8 '\u8000'+'A'*9999 1245 (+0%) 1245
utf-8 '\u8000'+'\x80'*9999 382 (+46%) 556
utf-8 '\u8000'+'\u0100'*9999 383 (+45%) 556
utf-8 '\U00010000'*10000 358 (+0%) 359
utf-8 '\U00010000'+'A'*9999 1171 (-0%) 1170
utf-8 '\U00010000'+'\x80'*9999 381 (+30%) 495
utf-8 '\U00010000'+'\u0100'*9999 381 (+30%) 495
utf-8 '\U00010000'+'\u8000'*9999 404 (-5%) 385
On Intel Atom the results did not change or become a little better.
 vanilla patched
utf-8 'A'*10000 623 (+3%) 642
utf-8 '\x80'*10000 145 (+9%) 158
utf-8 '\x80'+'A'*9999 354 (+4%) 367
utf-8 '\u0100'*10000 164 (+0%) 164
utf-8 '\u0100'+'A'*9999 343 (+2%) 351
utf-8 '\u0100'+'\x80'*9999 164 (+1%) 165
utf-8 '\u8000'*10000 175 (-2%) 171
utf-8 '\u8000'+'A'*9999 349 (+3%) 359
utf-8 '\u8000'+'\x80'*9999 164 (+0%) 164
utf-8 '\u8000'+'\u0100'*9999 164 (+0%) 164
utf-8 '\U00010000'*10000 152 (-1%) 150
utf-8 '\U00010000'+'A'*9999 313 (+2%) 319
utf-8 '\U00010000'+'\x80'*9999 161 (+1%) 162
utf-8 '\U00010000'+'\u0100'*9999 161 (+1%) 162
utf-8 '\U00010000'+'\u8000'*9999 160 (-2%) 156

> However, if the continuation byte check to do the simplest way ((ch) >= 
> 0x80 && (ch) < 0xC0), this has the same effect (speed up to +45%) on 
> AMD Athlon.
Doesn't produce any significant speedup on Intel Core i5-2500.

> It seems the patch relies on a two's complement representation of
> integers. Mark, do you think that's ok?
(1) Relying on two's complement integers seems fine to me: we're already relying on it in other places in Python (e.g., bitwise operations for ints in Python 2.x); it seems unlikely Python's going to run into current or future hardware that uses anything else; and any special-case code for ones' complement or sign-magnitude is going to be essentially unused and awkward to test, so it's probably better not to have it in the codebase at all.
In an ideal world, I guess we'd add some configure-time tests for two's complement so that in the unlikely event that Python *does* meet a non two's complement platform the build fails early with a clear message rather than the tests failing in strange ways.
(2) The bit that Martin identifies: relying on conversion from unsigned to signed doing a wraparound modulo 2**<suitable n> is a bit more troubling; it's something that I try to avoid where possible, but that's not always easy. I don't recall ever having encountered this causing problems in practice, though---it feels like a leftover from a non-two's complement world where processors would have a hard time giving wraparound semantics, so the C standard didn't want to require it. Again, if we're going to rely on this, it would probably make sense to have some configure-time checks; and it would be better not to rely on it at all without a really good reason.

Here is a patch that uses some sort of autodetection.

Any chance to commit the patch before final feature freeze?

> Any chance to commit the patch before final feature freeze?
I'll defer to Mark :-)

Okay, will look at this this afternoon.

I'm happy to apply the 'decode_utf8_range_check.patch'; I'll do that unless there are objections. The code is clearer than the original, and if we get a speedup into the bargain then I don't see a reason not to apply this.
I'm less comfortable with either the original patch, or the most recent one (decode_utf8_signed_byte-2.patch).

Serhiy, does this patch also fix #8271?
If so, can you also include the tests I wrote for it?

New changeset 3214c9ebcf5e by Mark Dickinson in branch 'default':
Issue #14923: Optimize continuation-byte check in UTF-8 decoding. Patch by Serhiy Storchaka.
http://hg.python.org/cpython/rev/3214c9ebcf5e 

Patch applied. Closing.
Ezio: the patch is pure optimization, with no change in semantics; I don't see how it could fix #8271.

> Serhiy, does this patch also fix #8271?
No, this patch not change behavior. But updated patch for issue 8271 now
contains this patch (I hope this will help merge).
> If so, can you also include the tests I wrote for it?
Your tests included in patch for issue 8271.