[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