Author Topic: (Optimization) Use SELECT CASE AS CONST instead of AS LONG for special CASES  (Read 5720 times)

0 Members and 1 Guest are viewing this topic.

Offline Theo Gottwald

  • Administrator
  • Hero Member
  • *****
  • Posts: 897
    • it-berater
Whats with SELECT CASE AS CONST ?
When shall it be use?

In SELECT CASE AS LONG, the compiled code will check the value against each CASE doing a COMPARE, until the first fit is found.
In SELECT CASE AS CONST the compiled code contains a Jump-Table, which has an entry for any possible values, therefore there are not that many compares.
It just takes the indexed value and jumps.

Using SELECT CASE AS CONST DisASM shows something like the code below.
Which is a bit misleading because the JUMP-Table is been treated as ASM-Code from DisASM.

In fact we see that there is slight Overhead against SELECT CASE AS LONG when there are less then (assumption) 40 CASES.
For Subprogramms with a lot of CASES (>40) the AS CONST is faster as it does not need to compare 40 times at worst case.
In fact with SELECT CASE AS CONST each CASE is similar fast, as the jumps are beeing read from the JUMP-TABLE.

Example 1:
Code: [Select]

SUB TestfuncA()
REGISTER R01 AS LONG,R02 AS LONG
!NOP
R01=100
SELECT CASE AS CONST R01
    !NOP
    CASE 12122: REM
    !NOP
  CASE ELSE
    !NOP
    REM
    !NOP
 END SELECT
    ! NOP
END SUB   

' Becomes in DisASM:

4023D0 90                     NOP
4023D1 C7C664000000           MOV ESI, DWORD 00000064
4023D7 8BC6                   MOV EAX, ESI
4023D9 E88F260000             CALL L404A6D
'-----------------------------------------------------------
' expected Jump-Table
'
4023DE 0200                   ADD AL, BYTE PTR [EAX]
4023E0 0000                   ADD BYTE PTR [EAX], AL
4023E2 0100                   ADD DWORD PTR [EAX], EAX
4023E4 0000                   ADD BYTE PTR [EAX], AL
4023E6 F5                     CMC
4023E7 234000                 AND EAX, DWORD PTR [EAX+00]
4023EA EF                     OUT DX, EX
4023EB 234000                 AND EAX, DWORD PTR [EAX+00]
'-----------------------------------------------------------
4023EE 90                     NOP
4023EF 90                     NOP
4023F0 E902000000             JMP L4023F7
4023F5 90                     NOP
4023F6 90                     NOP
4023F7 90                     NOP
4023F8 B805000000             MOV EAX, DWORD 00000005
4023FD 03C6                   ADD EAX, ESI
4023FF 89856CFFFFFF           MOV DWORD PTR [EBP+FFFFFF6C], EAX
402405 C7C700000000           MOV EDI, DWORD 00000000
40240B E903000000             JMP L402413
402410 90                     NOP

'-----------------------------------------------------------
' Jump-Code
'-----------------------------------------------------------
404A6D 5B                     POP EBX
404A6E 2B03                   SUB EAX, DWORD PTR [EBX]
404A70 7C09                   JL  SHORT L404A7B
404A72 3B4304                 CMP EAX, DWORD PTR [EBX+04]
404A75 7D04                   JGE SHORT L404A7B
404A77 FF64830C               JMP  DWORD PTR [EBX+4*EAX+0C]
404A7B FF6308                 JMP  DWORD PTR [EBX+08]

Now lets dig a bit deeper and lets see how the Jump-Table grows with diffrent cases.


Example 2: Just 2 CASES, which follow sequential:

Code: [Select]
SUB TestfuncA()
REGISTER R01 AS LONG,R02 AS LONG
!NOP
R01=100
SELECT CASE AS CONST R01
    !NOP
    CASE 1: REM
    !NOP
    CASE 2: REM
    !NOP
  CASE ELSE
    !NOP
    REM
    !NOP
 END SELECT
    ! NOP
END SUB   

' will be:

4023CE 90                     NOP
4023CF C7C664000000           MOV ESI, DWORD 00000064
4023D5 8BC6                   MOV EAX, ESI
4023D7 E871260000             CALL L404A4D
'-----------------------------------------------------
' Jump-Table - this DisASM Listing is invalid
'-----------------------------------------------------
4023DC 0100                   ADD DWORD PTR [EAX], EAX
4023DE 0000                   ADD BYTE PTR [EAX], AL
4023E0 0200                   ADD AL, BYTE PTR [EAX]
4023E2 0000                   ADD BYTE PTR [EAX], AL
4023E4 FD                     STD
4023E5 234000                 AND EAX, DWORD PTR [EAX+00]
4023E8 F1                     ???
4023E9 234000                 AND EAX, DWORD PTR [EAX+00]
4023EC F723                   MUL  DWORD PTR [EBX]
4023EE 40                     INC  EAX
4023EF 009090E90800           ADD BYTE PTR [EAX+0008E990], DL
4023F5 0000                   ADD BYTE PTR [EAX], AL
4023F7 90                     NOP
4023F8 E902000000             JMP L4023FF
4023FD 90                     NOP
4023FE 90                     NOP
4023FF 90                     NOP
As DisASM tries to walk through the Jump-Table which in fact is not ASM-Code but binary Data,
it gets out of sync with the ASM-Code. Thats why the Listing is only a hint.
It shows the lenght of the Jump-Table.


Example 3: Still 2 CASES, but bigger numeric difference.
In fact we only add a 0. But the final Outcome is a lot bigger then before.

Code: [Select]
SUB TestfuncA()
REGISTER R01 AS LONG,R02 AS LONG
!NOP
R01=100
SELECT CASE AS CONST R01
    !NOP
    CASE 1: REM
    !NOP
    CASE 20: REM
    !NOP
  CASE ELSE
    !NOP
    REM
    !NOP
 END SELECT
    ! NOP
END SUB     

' will become:

4023CE 90                     NOP
4023CF C7C664000000           MOV ESI, DWORD 00000064
4023D5 8BC6                   MOV EAX, ESI
4023D7 E8C1260000             CALL L404A9D
'-----------------------------------------------------
' Jump-Table - this DisASM Listing is invalid
'-----------------------------------------------------
4023DC 0100                   ADD DWORD PTR [EAX], EAX
4023DE 0000                   ADD BYTE PTR [EAX], AL
4023E0 1400                   ADC AL, BYTE 00
4023E2 0000                   ADD BYTE PTR [EAX], AL
4023E4 45                     INC  EBP
4023E5 2440                   AND AL, BYTE 40
4023E7 0039                   ADD BYTE PTR [ECX], BH
4023E9 2440                   AND AL, BYTE 40
4023EB 004524                 ADD BYTE PTR [EBP+24], AL
4023EE 40                     INC  EAX
4023EF 004524                 ADD BYTE PTR [EBP+24], AL
4023F2 40                     INC  EAX
4023F3 004524                 ADD BYTE PTR [EBP+24], AL
4023F6 40                     INC  EAX
4023F7 004524                 ADD BYTE PTR [EBP+24], AL
4023FA 40                     INC  EAX
4023FB 004524                 ADD BYTE PTR [EBP+24], AL
4023FE 40                     INC  EAX
4023FF 004524                 ADD BYTE PTR [EBP+24], AL
402402 40                     INC  EAX
402403 004524                 ADD BYTE PTR [EBP+24], AL
402406 40                     INC  EAX
402407 004524                 ADD BYTE PTR [EBP+24], AL
40240A 40                     INC  EAX
40240B 004524                 ADD BYTE PTR [EBP+24], AL
40240E 40                     INC  EAX
40240F 004524                 ADD BYTE PTR [EBP+24], AL
402412 40                     INC  EAX
402413 004524                 ADD BYTE PTR [EBP+24], AL
402416 40                     INC  EAX
402417 004524                 ADD BYTE PTR [EBP+24], AL
40241A 40                     INC  EAX
40241B 004524                 ADD BYTE PTR [EBP+24], AL
40241E 40                     INC  EAX
40241F 004524                 ADD BYTE PTR [EBP+24], AL
402422 40                     INC  EAX
402423 004524                 ADD BYTE PTR [EBP+24], AL
402426 40                     INC  EAX
402427 004524                 ADD BYTE PTR [EBP+24], AL
40242A 40                     INC  EAX
40242B 004524                 ADD BYTE PTR [EBP+24], AL
40242E 40                     INC  EAX
40242F 004524                 ADD BYTE PTR [EBP+24], AL
402432 40                     INC  EAX
402433 003F                   ADD BYTE PTR [EDI], BH
402435 2440                   AND AL, BYTE 40
402437 009090E90800           ADD BYTE PTR [EAX+0008E990], DL
40243D 0000                   ADD BYTE PTR [EAX], AL
'-----------------------------------------------------
' Jump-Table End - this DisASM Listing is invalid
'-----------------------------------------------------
40243F 90                     NOP
402440 E902000000             JMP L402447
402445 90                     NOP
402446 90                     NOP
402447 90                     NOP

Example 4:
Lets see what happens, if we use bigger numbers, small difference between the CASES:

Code: [Select]
SUB TestfuncA()
REGISTER R01 AS LONG,R02 AS LONG
!NOP
R01=100
SELECT CASE AS CONST R01
    !NOP
    CASE 100: REM
    !NOP
    CASE 101: REM
    !NOP
  CASE ELSE
    !NOP
    REM
    !NOP
 END SELECT
    ! NOP
END SUB               

' we get:

4023CE 90                     NOP
4023CF C7C664000000           MOV ESI, DWORD 00000064
4023D5 8BC6                   MOV EAX, ESI
4023D7 E871260000             CALL L404A4D
4023DC 640000                 FS: ADD BYTE PTR [EAX], AL
4023DF 0002                   ADD BYTE PTR [EDX], AL
4023E1 0000                   ADD BYTE PTR [EAX], AL
4023E3 00FD                   ADD CH, BH
4023E5 234000                 AND EAX, DWORD PTR [EAX+00]
4023E8 F1                     ???
4023E9 234000                 AND EAX, DWORD PTR [EAX+00]
4023EC F723                   MUL  DWORD PTR [EBX]
4023EE 40                     INC  EAX
4023EF 009090E90800           ADD BYTE PTR [EAX+0008E990], DL
4023F5 0000                   ADD BYTE PTR [EAX], AL
4023F7 90                     NOP
4023F8 E902000000             JMP L4023FF
4023FD 90                     NOP
4023FE 90                     NOP
4023FF 90                     NOP

The compiler is intelligent enough to start counting at the lowest number.
Let me say that this is true, no matter in which order the CASES are placed.

Example 5:
In this Example, we will touch the Limit of SELECT CASE AS CONST in the current 8.03 compiler.

While this will compile:

Code: [Select]
SUB TestfuncA()
REGISTER R01 AS LONG,R02 AS LONG
!NOP
R01=100
SELECT CASE AS CONST R01
    !NOP
    CASE 1: REM
    !NOP
    CASE 3057: REM
    !NOP
  CASE ELSE
    !NOP
    REM
    !NOP
 END SELECT
    ! NOP
END SUB   


Its enough to just change the 3057 into 3058 to get the

Code: [Select]
Error 402 in F:\00_RPGM\01_PB\01_PRO~3\00_SPE~1\00_SPEED-Test.bas(16:025):  Statement too long/complex
Line 16: SELECT CASE AS CONST R01
==============================
Compile failed at 20:39:32 on 05.08.2007

This shows us, that the difference between the numeric inputs in SELECT CASE AS CONST can not exceed 3056.
The compiler just doesn't want to make a bigger Jumptable in its actual version.

But even if there are only 2 CASES, if you use SELECT CASE AS CONST with this difference,
you will get this big Jump-Table.

Conclusion: Regularly always use "SELECT CASE AS LONG".
In CASES with A LOT of CASES :-) which are near to each other, think of using SELECT CASE AS CONST.

And a final tip: When using SELECT CASE AS LONG, always sort the CASES in a way that the most often used CASES come first.
 
« Last Edit: August 05, 2007, 08:54:47 PM by Theo Gottwald »

Offline Petr Schreiber

  • Full Member
  • ***
  • Posts: 183
Hi,

this is interesting comparation, thanks.
I have never used AS CONST yet, always AS LONG.


Bye,
Petr
AMD Sempron 3400+ | 1GB RAM @ 533MHz | GeForce 6200 / GeForce 9500GT | 32bit Windows XP SP3

psch.thinbasic.com

Offline Eros Olmi

  • Full Member
  • ***
  • Posts: 243
    • thinBasic
Perfect comparison Theo. Thanks a lot

thinBasic Script Interpreter - www.thinbasic.com | www.thinbasic.com/community
Win7Pro 64bit - 8GB Ram - Intel i7 M620 2.67GHz - NVIDIA Quadro FX1800M 1GB

Offline Kent Sarikaya

  • Full Member
  • ***
  • Posts: 174
I will post as I wasn't sure if allowed to on these type of useful posts... but as there have been posts I will assume it is ok. Thanks Theo, very interesting article and a whole new area of unknown behind the scenes info!!