¿Por qué el algoritmo de "inicio pequeño" para el desplazamiento de rama no es óptimo?

[pregunta en negrita en la parte inferior]

Cuando un ensamblador genera una codificación binaria, debe decidir si hacer que cada rama sea larga o corta, lo mejor será corto, si es posible. Esta parte del ensamblador se llamaAlgoritmo de optimización de desplazamiento de rama (BDO). Un enfoque típico es que el ensamblador hacetodas las codificaciones de ramificación son cortas (si son inferiores a algún umbral), entonces aumentan iterativamente cualquier salto de ramificación a longs que no alcanzan. Esto, por supuesto, puede hacer que otras ramas se conviertan en saltos largos. Por lo tanto, el ensamblador debe seguir pasando por la lista de salto hasta que no se requiera un aumento de tamaño. Este enfoque de tiempo cuadrático parece ser un algoritmo óptimo para mí, pero supuestamente BDO es NP completo y este enfoque no es realmente óptimo.

Randall Hyde proporcionó un contraejemplo:

                  .386 
                  .model  flat, syscall
00000000          .code
00000000          _HLAMain        proc


00000000  E9 00000016          jmpLbl:         jmp     [near ptr] target
00000005 = 00000005            jmpSize         =       $-jmpLbl
00000005  00000016 [                           byte    32 - jmpSize*2
dup
(0)
            00
           ]
0000001B                       target:
0000001B                       _HLAMain        endp
                                                end

Al agregar la parte entre paréntesis "[cerca de ptr]" y forzar una codificación de 5 bytes, el binario en realidad termina siendo más corto porque la matriz asignada es más pequeña por el doble de la cantidad de salto. Por lo tanto, al acortar la codificación de salto, el código final es en realidad más largo.

Esto me parece un caso extremadamente patológico, y no es realmente relevante porque las codificaciones de ramificación son aún más pequeñas, es solo este extraño efecto secundario en una parte no ramificada del programa, lo que hace que el binario se agrande. Como las propias codificaciones de ramificación son aún más pequeñas, realmente no considero que sea un contraejemplo válido para el algoritmo de "inicio pequeño".

¿Puedo considerar el algoritmo start-small como un algoritmo BDO óptimo o existe unrealista caso en el que no proporciona un tamaño de codificación mínimo para todas las ramas?

Respuestas a la pregunta(2)

Su respuesta a la pregunta