Skip to content

Improve performance for switch in ceval.c when using MSVC #91719

Closed
Closed
Improve performance for switch in ceval.c when using MSVC#91719
Labels
performancePerformance or resource usagetype-bugAn unexpected behavior, bug, or error

Description

@gvanrossum
gvanrossum
opened on Apr 20, 2022

We've received reports of MSVC not generating optimal code, e.g. gh-89279.

One possible improvement would be to get the big switch statement in ceval.c to generate better code. It's been rumored that MSVC will generate essentially a computed goto if all cases are filled.

See my investigations at faster-cpython/ideas#321 (comment)

Activity

  1. gvanrossum
    added
    type-bugAn unexpected behavior, bug, or error
    on Apr 20, 2022
  2. AlexWaygood
    added
    performancePerformance or resource usage
    on Apr 20, 2022
  3. gvanrossum
    added a commit that references this issue on Apr 21, 2022

    GH-91719: Make MSVC generate somewhat faster switch code (#91718)

    f8dc618

  4. gvanrossum commented on Apr 23, 2022

    @gvanrossum
    gvanrossum
    on Apr 23, 2022
    MemberAuthor

    Fixed by #91718.

  5. gvanrossum
    closed this as completedon Apr 23, 2022
  6. vstinner
    added 2 commits that reference this issue on Apr 25, 2022

    gh-91719: Add pycore_opcode.h internal header file (#91906)

    64a54e5

    gh-91719: Mark pycore_opcode.h as generated in .gitattributes (#91976)

    b733708

  7. neonene commented on May 22, 2022

    @neonene
    neonene
    on May 22, 2022
    Contributor

    [3.12] REPORT: Efficient switch(opcode) seems to require 182 or more effective cases. Starting from e48ac9c with 179 opcodes, the switch loads indexed memory twice, not once. I expect next alpha to have a sufficient number of opcodes.

    Details of the switch in e48ac9c (release build) 
    lea rcx,qword ptr ds:[7FEF2F20000]     | ceval.c:1827
movzx eax,r13b                         |
mov rdi,r14                            |
mov dword ptr ss:[rbp-70],eax          |
mov rdx,r14                            |
mov qword ptr ss:[rbp-60],r12          |
mov r9,r14                             |
mov qword ptr ss:[rsp+78],r14          |
mov r11,r14                            |
movzx eax,byte ptr ds:[rcx+rax+22C7BC] | <<<<<
mov r8,r14                             |
mov qword ptr ss:[rsp+70],r12          |
mov qword ptr ss:[rsp+60],r12          |
mov qword ptr ss:[rbp-78],r12          |
mov ecx,dword ptr ds:[rcx+rax*4+22C4F0 | <<<<<
lea rax,qword ptr ds:[7FEF2F20000]     |
add rcx,rax                            |
mov qword ptr ss:[rsp+68],r12          |
movsxd rsi,r15d                        |
jmp rcx                                |

    Example changes of EXTRA_CASES in pycore_opcode.h:

    #define EXTRA_CASES \
    case 253: Py_FatalError("op:253"); \
    case 254: Py_FatalError("op:254"); \
    case 178: \
    case 179: \
    case 180: \
    case 181: \
    case 182: \
    case 183: \
    ...
    case 251: \
    case 252: \
        ;


lea rcx,qword ptr ds:[7FEF2F20000]     | ceval.c:1827
movzx eax,r13b                         |
mov rdi,r14                            |
mov dword ptr ss:[rbp-70],eax          |
mov r9,r14                             |
mov qword ptr ss:[rbp-60],r12          |
mov r8,r14                             |
mov qword ptr ss:[rsp+78],r14          |
mov r11,r14                            |
mov ecx,dword ptr ds:[rcx+rax*4+22C4E8 | <<<<<
mov rdx,r14                            |
lea rax,qword ptr ds:[7FEF2F20000]     |
mov qword ptr ss:[rsp+70],r12          |
add rcx,rax                            |
mov qword ptr ss:[rsp+60],r12          |
mov qword ptr ss:[rbp-78],r12          |
mov qword ptr ss:[rsp+68],r12          |
movsxd rsi,r15d                        |
jmp rcx                                |

    #define EXTRA_CASES \
    case 252: Py_FatalError("op:252"); \
    case 253: Py_FatalError("op:253"); \
    case 254: Py_FatalError("op:254"); \
    default:


mov qword ptr ss:[rsp+48],r14          | ceval.c:1827
mov r9,qword ptr ss:[rsp+30]           |
lea rcx,qword ptr ds:[7FEF2F20000]     |
movzx edi,r13b                         |
mov rdx,r12                            |
mov qword ptr ss:[rsp+58],rdx          |
mov r8,r14                             |
mov qword ptr ss:[rbp-80],r14          |
cmp edi,FF                             |
ja python312.7FEF314BFE3               | unknown opcode error
mov ecx,dword ptr ds:[rcx+rdi*4+22C2E0 | <<<<<
lea rax,qword ptr ds:[7FEF2F20000]     |
add rcx,rax                            |
movsxd rsi,r15d                        |
jmp rcx                                |

    #define EXTRA_CASES \
    case 178: Py_FatalError("op:178"); \
    case 179: Py_FatalError("op:179"); \
    case 180: Py_FatalError("op:180"); \
    default:


mov qword ptr ss:[rsp+48],r14          | ceval.c:1827
mov r9,qword ptr ss:[rsp+30]           |
lea rcx,qword ptr ds:[7FEF30B0000]     |
movzx edi,r13b                         |
mov rdx,r12                            |
mov qword ptr ss:[rsp+58],rdx          |
mov r8,r14                             |
mov qword ptr ss:[rbp-80],r14          |
cmp edi,FF                             |
ja python312.7FEF32DBFE3               | unknown opcode error
mov ecx,dword ptr ds:[rcx+rdi*4+22C2E0 | <<<<<
lea rax,qword ptr ds:[7FEF30B0000]     |
add rcx,rax                            |
movsxd rsi,r15d                        |
jmp rcx                                |

    As for performance advantage over loading memory twice, the examples above has little for me. Each of the following was faster on PGO:

    • Avoid falling through in EXTRA_CASES, giving each an exclusive body without default.
    • Use something better than Py_FatalError().
    • Make default case unreachable.

  8. gvanrossum commented on May 25, 2022

    @gvanrossum
    gvanrossum
    on May 25, 2022
    MemberAuthor

    Thanks for the detailed and clear report. It sounds like in the long term we would be okay without depending on the EXTRA_CASES macro, though we might want to add a check somewhere that we have at least 182 cases. (It would be better if we could directly test for the extra memory indirection but that seems beyond our current tooling. :-)

    As for performance advantage over loading memory twice, the examples above has little for me. Each of the following was faster on PGO:

    • Avoid falling through in EXTRA_CASES, giving each an exclusive body without default.
    • Use something better than Py_FatalError().
    • Make default case unreachable.

    I'm not sure how come any of those would make a difference given that we never execute the default case. Or am I not following you?

  9. neonene commented on May 27, 2022

    @neonene
    neonene
    on May 27, 2022
    Contributor

    I'm not sure why either(EDIT: improved by #94364), so I tried making a small reproducer. After trimming the cases in eval loop, INSTRUCTION_START() macro remained loading memory twice, which is not implemented in 3.10. I'd like to look into after new opcodes are introduced into 3.12.

    #include <stdint.h>
typedef uint16_t _Py_CODEUNIT;

int
main(int argc, char *argv[])
{
    uint8_t opcode = 0;
    _Py_CODEUNIT tmp[10];
    _Py_CODEUNIT *next_instr = tmp;

    switch (opcode) {
    case 255 : next_instr++; break;
    case   0 : next_instr++; break;
    ...
    }
}

    Current jump behaviors using case 255:

    Equivalent to if-else with 6 cases 
        switch (opcode) {
    case 255 : next_instr++; break;
    case   0 : next_instr++; break;
    case   1 : next_instr++; break;
    case   2 : next_instr++; break;
    case   3 : next_instr++; break;
    case   4 : next_instr++; break;
    }


mov qword ptr ss:[rsp+10],rdx
mov dword ptr ss:[rsp+8],ecx
sub rsp,38
mov rax,qword ptr ds:[<__security_cook
xor rax,rsp
mov qword ptr ss:[rsp+28],rax
mov byte ptr ss:[rsp],0
lea rax,qword ptr ss:[rsp+10]
mov qword ptr ss:[rsp+8],rax
movzx eax,byte ptr ss:[rsp]
mov dword ptr ss:[rsp+4],eax
cmp dword ptr ss:[rsp+4],3
jg repro.13FE36EC7
cmp dword ptr ss:[rsp+4],3
je repro.13FE36F1A
cmp dword ptr ss:[rsp+4],0
je repro.13FE36EEA
cmp dword ptr ss:[rsp+4],1
je repro.13FE36EFA
cmp dword ptr ss:[rsp+4],2
je repro.13FE36F0A
jmp repro.13FE36F38
cmp dword ptr ss:[rsp+4],4
je repro.13FE36F2A
cmp dword ptr ss:[rsp+4],FF
je repro.13FE36EDA
jmp repro.13FE36F38
mov rax,qword ptr ss:[rsp+8]
add rax,2
mov qword ptr ss:[rsp+8],rax
jmp repro.13FE36F38
mov rax,qword ptr ss:[rsp+8]
add rax,2
mov qword ptr ss:[rsp+8],rax
jmp repro.13FE36F38
mov rax,qword ptr ss:[rsp+8]
add rax,2
mov qword ptr ss:[rsp+8],rax
jmp repro.13FE36F38
mov rax,qword ptr ss:[rsp+8]
add rax,2
mov qword ptr ss:[rsp+8],rax
jmp repro.13FE36F38
mov rax,qword ptr ss:[rsp+8]
add rax,2
mov qword ptr ss:[rsp+8],rax
jmp repro.13FE36F38
mov rax,qword ptr ss:[rsp+8]
add rax,2
mov qword ptr ss:[rsp+8],rax
xor eax,eax
mov rcx,qword ptr ss:[rsp+28]
xor rcx,rsp
call repro.13FE32513
add rsp,38
ret
    Single memory load with 7 to 63 cases 
        switch (opcode) {
    case 255 : next_instr++; break;
    case   0 : next_instr++; break;
    ...
    case   5 : next_instr++; break;  // from here
    case   6 : next_instr++; break;
    case   7 : next_instr++; break;
    ...
    case  61 : next_instr++; break;
    }


mov qword ptr ss:[rsp+10],rdx          |
mov dword ptr ss:[rsp+8],ecx           |
sub rsp,48                             |
mov rax,qword ptr ds:[<__security_cook |
xor rax,rsp                            |
mov qword ptr ss:[rsp+30],rax          |
mov byte ptr ss:[rsp],0                |
lea rax,qword ptr ss:[rsp+18]          |
mov qword ptr ss:[rsp+8],rax           |
movzx eax,byte ptr ss:[rsp]            |
mov dword ptr ss:[rsp+10],eax          |
cmp dword ptr ss:[rsp+10],FF           |
jg repro.13F3E6ED9                     |
cmp dword ptr ss:[rsp+10],FF           |
je repro.13F3E6EDB                     |
cmp dword ptr ss:[rsp+10],5            |
ja repro.13F3E6F49                     |
movsxd rax,dword ptr ss:[rsp+10]       |
lea rcx,qword ptr ds:[13F3E0000]       |
mov eax,dword ptr ds:[rcx+rax*4+6F60]  | <<<<<
add rax,rcx                            |
jmp rax                                |
    Double memory load with 64 to 181 cases 
        switch (opcode) {
    case 255 : next_instr++; break;
    case   0 : next_instr++; break;
    ...
    case  62 : next_instr++; break;  // from here
    case  63 : next_instr++; break;
    case  64 : next_instr++; break;
    ...
    case 179 : next_instr++; break;
    }


mov qword ptr ss:[rsp+10],rdx          |
mov dword ptr ss:[rsp+8],ecx           |
sub rsp,38                             |
mov rax,qword ptr ds:[<__security_cook |
xor rax,rsp                            |
mov qword ptr ss:[rsp+28],rax          |
mov byte ptr ss:[rsp+8],0              |
lea rax,qword ptr ss:[rsp+10]          |
mov qword ptr ss:[rsp],rax             |
movzx eax,byte ptr ss:[rsp+8]          |
mov dword ptr ss:[rsp+C],eax           |
cmp dword ptr ss:[rsp+C],FF            |
ja repro.13F4A72F1                     |
movsxd rax,dword ptr ss:[rsp+C]        |
lea rcx,qword ptr ds:[13F4A0000]       |
movzx eax,byte ptr ds:[rcx+rax+740C]   | <<<<<
mov eax,dword ptr ds:[rcx+rax*4+7308]  | <<<<<
add rax,rcx                            |
jmp rax                                |
    Single memory load with 182 or more cases 
        switch (opcode) {
    case 255 : next_instr++; break;
    case   0 : next_instr++; break;
    ...
    case 180 : next_instr++; break;  // from here
    case 181 : next_instr++; break;
    case 182 : next_instr++; break;
    ...
    case 254 : next_instr++; break;
    }


mov qword ptr ss:[rsp+10],rdx          |
mov dword ptr ss:[rsp+8],ecx           |
sub rsp,38                             |
mov rax,qword ptr ds:[<__security_cook |
xor rax,rsp                            |
mov qword ptr ss:[rsp+28],rax          |
mov byte ptr ss:[rsp+8],0              |
lea rax,qword ptr ss:[rsp+10]          |
mov qword ptr ss:[rsp],rax             |
movzx eax,byte ptr ss:[rsp+8]          |
mov dword ptr ss:[rsp+C],eax           |
cmp dword ptr ss:[rsp+C],FF            |
ja repro.13F847ABF                     |
movsxd rax,dword ptr ss:[rsp+C]        |
lea rcx,qword ptr ds:[13F840000]       |
mov eax,dword ptr ds:[rcx+rax*4+7AD4]  | <<<<<
add rax,rcx                            |
jmp rax                                |

    Another behavior without case 255

    MSVC seems to check whether existing cases are continuous or not, rather than their count. The following shows an extra memory load:

    Details 
        // They are discontinuous and their maximum opcode is greater than 20
    switch (opcode) {
    case   0 : next_instr++; break;
    case   5 : next_instr++; break;
    case  18 : next_instr++; break;
    case  19 : next_instr++; break;
    case  20 : next_instr++; break;
    case  21 : next_instr++; break;
    }


mov qword ptr ss:[rsp+10],rdx          |
mov dword ptr ss:[rsp+8],ecx           |
sub rsp,48                             |
mov rax,qword ptr ds:[<__security_cook |
xor rax,rsp                            |
mov qword ptr ss:[rsp+30],rax          |
mov byte ptr ss:[rsp],0                |
lea rax,qword ptr ss:[rsp+18]          |
mov qword ptr ss:[rsp+8],rax           |
movzx eax,byte ptr ss:[rsp]            |
mov dword ptr ss:[rsp+10],eax          |
cmp dword ptr ss:[rsp+10],15           |
ja repro.13FE56F27                     |
movsxd rax,dword ptr ss:[rsp+10]       |
lea rcx,qword ptr ds:[13FE50000]       |
movzx eax,byte ptr ds:[rcx+rax+6F58]   | <<<<<
mov eax,dword ptr ds:[rcx+rax*4+6F3C]  | <<<<<
add rax,rcx                            |
jmp rax                                |
mov rax,qword ptr ss:[rsp+8]           |
add rax,2                              |
mov qword ptr ss:[rsp+8],rax           |
jmp repro.13FE56F27                    |
mov rax,qword ptr ss:[rsp+8]           |
add rax,2                              |
mov qword ptr ss:[rsp+8],rax           |
jmp repro.13FE56F27                    |
mov rax,qword ptr ss:[rsp+8]           |
add rax,2                              |
mov qword ptr ss:[rsp+8],rax           |
jmp repro.13FE56F27                    |
mov rax,qword ptr ss:[rsp+8]           |
add rax,2                              |
mov qword ptr ss:[rsp+8],rax           |
jmp repro.13FE56F27                    |
mov rax,qword ptr ss:[rsp+8]           |
add rax,2                              |
mov qword ptr ss:[rsp+8],rax           |
jmp repro.13FE56F27                    |
mov rax,qword ptr ss:[rsp+8]           |
add rax,2                              |
mov qword ptr ss:[rsp+8],rax           |
xor eax,eax                            |
mov rcx,qword ptr ss:[rsp+30]          |
xor rcx,rsp                            |
call repro.13FE52513                   |
add rsp,48                             |
ret                                    |

  10. erlend-aasland commented on May 27, 2022

    @erlend-aasland
    erlend-aasland
    on May 27, 2022
    Contributor

    Do you want to reopen this, or create a new issue?

  11. neonene commented on May 27, 2022

    @neonene
    neonene
    on May 27, 2022
    Contributor

    The faster-cpython site would be better for more information.

  12. gvanrossum
    added a commit that references this issue on Jun 30, 2022

    gh-91719: Reload opcode on unknown error so that C can optimize the d…

    ea39b77
  13. miss-islington
    added a commit that references this issue on Jun 30, 2022

    pythongh-91719: Reload opcode on unknown error so that C can optimize…

    a28f633
  14. gvanrossum
    added 2 commits that reference this issue on Jun 30, 2022

    gh-91719: Reload opcode on unknown error so that C can optimize the d…

    fdc0081

    pythongh-91719: Reload opcode on unknown error so that C can optimize…

    c9920dd
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

    performancePerformance or resource usagetype-bugAn unexpected behavior, bug, or error

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions