View Full Version : [Generale] Multithreaded parsing
Salve a tutti,
dato il crescente numero di core degli attuali processori, l'uso dei threads si stà sempre più diffondendo per via dei vantaggi che non starò qui ad elencare (eccezione per Python che per inciso adoro :P).
Mi chiedevo quindi, durante una normale procedura di parsing, secondo voi, si può fare uso di multithreading per eseguire in modo concorrenziale sia il lexer che il parser vero e proprio?
Mi viene in mente una soluzione di parsing predittivo in cui lo scanner comunica con il parser tramite l'inserzione dei simboli in una tabella anzichè usare la più classica get_next_token() direttamente quando il parser ha bisogno di un nuovo token.
Ho letto sul web qualche articolo in inglese che però parlava di parsing concorrenziale non di eseguire assieme scanner e parser.
Mi vengono però in mente un paio di casi in cui sarebbe necessario usare un semaforo per impedire ai due thread di entrare in conflitto su certi dati, per esempio, il parser finisce di analizzare i token e ne richiede uno nuovo che lo scanner stà inserendo... Insomma, non sarebbe certo facile come un parser normale, ma appunto, potrebbe secondo voi costituire una alternativa per migliorare le prestazioni di parsing?
Ps. ho visto più indietro (parecchio), un topic riguardante un contest di parsing, ma pare morto li!?!
Grazie a tutti,
Lex
cdimauro
04-06-2010, 08:21
Potresti usare un approccio del tipo produttore -> consumatore, col thread del lex che produce i token, e quello del parser che li consuma.
Ci sono però due problemi con questo approccio. Il primo è che per sincronizzarli devi usare roba come lock et similia, che riduce le prestazioni del sistema.
Il secondo, più grave, è che quest'approccio funziona soltanto con parser che non sono sensibili al contesto. Quindi se il tuo lexer produce token che non dipendono dal contesto, allora sei a posto, altrimenti non puoi utilizzarlo.
Potresti usare un approccio del tipo produttore -> consumatore, col thread del lex che produce i token, e quello del parser che li consuma.
Ci sono però due problemi con questo approccio. Il primo è che per sincronizzarli devi usare roba come lock et similia, che riduce le prestazioni del sistema.
Il secondo, più grave, è che quest'approccio funziona soltanto con parser che non sono sensibili al contesto. Quindi se il tuo lexer produce token che non dipendono dal contesto, allora sei a posto, altrimenti non puoi utilizzarlo.
praticamente quasi la mia tesi della triennale anni e anni fà
Potresti usare un approccio del tipo produttore -> consumatore, col thread del lex che produce i token, e quello del parser che li consuma.
E' esattamente quello che pensavo, ma non avendo trovato molto in questa direzione, prima di provare per incappare nella eventuale impossibilità di realizzazione ho preferito chiedere.
Ci sono però due problemi con questo approccio. Il primo è che per sincronizzarli devi usare roba come lock et similia, che riduce le prestazioni del sistema.
Il secondo, più grave, è che quest'approccio funziona soltanto con parser che non sono sensibili al contesto. Quindi se il tuo lexer produce token che non dipendono dal contesto, allora sei a posto, altrimenti non puoi utilizzarlo.
Si, il parser genera token context-free. E' più che altro a scopo didattico e con la scusa spero di ricavarci un piccolo linguaggio da poter usare per configurazioni varie.
Hai per caso qualche riferimento che descriva più approfonditamente problemi e soluzioni (eventuali) legate a questo tipo di parsing?
Mille grazie per la risposta,
Ciao.
Ci sono però due problemi con questo approccio. Il primo è che per sincronizzarli devi usare roba come lock et similia, che riduce le prestazioni del sistema.
Trattandosi di un algoritmo non intrinsecamente parallelo dubito che si possa fare altrimenti.
Detto questo non so se ne valga la pena, molto piu' semplice compilare piu' unita' in parallelo...
Trattandosi di un algoritmo non intrinsecamente parallelo dubito che si possa fare altrimenti.
Detto questo non so se ne valga la pena, molto piu' semplice compilare piu' unita' in parallelo...
Non sai se ne vale la pena perchè non credi ce ne sia un beneficio in termini prestazionali, o per altro?
Ciao.
Non sai se ne vale la pena perchè non credi ce ne sia un beneficio in termini prestazionali, o per altro?
Ciao.
Intendo dire che di solito un programma che non sia banale e' diviso in piu' moduli indipendenti, ed e' piu' facile far partire N esecuzioni diverse in parallelo che non parallelizzare il compilatore stesso. Quando programmo in C++ uso il gcc che non e' parallelo ma questo non mi vieta di riuscire ad usare tutti e quattro i core della macchina.
Quoto. La compilazione di un file e' cosa breve. Inutile parallelizzare la compilazione singola. Meglio invece istanziare piu' compilatori per compilare piu' file in parallelo, cosa che viene gia' fatta da parecchi tool.
Diverso invece sarebbe pensare di parallelizzare il parsing di un file XML per costruirne l'albero. Ci sono mostri di XML in giro per i quali potrebbe valerne la pena.
Ma tipicamente questi problemi hanno sempre un canale seriale da qualche parte, (es scarico il file XML da rete) e il collo di bottiglia e' quasi sempre li' piuttosto che nel processamento, che e' di per se banale.
cdimauro
04-06-2010, 20:30
Hai per caso qualche riferimento che descriva più approfonditamente problemi e soluzioni (eventuali) legate a questo tipo di parsing?
Francamente no. E' passato parecchio tempo da quando ho studiato i parser (ti consiglio "The Dragon Book", che è la "bibbia" in materia), e la soluzione che ti ho fornito prima non riguarda nemmeno i parser veri e propri, ma ho semplicemente applicato il classico pattern del produttore / consumatore (nemmeno potevo immaginare che fosse stato oggetto della tesi di "qualcuno" :p).
Per il resto, concordo con quanto hanno scritto gli altri.
Trattandosi di un algoritmo non intrinsecamente parallelo dubito che si possa fare altrimenti.
Se la grammatica è context-free, come ha già detto, credo che lexer e parser abbiano buone probabilità di essere implementati in thread separati e "paralleli" (anche se rimane il problema della sincronizzazione, appunto).
Detto questo non so se ne valga la pena, molto piu' semplice compilare piu' unita' in parallelo...
Perfettamente d'accordo. E' la soluzione migliore e la più comoda (praticamente a costo zero).
Intendo dire che di solito un programma che non sia banale e' diviso in piu' moduli indipendenti, ed e' piu' facile far partire N esecuzioni diverse in parallelo che non parallelizzare il compilatore stesso. Quando programmo in C++ uso il gcc che non e' parallelo ma questo non mi vieta di riuscire ad usare tutti e quattro i core della macchina.
Chiarissimo.
Diverso invece sarebbe pensare di parallelizzare il parsing di un file XML per costruirne l'albero. Ci sono mostri di XML in giro per i quali potrebbe valerne la pena.
Ma tipicamente questi problemi hanno sempre un canale seriale da qualche parte, (es scarico il file XML da rete) e il collo di bottiglia e' quasi sempre li' piuttosto che nel processamento, che e' di per se banale.
E se il parser fosse il front-end di un interprete anzichè di un compilatore?
Non puoi eseguire più interpreti per eseguire uno stesso programma (singolo processo). Poi è chiaro che anche gli interpreti si possano lanciare in parallelo ma non beneficia di aumento di prestazioni.
Francamente no. E' passato parecchio tempo da quando ho studiato i parser (ti consiglio "The Dragon Book", che è la "bibbia" in materia), e la soluzione che ti ho fornito prima non riguarda nemmeno i parser veri e propri, ma ho semplicemente applicato il classico pattern del produttore / consumatore (nemmeno potevo immaginare che fosse stato oggetto della tesi di "qualcuno" :p).Ti ringrazio, andrò a cercarne una copia cartacea e, in caso di fallimento, cercherò l'ebook.
Per il resto, concordo con quanto hanno scritto gli altri.
Se la grammatica è context-free, come ha già detto, credo che lexer e parser abbiano buone probabilità di essere implementati in thread separati e "paralleli" (anche se rimane il problema della sincronizzazione, appunto).Ciononostante la cosa devo ammettere che mi intriga, proprio per questa difficoltà di implementazione. Mi piace fare qualcosa di inusuale (ma non inutile), soprattutto per ricerca.
Perfettamente d'accordo. E' la soluzione migliore e la più comoda (praticamente a costo zero).
Mi ripeto, è se fosse il front-end di un interprete?
Grazie a tutti per l'interesse.
E se il parser fosse il front-end di un interprete anzichè di un compilatore?
Non puoi eseguire più interpreti per eseguire uno stesso programma (singolo processo). Poi è chiaro che anche gli interpreti si possano lanciare in parallelo ma non beneficia di aumento di prestazioni.
Qui potresti avere qualche vantaggio (anche se secondo me non troppo elevato).
In questo caso potresti procedere con la strategia suggerita da cdimauro, se procedi in modo intelligente la quantita' di lavoro in piu' non e' improponibile.
cdimauro
05-06-2010, 15:34
Ti ringrazio, andrò a cercarne una copia cartacea e, in caso di fallimento, cercherò l'ebook.
Se non trovi una copia del Dragon Book ti offro una cena. :O
Poi io preferisco nettamente il cartaceo, se posso.
Ciononostante la cosa devo ammettere che mi intriga, proprio per questa difficoltà di implementazione. Mi piace fare qualcosa di inusuale (ma non inutile), soprattutto per ricerca.
Considera che di già lexer e parser sono legati da un rapporto "produttore -> consumatore". Poi con parser come ANTLR (http://www.antlr.org/) questo rapporto lo trovi esplicitato.
Non so a quali tecnologie e linguaggio ti stai affidando per realizzare il tutto, ma può darsi che non dovrai sbatterti più di tanto nell'impresa. ;)
Qui potresti avere qualche vantaggio (anche se secondo me non troppo elevato).
Come sospettavo, comunque è a scopo didattico non mi serve per un ambiente di produzione. Semplicemente mi piace fare ricerca e test, non si sà mai quel che viene fuori, senza contare l'interesse della scoperta.
Se non trovi una copia del Dragon Book ti offro una cena. :O
Beh, se dovessi accidentalmente dimenticarmi come si usa google, dove stanno le librerie e dovessi cercare nella mia libreria in casa...
dove ci incontriamo? :D
Poi io preferisco nettamente il cartaceo, se posso.
Quoto. Passo già parecchie ore al PC, nonostante stia solo su schermi LCD con la luminosità al minimo la sera, col calar delle tenebre non vedo poi molto al buio. E poi, l'odore di un libro nuovo è sconosciuto agli ebook...
Considera che di già lexer e parser sono legati da un rapporto "produttore -> consumatore". Poi con parser come ANTLR (http://www.antlr.org/) questo rapporto lo trovi esplicitato.Si ho avuto modo di vedere ANTLR ma ammetto di non averlo mai usato... da quello che vedo sembra una pacchia da usare...
Non so a quali tecnologie e linguaggio ti stai affidando per realizzare il tutto, ma può darsi che non dovrai sbatterti più di tanto nell'impresa. ;)
Libri e reference in primis, non essendo un lavoro ma mera ricerca (da usare casomai in un futuro interprete che dovrò realizzare) ho totale libertà di scelta... Comunque penso di affidarmi ai più classici C/C++, o qualche linguaggio che semplifichi il tutto, magari Python.
cdimauro
06-06-2010, 21:24
Beh, se dovessi accidentalmente dimenticarmi come si usa google, dove stanno le librerie e dovessi cercare nella mia libreria in casa...
dove ci incontriamo? :D
A Catania. :cool:
Si ho avuto modo di vedere ANTLR ma ammetto di non averlo mai usato... da quello che vedo sembra una pacchia da usare...
Togli pure il sembra. :D
Libri e reference in primis, non essendo un lavoro ma mera ricerca (da usare casomai in un futuro interprete che dovrò realizzare) ho totale libertà di scelta... Comunque penso di affidarmi ai più classici C/C++, o qualche linguaggio che semplifichi il tutto, magari Python.
Togli il magari. :D
Ho già realizzato qualcosa con ANTLR & Python, e mi sono trovato benissimo. Poi ANTLR ha un ottime IDE, ANTLRWork, che ti permette di sviluppare grammatiche (e parser annessi) molto comodamente.
A Catania. :cool:
Uhm... viaggio compreso con la cena? (sono 1.400 e rotti km)
Vabbè non vorrei sembrare uno scroccone, il viaggio ce lo metto io. E' un'occasione per fare una vacanza.
Togli pure il sembra. :D
Togli il magari. :D
Mi stai intrigando...
Ho già realizzato qualcosa con ANTLR & Python, e mi sono trovato benissimo.
Come darti torto, Python è il mio linguaggio ideale e come tale lo è anche in ambito di ricerca (senza eguali). Poi da quello che dici...
Poi ANTLR ha un ottime IDE, ANTLRWork, che ti permette di sviluppare grammatiche (e parser annessi) molto comodamente.
Ne ho sentito parlare più volte molto positivamente, mi verrebbe da asserire che sia questo il motivo del suo successo rispetto ad altri tool (vedi yacc bison e compagnia bella)... ma non ho usato mai nemmeno quelli, anche se, dalle documentazioni che studiai all'epoca è tutta un'altra storia rispetto ad ANTRL.
cdimauro
06-06-2010, 21:58
Uhm... viaggio compreso con la cena? (sono 1.400 e rotti km)
Vabbè non vorrei sembrare uno scroccone, il viaggio ce lo metto io. E' un'occasione per fare una vacanza.
La Sicilia merita. :cool:
Come darti torto, Python è il mio linguaggio ideale e come tale lo è anche in ambito di ricerca (senza eguali). Poi da quello che dici...
Ne ho sentito parlare più volte molto positivamente, mi verrebbe da asserire che sia questo il motivo del suo successo rispetto ad altri tool (vedi yacc bison e compagnia bella)... ma non ho usato mai nemmeno quelli, anche se, dalle documentazioni che studiai all'epoca è tutta un'altra storia rispetto ad ANTRL.
Mettiamola così: ANTLR è il Python dei generatori di parser. Sintassi semplice ed elegante, genera codice molto facile anche da leggere e debuggare, ed è enormemente produttivo.
Un altro punto di forza è che il lexer e il parser li scrivi nello stesso linguaggio e anche nello stesso file. Un altro è che invece del parser puoi direttamente fargli generare (sempre con lo stesso linguaggio) l'AST delle espressioni parserizzate; così salti pure questa fase, che negli altri parser tipo YACC & co. dev'essere fatta generalmente a manina.
La Sicilia merita. :cool: Non ne dubito. Se avrò l'occasione di venirci ti avviso, potrei offrirla anche io una cena, il posto lo scegli tu però (con tutte le responsabilità del caso :p)
Mettiamola così: ANTLR è il Python dei generatori di parser. Sintassi semplice ed elegante, genera codice molto facile anche da leggere e debuggare, ed è enormemente produttivo.
Un altro punto di forza è che il lexer e il parser li scrivi nello stesso linguaggio e anche nello stesso file. Un altro è che invece del parser puoi direttamente fargli generare (sempre con lo stesso linguaggio) l'AST delle espressioni parserizzate; così salti pure questa fase, che negli altri parser tipo YACC & co. dev'essere fatta generalmente a manina.
Ah però. Dell'AST non ne ero a conoscenza... a questo punto anche solo a tempo perso (anche se penso di potergli dedicare un po' di spazio) è da provare. La curiosità e la voglia non mancano... se non sono richiesti requisiti, sono in rotta.
cdimauro
07-06-2010, 05:52
Purtroppo su Wikipedia si trova poco sugli AST (http://en.wikipedia.org/wiki/Abstract_syntax_tree), per cui ti consiglio di studiare l'argomento sul libro che t'ho consigliato.
Qui (http://www.antlr.org/wiki/display/ANTLR3/Five+minute+introduction+to+ANTLR+3) trovi un'introduzione ad ANTLR "in 5 minuti". Mentre qui (http://www.antlr.org/wiki/display/ANTLR3/Expression+evaluator) un esempio un po' più complesso, di una calcolatrice, in cui viene mostrato anche come far generare direttamente un AST, e un parser che lo "scorre".
Tra l'altro ho scoperto adesso dal sito che l'ha usato Google nel suo App Engine. :D
P.S. Allora ti aspetto. :)
Purtroppo su Wikipedia si trova poco sugli AST (http://en.wikipedia.org/wiki/Abstract_syntax_tree), per cui ti consiglio di studiare l'argomento sul libro che t'ho consigliato.
Già, gli AST li studiai, anche se molto alla veloce, su una dispensa universitaria, per poi passare subito al Three Address Code :)
Comprerò quanto prima il libro che mi hai consigliato, non vedo l'ora di averlo sotto mano per iniziare a divorarlo.
Qui (http://www.antlr.org/wiki/display/ANTLR3/Five+minute+introduction+to+ANTLR+3) trovi un'introduzione ad ANTLR "in 5 minuti". Mentre qui (http://www.antlr.org/wiki/display/ANTLR3/Expression+evaluator) un esempio un po' più complesso, di una calcolatrice, in cui viene mostrato anche come far generare direttamente un AST, e un parser che lo "scorre".
Perfetto! il secondo sembra interessante, strano che ieri spulciando non l'abbia trovato... grazie mille per il link.
Tra l'altro ho scoperto adesso dal sito che l'ha usato Google nel suo App Engine. :D Allora ti ho battuto :O io l'ho scoperto tanto tanto tempo fà.... circa.... ieri sera.
P.S. Allora ti aspetto. :)
ottimo :cool:
Guarda un po' cosa ho trovato, magari li hai già visti, ma:
1 - The Language from the Dragon Book in ANTLR (http://www1.cs.columbia.edu/~sedwards/classes/2006/w4115-fall/dragonbook-language.pdf)
2 - Automate translation of Java to Python (http://roundrockriver.wordpress.com/2007/02/15/automated-translation-of-java-to-python/)
cdimauro
07-06-2010, 20:50
No, non li avevo mai visti. Appena ho un po' di tempo mi smazzo il PDF (l'altro l'ho già letto, ed è una bella esperienza :)).
Grazie!
No, non li avevo mai visti. Appena ho un po' di tempo mi smazzo il PDF (l'altro l'ho già letto, ed è una bella esperienza :)).
Già è proprio bello trovare di tanto in tanto questi progettini cosi interessanti.
Grazie!
A te!
Non mi avessi condotto su ANTLR non li avrei mai trovati nemmeno io :)
tylerdurden83
09-06-2010, 19:07
Probabilmente non ho capito bene cosa ti serve, ma la butto lì...
Ti va bene parallelizzare il parsing di un documento scomponendolo in sottosezioni?
Ad esempio, dovetti parsare dei log applicativi piuttosto grossi, e una volta scoperto se una riga era di interesse o meno, prenderne dei sottocampi e spararli su DB. Un approccio rozzo ma efficiente era, ad es, usare Runtime.getCpuCount per prendere il num di cpu a disposizione, e passare TotaleRigheNelLog/CpuCount (con opportuni offset) ad ogni thread per il parsing ed inserimento su db
Ciao.
Io intendevo proprio parallelizzare il parsing rendendo concorrenti scanner e parser, in modo che entrambi lavorino autonomamente: lo scanner inserendo nuovi simboli e il parser esaminandoli senza che uno debba aspettare e/o dipendere dall'altro (almeno fino a che uno dei due non debba comunicare una eccezione).
Vedi ad esempio la classica get_next_token() che richiama il parser quando ha bisogno di un nuovo token.
Il tuo metodo non l'ho mai usato per fare il parsing di un documento enorme ma ammetto di averci pensato, e di averla scartata: se ti interessa la "legge di Amdahl" fornisce una interessante spiegazione.
L'aumento delle prestazione, la potenza scalare, il cosiddetto "speed up" non è proporzionale al numero di threads ma dipende da altri fattori, e la legge di Amdhal lo dimostra.
Grazie mille per la risposta : )
ps. mi viene in mente il classico caso di ottimizzazione dei cicli condizionali che favoriscono l'ipotesi più frequente a quella meno frequente. Ma questa, è un'altra storia : )
vBulletin® v3.6.4, Copyright ©2000-2026, Jelsoft Enterprises Ltd.