Select und If - Geschwindigkeit (ASM)

[Chimorin]

Heyho,
Ich diskutiere gerade mit einem Freund, der meint, dass Select in Assembler nichts anderes ist als ein verschachteltes If-Gebilde. Stimmt das? Auch in Bezug auf andere Programmiersprachen und Ähnliches (C,... , Java und so).

[STARGÅTE]

Ja stimmt.
Die Cases sind nichts anderes als viele ElseIfs.

Effektiver wäre es natürlich, wenn Select:Case einen Index anlegen könnte, sodass anhand des Werts ein direkter Sprung möglich ist, ich kenne aber keine Sprache wo das so implementiert ist, müsste man also wenn dann selber umsetzen.

[Danilo]

Effektiver wäre es natürlich, wenn Select:Case einen Index anlegen könnte, sodass anhand des Werts ein direkter Sprung möglich ist, ich kenne aber keine Sprache wo das so implementiert ist, müsste man also wenn dann selber umsetzen.

Das wird beim Compilerbau so gelehrt (bzw. bei weiterführenden Optimierungen), und ich denke mal, dass das einige
hochoptimierende Compiler auch teilweise so umsetzen.
Dabei kommt es darauf an wie gross der Unterschied zwischen dem kleinsten und dem größten Case-Wert ist.
Eine Tabelle von ein paar Bytes oder Kilobytes ist ja OK, aber wenn die Sprungtabelle zu gross wird, ist das auch wieder nix...

Code: Alles auswählen

x = 3
Select x
    Case 1
        Debug "1"
    Case 2
        Debug "2"
    Case 3
        Debug "3"
    Case 4
        Debug "4"
    Case 6
        Debug "6"
EndSelect



; optimiert
!MOV EAX, [v_x]
!JMP [l_case1+EAX*4]
case1_L1:
    Debug "1"
    !JMP l_endcase1
case1_L2:
    Debug "2"
    !JMP l_endcase1
case1_L3:
    Debug "3"
    !JMP l_endcase1
case1_L4:
    Debug "4"
    !JMP l_endcase1
case1_L6:
    Debug "6"
    ;!JMP l_endcase1 ; weg optimiert
endcase1:

DataSection
    case1:
    Data.i 0, ?case1_L1, ?case1_L2, ?case1_L3, ?case1_L4, 0, ?case1_L6
EndDataSection



;----------------------------------



x = 306
Select x
    Case 301
        Debug "301"
    Case 302
        Debug "302"
    Case 303
        Debug "303"
    Case 304
        Debug "304"
    Case 306
        Debug "306"
EndSelect



; optimiert
!MOV EAX, [v_x]
!SUB EAX, 300
!JMP [l_case2+EAX*4]
case2_L1:
    Debug "301"
    !JMP l_endcase2
case2_L2:
    Debug "302"
    !JMP l_endcase2
case2_L3:
    Debug "303"
    !JMP l_endcase2
case2_L4:
    Debug "304"
    !JMP l_endcase2
case2_L6:
    Debug "306"
    ; !JMP l_endcase2 ; weg optimiert
endcase2:

DataSection
    case2:
    Data.i 0, ?case2_L1, ?case2_L2, ?case2_L3, ?case2_L4, 0, ?case2_L6
EndDataSection

Wie in diesem Beispiel für x86 springt man also direkt in den Case-Block, anstatt 5 Vergleiche für die 5 Cases zu machen.

Ein hochoptimierender Compiler würde bei diesem simplen Beispiel sogar noch weiter gehen können.
Da der Wert von x direkt vor dem Select-Case-Block zugewiesen wird (x = 3, x = 306), und der Compiler
diese Konstante kennt, würde er alle anderen Cases entfernen und nur den Block für x=3 oder x = 306
einfügen können:

Code: Alles auswählen

x = 3
Select x
    Case 1
        Debug "1"
    Case 2
        Debug "2"
    Case 3
        Debug "3"
    Case 4
        Debug "4"
    Case 6
        Debug "6"
EndSelect



; optimiert
Debug "3"



;----------------------------------



x = 306
Select x
    Case 301
        Debug "301"
    Case 302
        Debug "302"
    Case 303
        Debug "303"
    Case 304
        Debug "304"
    Case 306
        Debug "306"
EndSelect



; optimiert
Debug "306"

[Chimorin]

Danke für die Antworten. Zum Verständnis: Switch:Case oder wie man das auch immer nennen möge ist in ASM nichts anderes als eine riesige If-Abfrage mit dem kleinen Unterschied, dass beim Switch:Case mit Sprungtabellen hantiert wird (Somit nicht alle Möglichkeiten durchlaufen werden).

[STARGÅTE]

Wie Danilo schon sagte, nur wenn der Compiler dahingehend optimiert!
Andernfalls sieht das so aus:

Code: Alles auswählen

Select x
    Case 1
        Debug "1"
    Case 2
        Debug "2"
    Case 3 to 10
        Debug "3 To 10"
    Case 11, 13
        Debug "11 Or 13"
    Case 12, 14
        Debug "12 Or 14"
EndSelect

Code: Alles auswählen

If x = 1
        Debug "1"
ElseIf x = 2
        Debug "2"
ElseIf x >= 3 And x <= 10
        Debug "3 To 10"
ElseIf x = 11 Or x = 13
        Debug "11 Or 13"
ElseIf x = 12 Or x = 14
        Debug "12 Or 14"
EndIf

Daher sollte man bei einem Select-Block die am häufigsten eintretenden Möglichkeiten zuerst nennen (zumindest wenn daraus ein If-Block wird), damit möglichst wenig Abfragen nötig sind.

[Chimorin]

Ok, danke für die Antworten. Wie sieht das in PB aus? (Ich war immer der Meinung, dass Select schneller wäre, jetzt müsste ich alles anpassen ^^)

[_sivizius]

die ganze optimierung bringt halt nur nichts, wenn man z.B.:

Code: Alles auswählen

Select x
  Case 4
    Debug "4"
  Case 23
    Debug "23"
  Case 1337, 2, 7
    Debug "1337"
EndSelect 

hat. btw. dieses Debug wird auch assembliert, diese Sprünge könnte man also ganz weg machen:

Code: Alles auswählen

  MOV    rdi,1
  CALL   DBL
  PUSH   qword [PB_StringBasePosition]
  MOVSX  rax,byte [v_x]
  PUSH   rax
  MOV    rdi,[rsp]
  SUB    rsp,32
  CALL   PB_DEBUGGER_PrintQuad
  ADD    rsp,40
  POP    qword [PB_StringBasePosition]

(oder so ähnlich)
Bzw. durch Rechenoperationen erweitern, womit für einfache Fälle Case überflüssig und für komplizierte kaum optimierbar wäre.
irre ich?

[Chimorin]

Ich weiß nicht, ob ich das einfach überlesen habe, aber ich würde gerne wissen, ob Select in PB gegenüber If optimiert ist und schneller ist...
Mir kommt es so vor, als wäre If schneller als Select (Mehr als 200ms bei 10000 Durchläufen. Das sind 0,02ms pro Durchlauf!!! )

Code: Alles auswählen

EnableExplicit

Define.i zeit0, zeit1, zeit2, zeit3, pruef = 10, zaehler = 0

zeit0 = ElapsedMilliseconds()
For zaehler = 0 To 10000
  If pruef = 0
    Debug "Null"
    
  ElseIf pruef = 1
    Debug "Eins"
    
  ElseIf pruef = 2
    Debug "Zwei"
    
  ElseIf pruef = 3
    Debug "Drei"
    
  ElseIf pruef = 4
    Debug "Vier"
    
  ElseIf pruef = 5
    Debug "Fünf"
    
  ElseIf pruef = 6
    Debug "Sechs"
    
  ElseIf pruef = 7
    Debug "Sieben"
    
  ElseIf pruef = 8
    Debug "Acht"
    
  ElseIf pruef = 9
    Debug "Neun"
    
  ElseIf pruef = 10
    Debug "Zehn"
    
  EndIf
Next zaehler
zeit1 = ElapsedMilliseconds()

zeit2 = ElapsedMilliseconds()
For zaehler = 0 To 10000
  Select pruef
    Case 0
      Debug "Null"
      
    Case 1
      Debug "Eins"
      
    Case 2
      Debug "Zwei"
      
    Case 3
      Debug "Drei"
      
    Case 4
      Debug "Vier"
      
    Case 5
      Debug "Fünf"
      
    Case 6
      Debug "Sechs"
      
    Case 7
      Debug "Sieben"
      
    Case 8
      Debug "Acht"
      
    Case 9
      Debug "Neun"
      
    Case 10
      Debug "Zehn"
      
  EndSelect
Next zaehler
zeit3 = ElapsedMilliseconds()

Debug zeit1 - zeit0
Debug zeit3 - zeit2

[ts-soft]

Zeitmessung mit eingeschaltetem Debugger ist in keinster Weise aussagefähig, wann wollt Ihr das
endlich begreifen. Solche Messungen sind einfach nur Zeitverschwendung!

(Ausserdem kann ich mir nicht vorstellen, das der Zeitunterschied zwischen If und Select so gross ist,
das er irgendwo zum tragen kommen sollte )

Gruß
Thomas

[RSBasic]

+1
Man sollte sich lieber auf das Programmieren bzw. auf die Umsetzung der Anwendung konzentrieren und nicht krampfartig versuchen, ein paar Millisekunden herauszuholen. Wenn man optimieren möchte, dann eher bei aufwändigen Vorgängen.