[antlr-interest] Theading Tree Walkers
Loring Craymer
lgcraymer at yahoo.com
Mon Feb 2 14:04:50 PST 2009
Since you are only walking the tree, not rewriting it, in parallel, you could probably get by with a model where only one thread "owns" the AST nodes and does reference counting. That is, look at
ASTRefCount.hpp
ASTRefCount.cpp
RefCount.hpp
and change the reference counting/deletion logic to recognize one node as owner:
add "if (mynode == ASTRef::mynode) ..." around the reference counting code for ASTs
and initialize ASTRef::mynode during parser creation.
(BTW: replace "mynode" by whatever OpenMP uses for getting the local thread id.)
There are other approaches which might work, as well, but this one is a good way to eliminate race conditions without impacting ANTLR behavior and with minimal impact on performance.
--Loring
----- Original Message ----
> From: "code_dude at nym.hush.com" <code_dude at nym.hush.com>
> To: code_dude at nym.hush.com; antlr-interest at antlr.org; lgcraymer at yahoo.com
> Sent: Monday, February 2, 2009 11:09:34 AM
> Subject: Re: [antlr-interest] Theading Tree Walkers
>
>
> Thanks Loring,
> Thats a bit of a blow- My interpreter depends heavily on Tree
> parsing, and it needs to be multi-threaded.
> Can you think of any quick fixes ?
> Would the correct solution to be convert the Parse tree into a
> thread safe tree Of my choosing ?
> what about creating my Parse tree with a custom ast factory thats
> thread safe ?
>
> Regards code dude
>
>
>
> On Mon, 02 Feb 2009 18:51:14 +0000 Loring Craymer
> wrote:
> >C++ garbage collection (uses reference counting in ASTRef) for
> >ANTLR 2 is _not_ thread safe, nor was it intended to be. You'll
> >have to judiciously add in lock/unlock calls to make it so.
> >AFAIK, no one has taken the effort to make any of the ANTLR
> >runtimes thread safe, nor is there any reason to do so under
> >normal conditions--ANTLR operates serially on input data,
> >including trees.
> >
> >--Loring
> >
> >
> >
> >----- Original Message ----
> >> From: "code_dude at nym.hush.com"
> >> To: antlr-interest at antlr.org
> >> Sent: Monday, February 2, 2009 9:11:30 AM
> >> Subject: [antlr-interest] Theading Tree Walkers
> >>
> >> Hi there,
> >> Im using antr-2.7.6 (C++ code generation) and have a threading
> >> problem with the antlr generated tree walker.
> >>
> >> Basically what Im doing if taking the parse tree and sorting the
> >
> >> expressions ( using my custom function openmp_sort(tr, &inn_vtr)
> >)
> >> into their own basic blocks then and then parallel process
> >(using
> >> Open MP) the expressions in each block.
> >>
> >> The thing I when I run it , every so often I get a segmentation
> >> fault from my tree parser. Below is the stack trace from ddd
> >>
> >>
> >> antlr::ASTRef::~ASTRef () (destructor called from
> >ASTRefCount.hpp)
> >> ncoTree::assign (process an essign expression)
> >> ncoTree::out (expression walker)
> >> ncoTree::statements (statement walker)
> >>
> >>
> >> Below is an example of my "openmp_sort(RefAST
> >> tr,std::vector&inn_vtr)" function in action. Also
> >> attached is ( a big simplification ) code detailing how I invoke
> >
> >> the antlr generated code. I hope I have made clear what I'm
> >doing.
> >>
> >>
> >>
> >> // Input Expressions
> >> A=10;
> >> B=20;
> >> C=30;
> >> D=40;
> >> A++;
> >> B*=20;
> >> C-=40;
> >> E=A+B;
> >> F=A+B+C+D+E;
> >> G=A;
> >> G++;
> >> D++;
> >> H=20/++A;
> >> I=A+C+D;
> >> J=40;
> >> K=H*(C-=1);
> >>
> >> // Sorted Expressions
> >> -------------------------------
> >> ( EXPR ( = A 10 ) )
> >> ( EXPR ( = B 20 ) )
> >> ( EXPR ( = C 30 ) )
> >> ( EXPR ( = D 40 ) )
> >> ( EXPR ( = J 40 ) )
> >> -------------------------------
> >> -------------------------------
> >> ( EXPR ( POST_INC A ) )
> >> ( EXPR ( *= B 20 ) )
> >> ( EXPR ( -= C 40 ) )
> >> -------------------------------
> >> -------------------------------
> >> ( EXPR ( = E ( + A B ) ) )
> >> ( EXPR ( = G A ) )
> >> -------------------------------
> >> -------------------------------
> >> ( EXPR ( = F ( + ( + ( + ( + A B ) C ) D ) E ) ) )
> >> ( EXPR ( POST_INC G ) )
> >> -------------------------------
> >> -------------------------------
> >> ( EXPR ( POST_INC D ) )
> >> ( EXPR ( = H ( / 20 ( ++ A ) ) ) )
> >> -------------------------------
> >> -------------------------------
> >> ( EXPR ( = I ( + ( + A C ) D ) ) )
> >> -------------------------------
> >> -------------------------------
> >> ( EXPR ( = K ( * H ( -= C 1 ) ) ) )
> >> -------------------------------
> >>
> >>
> >> /********************** Code
> >> *************************************************/
> >>
> >> int parse_antlr(std::vector&prs_vtr,char* fl_spt_usr,char
> >> *cmd_ln_sng)
> >> {
> >>
> >> ANTLR_USING_NAMESPACE(std);
> >> ANTLR_USING_NAMESPACE(antlr);
> >>
> >>
> >> int idx;
> >> prs_cls *prs_arg;
> >> std::string filename(fl_spt_usr);
> >>
> >> std::vectorwlk_vtr;
> >> std::vectorinn_vtr;
> >>
> >> ncoLexer *lexer=NULL;
> >> ncoParser *parser=NULL;
> >>
> >> istringstream *sin=NULL;
> >> ifstream *in=NULL;
> >>
> >>
> >> RefAST tr,a;
> >> ASTFactory ast_factory;
> >>
> >> prs_arg=&prs_vtr[0];
> >>
> >> std::vectorwlk_vtr;
> >> std::vectorinn_vtr;
> >>
> >>
> >>
> >> if( cmd_ln_sng ){
> >> sin= new istringstream(cmd_ln_sng);
> >> lexer= new ncoLexer( *sin, prs_arg);
> >> selector.addInputStream(lexer,cmd_ln_sng);
> >> selector.select(cmd_ln_sng);
> >> }else {
> >> in=new ifstream(filename.c_str());
> >> lexer= new ncoLexer( *in, prs_arg);
> >> selector.addInputStream(lexer,filename);
> >> selector.select(filename);
> >>
> >> }
> >>
> >>
> >> lexer->setFilename(filename);
> >>
> >> parser= new ncoParser(selector);
> >> parser->setFilename(filename);
> >> parser->inc_vtr.push_back(filename);
> >>
> >>
> >> parser->initializeASTFactory(ast_factory);
> >> parser->setASTFactory(&ast_factory);
> >>
> >>
> >> // Parse the input expressions
> >> parser->program();
> >> a = parser->getAST();
> >>
> >> tr=a;
> >>
> >> // Do an OpenMP Sort
> >> (void)openmp_sort(tr,&inn_vtr);
> >>
> >> // initialize walkers
> >> ncoTree* wlk_obj;
> >> for(idx=0 ; idx< (int)prs_vtr.size(); idx++){
> >> wlk_obj=new ncoTree(&prs_vtr[idx]);
> >> wlk_obj->initializeASTFactory(ast_factory);
> >> wlk_obj->setASTFactory(&ast_factory);
> >> wlk_vtr.push_back(wlk_obj);
> >> }
> >>
> >>
> >>
> >>
> >> // walk the tree in parallel processing statements
> >>
> >> #ifdef _OPENMP
> >> #pragma omp parallel for default(none) private(kdx,wlk_vtr,tr)
> >> #endif
> >> for(kdx=0 ;kdx< nbr_sz; kdx++) {
> >>
> >> tr=inn_vtr[kdx];
> >> wlk_vtr[omp_get_thread_num]->statements(tr);
> >>
> >>
> >> } //end OPENMP parallel loop
> >>
> >>
> >>
> >>
> >>
> >>
> >>
> >> return 1;
> >> }
> >>
> >>
> >> /********************** Code
> >> *************************************************/
> >>
> >>
> >>
> >>
> >> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> >> Unsubscribe:
> >> http://www.antlr.org/mailman/options/antlr-interest/your-email-
> >address
More information about the antlr-interest
mailing list