[pergunta em negrito na parte inferior]

Quando um assembler gera uma codificação binária, ele precisa decidir se deseja tornar cada ramificação longa ou curta, sendo a curta melhor, se possível. Essa parte do montador é chamada dealgoritmo de otimização de deslocamento de ramificação (BDO). Uma abordagem típica é que o montador faztudo as codificações de ramificações são curtas (se elas são menores que um limite), então aumenta iterativamente todos os ramificações que saltam para comprimentos que não atingem. Obviamente, isso pode fazer com que outros ramos sejam convertidos em saltos longos. Portanto, o montador deve continuar passando pela lista de atalhos até que não seja necessário mais upsizing. Essa abordagem de tempo quadrático parece ser um algoritmo ideal para mim, mas supostamente o BDO é NP completo e essa abordagem não é realmente ideal.

Randall Hyde forneceu um contra-exemplo:

                  .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

Adicionando a peça entre colchetes "[near ptr]" e forçando uma codificação de 5 bytes, o binário acaba sendo mais curto, porque a matriz alocada é menor, dobrando a quantidade do tamanho do salto. Assim, diminuindo a codificação de salto, o código final é realmente mais longo.

Este parece ser um caso extremamente patológico para mim, e não é realmente relevante porque as codificações de ramificação ainda são menores, é apenas esse efeito colateral bizarro em uma parte não ramificada do programa, que faz com que o binário fique maior. Como as próprias codificações de ramificação ainda são menores, não considero realmente um contra-exemplo válido para o algoritmo "start small".

Posso considerar o algoritmo start-small um ótimo algoritmo BDO ou existe umrealista caso em que ele não fornece um tamanho mínimo de codificação para todas as ramificações?