Sobre el `branching prediction` en x86

En cierto tablón de discusión, de cuyo nombre no quiero acordarme se hablaba sobre la optimización de switches en SBCL (un intérprete/compilador de common lisp), que hacía una serie de CMP, JMP en vez de usar una table, alguien daba como motivo el "branch prediction", parecía poco probable pero algo entretenido de probar.

Nota: mi experiencia con ensamblador es bastante limitada, así que lo que resulte de esto creételo lo justo ;)

El código ejemplo que se daba era:

(defun tswitch (x)
           (declare (optimize (speed 3)))
           (declare (fixnum x))
           (case x
             (1 (princ 4))
             (2 (princ 3))
             (3 (princ 2))
             (4 (princ 1))
             (t (princ x))))

Y el compilado resultante:

; 252C172C:       83FA04           CMP EDX, 4                 ; no-arg-parsing entry point
;       2F:       7462             JEQ L3
;       31:       83FA08           CMP EDX, 8
;       34:       7447             JEQ L2
;       36:       83FA0C           CMP EDX, 12
;       39:       742C             JEQ L1
;       3B:       83FA10           CMP EDX, 16
;       3E:       7411             JEQ L0
;       40:       8B05F0162C25     MOV EAX, [#x252C16F0]      ; #<FDEFINITION object for PRINC>
;       46:       B904000000       MOV ECX, 4
;       4B:       FF7504           PUSH DWORD PTR [EBP+4]
;       4E:       FF6005           JMP DWORD PTR [EAX+5]
;       51: L0:   BA04000000       MOV EDX, 4
;       56:       8B05F0162C25     MOV EAX, [#x252C16F0]      ; #<FDEFINITION object for PRINC>
;       5C:       B904000000       MOV ECX, 4
;       61:       FF7504           PUSH DWORD PTR [EBP+4]
;       64:       FF6005           JMP DWORD PTR [EAX+5]
;       67: L1:   BA08000000       MOV EDX, 8
;       6C:       8B05F0162C25     MOV EAX, [#x252C16F0]      ; #<FDEFINITION object for PRINC>
;       72:       B904000000       MOV ECX, 4
;       77:       FF7504           PUSH DWORD PTR [EBP+4]
;       7A:       FF6005           JMP DWORD PTR [EAX+5]
;       7D: L2:   BA0C000000       MOV EDX, 12
;       82:       8B05F0162C25     MOV EAX, [#x252C16F0]      ; #<FDEFINITION object for PRINC>
;       88:       B904000000       MOV ECX, 4
;       8D:       FF7504           PUSH DWORD PTR [EBP+4]
;       90:       FF6005           JMP DWORD PTR [EAX+5]
;       93: L3:   BA10000000       MOV EDX, 16
;       98:       8B05F0162C25     MOV EAX, [#x252C16F0]      ; #<FDEFINITION object for PRINC>
;       9E:       B904000000       MOV ECX, 4
;       A3:       FF7504           PUSH DWORD PTR [EBP+4]
;       A6:       FF6005           JMP DWORD PTR [EAX+5]
;       A9:       CC0A             BREAK 10                   ; error trap
;       AB:       02               BYTE #X02
;       AC:       18               BYTE #X18                  ; INVALID-ARG-COUNT-ERROR
;       AD:       4F               BYTE #X4F                  ; ECX
;       AE:       CC0A             BREAK 10                   ; error trap
;       B0:       02               BYTE #X02
;       B1:       08               BYTE #X08                  ; OBJECT-NOT-FIXNUM-ERROR
;       B2:       90               BYTE #X90                  ; EDX

Con pocos cambios aquí y allá podemos convertirlo en un código compilable con nasm para pruebas de velocidad, hace 10000 000 iteraciones, 5000 000 con cada ciclo (aclaración después del código):

global _start

;;;  Definiciones básicas
%define ADDR [static_mem]

section .data
static_mem:     dd 0

section .text
;;; Código real
_start:
    ;; Probamos los ciclos 4 <-> 16
    mov edx, 4
    times 5000000 call tested_switch

    ;; Probamos los ciclos 8 <-> 12
    mov edx, 8
    times 5000000 call tested_switch

;;; Cerramos correctamente
_end:
        ;; Exit with 0
        mov eax, 1
        xor ebx, ebx
        int 0x80

;;; Código a testear
tested_switch:
        cmp edx, 4
        je L3

    cmp edx, 8
        je L2

    cmp edx, 12
        je L1

    cmp edx, 16
        je L0

;;; Default
        mov eax, ADDR      ; #<FDEFINITION object for PRINC>
        mov ecx, 4

    ret


;;; 16
L0:
        mov edx, 4
        mov eax, ADDR      ; #<FDEFINITION object for PRINC>
        mov ecx, 4

    ret

;;; 12
L1:
        mov edx, 8
        mov eax, ADDR      ; #<FDEFINITION object for PRINC>
        mov ecx, 4

    ret

;;; 8
L2:
        mov edx, 12
        mov eax, ADDR      ; #<FDEFINITION object for PRINC>
        mov ecx, 4

    ret

;;; 4
L3:
        mov edx, 16
        mov eax, ADDR      ; #<FDEFINITION object for PRINC>
        mov ecx, 4

    ret

Por la naturaleza del código generado el EDX va siguiendo estas secuencias (al no probar seguido lo mismo más dificil al branching prediction):

4 -> 16
8 -> 12
12 -> 8
16 -> 4

Otros no cambian

Lo ensamblamos y linkamos(en máquinas de 32 bits, habría que cambiar elf64 por elf32, supongo):

$ nasm -f elf64 raw.asm -o raw.o # Tarda un rato en generarlo por que tiene que incluir 10 millones de calls :P

$ ld raw.o -o raw

Los resultados hacen que (en esta máquina) esté alrededor de los 0.200 segundos:

$ time ./raw

real    0m0.195s
user    0m0.156s
sys 0m0.036s


$ time ./raw

real    0m0.195s
user    0m0.160s
sys 0m0.032s


$ time ./raw

real    0m0.196s
user    0m0.152s
sys 0m0.040s


$ time ./raw

real    0m0.218s
user    0m0.168s
sys 0m0.032s


$ time ./raw

real    0m0.195s
user    0m0.156s
sys 0m0.036s


$ time ./raw

real    0m0.197s
user    0m0.152s
sys 0m0.040s


$ time ./raw

real    0m0.200s
user    0m0.168s
sys 0m0.028s

* Y ahora con tablas de salto!!! ***

Aquí va el código:

global _start

;;;  Definiciones básicas
%define ADDR [static_mem]

section .data
static_mem:          dd 0

;;; Tabla de saltos
jump_table:
    dd LDEFAULT ;  0
    dd LDEFAULT ;  1
    dd LDEFAULT ;  2
    dd LDEFAULT ;  3
    dd L3       ;  4
    dd LDEFAULT ;  5
    dd LDEFAULT ;  6
    dd LDEFAULT ;  7
    dd L2       ;  8
    dd LDEFAULT ;  9
    dd LDEFAULT ; 10
    dd LDEFAULT ; 11
    dd L1       ; 12
    dd LDEFAULT ; 13
    dd LDEFAULT ; 14
    dd LDEFAULT ; 15
    dd L0       ; 16


section .text
;;; Código real
_start:
    ;; Probamos los ciclos 4 <-> 16
    mov edx, 4
    times 5000000 call tested_switch

    ;; Probamos los ciclos 8 <-> 12
    mov edx, 8
    times 5000000 call tested_switch

;;; Cerramos correctamente
_end:
        ;; Exit with 0
        mov eax, 1
        xor ebx, ebx
        int 0x80
;;; Código a testear
tested_switch:
    ;; Multiplicamos edx por 4 por que este es el tamaño de las entradas de la tabla
    ;;  ... aunque no estoy demasiado seguro :P
    shl edx, 2

    mov ebx, [jump_table + edx]
    jmp rbx

;;; Default
LDEFAULT:
        mov eax, ADDR      ; #<FDEFINITION object for PRINC>
        mov ecx, 4
        ret

;;; 16
L0:
        mov edx, 4
        mov eax, ADDR      ; #<FDEFINITION object for PRINC>
        mov ecx, 4

    ret

;;; 12
L1:
        mov edx, 8
        mov eax, ADDR      ; #<FDEFINITION object for PRINC>
        mov ecx, 4

    ret

;;; 8
L2:
        mov edx, 12
        mov eax, ADDR      ; #<FDEFINITION object for PRINC>
        mov ecx, 4

    ret

;;; 4
L3:
        mov edx, 16
        mov eax, ADDR      ; #<FDEFINITION object for PRINC>
        mov ecx, 4

    ret

De nuevo ensamblamos y enlazamos:

$ nasm -f elf64 tables.asm -o tables.o
$ ld tables.o -o tables

Y aquí los resultados

$ time ./tables

real    0m0.291s
user    0m0.252s
sys 0m0.036s


$ time ./tables

real    0m0.290s
user    0m0.256s
sys 0m0.036s


$ time ./tables

real    0m0.294s
user    0m0.276s
sys 0m0.012s


$ time ./tables

real    0m0.290s
user    0m0.256s
sys 0m0.036s


$ time ./tables

real    0m0.310s
user    0m0.252s
sys 0m0.040s


$ time ./tables

real    0m0.299s
user    0m0.244s
sys 0m0.048s


$ time ./tables

real    0m0.291s
user    0m0.264s
sys 0m0.024s

$ time ./tables

real    0m0.293s
user    0m0.260s
sys 0m0.024s


$ time ./tables

real    0m0.289s
user    0m0.228s
sys 0m0.056s


$ time ./tables

real    0m0.289s
user    0m0.248s
sys 0m0.036s

Conclusión: sorprendentemente parece que para switches pequeños (al menos en esta máquina en concreto), la solución más rápida (un 50% más) es la de usar if's. (A menos que pifiara el código, posibilidad nada desdeñable).

Saludos

Recuperando un archivo eliminado pero abierto por otro proceso » « Grandes frases