search

jespersm / groovy

Mirror of Apache Groovy
Apache License 2.0
2 stars 1 forks source link

Improve the performance of the new parser #37

Closed daniellansun closed 5 years ago

daniellansun commented 8 years ago

@sharwell provided a useful advice:

"You can save a great deal of time on correct inputs by using a two-stage parsing strategy.

1) Attempt to parse the input using BailErrorStrategy and PredictionMode.SLL. If no exception is thrown, you know the answer is correct. 2) If a ParseCancellationException is thrown, retry the parse using the default settings (DefaultErrorStrategy and PredictionMode.LL)."

https://github.com/antlr/antlr4/issues/192

daniellansun commented 8 years ago

The new parser will hang when parsing some scripts because of SLL parsing strategy. I'm not sure whether it is a bug of antlr4.

parser.getInterpreter().setPredictionMode(PredictionMode.SLL); // try simpler/faster SLL(*)
parser.removeErrorListeners();
parser.setErrorHandler(new BailErrorStrategy());
daniellansun commented 8 years ago

Thread Dump:

"Test worker" #11 prio=5 os_prio=0 tid=0x0000000058ab5000 nid=0x21dc runnable [0x0000000059bda000]
   java.lang.Thread.State: RUNNABLE
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at java.util.HashMap.getNode(HashMap.java:571)
    at java.util.HashMap.containsKey(HashMap.java:595)
    at org.antlr.v4.runtime.atn.PredictionContext.combineCommonParents(PredictionContext.java:498)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:482)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:197)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeSingletons(PredictionContext.java:248)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:178)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:418)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:197)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeSingletons(PredictionContext.java:248)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:178)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeSingletons(PredictionContext.java:248)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:178)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:418)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:197)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeSingletons(PredictionContext.java:248)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:178)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:418)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:197)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeSingletons(PredictionContext.java:248)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:178)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:418)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:197)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:418)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:197)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeSingletons(PredictionContext.java:248)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:178)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:418)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:197)
    at org.antlr.v4.runtime.atn.ATNConfigSet.add(ATNConfigSet.java:178)
    at org.antlr.v4.runtime.atn.ATNConfigSet.add(ATNConfigSet.java:146)
    at org.antlr.v4.runtime.atn.PredictionMode.hasSLLConflictTerminatingPrediction(PredictionMode.java:256)
    at org.antlr.v4.runtime.atn.ParserATNSimulator.computeTargetState(ParserATNSimulator.java:621)
    at org.antlr.v4.runtime.atn.ParserATNSimulator.execATN(ParserATNSimulator.java:473)
    at org.antlr.v4.runtime.atn.ParserATNSimulator.adaptivePredict(ParserATNSimulator.java:412)
    at org.codehaus.groovy.parser.antlr4.GroovyParser.compilationUnit(GroovyParser.java:400)
    at org.codehaus.groovy.parser.antlr4.ASTBuilder.startParsing(ASTBuilder.java:114)
    at org.codehaus.groovy.parser.antlr4.ASTBuilder.<init>(ASTBuilder.java:82)
    at org.codehaus.groovy.parser.antlr4.Antlrv4ParserPlugin.buildAST(Antlrv4ParserPlugin.java:37)
    at org.codehaus.groovy.control.SourceUnit.convert(SourceUnit.java:269)
    at org.codehaus.groovy.control.SourceUnit$convert$0.call(Unknown Source)
    at org.codehaus.groovy.parser.antlr4.Main.process(Main.groovy:71)
    at org.codehaus.groovy.parser.antlr4.Main$process.call(Unknown Source)
    at org.codehaus.groovy.runtime.callsite.CallSiteArray.defaultCall(CallSiteArray.java:48)
    at org.codehaus.groovy.runtime.callsite.AbstractCallSite.call(AbstractCallSite.java:113)
    at org.codehaus.groovy.runtime.callsite.AbstractCallSite.call(AbstractCallSite.java:125)
    at org.codehaus.groovy.parser.antlr4.MainTest.$spock_feature_0_1(MainTest.groovy:148)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:498)
    at org.spockframework.util.ReflectionUtil.invokeMethod(ReflectionUtil.java:153)
    at org.spockframework.runtime.model.MethodInfo.invoke(MethodInfo.java:84)
    at org.spockframework.runtime.BaseSpecRunner.invokeRaw(BaseSpecRunner.java:480)
    at org.spockframework.runtime.BaseSpecRunner.invoke(BaseSpecRunner.java:463)
    at org.spockframework.runtime.BaseSpecRunner.runFeatureMethod(BaseSpecRunner.java:405)
    at org.spockframework.runtime.BaseSpecRunner.doRunIteration(BaseSpecRunner.java:324)
    at org.spockframework.runtime.BaseSpecRunner$6.invoke(BaseSpecRunner.java:309)
    at org.spockframework.runtime.BaseSpecRunner.invokeRaw(BaseSpecRunner.java:480)
    at org.spockframework.runtime.BaseSpecRunner.invoke(BaseSpecRunner.java:463)
    at org.spockframework.runtime.BaseSpecRunner.runIteration(BaseSpecRunner.java:288)
    at org.spockframework.runtime.BaseSpecRunner.initializeAndRunIteration(BaseSpecRunner.java:278)
    at org.spockframework.runtime.ParameterizedSpecRunner.runIterations(ParameterizedSpecRunner.java:119)
    at org.spockframework.runtime.ParameterizedSpecRunner.runParameterizedFeature(ParameterizedSpecRunner.java:43)
    at org.spockframework.runtime.BaseSpecRunner.doRunFeature(BaseSpecRunner.java:262)
    at org.spockframework.runtime.BaseSpecRunner$5.invoke(BaseSpecRunner.java:246)
    at org.spockframework.runtime.BaseSpecRunner.invokeRaw(BaseSpecRunner.java:480)
    at org.spockframework.runtime.BaseSpecRunner.invoke(BaseSpecRunner.java:463)
    at org.spockframework.runtime.BaseSpecRunner.runFeature(BaseSpecRunner.java:238)
    at org.spockframework.runtime.BaseSpecRunner.runFeatures(BaseSpecRunner.java:188)
    at org.spockframework.runtime.BaseSpecRunner.doRunSpec(BaseSpecRunner.java:98)
    at org.spockframework.runtime.BaseSpecRunner$1.invoke(BaseSpecRunner.java:84)
    at org.spockframework.runtime.BaseSpecRunner.invokeRaw(BaseSpecRunner.java:480)
    at org.spockframework.runtime.BaseSpecRunner.invoke(BaseSpecRunner.java:463)
    at org.spockframework.runtime.BaseSpecRunner.runSpec(BaseSpecRunner.java:76)
    at org.spockframework.runtime.BaseSpecRunner.run(BaseSpecRunner.java:67)
    at org.spockframework.runtime.Sputnik.run(Sputnik.java:63)
    at org.gradle.api.internal.tasks.testing.junit.JUnitTestClassExecuter.runTestClass(JUnitTestClassExecuter.java:112)
    at org.gradle.api.internal.tasks.testing.junit.JUnitTestClassExecuter.execute(JUnitTestClassExecuter.java:56)
    at org.gradle.api.internal.tasks.testing.junit.JUnitTestClassProcessor.processTestClass(JUnitTestClassProcessor.java:66)
    at org.gradle.api.internal.tasks.testing.SuiteTestClassProcessor.processTestClass(SuiteTestClassProcessor.java:51)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:498)
    at org.gradle.messaging.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:35)
    at org.gradle.messaging.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:24)
    at org.gradle.messaging.dispatch.ContextClassLoaderDispatch.dispatch(ContextClassLoaderDispatch.java:32)
    at org.gradle.messaging.dispatch.ProxyDispatchAdapter$DispatchingInvocationHandler.invoke(ProxyDispatchAdapter.java:93)
    at com.sun.proxy.$Proxy2.processTestClass(Unknown Source)
    at org.gradle.api.internal.tasks.testing.worker.TestWorker.processTestClass(TestWorker.java:109)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:498)
    at org.gradle.messaging.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:35)
    at org.gradle.messaging.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:24)
    at org.gradle.messaging.remote.internal.hub.MessageHub$Handler.run(MessageHub.java:360)
    at org.gradle.internal.concurrent.ExecutorPolicy$CatchAndRecordFailures.onExecute(ExecutorPolicy.java:54)
    at org.gradle.internal.concurrent.StoppableExecutorImpl$1.run(StoppableExecutorImpl.java:40)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:745)

   Locked ownable synchronizers:
    - <0x00000000a6e51228> (a java.util.concurrent.ThreadPoolExecutor$Worker)

Complete Dump:

2016-05-03 22:06:35
Full thread dump Java HotSpot(TM) 64-Bit Server VM (25.92-b14 mixed mode):

"RMI TCP Connection(9)-107.252.127.104" #20 daemon prio=5 os_prio=0 tid=0x000000005a893000 nid=0x13e0 runnable [0x000000006122e000]
   java.lang.Thread.State: RUNNABLE
    at java.net.SocketInputStream.socketRead0(Native Method)
    at java.net.SocketInputStream.socketRead(SocketInputStream.java:116)
    at java.net.SocketInputStream.read(SocketInputStream.java:170)
    at java.net.SocketInputStream.read(SocketInputStream.java:141)
    at java.io.BufferedInputStream.fill(BufferedInputStream.java:246)
    at java.io.BufferedInputStream.read(BufferedInputStream.java:265)
    - locked <0x00000000a7f18e98> (a java.io.BufferedInputStream)
    at java.io.FilterInputStream.read(FilterInputStream.java:83)
    at sun.rmi.transport.tcp.TCPTransport.handleMessages(TCPTransport.java:550)
    at sun.rmi.transport.tcp.TCPTransport$ConnectionHandler.run0(TCPTransport.java:826)
    at sun.rmi.transport.tcp.TCPTransport$ConnectionHandler.lambda$run$0(TCPTransport.java:683)
    at sun.rmi.transport.tcp.TCPTransport$ConnectionHandler$$Lambda$3/1751489367.run(Unknown Source)
    at java.security.AccessController.doPrivileged(Native Method)
    at sun.rmi.transport.tcp.TCPTransport$ConnectionHandler.run(TCPTransport.java:682)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:745)

   Locked ownable synchronizers:
    - <0x00000000a7bcd098> (a java.util.concurrent.ThreadPoolExecutor$Worker)

"RMI TCP Connection(12)-107.252.127.104" #19 daemon prio=5 os_prio=0 tid=0x000000005a898000 nid=0x2274 runnable [0x00000000614dd000]
   java.lang.Thread.State: RUNNABLE
    at java.net.SocketInputStream.socketRead0(Native Method)
    at java.net.SocketInputStream.socketRead(SocketInputStream.java:116)
    at java.net.SocketInputStream.read(SocketInputStream.java:170)
    at java.net.SocketInputStream.read(SocketInputStream.java:141)
    at java.io.BufferedInputStream.fill(BufferedInputStream.java:246)
    at java.io.BufferedInputStream.read(BufferedInputStream.java:265)
    - locked <0x00000000b9d061d8> (a java.io.BufferedInputStream)
    at java.io.FilterInputStream.read(FilterInputStream.java:83)
    at sun.rmi.transport.tcp.TCPTransport.handleMessages(TCPTransport.java:550)
    at sun.rmi.transport.tcp.TCPTransport$ConnectionHandler.run0(TCPTransport.java:826)
    at sun.rmi.transport.tcp.TCPTransport$ConnectionHandler.lambda$run$0(TCPTransport.java:683)
    at sun.rmi.transport.tcp.TCPTransport$ConnectionHandler$$Lambda$3/1751489367.run(Unknown Source)
    at java.security.AccessController.doPrivileged(Native Method)
    at sun.rmi.transport.tcp.TCPTransport$ConnectionHandler.run(TCPTransport.java:682)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:745)

   Locked ownable synchronizers:
    - <0x00000000a7b2d940> (a java.util.concurrent.ThreadPoolExecutor$Worker)

"JMX server connection timeout 18" #18 daemon prio=5 os_prio=0 tid=0x000000005a893800 nid=0x2254 in Object.wait() [0x000000006136f000]
   java.lang.Thread.State: TIMED_WAITING (on object monitor)
    at java.lang.Object.wait(Native Method)
    at com.sun.jmx.remote.internal.ServerCommunicatorAdmin$Timeout.run(ServerCommunicatorAdmin.java:168)
    - locked <0x00000000a7af7b50> (a [I)
    at java.lang.Thread.run(Thread.java:745)

   Locked ownable synchronizers:
    - None

"RMI Scheduler(0)" #17 daemon prio=5 os_prio=0 tid=0x000000005a897800 nid=0x224c waiting on condition [0x000000005dc5e000]
   java.lang.Thread.State: TIMED_WAITING (parking)
    at sun.misc.Unsafe.park(Native Method)
    - parking to wait for  <0x00000000a7a89f90> (a java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject)
    at java.util.concurrent.locks.LockSupport.parkNanos(LockSupport.java:215)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.awaitNanos(AbstractQueuedSynchronizer.java:2078)
    at java.util.concurrent.ScheduledThreadPoolExecutor$DelayedWorkQueue.take(ScheduledThreadPoolExecutor.java:1093)
    at java.util.concurrent.ScheduledThreadPoolExecutor$DelayedWorkQueue.take(ScheduledThreadPoolExecutor.java:809)
    at java.util.concurrent.ThreadPoolExecutor.getTask(ThreadPoolExecutor.java:1067)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1127)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:745)

   Locked ownable synchronizers:
    - None

"RMI TCP Accept-0" #15 daemon prio=5 os_prio=0 tid=0x000000005a896000 nid=0x2238 runnable [0x000000005dfef000]
   java.lang.Thread.State: RUNNABLE
    at java.net.DualStackPlainSocketImpl.accept0(Native Method)
    at java.net.DualStackPlainSocketImpl.socketAccept(DualStackPlainSocketImpl.java:131)
    at java.net.AbstractPlainSocketImpl.accept(AbstractPlainSocketImpl.java:409)
    at java.net.PlainSocketImpl.accept(PlainSocketImpl.java:199)
    - locked <0x00000000a7a98b70> (a java.net.SocksSocketImpl)
    at java.net.ServerSocket.implAccept(ServerSocket.java:545)
    at java.net.ServerSocket.accept(ServerSocket.java:513)
    at sun.management.jmxremote.LocalRMIServerSocketFactory$1.accept(LocalRMIServerSocketFactory.java:52)
    at sun.rmi.transport.tcp.TCPTransport$AcceptLoop.executeAcceptLoop(TCPTransport.java:400)
    at sun.rmi.transport.tcp.TCPTransport$AcceptLoop.run(TCPTransport.java:372)
    at java.lang.Thread.run(Thread.java:745)

   Locked ownable synchronizers:
    - None

"/127.0.0.1:54209 to /127.0.0.1:54208 workers Thread 3" #13 prio=5 os_prio=0 tid=0x0000000058b62000 nid=0x21e4 runnable [0x0000000059d7e000]
   java.lang.Thread.State: RUNNABLE
    at sun.nio.ch.WindowsSelectorImpl$SubSelector.poll0(Native Method)
    at sun.nio.ch.WindowsSelectorImpl$SubSelector.poll(WindowsSelectorImpl.java:296)
    at sun.nio.ch.WindowsSelectorImpl$SubSelector.access$400(WindowsSelectorImpl.java:278)
    at sun.nio.ch.WindowsSelectorImpl.doSelect(WindowsSelectorImpl.java:159)
    at sun.nio.ch.SelectorImpl.lockAndDoSelect(SelectorImpl.java:86)
    - locked <0x00000000a6e31388> (a sun.nio.ch.Util$2)
    - locked <0x00000000a6e31378> (a java.util.Collections$UnmodifiableSet)
    - locked <0x00000000a6e31138> (a sun.nio.ch.WindowsSelectorImpl)
    at sun.nio.ch.SelectorImpl.select(SelectorImpl.java:97)
    at sun.nio.ch.SelectorImpl.select(SelectorImpl.java:101)
    at org.gradle.messaging.remote.internal.inet.SocketConnection$SocketInputStream.read(SocketConnection.java:154)
    at com.esotericsoftware.kryo.io.Input.fill(Input.java:139)
    at com.esotericsoftware.kryo.io.Input.require(Input.java:159)
    at com.esotericsoftware.kryo.io.Input.readByte(Input.java:255)
    at org.gradle.internal.serialize.kryo.KryoBackedDecoder.readByte(KryoBackedDecoder.java:80)
    at org.gradle.messaging.remote.internal.hub.InterHubMessageSerializer$MessageReader.read(InterHubMessageSerializer.java:63)
    at org.gradle.messaging.remote.internal.hub.InterHubMessageSerializer$MessageReader.read(InterHubMessageSerializer.java:52)
    at org.gradle.messaging.remote.internal.inet.SocketConnection.receive(SocketConnection.java:77)
    at org.gradle.messaging.remote.internal.hub.MessageHub$ConnectionReceive.run(MessageHub.java:235)
    at org.gradle.internal.concurrent.ExecutorPolicy$CatchAndRecordFailures.onExecute(ExecutorPolicy.java:54)
    at org.gradle.internal.concurrent.StoppableExecutorImpl$1.run(StoppableExecutorImpl.java:40)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:745)

   Locked ownable synchronizers:
    - <0x00000000a6e30b70> (a java.util.concurrent.ThreadPoolExecutor$Worker)

"/127.0.0.1:54209 to /127.0.0.1:54208 workers Thread 2" #12 prio=5 os_prio=0 tid=0x0000000058b61800 nid=0x21e0 waiting on condition [0x0000000059e7e000]
   java.lang.Thread.State: WAITING (parking)
    at sun.misc.Unsafe.park(Native Method)
    - parking to wait for  <0x00000000a6e50f00> (a java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject)
    at java.util.concurrent.locks.LockSupport.park(LockSupport.java:175)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.await(AbstractQueuedSynchronizer.java:2039)
    at org.gradle.messaging.remote.internal.hub.queue.EndPointQueue.take(EndPointQueue.java:49)
    at org.gradle.messaging.remote.internal.hub.MessageHub$ConnectionDispatch.run(MessageHub.java:278)
    at org.gradle.internal.concurrent.ExecutorPolicy$CatchAndRecordFailures.onExecute(ExecutorPolicy.java:54)
    at org.gradle.internal.concurrent.StoppableExecutorImpl$1.run(StoppableExecutorImpl.java:40)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:745)

   Locked ownable synchronizers:
    - <0x00000000a6e30d08> (a java.util.concurrent.ThreadPoolExecutor$Worker)

"Test worker" #11 prio=5 os_prio=0 tid=0x0000000058ab5000 nid=0x21dc runnable [0x0000000059bda000]
   java.lang.Thread.State: RUNNABLE
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at java.util.Arrays.equals(Arrays.java:2829)
    at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:101)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at org.antlr.v4.runtime.atn.SingletonPredictionContext.equals(SingletonPredictionContext.java:83)
    at java.util.HashMap.getNode(HashMap.java:571)
    at java.util.HashMap.containsKey(HashMap.java:595)
    at org.antlr.v4.runtime.atn.PredictionContext.combineCommonParents(PredictionContext.java:498)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:482)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:197)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeSingletons(PredictionContext.java:248)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:178)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:418)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:197)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeSingletons(PredictionContext.java:248)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:178)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeSingletons(PredictionContext.java:248)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:178)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:418)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:197)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeSingletons(PredictionContext.java:248)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:178)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:418)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:197)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeSingletons(PredictionContext.java:248)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:178)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:418)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:197)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:418)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:197)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeSingletons(PredictionContext.java:248)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:178)
    at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:418)
    at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:197)
    at org.antlr.v4.runtime.atn.ATNConfigSet.add(ATNConfigSet.java:178)
    at org.antlr.v4.runtime.atn.ATNConfigSet.add(ATNConfigSet.java:146)
    at org.antlr.v4.runtime.atn.PredictionMode.hasSLLConflictTerminatingPrediction(PredictionMode.java:256)
    at org.antlr.v4.runtime.atn.ParserATNSimulator.computeTargetState(ParserATNSimulator.java:621)
    at org.antlr.v4.runtime.atn.ParserATNSimulator.execATN(ParserATNSimulator.java:473)
    at org.antlr.v4.runtime.atn.ParserATNSimulator.adaptivePredict(ParserATNSimulator.java:412)
    at org.codehaus.groovy.parser.antlr4.GroovyParser.compilationUnit(GroovyParser.java:400)
    at org.codehaus.groovy.parser.antlr4.ASTBuilder.startParsing(ASTBuilder.java:114)
    at org.codehaus.groovy.parser.antlr4.ASTBuilder.<init>(ASTBuilder.java:82)
    at org.codehaus.groovy.parser.antlr4.Antlrv4ParserPlugin.buildAST(Antlrv4ParserPlugin.java:37)
    at org.codehaus.groovy.control.SourceUnit.convert(SourceUnit.java:269)
    at org.codehaus.groovy.control.SourceUnit$convert$0.call(Unknown Source)
    at org.codehaus.groovy.parser.antlr4.Main.process(Main.groovy:71)
    at org.codehaus.groovy.parser.antlr4.Main$process.call(Unknown Source)
    at org.codehaus.groovy.runtime.callsite.CallSiteArray.defaultCall(CallSiteArray.java:48)
    at org.codehaus.groovy.runtime.callsite.AbstractCallSite.call(AbstractCallSite.java:113)
    at org.codehaus.groovy.runtime.callsite.AbstractCallSite.call(AbstractCallSite.java:125)
    at org.codehaus.groovy.parser.antlr4.MainTest.$spock_feature_0_1(MainTest.groovy:148)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:498)
    at org.spockframework.util.ReflectionUtil.invokeMethod(ReflectionUtil.java:153)
    at org.spockframework.runtime.model.MethodInfo.invoke(MethodInfo.java:84)
    at org.spockframework.runtime.BaseSpecRunner.invokeRaw(BaseSpecRunner.java:480)
    at org.spockframework.runtime.BaseSpecRunner.invoke(BaseSpecRunner.java:463)
    at org.spockframework.runtime.BaseSpecRunner.runFeatureMethod(BaseSpecRunner.java:405)
    at org.spockframework.runtime.BaseSpecRunner.doRunIteration(BaseSpecRunner.java:324)
    at org.spockframework.runtime.BaseSpecRunner$6.invoke(BaseSpecRunner.java:309)
    at org.spockframework.runtime.BaseSpecRunner.invokeRaw(BaseSpecRunner.java:480)
    at org.spockframework.runtime.BaseSpecRunner.invoke(BaseSpecRunner.java:463)
    at org.spockframework.runtime.BaseSpecRunner.runIteration(BaseSpecRunner.java:288)
    at org.spockframework.runtime.BaseSpecRunner.initializeAndRunIteration(BaseSpecRunner.java:278)
    at org.spockframework.runtime.ParameterizedSpecRunner.runIterations(ParameterizedSpecRunner.java:119)
    at org.spockframework.runtime.ParameterizedSpecRunner.runParameterizedFeature(ParameterizedSpecRunner.java:43)
    at org.spockframework.runtime.BaseSpecRunner.doRunFeature(BaseSpecRunner.java:262)
    at org.spockframework.runtime.BaseSpecRunner$5.invoke(BaseSpecRunner.java:246)
    at org.spockframework.runtime.BaseSpecRunner.invokeRaw(BaseSpecRunner.java:480)
    at org.spockframework.runtime.BaseSpecRunner.invoke(BaseSpecRunner.java:463)
    at org.spockframework.runtime.BaseSpecRunner.runFeature(BaseSpecRunner.java:238)
    at org.spockframework.runtime.BaseSpecRunner.runFeatures(BaseSpecRunner.java:188)
    at org.spockframework.runtime.BaseSpecRunner.doRunSpec(BaseSpecRunner.java:98)
    at org.spockframework.runtime.BaseSpecRunner$1.invoke(BaseSpecRunner.java:84)
    at org.spockframework.runtime.BaseSpecRunner.invokeRaw(BaseSpecRunner.java:480)
    at org.spockframework.runtime.BaseSpecRunner.invoke(BaseSpecRunner.java:463)
    at org.spockframework.runtime.BaseSpecRunner.runSpec(BaseSpecRunner.java:76)
    at org.spockframework.runtime.BaseSpecRunner.run(BaseSpecRunner.java:67)
    at org.spockframework.runtime.Sputnik.run(Sputnik.java:63)
    at org.gradle.api.internal.tasks.testing.junit.JUnitTestClassExecuter.runTestClass(JUnitTestClassExecuter.java:112)
    at org.gradle.api.internal.tasks.testing.junit.JUnitTestClassExecuter.execute(JUnitTestClassExecuter.java:56)
    at org.gradle.api.internal.tasks.testing.junit.JUnitTestClassProcessor.processTestClass(JUnitTestClassProcessor.java:66)
    at org.gradle.api.internal.tasks.testing.SuiteTestClassProcessor.processTestClass(SuiteTestClassProcessor.java:51)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:498)
    at org.gradle.messaging.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:35)
    at org.gradle.messaging.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:24)
    at org.gradle.messaging.dispatch.ContextClassLoaderDispatch.dispatch(ContextClassLoaderDispatch.java:32)
    at org.gradle.messaging.dispatch.ProxyDispatchAdapter$DispatchingInvocationHandler.invoke(ProxyDispatchAdapter.java:93)
    at com.sun.proxy.$Proxy2.processTestClass(Unknown Source)
    at org.gradle.api.internal.tasks.testing.worker.TestWorker.processTestClass(TestWorker.java:109)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:498)
    at org.gradle.messaging.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:35)
    at org.gradle.messaging.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:24)
    at org.gradle.messaging.remote.internal.hub.MessageHub$Handler.run(MessageHub.java:360)
    at org.gradle.internal.concurrent.ExecutorPolicy$CatchAndRecordFailures.onExecute(ExecutorPolicy.java:54)
    at org.gradle.internal.concurrent.StoppableExecutorImpl$1.run(StoppableExecutorImpl.java:40)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:745)

   Locked ownable synchronizers:
    - <0x00000000a6e51228> (a java.util.concurrent.ThreadPoolExecutor$Worker)

"Service Thread" #9 daemon prio=9 os_prio=0 tid=0x000000005743f000 nid=0x21c4 runnable [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

   Locked ownable synchronizers:
    - None

"C1 CompilerThread2" #8 daemon prio=9 os_prio=2 tid=0x00000000573bc800 nid=0x21c0 waiting on condition [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

   Locked ownable synchronizers:
    - None

"C2 CompilerThread1" #7 daemon prio=9 os_prio=2 tid=0x00000000573bb000 nid=0x21bc waiting on condition [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

   Locked ownable synchronizers:
    - None

"C2 CompilerThread0" #6 daemon prio=9 os_prio=2 tid=0x00000000573b7000 nid=0x21b8 waiting on condition [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

   Locked ownable synchronizers:
    - None

"Attach Listener" #5 daemon prio=5 os_prio=2 tid=0x00000000573a8000 nid=0x21b4 waiting on condition [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

   Locked ownable synchronizers:
    - None

"Signal Dispatcher" #4 daemon prio=9 os_prio=2 tid=0x00000000573a7800 nid=0x21b0 runnable [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

   Locked ownable synchronizers:
    - None

"Finalizer" #3 daemon prio=8 os_prio=1 tid=0x0000000055fb9000 nid=0x21ac in Object.wait() [0x00000000122fe000]
   java.lang.Thread.State: WAITING (on object monitor)
    at java.lang.Object.wait(Native Method)
    at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:143)
    - locked <0x00000000a68a63c0> (a java.lang.ref.ReferenceQueue$Lock)
    at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:164)
    at java.lang.ref.Finalizer$FinalizerThread.run(Finalizer.java:209)

   Locked ownable synchronizers:
    - None

"Reference Handler" #2 daemon prio=10 os_prio=2 tid=0x0000000055f72000 nid=0x21a8 in Object.wait() [0x000000005736e000]
   java.lang.Thread.State: WAITING (on object monitor)
    at java.lang.Object.wait(Native Method)
    at java.lang.Object.wait(Object.java:502)
    at java.lang.ref.Reference.tryHandlePending(Reference.java:191)
    - locked <0x00000000a69b8000> (a java.lang.ref.Reference$Lock)
    at java.lang.ref.Reference$ReferenceHandler.run(Reference.java:153)

   Locked ownable synchronizers:
    - None

"main" #1 prio=5 os_prio=0 tid=0x000000000264e800 nid=0x2190 waiting on condition [0x000000000298f000]
   java.lang.Thread.State: WAITING (parking)
    at sun.misc.Unsafe.park(Native Method)
    - parking to wait for  <0x00000000a6e8ae10> (a java.util.concurrent.CountDownLatch$Sync)
    at java.util.concurrent.locks.LockSupport.park(LockSupport.java:175)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:836)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.doAcquireSharedInterruptibly(AbstractQueuedSynchronizer.java:997)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireSharedInterruptibly(AbstractQueuedSynchronizer.java:1304)
    at java.util.concurrent.CountDownLatch.await(CountDownLatch.java:231)
    at org.gradle.api.internal.tasks.testing.worker.TestWorker.execute(TestWorker.java:70)
    at org.gradle.api.internal.tasks.testing.worker.TestWorker.execute(TestWorker.java:45)
    at org.gradle.process.internal.child.ActionExecutionWorker.execute(ActionExecutionWorker.java:85)
    at org.gradle.process.internal.child.ActionExecutionWorker.execute(ActionExecutionWorker.java:37)
    at org.gradle.process.internal.child.ImplementationClassLoaderWorker.execute(ImplementationClassLoaderWorker.java:87)
    at org.gradle.process.internal.child.ImplementationClassLoaderWorker.execute(ImplementationClassLoaderWorker.java:41)
    at org.gradle.process.internal.child.SystemApplicationClassLoaderWorker.call(SystemApplicationClassLoaderWorker.java:49)
    at org.gradle.process.internal.child.SystemApplicationClassLoaderWorker.call(SystemApplicationClassLoaderWorker.java:33)
    at jarjar.org.gradle.process.internal.launcher.GradleWorkerMain.run(GradleWorkerMain.java:69)
    at jarjar.org.gradle.process.internal.launcher.GradleWorkerMain.main(GradleWorkerMain.java:74)

   Locked ownable synchronizers:
    - None

"VM Thread" os_prio=2 tid=0x0000000055f6a800 nid=0x21a4 runnable 

"GC task thread#0 (ParallelGC)" os_prio=0 tid=0x00000000024cc800 nid=0x2194 runnable 

"GC task thread#1 (ParallelGC)" os_prio=0 tid=0x00000000024ce000 nid=0x2198 runnable 

"GC task thread#2 (ParallelGC)" os_prio=0 tid=0x00000000024cf800 nid=0x219c runnable 

"GC task thread#3 (ParallelGC)" os_prio=0 tid=0x00000000024d1000 nid=0x21a0 runnable 

"VM Periodic Task Thread" os_prio=2 tid=0x0000000057400000 nid=0x21c8 waiting on condition 

JNI global references: 287
sharwell commented 8 years ago

@danielsun1106 Can you try using com.tunnelvisionlabs:antlr4 instead of org.antlr:antlr4? Let me know if the performance is noticeably different in your particular application.

daniellansun commented 8 years ago

@sharwell Sam, I'll try later. Maybe I have to modify the package name manually. Thanks in advance!

daniellansun commented 8 years ago

@sharwell @parrt I tried com.tunnelvisionlabs:antlr4 just now, its SLL parsing strategy is very efficient. The performance issue of org.antlr:antlr4(4.5.3) does not exist in the com.tunnelvisionlabs:antlr4(4.5). Could you tell me how to workaround the issue with org.antlr:antlr4? Thanks.

sharwell commented 8 years ago

@danielsun1106 The alternative package I mentioned contains a large number of optimizations which are not planned to be incorporated into the reference release. For most day-to-day users of ANTLR, these optimizations are excessively complicated and provide little real world benefit. However, on a few occasions I have seen large and/or complicated grammars unable to work at all without them. To make things worse, different grammars which require the "optimized" release tend to require it be used with different settings - for example the grammar for the Boo programming language requires us to enable an LL parsing setting that defaults to disabled in the optimized release because it actually slows down other grammars.

If your test is limited to SLL parsing, then you are likely benefiting from one or more of the following features of the optimized release:

  1. Tail call elimination
  2. Reduced memory usage for the DFA cache
  3. Optimized SLL PredictionContext construction (through the PredictionContextCache)
  4. Improved SLL termination condition (currently no known grammar exhibits this as a dominant performance characteristic, but it is a possibility since there are theoretically cases where the SLL prediction lookahead is shorter)
blackdrag commented 8 years ago

So maybe this is something that should be done once the grammar is stable?

daniellansun commented 8 years ago

@sharwell Thanks for your detailed reply! The two-stage parsing strategy may be much suitable for the new parser based on Antlr4. It's pity that we can not apply two-stage parsing strategy because of the performance issue of org.antlr:antlr4.

@blackdrag You're right. We can tune the performance later.

parrt commented 8 years ago

The tail call elimination is the biggie I suspect. I plan on following Sam's lead there and will introduce into antlr/antlr4 repo when it bumps up in priority for me.

daniellansun commented 8 years ago

grails-web-databinding/src/main/groovy/org/grails/web/databinding/GrailsWebDataBindingListener.groovy cost 22s; grails-web-databinding/src/main/groovy/grails/web/databinding/GrailsWebDataBinder.groovy cost 3s; grails-databinding/src/main/groovy/grails/databinding/SimpleDataBinder.groovy cost 3s; ...

http://ci.groovy-lang.org/viewLog.html?buildId=33761&tab=testsInfo&buildTypeId=Groovy_Antlr4grammar

jespersm commented 8 years ago

@danielsun1106 : I think (and hope) that the test in question is impacted by something outside of the test suite (such as noisy neighbors in the VM, or even clock skew).

Nothing in the parsing of that fairly short file should give us that kind of performance, and the prior tests took much shorter time.

daniellansun commented 8 years ago

@jespersm : Unfortunately, parsing "GrailsWebDataBindingListener.groovy" really costs a lot of time. On my machine it costs about 36s...

I extracted the code snippet as follows, parsing which costs most of the time:

// costs about 30s
String[] codes = [
        className + '.' + propertyName + '.typeMismatch.error',
        className + '.' + propertyName + '.typeMismatch',
        classAsPropertyName + '.' + propertyName + '.typeMismatch.error',
        classAsPropertyName + '.' + propertyName + '.typeMismatch',
        bindingResult.resolveMessageCodes('typeMismatch', propertyName)
].flatten() as String[]
// costs about 1s
String[] codes = [
].flatten() as String[]
daniellansun commented 8 years ago

In order to improve the performance when parsing large numbers of files, I plan to implement a LRU cache, which will replace the default PredictionContextCache. The LRU cache will be based on Guava's CacheBuilder(https://github.com/google/guava/blob/master/guava/src/com/google/common/cache/CacheBuilder.java). Any thought about it? @blackdrag @jespersm

ps: Guava is developed by Google and licenced under APL2

blackdrag commented 8 years ago

the problem is the size of the guava library with 2+ MB and their compatibility issues with other guava versions. If you base it on their source it should be ok, since it is APL2

daniellansun commented 8 years ago

I see. Thanks :-)

sharwell commented 8 years ago

@danielsun1106 One of the areas of optimization in my fork of ANTLR 4 is the construction and storage of PredictionContext instances. This includes substantial work on both the time it takes to construct the instances as well as the memory required to store them.

daniellansun commented 8 years ago

@sharwell Sam, I found your optimized fork at https://github.com/sharwell/antlr4

Can I get the latest version(merged 4.5.3 codes from the antlr/antlr4) via "com.tunnelvisionlabs:antlr4" as usual? I will give it a try :-)

Finally, Could you tell whether the optimized fork is licensed under APL2?

ps: I tried to cache PredicationContext instances via LRU cache, no memory leak but still very slow...

Cheers, Daniel.Sun

daniellansun commented 8 years ago

http://mvnrepository.com/artifact/com.tunnelvisionlabs/antlr4/4.5.3

It is licensed under BSD, same with antlr/antlr4 :-)

daniellansun commented 8 years ago

@sharwell Sam, I find ParserATNSimulator does not support manage decisionToDFA and sharedContextCache by ourselves. I'm afraid they will keep growing and memory leak happen again. Could you confirm it for us?

https://github.com/sharwell/antlr4/blob/optimized/runtime/Java/src/org/antlr/v4/runtime/atn/ParserATNSimulator.java

sharwell commented 8 years ago

@danielsun1106 The lexer and parser each store a DFA. You can clear the DFA on either to release the memory used by it, but doing so means the next time you parse a file it will have to rebuild all required sections of the DFA it needs for parsing. Typically the lexer DFA remains very small relative to the parser DFA, so in practice I've only ever needed to clear the latter.

// Clear a lexer DFA:
lexer.getInterpreter().atn.clearDFA();

// Clear a parser DFA:
parser.getInterpreter().atn.clearDFA();

:warning: The clearDFA method is not thread safe. Make sure no threads are actively parsing at the time it is called.

daniellansun commented 8 years ago

@sharwell I see, thanks. How about the sharedContextCache? It is another cause of memory leak...

sharwell commented 8 years ago

@danielsun1106 I don't think the sharedContextCache field exists in my fork. The ATN.contextCache field is cleared along with the DFA in my clearDFA method.

:bulb: The memory characteristics of the two forks are dramatically different. Make sure to not reuse results from analyzing the reference release when looking for ways to improve the optimized release. That said, if you do find ways to improve things it would be a nice addition. :grinning:

daniellansun commented 8 years ago

That's great! I'll try later :-) ps: antlr4-gradle-plugin depends on org.antlr:antlr4:4.2.2 by default, so I have to update the plugin first(https://github.com/danielsun1106/antlr4-gradle-plugin).

class Antlr4Plugin implements Plugin<Project> {
    void apply(Project project) {
        project.configurations {
            antlr4
        }
        project.dependencies {
            antlr4 'org.antlr:antlr4:4.2.2' // should be modified as 'com.tunnelvisionlabs:antlr4:4.5.3'
        }

        project.task('antlr4', type:Antlr4Task)
    }
}
daniellansun commented 8 years ago

@sharwell We have to synchronize the accessing of clearDFA and parsing code because the DFA array is shared and clearDFA is not thread safe. The synchronization will impact the performance because parsing is time-consuming, if parsing does not complete, other clearDFA and parsing have to wait...

Because we have to clearDFA before parsing each time, how about making each parser has its own DFA array and context cache and initialize DFA array and context cache when creating the parser, which will help us remove the synronization and gain better performance.

// Groovy script will be accessed concurrently in the production environment. synchronized(GroovyParser.class) { atn.clearDFA(); startParsing(); // time-consuming }

The suggestion is based on the following content :-) "The clearDFA method is not thread safe. Make sure no threads are actively parsing at the time it is called." "in practice I've only ever needed to clear the latter."

sharwell commented 8 years ago

Because we have to clearDFA before parsing each time, how about making each parser has its own DFA array and context cache and initialize DFA array and context cache when creating the parser, which will help us remove the synronization and gain better performance.

The DFA cache is a concurrent data structure that is designed and intended to be used in concurrent parsing scenarios without synchronization. The fast path (the case where DFA states already exist for the current input) does not have any synchronization at all. Assigning separate DFA instances to different parsers is a substantial waste of computing resources (the DFA will be recomputed and the memory will be multiplied by the the number of concurrent parser instances).

Based on the evidence provided so far, my suggestion is do not call clearDFA at all (ever). The method will cripple the performance of your parser. And if you do want to clear it, you should use a cache eviction policy that supports full concurrency of the parser without synchronization on the fast path.

daniellansun commented 8 years ago

@sharwell I'll try not to clearDFA according to your suggestion and hope memory leak will not occur with the optimized antlr4(https://github.com/antlr/antlr4/issues/499) Thanks.

sharwell commented 8 years ago

@danielsun1106 I'm not sure about the reference release, but the optimized version only caches PredictionContext instances which actually appear in a DFAState (thus implying means the parser has seen actual inputs which required that state). Considering that cache hits and lookup speed are so vital for prediction performance that standard hashing algorithms were causing major problems (antlr/antlr4#246, and sorry about the lack of an explanation on that PR), the growth of the DFA and the PredictionContext cache are less of a memory leak and more an indication that some grammars simply require more memory than others when parsing.

daniellansun commented 8 years ago

@sharwell If I do not clearDFA, the jvm heap is used up and jvm hangs when executing 1400+ test cases(2271 test cases in total).

Then I have to clearDFA before parsing, completing all test cases costs about 14 minutes on my machine(Note antlr/antlr4 costs 11~12 minutes).

At last I try to use the two-stage parsing strategy, optimized antlr4 costs 11~12 minutes(almost same with antlr/antlr4).

jespersm commented 8 years ago

We need to solve both issues. Performance must be first priority, so that we can reduce the worst-case measurements we're seeing now. I assume that the improved prediction context is part of the solution.

However, for long-running instances such as application servers, an unbounded cache is not very good. If we can reset or trim this cache at (configurable) intervals, we can at least work around the issue.

sharwell commented 8 years ago

@danielsun1106 Is there a branch where I can check out and run those tests easily? Sometimes there are small non-functional changes I can make to the grammar or use site to make a big perf difference.

sharwell commented 8 years ago

@jespersm Interval-based clearing of the cache is certainly one approach. You can do it safely like this:

// Field to hold the current ATN to use for parsing
private ATN fooParserATN;

{
  // call clearDFA to initialize the ATN
  clearDFA();
}

public final ATN getFooParserATN() {
  return fooParserATN;
}

public final void clearDFA() {
  // Clear the DFA by creating a new ATN instance. When all parser instances
  // referencing the old ATN are garbage collected, the GC will also be able
  // to reclaim the old DFA.
  fooParserATN = new ATNDeserializer().deserialize(FooParser._serializedATN.toCharArray());
}

// construct a parser
FooParser fooParser = new FooParser(...);
fooParser.setInterpreter(new ParserATNSimulator(fooParser, getFooParserATN());

In the above approach, clearDFA() is thread-safe, and works by delaying the actual reclamation of memory until all currently running parse operations complete.

:warning: The reference release of ANTLR does not store the DFA as part of the ATN, so this approach would not work without modification.

daniellansun commented 8 years ago

@sharwell Sam, "interval-based clearing of the cache" seems what I have been looking for :-) I'll try to create a performance tuning branch in my repository later. Thanks for your help!

sharwell commented 8 years ago

@danielsun1106 Keep in mind that I don't need the branch clean, I just need it to work. If I can get it running on a reasonably sized test scenario I can typically make a big improvement in not much time. :smile:

jespersm commented 8 years ago

@sharwell To run the tests, you need to fetch https://github.com/jespersm/groovy and checkout the antlr4 branch, and run gradle -PuseAntlr4=true test. That executes a lot of parses.

daniellansun commented 8 years ago

@sharwell @jespersm I plan to create a new repository to focus on tuning antlr4 performance(no need to build Groovy, which is very time-consuming). The code using the optimized antlr4 is stashed on my local machine and will be committed to the new repository later.

daniellansun commented 8 years ago

@sharwell If possible, how about caching DFA and predication context in a LRU cache(its size can be fixed)? The LRU cache can base on Google's ConcurrentLinkedHashMap(https://github.com/ben-manes/concurrentlinkedhashmap/)

daniellansun commented 8 years ago

@sharwell The new repository is here: https://github.com/danielsun1106/groovy-antlr4-grammar-optimized, you can clone it and run test cases via 

./gradlew -PuseAntlr4=true -Dfile.encoding=UTF-8 :test --tests org.codehaus.groovy.parser.antlr4.MainTest

The test result report can be found at build/reports/tests/

If you want to run test cases again, executing gradlew clean to clean the project is strongly recommended. If you just want to generate code with antlr4, execute gradlew antlr4

ps: We create parser and start parsing at org.codehaus.groovy.parser.antlr4.ASTBuilder Currently the parser uses two-stage parsing strategy for better performance, but still very slow:

    public ModuleNode buildAST() {
        this.parser.getInterpreter().setPredictionMode(PredictionMode.SLL);
        this.parser.removeErrorListeners();
        this.parser.setErrorHandler(new BailErrorStrategy());

        try {
            this.startParsing(this.parser);
        } catch (RuntimeException e) {
            if (log.isLoggable(Level.FINE)) {
                log.fine(e.getMessage());
            }

            ((CommonTokenStream) this.parser.getInputStream()).reset();
            this.setupErrorListener(this.parser);
            this.parser.setErrorHandler(new DefaultErrorStrategy());
            this.parser.getInterpreter().setPredictionMode(PredictionMode.LL);

            this.startParsing(this.parser);
        }

        this.addClasses();

        return this.moduleNode;
    }
daniellansun commented 8 years ago

In order to improve the whole performance and maintainability, I am rewriting the parser, which is based on the Java grammar updated by @sharwell (https://github.com/antlr/grammars-v4/blob/master/java/Java.g4).

The following performance issue does not exist in the new parser( https://github.com/danielsun1106/groovy-parser/commit/9950cd6d46838548161d51d626240a4cbe537d6b )

// costs about 30s
String[] codes = [
        className + '.' + propertyName + '.typeMismatch.error',
        className + '.' + propertyName + '.typeMismatch',
        classAsPropertyName + '.' + propertyName + '.typeMismatch.error',
        classAsPropertyName + '.' + propertyName + '.typeMismatch',
        bindingResult.resolveMessageCodes('typeMismatch', propertyName)
].flatten() as String[]