Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

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

by demerphq (Chancellor)
on Oct 22, 2003 at 22:38 UTC ( #301410=note: print w/ replies, xml ) Need Help??


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

Im very confused about this node. How does C's switch statement offer O(1) time? Im wracking my brain to see how this could be done without becoming hopelessly inefficient. Also your update is confusing too, the switch like code posted drops out of the loop once a condition has been met. I suppose strictly speaking a series of conditionals can be described as O(N), but this deosnt seem to match up with the spirit of your usage.


---
demerphq

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



Comment on Re: Re: Perl Idioms Explained: && and || "Short Circuit" operators
Download Code
Re: Re: Re: Perl Idioms Explained: && and || "Short Circuit" operators
by BrowserUk (Pope) on Oct 22, 2003 at 23:09 UTC

    Now you've confused me:)

    Doesn't O(1) (in this case) mean that a condition is only tested once with the C-switch statement. Whereas the implementation shown in the OP, all tests from 0 to N where N is the met condition's lexical position within the group, hence worst case O(N) if the last case is the one chosen?

    It was this bit of your post that confused me

    ...Im wracking my brain to see how this could be done without becoming hopelessly inefficient....

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

      Well, what I mean is that I dont see how in C the conditional is only evaluated once. I dont know enough about how C implements a case statement to say for sure But i dont see how a case statement could be implemented in such a way without adding a lot of code to the statement, which would potentially be far more expensive than converting it to a series of conditionals. For instance something like this

      switch (val) { case 1 : handle_case1; break; case 2 : handle_case2; break; case 5 : handle_case5; case 10: handle_case10; default: handle_default; }

      I would guess would get converted to something like

      if (val == 1) { handle_case1; } elsif (val == 2) { handle_case2; } else { if (val == 5) { goto CASE5; } elsif (val == 10) { goto CASE10; } else { goto DEFAULT; } CASE5: handle_case5; CASE10: handle_case10; DEFAULT: handle_default; }

      Or something like it. I just dont see how it could be handled otherwise. Perhaps the fact that it only operates on ints means that there is a neater optimisation. But if you extend switch to handle strings as it does in pascal then I think the situation becomes even more difficult.

      Thanks to the CB for clarifying that switch only handles ints. That issue may make my ruminations on this invalid. I dont know. Id be interested to hear from someone that does. As I said, this issue confuses me. :-)


      ---
      demerphq

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


        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

        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!

Re: Re: Re: Perl Idioms Explained: && and || "Short Circuit" operators
by fletcher_the_dog (Friar) on Oct 22, 2003 at 23:17 UTC
    C switch statements create an internal jump table that is more or less like a hash so that they can skip testing cases that are are going to fail, this makes them O(1). For example in the following switch statement if 'test' equals 'c' the code jumps right to case 'c', it doesn't test to see if 'test' equals 'a' or 'b':
    switch(test){ case 'a': # do something case 'b': # do something else case 'c': # do something else }
    This of course means that the possible cases (but not the test value) are static and must be known at compile time which decreases flexibilty but increases speed.

      Im still confused how this works. :-) How does it map discontiguous values into a jump table without doing a lot of work?


      ---
      demerphq

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


        Think of the c compiler doing something like this:
        sub CompileSwitch{ my %hash; my @commands; my $command = 0; my $mydefault; while (@_) { my $case = shift; my $code = shift; if ($case eq "default") { $mydefault = $code; last; } $hash{$case} = $command++; push @commands,$code; } return sub{ my $case = shift; my $i = $hash{$case}; if (defined $i) { # fall through , a C switch doesn't test following cases it # just goes to the end or till it hits a break for (;$i<@commands;$i++) { # execute code &{$commands[$i]} } } elsif (defined $mydefault) { &$mydefault; } } } my $switch = CompileSwitch( 'a'=>sub { print "a"}, 'b'=>sub { print "b"}, 'c'=>sub { print "c"; last}, 'x'=>sub { print "x"}, 'y'=>sub { print "y"}, 'z'=>sub { print "z"}, 'default'=>sub { print "unknown case"} ); foreach (qw(a b c d e f x y z)) { print "testing $_\n"; $switch->($_); print "\n"; } __OUTPUT__ testing a abc testing b bc testing c c testing d unknown case testing e unknown case testing f unknown case testing x xyz testing y yz testing z z
Re: Re: Re: Perl Idioms Explained: && and || "Short Circuit" operators
by pg (Canon) on Oct 23, 2003 at 02:34 UTC

    It is correct to say C's switch is O(1).

    Theoritically speaking, BrowserUK is also wrong when he said O(1) means test once. However he had something in () said "in this case", which made himself "politically" right ;-)

    Strictly speaking, O(1) means that the cost is a constant, not a function of any variable, thus it is considered ideal, as the cost is 100% predictable. The complexity (worst scenario cost) of the switch statement is determined at the coding time, not base on the input data at execution time.

    C's switch statement falls into this category. I personally believe that there is a benefit to have it in Perl.

      Indeed if having an execution of O(1) is switch's primary benefit, that will not be present in Perl6's switch, except perhaps in primitive uses. C's switches must have constant case labels to facilitate the chicanery it uses for producing O(1) behavior. Perl6 will not enforce constants as the "labels". From what I understand, you'll be able to use any Perl expression you wish as a label. Therefore, each one will need to be evaluated, at runtime, to find the correct one. I think in this case, the benefit to the switch statement for Perl would be its conciseness over using chained if/elses.

      kelan


      Perl6 Grammar Student

        Hrm, that's kinda unfortunate. A C-style switch is always a tradeoff, flexibility wise, but the tradeoff can be big if you have a large number of cases. I supose if we're lucky, perl6 will optimize switches that use constant expressions into a jump table, though I suspect such a feature wouldn't be out in the first version of perl6--time enough for optimizations later.

        ----
        I wanted to explore how Perl's closures can be manipulated, and ended up creating an object system by accident.
        -- Schemer

        :(){ :|:&};:

        Note: All code is untested, unless otherwise stated

        I look forward to the power of the P6 Given/When construct immensely, but I still hanker for the the limited but oh-so-useful and efficient switch/case construct. There are so many occasions when this simple integer-based dispatch mechanism is exactly all that is needed, that I think it would be worth having, in addition to the much more powerful, but equally, much less efficient Given/When construct.

        I'm aware of theDamian's switch module, but it attempts to be much more than a simple switch construct, coming much closer to the given/when flexibility. The downside of that it that it is much less efficient for the predominant 'simple case'. I've also had problems with it getting confused.

        Hash based dispatch tables are okay and pretty efficient, but the need to put the selected code into either a sub or runtime eval makes it less useful for things where the selected code is minimal and speed important. Calling a sub to increment or decrement a count is high overhead if your scanning long strings and maintaining counts as you go.


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

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (9)
As of 2014-09-17 20:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (99 votes), past polls