Skip to content

Faster utf-16 decoder #58829

Closed
Closed
Faster utf-16 decoder#58829
Labels
interpreter-core(Objects, Python, Grammar, and Parser dirs)performancePerformance or resource usagetopic-unicode

Description

@serhiy-storchaka
serhiy-storchaka
opened on Apr 19, 2012
BPO 14624
Nosy @loewis, @pitrou, @vstinner, @ezio-melotti, @asvetlov, @serhiy-storchaka
Files
  • decode_utf16.patch
  • decodebench.py
  • bench-diff.py
  • decode_utf16_2.patch
  • decode_utf16_3.patch
  • decode_utf16_4.patch
  • decode_utf16_5.patch
  • decode_utf16_6.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 2012-05-15.21:52:07.385>
created_at = <Date 2012-04-19.20:59:00.603>
labels = ['interpreter-core', 'expert-unicode', 'performance']
title = 'Faster utf-16 decoder'
updated_at = <Date 2012-05-19.09:02:56.808>
user = 'https://github.com/serhiy-storchaka'

    bugs.python.org fields:

    activity = <Date 2012-05-19.09:02:56.808>
actor = 'serhiy.storchaka'
assignee = 'none'
closed = True
closed_date = <Date 2012-05-15.21:52:07.385>
closer = 'pitrou'
components = ['Interpreter Core', 'Unicode']
creation = <Date 2012-04-19.20:59:00.603>
creator = 'serhiy.storchaka'
dependencies = []
files = ['25277', '25323', '25324', '25443', '25536', '25590', '25601', '25602']
hgrepos = []
issue_num = 14624
keywords = ['patch']
message_count = 15.0
messages = ['158748', '158751', '158753', '158772', '159077', '159090', '159847', '159858', '160442', '160572', '160672', '160766', '160768', '160769', '161100']
nosy_count = 8.0
nosy_names = ['loewis', 'pitrou', 'vstinner', 'ezio.melotti', 'Arfrever', 'asvetlov', 'python-dev', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue14624'
versions = ['Python 3.3']

    Activity

    1. serhiy-storchaka commented on Apr 19, 2012

      @serhiy-storchaka
      serhiy-storchaka
      on Apr 19, 2012
      MemberAuthor

      I propose a patch, which accelerates the utf-16 decoder. With PEP-393 utf-16 decoder slowed down a few times (3-4x), this patch returns the performance at the level of Python 3.2 and even higher (+10-30% over 3.2).

      In addition, it fixes a few bugs in the utf-16 decoder. Also as a side effect is possible acceleration of other decoders.

    2. serhiy-storchaka
      added
      interpreter-core(Objects, Python, Grammar, and Parser dirs)
      performancePerformance or resource usage
      on Apr 19, 2012

    3. vstinner commented on Apr 19, 2012

      @vstinner
      vstinner
      on Apr 19, 2012
      Member

      See also bpo-14625 for UTF-32 decoder.

    4. serhiy-storchaka commented on Apr 19, 2012

      @serhiy-storchaka
      serhiy-storchaka
      on Apr 19, 2012
      MemberAuthor

      See also issue bpo-14579 for utf-16 decoder bugs.

    5. loewis commented on Apr 19, 2012

      @loewis
      loewismannequin
      on Apr 19, 2012
      Mannequin

      Serhiy: can you please submit a contributor form?

    6. serhiy-storchaka commented on Apr 23, 2012

      @serhiy-storchaka
      serhiy-storchaka
      on Apr 23, 2012
      MemberAuthor

      Here are the results of benchmarking (numbers in MB/s).

      On 32-bit Linux, AMD Athlon 64 X2 4600+ @ 2.4GHz:

                                            Py2.7        Py3.2        Py3.3       patch

      utf-16le 'A'*10000 504 (+282%) 1905 (+1%) 565 (+241%) 1927
      utf-16le '\x80'*10000 503 (+264%) 1894 (-3%) 417 (+340%) 1833
      utf-16le '\x80'+'A'*9999 504 (+264%) 1890 (-3%) 422 (+335%) 1834
      utf-16le '\u0100'*10000 503 (+249%) 1896 (-7%) 357 (+391%) 1754
      utf-16le '\u0100'+'A'*9999 504 (+252%) 1896 (-6%) 360 (+393%) 1776
      utf-16le '\u0100'+'\x80'*9999 503 (+249%) 1890 (-7%) 357 (+392%) 1756
      utf-16le '\u8000'*10000 503 (-18%) 355 (+16%) 75 (+449%) 412
      utf-16le '\u8000'+'A'*9999 504 (+254%) 1892 (-6%) 359 (+397%) 1783
      utf-16le '\u8000'+'\x80'*9999 503 (+249%) 1896 (-7%) 357 (+392%) 1755
      utf-16le '\u8000'+'\u0100'*9999 503 (+258%) 1901 (-5%) 359 (+402%) 1802
      utf-16le '\U00010000'*10000 484 (-14%) 379 (+9%) 103 (+303%) 415
      utf-16le '\U00010000'+'A'*9999 504 (+244%) 1905 (-9%) 353 (+392%) 1735
      utf-16le '\U00010000'+'\x80'*9999 503 (+245%) 1899 (-9%) 348 (+398%) 1733
      utf-16le '\U00010000'+'\u0100'*9999 503 (+244%) 1882 (-8%) 348 (+397%) 1729
      utf-16le '\U00010000'+'\u8000'*9999 503 (-18%) 355 (+16%) 71 (+482%) 413

      utf-16be 'A'*10000 504 (+284%) 1553 (+24%) 469 (+312%) 1933
      utf-16be '\x80'*10000 504 (+251%) 1551 (+14%) 387 (+357%) 1770
      utf-16be '\x80'+'A'*9999 504 (+261%) 1549 (+17%) 386 (+371%) 1819
      utf-16be '\u0100'*10000 503 (+175%) 1544 (-10%) 333 (+316%) 1384
      utf-16be '\u0100'+'A'*9999 505 (+178%) 1548 (-9%) 335 (+319%) 1403
      utf-16be '\u0100'+'\x80'*9999 503 (+179%) 1552 (-9%) 336 (+318%) 1405
      utf-16be '\u8000'*10000 503 (-2%) 415 (+19%) 75 (+559%) 494
      utf-16be '\u8000'+'A'*9999 504 (+179%) 1551 (-9%) 335 (+320%) 1408
      utf-16be '\u8000'+'\x80'*9999 504 (+178%) 1551 (-10%) 336 (+317%) 1402
      utf-16be '\u8000'+'\u0100'*9999 504 (+179%) 1549 (-9%) 336 (+318%) 1404
      utf-16be '\U00010000'*10000 483 (-7%) 407 (+10%) 105 (+326%) 447
      utf-16be '\U00010000'+'A'*9999 504 (+149%) 1554 (-19%) 317 (+295%) 1253
      utf-16be '\U00010000'+'\x80'*9999 503 (+153%) 1543 (-17%) 317 (+302%) 1275
      utf-16be '\U00010000'+'\u0100'*9999 503 (+153%) 1537 (-17%) 317 (+302%) 1274
      utf-16be '\U00010000'+'\u8000'*9999 503 (-2%) 415 (+19%) 71 (+597%) 495

      On 32-bit Linux, Intel Atom N570 @ 1.66GHz:

                                            Py2.7        Py3.2        Py3.3       patch

      utf-16le 'A'*10000 136 (+417%) 584 (+20%) 184 (+282%) 703
      utf-16le '\x80'*10000 136 (+392%) 580 (+15%) 160 (+318%) 669
      utf-16le '\x80'+'A'*9999 136 (+398%) 582 (+16%) 159 (+326%) 677
      utf-16le '\u0100'*10000 137 (+346%) 583 (+5%) 129 (+374%) 611
      utf-16le '\u0100'+'A'*9999 136 (+358%) 582 (+7%) 129 (+383%) 623
      utf-16le '\u0100'+'\x80'*9999 136 (+348%) 580 (+5%) 129 (+372%) 609
      utf-16le '\u8000'*10000 136 (+18%) 127 (+27%) 38 (+324%) 161
      utf-16le '\u8000'+'A'*9999 136 (+357%) 582 (+7%) 129 (+382%) 622
      utf-16le '\u8000'+'\x80'*9999 136 (+351%) 581 (+6%) 128 (+380%) 614
      utf-16le '\u8000'+'\u0100'*9999 136 (+349%) 581 (+5%) 129 (+374%) 611
      utf-16le '\U00010000'*10000 153 (-3%) 140 (+6%) 53 (+181%) 149
      utf-16le '\U00010000'+'A'*9999 136 (+296%) 581 (-7%) 131 (+311%) 538
      utf-16le '\U00010000'+'\x80'*9999 136 (+289%) 584 (-9%) 131 (+304%) 529
      utf-16le '\U00010000'+'\u0100'*9999 136 (+290%) 579 (-8%) 130 (+308%) 530
      utf-16le '\U00010000'+'\u8000'*9999 136 (+25%) 128 (+33%) 38 (+347%) 170

      utf-16be 'A'*10000 136 (+331%) 441 (+33%) 166 (+253%) 586
      utf-16be '\x80'*10000 136 (+309%) 440 (+26%) 145 (+283%) 556
      utf-16be '\x80'+'A'*9999 136 (+312%) 442 (+27%) 145 (+286%) 560
      utf-16be '\u0100'*10000 136 (+231%) 441 (+2%) 120 (+275%) 450
      utf-16be '\u0100'+'A'*9999 136 (+232%) 442 (+2%) 120 (+276%) 451
      utf-16be '\u0100'+'\x80'*9999 136 (+231%) 438 (+3%) 119 (+278%) 450
      utf-16be '\u8000'*10000 136 (+22%) 127 (+31%) 38 (+337%) 166
      utf-16be '\u8000'+'A'*9999 136 (+232%) 439 (+3%) 120 (+276%) 451
      utf-16be '\u8000'+'\x80'*9999 136 (+230%) 439 (+2%) 120 (+274%) 449
      utf-16be '\u8000'+'\u0100'*9999 136 (+232%) 439 (+3%) 120 (+276%) 451
      utf-16be '\U00010000'*10000 153 (-1%) 139 (+9%) 52 (+192%) 152
      utf-16be '\U00010000'+'A'*9999 136 (+211%) 440 (-4%) 121 (+250%) 423
      utf-16be '\U00010000'+'\x80'*9999 136 (+210%) 440 (-4%) 122 (+246%) 422
      utf-16be '\U00010000'+'\u0100'*9999 136 (+210%) 441 (-5%) 121 (+248%) 421
      utf-16be '\U00010000'+'\u8000'*9999 136 (+27%) 128 (+35%) 38 (+355%) 173

    7. pitrou commented on Apr 23, 2012

      @pitrou
      pitrou
      on Apr 23, 2012
      Member

      64 bit Linux, Intel Core i5-2500K @ 3.30GHz:

                                            vanilla 3.3   patched

      utf-16le 'A'*10000 1384 (+278%) 5233
      utf-16le 'A'*9999+'\x80' 1303 (+259%) 4684
      utf-16le 'A'*9999+'\u0100' 953 (+195%) 2813
      utf-16le 'A'*9999+'\u8000' 953 (+195%) 2814
      utf-16le 'A'*9999+'\U00010000' 979 (+197%) 2903
      utf-16le '\x80'*10000 1243 (+321%) 5230
      utf-16le '\x80'+'A'*9999 1256 (+313%) 5188
      utf-16le '\x80'*9999+'\u0100' 880 (+214%) 2765
      utf-16le '\x80'*9999+'\u8000' 880 (+214%) 2763
      utf-16le '\x80'*9999+'\U00010000' 899 (+218%) 2860
      utf-16le '\u0100'*10000 1047 (+370%) 4917
      utf-16le '\u0100'+'A'*9999 1046 (+369%) 4906
      utf-16le '\u0100'+'\x80'*9999 1047 (+370%) 4920
      utf-16le '\u0100'*9999+'\u8000' 1047 (+369%) 4906
      utf-16le '\u0100'*9999+'\U00010000' 791 (+253%) 2793
      utf-16le '\u8000'*10000 230 (+410%) 1173
      utf-16le '\u8000'+'A'*9999 1043 (+371%) 4911
      utf-16le '\u8000'+'\x80'*9999 1044 (+345%) 4645
      utf-16le '\u8000'+'\u0100'*9999 1041 (+350%) 4681
      utf-16le '\u8000'*9999+'\U00010000' 215 (+357%) 983
      utf-16le '\U00010000'*10000 362 (+170%) 976
      utf-16le '\U00010000'+'A'*9999 985 (+210%) 3052
      utf-16le '\U00010000'+'\x80'*9999 985 (+211%) 3066
      utf-16le '\U00010000'+'\u0100'*9999 983 (+209%) 3042
      utf-16le '\U00010000'+'\u8000'*9999 245 (+329%) 1052

      utf-16be 'A'*10000 1268 (+313%) 5240
      utf-16be 'A'*9999+'\x80' 1199 (+297%) 4758
      utf-16be 'A'*9999+'\u0100' 896 (+211%) 2786
      utf-16be 'A'*9999+'\u8000' 897 (+211%) 2788
      utf-16be 'A'*9999+'\U00010000' 919 (+214%) 2885
      utf-16be '\x80'*10000 1154 (+341%) 5087
      utf-16be '\x80'+'A'*9999 1155 (+343%) 5112
      utf-16be '\x80'*9999+'\u0100' 829 (+229%) 2728
      utf-16be '\x80'*9999+'\u8000' 828 (+229%) 2726
      utf-16be '\x80'*9999+'\U00010000' 852 (+232%) 2832
      utf-16be '\u0100'*10000 981 (+332%) 4241
      utf-16be '\u0100'+'A'*9999 981 (+330%) 4220
      utf-16be '\u0100'+'\x80'*9999 977 (+331%) 4213
      utf-16be '\u0100'*9999+'\u8000' 982 (+331%) 4237
      utf-16be '\u0100'*9999+'\U00010000' 748 (+237%) 2520
      utf-16be '\u8000'*10000 230 (+413%) 1180
      utf-16be '\u8000'+'A'*9999 979 (+331%) 4218
      utf-16be '\u8000'+'\x80'*9999 974 (+333%) 4215
      utf-16be '\u8000'+'\u0100'*9999 972 (+335%) 4226
      utf-16be '\u8000'*9999+'\U00010000' 215 (+361%) 992
      utf-16be '\U00010000'*10000 362 (+170%) 978
      utf-16be '\U00010000'+'A'*9999 924 (+232%) 3064
      utf-16be '\U00010000'+'\x80'*9999 921 (+223%) 2979
      utf-16be '\U00010000'+'\u0100'*9999 921 (+233%) 3064
      utf-16be '\U00010000'+'\u8000'*9999 245 (+329%) 1052

    8. python-dev commented on May 3, 2012

      @python-dev
      python-devmannequin
      on May 3, 2012
      Mannequin

      New changeset 830eeff4fe8f by Victor Stinner in branch 'default':
      Issue bpo-14624, bpo-14687: Optimize unicode_widen()
      http://hg.python.org/cpython/rev/830eeff4fe8f

    9. serhiy-storchaka commented on May 3, 2012

      @serhiy-storchaka
      serhiy-storchaka
      on May 3, 2012
      MemberAuthor

      Here is updated patch, taking into account that unicode_widen is already
      optimized.

    10. serhiy-storchaka commented on May 11, 2012

      @serhiy-storchaka
      serhiy-storchaka
      on May 11, 2012
      MemberAuthor

      The patch updated to stylistic conformity of the UTF-8 decoder. The decoding of the UCS2 non-surrogate characters a little speed up (+15%).

    11. serhiy-storchaka
      added
      topic-unicode
      on May 11, 2012

    12. pitrou commented on May 13, 2012

      @pitrou
      pitrou
      on May 13, 2012
      Member

      New performance figures under 64 bit Linux, Intel Core i5-2500K @ 3.30GHz:

                                            vanilla 3.3   patched

      utf-16le 'A'*10000 1411 (+290%) 5504
      utf-16le 'A'*9999+'\x80' 1368 (+263%) 4970
      utf-16le 'A'*9999+'\u0100' 1145 (+151%) 2871
      utf-16le 'A'*9999+'\u8000' 1144 (+151%) 2870
      utf-16le 'A'*9999+'\U00010000' 1164 (+154%) 2957
      utf-16le '\x80'*10000 1403 (+271%) 5209
      utf-16le '\x80'+'A'*9999 1406 (+272%) 5235
      utf-16le '\x80'*9999+'\u0100' 1138 (+138%) 2713
      utf-16le '\x80'*9999+'\u8000' 1138 (+139%) 2716
      utf-16le '\x80'*9999+'\U00010000' 1155 (+151%) 2897
      utf-16le '\u0100'*10000 1477 (+243%) 5062
      utf-16le '\u0100'+'A'*9999 1478 (+243%) 5072
      utf-16le '\u0100'+'\x80'*9999 1477 (+243%) 5062
      utf-16le '\u0100'*9999+'\u8000' 1478 (+242%) 5055
      utf-16le '\u0100'*9999+'\U00010000' 1201 (+131%) 2776
      utf-16le '\u8000'*10000 246 (+347%) 1100
      utf-16le '\u8000'+'A'*9999 1475 (+244%) 5069
      utf-16le '\u8000'+'\x80'*9999 1474 (+243%) 5062
      utf-16le '\u8000'+'\u0100'*9999 1473 (+243%) 5057
      utf-16le '\u8000'*9999+'\U00010000' 236 (+295%) 932
      utf-16le '\U00010000'*10000 393 (+164%) 1039
      utf-16le '\U00010000'+'A'*9999 1325 (+134%) 3106
      utf-16le '\U00010000'+'\x80'*9999 1326 (+134%) 3103
      utf-16le '\U00010000'+'\u0100'*9999 1326 (+134%) 3104
      utf-16le '\U00010000'+'\u8000'*9999 253 (+331%) 1091

      utf-16be 'A'*10000 1341 (+298%) 5342
      utf-16be 'A'*9999+'\x80' 1305 (+275%) 4888
      utf-16be 'A'*9999+'\u0100' 1101 (+157%) 2834
      utf-16be 'A'*9999+'\u8000' 1102 (+157%) 2831
      utf-16be 'A'*9999+'\U00010000' 1115 (+162%) 2917
      utf-16be '\x80'*10000 1326 (+296%) 5253
      utf-16be '\x80'+'A'*9999 1322 (+298%) 5258
      utf-16be '\x80'*9999+'\u0100' 1088 (+156%) 2781
      utf-16be '\x80'*9999+'\u8000' 1088 (+155%) 2770
      utf-16be '\x80'*9999+'\U00010000' 1103 (+159%) 2854
      utf-16be '\u0100'*10000 1344 (+221%) 4308
      utf-16be '\u0100'+'A'*9999 1342 (+223%) 4330
      utf-16be '\u0100'+'\x80'*9999 1343 (+221%) 4307
      utf-16be '\u0100'*9999+'\u8000' 1343 (+221%) 4306
      utf-16be '\u0100'*9999+'\U00010000' 1109 (+128%) 2529
      utf-16be '\u8000'*10000 248 (+341%) 1094
      utf-16be '\u8000'+'A'*9999 1340 (+223%) 4331
      utf-16be '\u8000'+'\x80'*9999 1341 (+221%) 4307
      utf-16be '\u8000'+'\u0100'*9999 1341 (+221%) 4309
      utf-16be '\u8000'*9999+'\U00010000' 239 (+290%) 931
      utf-16be '\U00010000'*10000 399 (+160%) 1037
      utf-16be '\U00010000'+'A'*9999 1230 (+152%) 3101
      utf-16be '\U00010000'+'\x80'*9999 1218 (+154%) 3095
      utf-16be '\U00010000'+'\u0100'*9999 1220 (+154%) 3095
      utf-16be '\U00010000'+'\u8000'*9999 257 (+318%) 1074

    13. serhiy-storchaka commented on May 14, 2012

      @serhiy-storchaka
      serhiy-storchaka
      on May 14, 2012
      MemberAuthor

      The patch updated with a little clarified code and added comments.

    14. serhiy-storchaka commented on May 15, 2012

      @serhiy-storchaka
      serhiy-storchaka
      on May 15, 2012
      MemberAuthor

      Here are two new patch. Checking for characters out-of-range moved,
      making the code simpler. Theoretically it is a bit slow down decoding of
      short UCS1 strings (up to 1 and 3 chars on 32- and 64-bit), but
      practically there is no difference. The second patch is different from
      the first patch that masks are not calculated and specified explicitly.
      I am not sure that it improves readability. The commiter has the choice.

    15. python-dev commented on May 15, 2012

      @python-dev
      python-devmannequin
      on May 15, 2012
      Mannequin

      New changeset cdcc816dea85 by Antoine Pitrou in branch 'default':
      Issue bpo-14624: UTF-16 decoding is now 3x to 4x faster on various inputs.
      http://hg.python.org/cpython/rev/cdcc816dea85

    16. pitrou commented on May 15, 2012

      @pitrou
      pitrou
      on May 15, 2012
      Member

      Thank you Serhiy! Now committed.

    17. pitrou
      closed this as completedon May 15, 2012

    18. serhiy-storchaka commented on May 19, 2012

      @serhiy-storchaka
      serhiy-storchaka
      on May 19, 2012
      MemberAuthor

      Thank you, Antoine. Now only bpo-14625 waits for review.

      changeset: 77012:3430d7329a3b
      +* UTF-8 and UTF-16 decoding is now 2x to 4x faster.

      In fact now UTF-16 decoding faster for a maximum of +25% compared to Python 3.2 on my computers (and sometimes a little slower yet). 2x to 4x it is faster compared to former slow-downed Python 3.3 (thanks to PEP-393).

    19. ezio-melotti
      transferred this issue fromon Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

    Metadata

    Metadata

    Assignees

    No one assigned

      Labels

      interpreter-core(Objects, Python, Grammar, and Parser dirs)performancePerformance or resource usagetopic-unicode

      Projects

      No projects

        Milestone

        No milestone

        Relationships

        None yet

        Development

        No branches or pull requests

        Issue actions