JIT basato su modelli di codice precompilati

2

Questa è un'idea pazzesca che mi è venuta in mente e sono interessato a sapere se sarebbe fattibile, o se qualcuno lo ha già scritto o implementato.

Immagina di essere su una piattaforma (una console di gioco, iOS, ...) dove non è possibile implementare un compilatore JIT a causa di motivi tecnici 1 - non è possibile rendere eseguibile la memoria scrivibile. Puoi scrivere un interprete, ma ti piacerebbe farlo più velocemente. Ora, la memoria è abbastanza economica e il codice è relativamente piccolo rispetto ad altre risorse, quindi puoi sempre aggiungere altro codice precompilato.

Che cosa succede se aggiungi al tuo binario molti pezzi di codice compilati (in anticipo) - uno per ogni sequenza di istruzioni che probabilmente ti serviranno? Puoi rendere i pezzi configurabili passando argomenti attraverso registri o memoria. Un semplice esempio è la sostituzione di un semplice ciclo (pseudocodice)

for i in range(100000):
    array[i] = 0;

con memset(&array, 0, 100000) . Ma puoi fare molto meglio. Compila alcuni programmi tipici, prendi i 1000 migliori N -grammi di istruzioni e inseriscili nel tuo binario. Ora li stringa tutti insieme - usando i salti calcolati (non so se sarebbero disponibili in un tipico sistema bloccato) - o avvolgendo quelli più grandi nelle funzioni, o usando alcuni trucchi basati sulla programmazione di ritorno. / p>

Qui ci sono alcuni compromessi:

  • Uno è che c'è un sovraccarico perché devi compilare molto più codice di quello che effettivamente utilizzerai. Tuttavia, potrebbe essere che il codice critico delle prestazioni (per una determinata piattaforma e caso d'uso) abbia molti pezzi comuni. Pensa ad esempio al codice grafico.

  • Un altro è che, mentre l'esecuzione dei bit di codice compilati è più veloce dell'interpretazione, si ha un sovraccarico dovuto al salto tra i bit di codice. Ho anche la sensazione che la mancanza di localizzazione della cache tra pezzi di codice distanti potrebbe essere una cattiva idea. Entrambi questi dovrebbero essere particolarmente veri per i processori moderni.

Quindi, mi chiedo se qualcuno più intelligente di me ci abbia già pensato e possa parlarmi di questi compromessi e di come funzionerebbe nella realtà.

1) Nota Non sto chiedendo degli aspetti legali , che comunque vanno oltre lo scopo del sito. Qualcuno potrebbe proibirti di scrivere un compilatore JIT e poi inventare qualcosa che tecnicamente non è una JIT, ma la stessa cosa nello spirito, e hai appena creato un sacco di lavoro per gli avvocati. Questa domanda riguarda gli aspetti tecnici: dì che vuoi qualcosa di simile a JIT su un computer con architettura Havard.

    
posta jdm 13.01.2016 - 20:48
fonte

2 risposte

5

Questa idea è ... meno pazza di quanto avrei detto a prima vista. Per lanciarlo in un linguaggio più sobrio, ciò significherebbe:

  1. Identificazione di schemi comuni nel codice interpretato
  2. Scrittura o generazione di codice nativo equivalente a tali modelli
  3. Sostituzione di istanze di questi modelli con chiamate al codice nativo

Meno il terzo passaggio, che è spesso lasciato agli utenti della lingua, questo è un modo molto popolare per rendere più veloci le lingue dinamiche. Beh, non estraggono N-grammi casuali dal codice, scelgono operazioni significative per le quali una funzione separata ha senso semantico, ma comunque accelerano (es.) Il codice Python scrivendo common operazioni in C e chiamandolo nel loro programma Python.

Tenendo presente questa arte precedente, le tue preoccupazioni mi sembrano infondate. Sarà proprio come qualsiasi altra funzione implementata in modo nativo, e chiamarla in genere è abbastanza efficiente. C'è un po 'di overhead dal salto (ma tieni presente che hai almeno un salto per istruzioni bytecode), e un po' di più dalla pressione icache, ma se la funzione valeva la pena ottimizzare in primo luogo, allora l'accelerazione superano di gran lunga quelle preoccupazioni.

Ma come sempre, il diavolo è nei dettagli. Eccone alcuni:

  • Probabilmente non vuoi passare a quali schemi si verificano più spesso, ma con quali modelli impiegano più tempo, il che ti porta nel regno delle ottimizzazioni guidate dal profilo. Certamente fattibile, ma piuttosto una seccatura nella pratica.
  • Se il pattern scrive su variabili utilizzate al di fuori del pattern o fa un flusso di controllo complicato come il ritorno dalla funzione circostante, è necessario includere il codice circostante nel pattern (e perdere le opportunità per applicarlo) o complicare, problema - riscrittura specifica del codice circostante.
  • A meno che non si esegua manualmente il secondo passaggio, la conversione in codice nativo probabilmente non è molto più efficace del semplice concatenamento delle operazioni con caratteri dinamici e late-bound che l'interprete eseguirà nell'interpretazione del codice originale. Questo spesso dà una bella accelerazione, ma raramente è così drastico come passare da un loop interpretato a memset .
  • Potrebbe essere piuttosto difficile scegliere automaticamente i limiti appropriati per i modelli. Forse vuoi assumere che alcuni input siano costanti, magari vuoi generalizzare le altre parti per applicare l'ottimizzazione più in generale, ecc.
  • I linguaggi dinamici di solito dispongono di funzionalità abbastanza estese per interrompere le ottimizzazioni.
  • Oh mio Dio non mi ha nemmeno iniziato a capire quanto sia difficile ottimizzare staticamente i linguaggi dinamici.
  • Davvero, no.
  • È così difficile che non ci crederesti.
  • Per lo meno dovresti assumere che tutti i valori coinvolti abbiano un tipo concreto (e idealmente uno incorporato che non può essere modificato) e ti liberino dal modello se ti trovi con tipi diversi. E anche quello può rompere le lingue come Ruby dove puoi anche ridefinire anche l'aritmetica sui numeri.
    • (Ovviamente potresti calpestare il piede e dichiarare che queste cose non sono permesse, ma poi non è più la stessa lingua e potresti ottenere molte più vittorie su tutta la linea ottimizzando l'interprete per questa nuova restrizione, o forse persino renderlo un compilatore statico.)

Forse puoi risolvere alcuni di questi problemi ottenendo ispirazione più dai compilatori JIT, in particolare tracciandoli . Cioè, esegui il programma, lascia che il compilatore JIT identifichi i percorsi di hot code (incluse le assunzioni fatte durante l'ottimizzazione) e inserisca staticamente queste tracce ottimizzate nel programma. Tracciare i compilatori JIT già sanno come gestire tutte queste cose. Sarebbe principalmente una sfida ingegneristica (rendere le strutture dati e il codice macchina adatti per un binario statico).

Un'altra variante della stessa idea è quella di rinunciare all'automazione della seconda e della terza fase: utilizzare gli strumenti per trovare schemi che potrebbero beneficiare dell'ottimizzazione, quindi ottimizzarli manualmente . Meno brillante, ma anche più probabile che funzioni effettivamente.

Conclusione : una buona idea per una tesi, ma non scommetterei che funzionasse nella sua forma attuale.

    
risposta data 13.01.2016 - 21:35
fonte
-2

Congratulazioni, hai inventato la DLL.

Modifica: Sì, è stato un po 'breve. Un commento avrebbe fatto. Quindi lasciami elaborare. Un po '.

Usando il codice precompilato per rendere più rapida la compilazione della tua applicazione, in particolare per il targeting di parti che vengono eseguite spesso, questo è ciò che offre una libreria di link dinamici. Consente inoltre di condividere il codice compilato tra diverse applicazioni. Il codice in esso può essere indirizzato sia dalle lingue compilate che dalle lingue interpretate. Questo è il caso del mondo Microsoft Windows, non so di altri ambienti.

Le DLL sono comuni nell'era Win32. La maggior parte se il sistema operativo Windows è implementato come DLL. Il concetto rimane nel mondo .net, l'estensione dei file è ancora DLL, sebbene sia preferibile chiamarli lì.

Quindi il mio punto è che è una grande idea (anche se ci è voluto un po 'di tempo per risolvere i problemi di versioning, comunemente noti come "inferno della DLL"), ma non sei il primo a venirne fuori.

    
risposta data 13.01.2016 - 22:57
fonte

Leggi altre domande sui tag