Jump to content

Talk:Switch statement/Archive 1

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
Archive 1

How does it work?

Just out of curiosity does anyone actually know the mechanics behind a switch statement? In other words how does a switch statement look in assembly? is it a jump, or a continuous set of conditionals?

I suppose this illustrates what im asking

int foo (int i)
{
  switch (i)
  {
  case 1: return 1;
  case 2: return 2;
  ...
  case n: return n;
  default: return 0;
  }
}

look the same as a whole lot of:

if else if else if

or would it jump immediately to the correct code? (i.e. actually switch) if it does switch, could someone explain how this works?

155.232.128.10 10:19, 24 January 2007 (UTC)

Naturally, it's not dictated by the language. (Or at least not by C). It is certainly correct for a compiler to emit a long chain of if, else if, else if... but it is possible to do much better. For example, the compiler can use the control variable as an index into a jump table. Of course in the example you cite above, the programmer would do much better simply to return n; without using a switch at all. ;) Psyno 02:00, 8 March 2007 (UTC)
It's a good question, and actually I think the article could use a section on that from an expert. The reason I think it's worth mentioning is that it's possible that it affects the performance of the program. When you are able to use a switch statement, is that better performance-wise than simply using a chain of "if" statements? I think there should be a discussion on that in the article by someone knowledgeable. Even if the answer is no, it is still worth mentioning in the article that the switch statement exists for reasons like code readability and there is no performance difference.
Mbarbier 05:14, 25 March 2007 (UTC)
In most BASIC's, a 'case label' is 'evaluated' the same way an IF/ELSE condition is evaluated. Historically, this meant that the 'evaluation' routine was called on the expression. This allows you to put functions or variables as both the switch variable and the case variable: SELECT fn1(x), CASE fn2(y). This may then be extended to allow a range or sequence as the case 'label', and allows dynamic (data dependent) logic expressions, sometimes implemented in a very restricted form in other languages by the keyword "IN", as <IF 'a' IN myset>. In PASCAL, a 'case label' is normally implemented as a mapped constant. This allows the branching logic to be evaluated at compilation. This is equivilant to allowing IF statements only with comparison to a constant: <IF (a==5)>, which is a well-known optimisation. Since all programming languages are Turing Complete, any program can be written using either approach.150.101.166.15 (talk) 03:08, 20 November 2007 (UTC)
In 2006, I had two examples in branch table showing how the equivalent of a switch statement worked in IBM Assembler. It was deleted by NicM unknown to me. I have just added a comment about the deletion in his Talk page.

Unfortunately the Switch statement suffers from a limitation in ANSI C because you can only 'branch' to labels within the function itself. This can be overcome to some extent by placing labels within the function that then call an external function. Sadly, there is a performance penalty for so doing because of the implied push/pop of stacks required for the function call. My first example showed that only 5 machine instructions were required to branch to a label within 4k of the branch table. The 2nd example showed how this could be extended to within 64K (actually 256k if labels were forced onto word boundaries) whilst at the same time halving the size of the branch table by using two byte offsets instead of actual branch instructions. By using 4 byte offsets (or addresses) extends this to a branch range of 2 gigabytes (or 8 gigabytes if aligned on word boundary). I repeat the deleted examples here:- The much longer example below assumes that the input consists of a random letter of the alphabet between A and Z in V1 and two numeric values V2 and V3. It performs the following steps:

  • V1 is checked for for the values "A" (add, index 0), "S" (subtract, index 1), "M" (multiply, index 2) and "D" (divide, index 3); all other inputs are considered invalid.
  • a branch is made into the branch table to jump to a seperate code section for each operation.

The following is an IBM System/360 example. The instruction length is 4 for the branch instruction.

          SR    R1,R1        CLEAR REGISTER used for input value.
 LOOP     IC    R1,V1        INSERT CHARACTER "V1" into the cleared reg.
          IC    R1,TABLE2(R1)    "CONVERT" value (to 0,4,8,12 etc)
          B     TABLE1(R1)         GO TO APPROPRIATE SECTION OF PROGRAM
 * this is where the (4 byte) branch instructions start 
 TABLE1   DS    0H               *** BRANCH TABLE *** (Keep in order)
          B     INVALID          0  (Any invalid character EG E,P,X,F)
          B     ADD              4  GO ADD V2 to V1
          B     SUBTRACT         8  GO SUBTRACT V2 FROM V1
          B     DIVIDE           12 GO and DIVIDE V1 BY V2
          B     MULTIPLY         16 GO and MULTIPLY V1 BY V2
 * end of branch table
 ADD      DS    0H               *** ADD section of program ***
 * section of code to perform addition
          AP    V2,V3            perform addition
          B     FINISH           end program
 SUBTRACT DS    0H 
 *              *** SUBTRACT section of program ***
 MULTIPLY DS    0H
 *              *** MULTIPLY section of program ***
 DIVIDE   DS    0H
 *              *** DIVIDE section of program ***
 INVALID  DS    0H               *** HERE on error ***
 *
 TABLE2   DC    256AL1(0)  TABLE of index values (set to "Invalid" = 00)
          ORG   TABLE1+C'A'
          DC    Al1(04)          VALUE FOR "Add" to replace "A"
          ORG   TABLE1+C'S'   
          DC    Al1(08)          VALUE for "Subtract" to replace "S"
          ORG   TABLE+C'D'
          DC    Al1(12)          VALUE FOR "Divide" to replace "D"
          ORG   TABLE+C'M'
          DC    Al1(16)          VALUE FOR "Multiply" to replace "M"
 *
 V1        DS    C                Input value 1
 V2        DS    PL6              Input value 2             
 V3        DS    PL2              Input Value 3
          END

The above program achieves validation and direct branching to the processing routine without any conditional instructions in just 5 instructions all of which are "fast" instructions.

(The index values in "TABLE2" could have been defined as "self-validating" (at assembly time) and not requiring the branch instructions to be in any particular order but has been shown as above for simplicity).

Similar indexing techniques can be used to handle all manner of efficient processing using coded values initially derived from input streams.

As an alternative to TABLE1 containing actual machine instructions, it could instead have consisted of 2, 3 or 4 byte offsets or absolute addresses of locations in this (or other seperately compiled) program. If the program is small enough, even a one byte offset might suffice for each table entry and represent the offset from the first processing routine to the each of the others (However, a two byte offset will normally provide the best trade off in terms of "expandability" versus table size, permitting 64K of processing code between the first and last entry point.

          SR    R1,R1        CLEAR REGISTER used for input value.         
          IC    R1,V1        INSERT CHARACTER "V1" into the cleared reg
          IC    R1,TABLE1(R1)    "CONVERT" value (to 0,2,4,6 etc)
          ICM   R1,3,TABLE3(R1)    "CONVERT" value (to offset from Add 
 *     
          B     ROUTINES(R1)         GO TO APPROPRIATE SECTION OF PROGRAM
 * this is where the (4 byte) branch instructions start 
 ROUTINES DS    0H               *** Start of processing routines *** 
 * Add follows      
 ADD      DS    0H               *** ADD section of program ***
 * section of code to perform addition
          AP    V2,V3            perform addition
          B     FINISH           end program
 SUBTRACT DS    0H 
 *              *** SUBTRACT section of program ***
 MULTIPLY DS    0H
 *              *** MULTIPLY section of program ***
 DIVIDE   DS    0H
 *              *** DIVIDE section of program ***
 MULTIPLY DS    0H
 *              *** MULTIPLY section of program ***
 INVALID  DS    0H               *** HERE on error ***
 *
 TABLE2   DC    256AL1(0)  TABLE of index values (set to "Invalid" = 00)
          ORG   TABLE1+C'A'
          DC    Al1(02)          VALUE FOR "Add" to replace "A"
          ORG   TABLE1+C'S'   
          DC    Al1(04)          VALUE for "Subtract" to replace "S"
          ORG   TABLE+C'D'
          DC    Al1(06)          VALUE FOR "Divide" to replace "D"
          ORG   TABLE+C'M'
          DC    Al1(08)          VALUE FOR "Multiply" to replace "M"
 *
 TABLE3   DC    AL2(INVALID-ROUTINES)    00 *offset to invalid routine*
          DC    AL2(ADD-ROUTINES)        02
          DC    AL2(SUBTRACT-ROUTINES)   04
          DC    AL2(DIVIDE-ROUTINES)     06
          DC    AL2(MULTIPLY-ROUTINES)   08
 *
 V1       DS    C                Input value 1
 V2       DS    PL6              Input value 2             
 V3       DS    PL2              Input Value 3
          END

No extra instruction has been needed here (it still requires just 5 instructions to get to the entry point of the appropriate routine) but the branch table is replaced by a new table (TABLE3) containing two byte offsets that are indexed by the value extracted from TABLE2 (but now containing 0,2,4,6,or 8 instead of 0,4,8,12 or 16 in previous example).

In this example, "TABLE3" is therefore only 50% of the size of the original branch table (TABLE1) although in this case saving a mere 2 x 4 =16 bytes! For a larger range of possible input values requiring a larger number of routines, this saving might be more significant.

History

The conversion of "raw data" input into coded values stored by the computer was commonplace in the early days of computing but has rapidly declined with the advent of cheap memory, cheap hard discs and cheap processing.

Its advantages are many and efficiencies great. Once a "value" has been converted to an index, it can be used to retrieve the value efficiently from a table or database at any time in the future. For example, there are a relatively few Countries in the world and so can easily be represented by a country code (as used in the international public telephone system). This code can be stored simply as a country number in computer records rather than a text string such as "Central African Republic" resulting in massive savings in storage and processing time. Numeric comparisons are significantly faster than text string comparisons and indexed retrievals significantly faster than string searches or retrieval from a file using a (much longer) "key".

Unfortunately, the Millenium bug has, in part, discredited the coding of raw data. This is a pity since the issue of small real memory is almost redundant but efficient processing is always an advantage. Classifying natural things into a much smaller number of meaningful categories has always been a goal of mankind since the dawn of history. An recent excellent example of this is coding for one of any of 16 million colours using a simple code of just 3 x one byte for each primary colour in range 0-255. " Kdakin3420 (talk) 06:32, 4 February 2008 (UTC)

Wikicode

Does wiki-language have a switch statement useble within a template definition? I need to convert numbers to words an also I need to convert numbers like 4 to 04. Thanks. O'RyanW ( ) 23:33, 21 April 2007 (UTC)

Found it!
{{#switch: <comparison value>   </nowiki>
| <value1> = <result1>
| <value2> = <result2>
| ...
| <valuen> = <resultn>
| <default result>
}}
And it works! O'RyanW ( ) 01:31, 22 April 2007 (UTC)

Perl

I seem to remember a bit of a kerfluffle with Perl not having a switch statement for a long time. Even now, Perl 6's switch statement is a little bit funky. I think this should be mentioned somehow. StaticSan (talk) 06:16, 11 November 2008 (UTC)

Windows PowerShell?

That shell example looks more like a series of if/elif/else statements in bash, or a Lisp "cond" clause, rather than a typical switch statement. Would be nice to have a bit of an explanation or comments since that code is hard to read. 69.181.219.234 (talk) 11:21, 16 March 2009 (UTC)