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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 | ; 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):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78 | 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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47 | $ 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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92 | 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67 | $ 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