Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re: Re: Re: Re: Re: Perl Idioms Explained: && and || "Short Circuit" operators

by BrowserUk (Pope)
on Oct 22, 2003 at 23:56 UTC ( #301428=note: print w/ replies, xml ) Need Help??


in reply to Re: Re: Re: Re: Perl Idioms Explained: && and || "Short Circuit" operators
in thread Perl Idioms Explained - && and || "Short Circuit" operators

No. On every implementation I've seen, switch/case is implemented almost exactly like perl's goto-EXPR, except that the target label is actually a machine instruction address known at compile time.

This simple C program

#include <stdio.h> int main() { switch ( 4 ) { case 1: printf( "case1\n" ); break; case 2: printf( "case2\n" ); break; case 3: printf( "case3\n" ); break; case 4: printf( "case4\n" ); break; case 5: printf( "case5\n" ); break; case 6: printf( "case6\n" ); break; } }

Is translated into this assembler

.386p ifdef ??version if ??version GT 500H .mmx endif endif model flat ifndef ??version ?debug macro endm endif ?debug S "test.c" ?debug T "test.c" _TEXT segment dword public use32 'CODE' _TEXT ends _DATA segment dword public use32 'DATA' _DATA ends _BSS segment dword public use32 'BSS' _BSS ends DGROUP group _BSS,_DATA _TEXT segment dword public use32 'CODE' _main proc near ?live1@0: ; ; int main() { ; push ebp mov ebp,esp ; ; ; switch ( 4 ) { ; @1: mov eax,4 cmp eax,6 ja short @2 jmp dword ptr [@10+4*eax] @10: dd @2 dd @9 dd @8 dd @7 dd @6 dd @5 dd @4 ; ; case 1: printf( "case1\n" ); break; ; @9: push offset s@ call _printf pop ecx @13: pop ebp ret ; ; case 2: printf( "case2\n" ); break; ; @8: push offset s@+7 call _printf pop ecx @14: pop ebp ret ; ; case 3: printf( "case3\n" ); break; ; @7: push offset s@+14 call _printf pop ecx @15: pop ebp ret ; ; case 4: printf( "case4\n" ); break; ; @6: push offset s@+21 call _printf pop ecx @16: pop ebp ret ; ; case 5: printf( "case5\n" ); break; ; @5: push offset s@+28 call _printf pop ecx @17: pop ebp ret ; ; case 6: printf( "case6\n" ); break; ; @4: push offset s@+35 call _printf pop ecx ; ; } ; } ; @2: @11: @12: pop ebp ret _main endp _TEXT ends _DATA segment dword public use32 'DATA' s@ label byte ; s@+0: db "case1",10,0 ; s@+7: db "case2",10,0 ; s@+14: db "case3",10,0 ; s@+21: db "case4",10,0 ; s@+28: db "case5",10,0 ; s@+35: db "case6",10,0 align 4 _DATA ends _TEXT segment dword public use32 'CODE' _TEXT ends public _main extrn _printf:near ?debug D "e:\Bcc55\include\_nfile.h" 10459 12320 ?debug D "e:\Bcc55\include\_null.h" 10459 12320 ?debug D "e:\Bcc55\include\_defs.h" 10459 12320 ?debug D "e:\Bcc55\include\_stddef.h" 10459 12320 ?debug D "e:\Bcc55\include\stdio.h" 10459 12320 ?debug D "test.c" 12119 1102 end

The salient part of which is

; switch ( 4 ) { ; @1: mov eax,4 // Load the selector expression (4) cmp eax,6 // Test if its outside the range of options (6) ja short @2 // If it is, jump to the default /* Otherwise, add the value * the size of the lookup table entries (4bytes) and add it to the base address of the dispatch table, then jump to the address help at that location in the table. */ jmp dword ptr [@10+4*eax] @10: dd @2 dd @9 dd @8 dd @7 dd @6 dd @5 dd @4 ; ; case 1: printf( "case1\n" ); break; ; @9:

Originally, the offsets were byte offsets and the table size had a maximum of 255. These days, the table entries are absolute 32-bit addresses and the table size can theoretically be 2 GB in size. In all cases, it is very fast.

The interesting part is coding the switch expression so that it converts your range of possible matches to an integer. String lookups can be index using str(i)(n)cmp() quite easily, but I've had to code some more esoteric versions in the past.


Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
Hooray!


Comment on Re: Re: Re: Re: Re: Perl Idioms Explained: && and || "Short Circuit" operators
Select or Download Code
Re: Re: Re: Re: Re: Re: Perl Idioms Explained: && and || "Short Circuit" operators
by demerphq (Chancellor) on Oct 23, 2003 at 00:13 UTC

    So would I be correct in understanding that

    switch (ulong_val) { case 0 : handle_case0; break; case ULONGMAX: handle_caseMAX; break; default : handle_default; break; }

    Generates a _huge_ dispatch table? Can that be correct? I found your dissambly to be very interesting, but I personaly would have like to have seen what happens when the input is discontiguous and operated on a variable and not a constant. Any chance of an update BrowserUk?


    ---
    demerphq

      First they ignore you, then they laugh at you, then they fight you, then you win.
      -- Gandhi


      Modern C compilers have the smarts built in to make intelligent decisions on what code to emit. In the case of your example of 2 widely spaced cases, it produces this

      Which as you can see, gets translated into a test and jump for the extreme case, another test and jump for the default case and a fall through for the 1 case.

      If you combine a contiguous range and an extreme case, you get.

        So the rub of this is that switch() is not O(1). But that as often as possible the optimizer will do its best to convert it to be so. Which if you think about it means that from a programmers perspective its merely syntactic sugar for a chain of ifs. I say this becuase its just as reasonable to assume that the optimizer could figure out that a chain of ifs can be represented by a jump table and do the same optimization there.

        Also in your private message to me you mentioned that on occassion the compiler constructs a multi gigabyte executable to try to provide this "optimization". Which I would have thought _totally_ defeats the purpose given that the swap/thrash times involved to implement it would _far_ outweigh the execution times of a chained if.

        Anyway, many thanks to you and the other respondants about this. I have certainly learned something.


        ---
        demerphq

          First they ignore you, then they laugh at you, then they fight you, then you win.
          -- Gandhi


Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://301428]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (12)
As of 2014-07-10 19:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When choosing user names for websites, I prefer to use:








    Results (215 votes), past polls