[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: SableCC hangs when 'compiling' a grammar



Hi everybody,

I've been examining the sablecc a bit with jdb and i've added some debug
print statements to the DFA optimize() method.

It looks like the sablecc is 'hanging' there. Actually it is not hanging at
all, i think. No output is produced in 'DFA.optimize()' and this method
takes a very very long time to complete. In 'jdb' is suspended and resumed
the main thread, set some breakpoints in this method and there seem not be
any dead-locks (any more).

I printed out the number of states that outer loop (for (i)) in this method
goes through for my example grammar:

 - Optimizing 133629 states.

I don't know that the average number of state-transitions processed in its
inner loop (for (j)), but it does not surprise me anymore that this method
takes a long time to complete.

Regards,
-- Anton.

PS: Here is the version in which some output is printed:
class DFA ........

    private void optimize()
    {       
        System.out.println("\n - Optimizing DFA.");
        List transitions = new ArrayList(20);

        System.out.println("   Optimizing "+states.size()+" states.");
        
        for(int i = 0; i < states.size(); i++)
        {
            DFA.State state = (DFA.State) states.get(i);
            transitions.add(new ArrayList(0));

            if ((i % 5000) == 0)
                System.out.println("\n   "+(i+1)+": ");
            System.out.print(".");
            
            for(int j = 0; j < state.transitions.size(); j++)
            {
                int max = 0;
                int st = -1;

                for(int k = 0; k < i; k++)
                {
                    int match = match(i,j,k);

                    if(match > max)
                    {
                        max = match;
                        st = k;
                    }
                }

                if(max < 2)
                {
                    ((List) transitions.get(i)).add(
                        state.transitions.get(j));
                }
                else
                {
                    DFA.Transition transition1 =
                        (DFA.Transition) state.transitions.get(j);
                    DFA.Transition transition2 =
                        (DFA.Transition) state.transitions.get(j + max - 1);

                    DFA.Transition transition =
                        new DFA.Transition(
                        new CharSet.Interval(
                        transition1.interval().start,
                        transition2.interval().end),
                        -2 - st);

                    ((List) transitions.get(i)).add(transition);
                    j += max - 1;
                }
            }
        }

        System.out.println("");
        for(int i = 0; i < states.size(); i++)
        {
            DFA.State state = (DFA.State) states.get(i);
            state.transitions = (List) transitions.get(i);
            System.out.print(".");
        }
        System.out.println(" - Optimizing DFA Ready.");
    }

-----Original Message-----
From: Mariusz Nowostawski [mailto:mariusz@marni.otago.ac.nz]
Sent: Tuesday, May 22, 2001 18:41
To: Etienne M. Gagnon
Cc: Anton Spaans; sablecc-list
Subject: Re: SableCC hangs when 'compiling' a grammar


On Tue, 22 May 2001, Etienne M. Gagnon wrote:

> "Etienne M. Gagnon" wrote:
> > main:
> >   [1] java.util.Vector.elementAt (Vector.java:419)
> >   [2] org.sablecc.sablecc.DFA.match (DFA.java:96)
>
> There is no reason why SableCC should still be using "Vector", as it is
> "synchonized" and SableCC is not meant to be multithreaded.  I think the
> Collection API provides an ArrayList (or something similar) which
> provides the functionality of Vector, but without synchronization.
>
> I haven't fixed this because I don't have the time to do it.  If you
> want (or anybody else) to implement this modification, please free to do
> so using the current CVS snapshot.(See http://sf.net/projects/sablecc/).


Done.

I have just moved all the dependencies from synchronized Vectors to
not synchronized Lists (ArrayList). Seems to compile examples a little
faster, but I do not have any numerical statistics. Code is in CVS, I have
run tests on all the grammars we have and it works ok.


> Maybe this could get you past the VM bug (if it is really a bug related
> to locks).

I have run the "new" version of SableCC on this test grammar, and
unfortunatelly the problem is not fixed. Normally I am getting OutOfMemory
exception, and with the increased memory for Java and gc verbose I am
getting:

<AF[32]: Allocation Failure. need 96 bytes, 9299 ms since last AF>
<AF[32]: managing allocation failure, action=1 (0/234421240)
(3145728/3145728)>
<GC: Wed May 23 10:20:55 2001


and my JVM freezes in here. I am using Java(TM) 2 Runtime Environment,
Standard Edition (build 1.3.0) Classic VM (build 1.3.0, J2RE 1.3.0 IBM
build cx130-20010329 (JIT enabled: jitc))

The problematic thing is that it freezes after consuming about 400 MB of
memory (I have 512MB together RAM+swap), which means whatever it is, it is
really memory consuming thing ;o)   To make sure that something is wrong,
would be good to run it on a machine with >1GB of virtual memory ;o)

best regards
Mariusz