[antlr-interest] ANTLR 2.7.5 C# runtime in a multi-threadedenvironment hangs

[Micheal J]

Hi Jim,

> Yesterday we were running a stress test and we got hung in an 
> infinite loop in ASTPair.advanceChildToEnd(). The problem was 
> the NextSibling chain wrapped on itself. When exploring how 
> this happened we discovered that some code had been added to 
> ASTPair since the 2.7.2.1. There is a new static Queue in the 
> class and two static methods GetInstance and PutInstance. The 
> parser generated code now calls GetInstance to create and 
> ASTPair and then calls PutInstance when it is done with it. I 
> am assuming this was done to recycle the ASTPairs and avoid 
> new and garbage collect.

The intent was to reduce the rate and magnitude of allocations thereby keep
the churn to a minimum.

> Why not just new an ASTPair when required and let the garbage 
> collector clean it up?

That was the old strategy. It had an often unpleasant cost in memory
usage/churn and overall performance. Especially for larger inputs and
grammars with deep[-ish] rule call depths.

> This is what 2.7.2.1 did. It costs 
> just about nothing to do a "new" in a garbage collected 
> environment (just move the heap pointer) and there is no 
> delete. The only impact is the garbage collect. Rapidly 
> turning over objects get cleanned up very efficiently in the 
> generational .NET garbage collector. Probably less cycles 
> than all the code to enqueue and dequeue the nodes especially 
> if you need critical sections to make it thread safe. A 
> thread static for the queue would work but that is slow too.

As the input size and rule call depth increases, the resource costs (and
hence performance costs) of those ASTPair instances becomes significant. I'm
thinking we need per-parser object pools. This would stll represent a
significant saving on the pre-2.7.5 unbounded scheme.

> Another option that I tried was to eliminate the Get & Put 
> Instance and change the ASTPair from a class to a struct. 
> This way there is no new on the heap at all. It is a value 
> class on the stack. There are a few other chages required to 
> make this work such as passing the currentAST nodes (ASTPair 
> objects) by ref to addASTChild and makeASTRoot in the 
> ASTFactory. There was also a virtual copy method that didn't 
> seem to be needed.

Sounds interesting. More detail on what you tried here would be appreciated.

> Can the next patch release can get rid of this problem?

2.7.6 certainly could have a per-parser object pool.


Micheal
ANTLR/C#