Re: Encode UTF-8 optimizations

On 08/22/2016 07:05 AM, [email protected] wrote:
> On Sunday 21 August 2016 08:49:08 Karl Williamson wrote:
>> On 08/21/2016 02:34 AM, [email protected] wrote:
>>> On Sunday 21 August 2016 03:10:40 Karl Williamson wrote:
>>>> Top posting.
>>>>
>>>> Attached is my alternative patch.  It effectively uses a different
>>>> algorithm to avoid decoding the input into code points, and to copy
>>>> all spans of valid input at once, instead of character at a time.
>>>>
>>>> And it uses only currently available functions.
>>>
>>> And that's the problem. As already wrote in previous email, calling
>>> function from shared library cannot be heavy optimized as inlined
>>> function and cause slow down. You are calling is_utf8_string_loc for
>>> non-strict mode which is not inlined and so encode/decode of non-stri=
ct
>>> mode will be slower...
>>>
>>> And also in is_strict_utf8_string_loc you are calling isUTF8_CHAR whi=
ch
>>> is calling _is_utf8_char_slow and which is calling utf8n_to_uvchr whi=
ch
>>> cannot be inlined too...
>>>
>>> Therefore I think this is not good approach...
>>>
>>
>> Then you should run your benchmarks to find out the performance.
>
> You are right, benchmarks are needed to show final results.
>
>> On valid input, is_utf8_string_loc() is called once per string.  The
>> function call overhead and non-inlining should be not noticeable.
>
> Ah right, I misread it as it is called per one valid sequence, not for
> whole string. You are right.

It is called once per valid sequence.  See below.

>
>> On valid input, is_utf8_char_slow() is never called.  The used-parts c=
an be
>> inlined.
>
> Yes, but this function is there to be called primary on unknown input
> which does not have to be valid. If I know that input is valid then
> utf8::encode/decode is enough :-)

What process_utf8() does is to copy the alleged UTF-8 input to the=20
output, verifying along the way that it actually is legal UTF-8 (with 2=20
levels of strictness, depending on the input parameter), and taking some=20
actions (exactly what depends on other input parameters) if and when it=20
finds invalid UTF-8.

The way it works after my patch is like an instruction pipeline.  You=20
start it up, and it stays in the pipeline as long as the next character=20
in the input is legal or it reaches the end.  When it finds illegal=20
input, it drops out of the pipeline, handles that, and starts up the=20
pipeline to process any remaining input.  If the entire input string is=20
valid, a single instance of the pipeline is all that gets invoked.

The use-case I envision is that the input is supposed to be valid UTF-8,=20
and the purpose of process_utf8() is to verify that that is in fact=20
true, and to take specified actions when it isn't.  Under that use-case,=20
taking longer to deal with invalid input is not a problem.  If that is=20
not your use-case, please explain what yours is.

And I think you misunderstand when is_utf8_char_slow() is called.  It is=20
called only when the next byte in the input indicates that the only=20
legal UTF-8 that might follow would be for a code point that is at least=20
U+200000, almost twice as high as the highest legal Unicode code point.=20
It is a Perl extension to handle such code points, unlike other=20
languages.  But the Perl core is not optimized for them, nor will it be.=20
  My point is that is_utf8_char_slow() will only be called in very=20
specialized cases, and we need not make those cases have as good a=20
performance as normal ones.

>> On invalid input, performance should be a minor consideration.
>
> See below...

See above. :)

>
>> The inner loop is much tighter in both functions; likely it can be hel=
d in
>> the cache.  The algorithm avoids a bunch of work compared to the previ=
ous
>> one.
>
> Right, for valid input algorithm is really faster. If it is because of
> less case misses... maybe... I can play with perf or another tool to
> look what is bottle neck now.
>
>> I doubt that it will be slower than that.  The only way to know in any
>> performance situation is to actually test.  And know that things will =
be
>> different depending on the underlying hardware, so only large differen=
ces
>> are really significant.
>
> So, here are my test results. You can say that they are subjective, but
> I would be happy if somebody provide better input for performance tests=
.
>
> Abbreviations:
> strict =3D Encode::encode/decode "UTF-8"
> lax =3D Encode::encode/decode "utf8"
> int =3D utf8::encode/decode
> orig =3D commit 92d73bfab7792718f9ad5c5dc54013176ed9c76b
> your =3D orig + 0001-Speed-up-Encode-UTF-8-validation-checking.patch
> my =3D orig + revert commit c8247c27c13d1cf152398e453793a91916d2185d
>
> Test cases:
> all =3D join "", map { chr } 0 .. 0x10FFFF
> short =3D "=C5=BElu=C5=A5ou=C4=8Dk=C3=BD k=C5=AF=C5=88 p=C4=9Bl =C4=8F=C3=
=A1belsk=C3=A9 =C3=B3dy " x 45
> long =3D $short x 1000
> invalid-short =3D "\xA0" x 1000
> invalid-long =3D "\xA0" x 1000000
>
> Encoding was called on string with Encode::_utf8_on() flag.
>
>
> Rates:
>
> encode:
>                    all       short     long  invalid-short invalid-long
> orig - strict      41/s    124533/s    132/s     115197/s        172/s
> your - strict     176/s    411523/s    427/s      54813/s         66/s
> my   - strict      80/s    172712/s    186/s     113787/s        138/s
>
> orig - lax       1010/s   3225806/s   6250/s     546800/s       5151/s
> your - lax        952/s   3225806/s   5882/s     519325/s       4919/s
> my   - lax       1060/s   3125000/s   6250/s     645119/s       5009/s
>
> orig - int    8154604/s  10000000/s    infty    9787566/s    9748151/s
> your - int    9135243/s  11111111/s    infty    8922821/s    9737657/s
> my   - int    9779395/s  10000000/s    infty    9822046/s    8949861/s
>
>
> decode:
>                    all       short     long  invalid-short invalid-long
> orig - strict      39/s    119048/s    131/s     108574/s        171/s
> your - strict     173/s    353357/s    442/s      42440/s         55/s
> my   - strict      69/s    166667/s    182/s     117291/s        135/s
>
> orig - lax         39/s    123609/s    137/s     127302/s        172/s
> your - lax        230/s    393701/s    495/s      37346/s         65/s
> my   - lax         79/s    158983/s    180/s     121456/s        138/s
>
> orig - int        274/s    546448/s    565/s    8219513/s      12357/s
> your - int        273/s    540541/s    562/s    7226066/s      12948/s
> my   - int        274/s    543478/s    562/s    8502902/s      12421/s
>
>
> int is there just for verifications of tests as utf8::encode/decode
> functions was not changed.
>
> Results are: your patch is faster for valid sequences (as you wrote
> above), but slower for invalid (in some cases radically).
>
> So I would propose two optimizations:
>
> 1) Change macro isUTF8_CHAR in is_strict_utf8_string_loc() with some ne=
w
>    which does not call utf8n_to_uvchr. That call is not needed as in
>    that case sequence is already invalid.

And an optimizing compiler should figure that out and omit the call, so=20
we shouldn't have to manually.  In the next few months I will be working=20
on some fixes to the :utf8 layer.  That could lead to a core function=20
similar to this, but without relying on the compiler to figure things out=
.
>
> 2) Try to make inline version of function is_utf8_string_loc(). Maybe
>    merge with is_strict_utf8_string_loc()? That should boost non strict
>    decoder for invalid sequences (now it is slower then strict one).

I'll look at which functions in utf8.c should be inlined.  This is a=20
candidate.  But I doubt that that is why this is slower in this case.=20
Read blead's perlhack.pod for performance testing tool hints.

Your comments caused me to realize that the call to utf8n_to_uvchr()=20
when the input is syntactically valid, but is an illegal code point=20
(like a surrogate, etc) could be replaced by the faster=20
valid_utf8_to_uvchr(), which has not been in the public API.  I have=20
pushed to

http://perl5.git.perl.org/perl.git/shortlog/refs/heads/smoke-me/khw-encod=
e

a version of blead which has this function made public, and inlined, in=20
case you want to test with it.

There are some things in the error handling code that could be improved=20
upon.  For example, memcpy() of a single character is slower than just=20
copying a byte at a time, as the function call overhead dwarfs the saving=
s.

>
> And maybe it could make sense make all needed functions as part of
> public API.

Yes

>
> Are you going to prepare pull request for Encode module?

I will, after everything is settled.  This may include changes to=20
Devel::PPPort to make sure this works on all perls that Encode supports.

However, I think it would be good to get the extra tests of malformed=20
inputs into the distribution.  (I haven't looked at your PR yet for=20
flaws.  I'll do that, and hopefully will find none, so will recommend=20
your PR be pulled.)
>
>
> Anyway, how it behave on EBCDIC platforms? And maybe another question
> what should  Encode::encode('UTF-8', $str) do on EBCDIC? Encode $str to
> UTF-8 or to UTF-EBCDIC?

It works fine on EBCDIC platforms.  There are other bugs in Encode on=20
EBCDIC that I plan on investigating as time permits.  Doing this has=20
fixed some of these for free.  The uvuni() functions should in almost=20
all instances be uvchr(), and my patch does that.

On EBCDIC platforms, UTF-8 is defined to be UTF-EBCDIC (or vice versa if=20
you prefer), so $str will effectively be in the version of UTF-EBCDIC=20
valid for the platform it is running on (there are differences depending=20
on the platform's underlying code page).
>