Para o meu projeto da feira de ciências, implementei uma otimização na rotina de classificação do Python. A idéia é mover as verificações de segurança que precisam ser realizadas durante cada comparação, por exemplo, verificações de tipo e verificações de largura de caracteres, fora do loop de classificação e realizar todas elas de uma só vez. Uma função de comparação otimizada é então selecionada de um portfólio com base nos resultados das verificações. Portanto, por exemplo, se as verificações determinarem que todos os objetos são do mesmo tipo, a função de comparação selecionada poderá ignorar a verificação geralmente necessária "são compatíveis com os tipos de objeto". Etc.
Eu tenho que escrever isso como um artigo, e atualmente estou trabalhando em uma revisão de literatura. Existem trabalhos descrevendo técnicas semelhantes em outras linguagens dinâmicas / em geral?
fonte
Respostas:
Não estou ciente de nada exatamente assim, mas há algumas coisas que são discutivelmente relacionadas.
Para classificação específica, isso está relacionado à transformação schwartziana , embora com um objetivo muito diferente. Na transformação Schwartzian, você percorre a entrada aplicando uma função cara e emparelhando a entrada e a saída, e depois classificando a saída. Isso contrasta com a execução dessa função cara em cada operação. No seu caso, sua "função cara" seria as verificações de tipo e as expedições dinâmicas . Um pouco diferente, você também verificaria uma propriedade para toda a lista e escolheria qual operação de comparação usar com base nisso.
Em uma veia totalmente diferente, existe uma técnica geral chamada cache polimórfico em linha ( pioneira pela equipe Self e abordada, entre muitas outras coisas, na tese de Craig Chamber ) e otimização adaptativa mais geralmente usada em algumas máquinas virtuais. O cache inline polimórfico resolve o problema de que, se fizermos um envio dinâmico, estaremos saltando para um código completamente desconhecido e, portanto, não podemos incorporá-lo e otimizá-lo e a função atual. A solução é simples: basta fazer um
ifteste para verificar se estamos em algum caso específico e, se for o caso, podemos alinhar esse código, caso contrário, fazemos o envio dinâmico. O problema é que existe um número desconhecido e ilimitado de casos possíveis. Isso não é um problema, porém, para umCompilador Just-In-Time (JIT), que pode fazer isso apenas nos casos realmente vistos em tempo de execução.Isso não resolve o seu problema, pois o envio dinâmico é baseado na classe de tempo de execução de um objeto, não em algum predicado arbitrário como "todos os elementos dessa matriz têm o mesmo tipo". É aqui que a otimização adaptativa entra e coisas como rastrear compiladores JIT. É bastante concebível que desenrolar um loop algumas vezes ou inlining alguns níveis de recursão possa levar à eliminação de muitas verificações de tipo com otimizações simples de estilo de propagação constante e, possivelmente, totalmente eliminadas por otimizações mais sofisticadas em alguns casos. No entanto, muitas vezes não fará o mesmo que você está sugerindo e precisaria ver um rastreio primeiro para cada uso da função de classificação. Por outro lado, se souber que todos os elementos são números, digamos, do código anterior, poderá eliminar completamente a verificação.
fonte