Pull #16628: use SLL prediction mode for fast javadoc parsing to improve performance #16628

mahfouz72 · 2025-03-22T15:15:10Z

This is the fastest prediction mode, and provides correct results for many grammars

public enum PredictionMode {
	/**
	 * The SLL(*) prediction mode. This prediction mode ignores the current
	 * parser context when making predictions. This is the fastest prediction
	 * mode, and provides correct results for many grammars. This prediction
	 * mode is more powerful than the prediction mode provided by ANTLR 3, but
	 * may result in syntax errors for grammar and input combinations which are
	 * not SLL.
	 *
	 * <p>
	 * When using this prediction mode, the parser will either return a correct
	 * parse tree (i.e. the same parse tree that would be returned with the
	 * {@link #LL} prediction mode), or it will report a syntax error. If a
	 * syntax error is encountered when using the {@link #SLL} prediction mode,
	 * it may be due to either an actual syntax error in the input or indicate
	 * that the particular combination of grammar and input requires the more
	 * powerful {@link #LL} prediction abilities to complete successfully.</p>
	 *
	 * <p>
	 * This prediction mode does not provide any guarantees for prediction
	 * behavior for syntactically-incorrect inputs.</p>
	 */
	SLL,
        .....

Diff Regression config: https://gist.githubusercontent.com/mahfouz72/33967bf86e4a29cafa429771b0e95808/raw/f621465b3c7dd6e64ac603d396570bf92a1a69d6/check_patch.xml

mahfouz72 · 2025-03-22T15:45:39Z

Interesting!

===================== BENCHMARK SUMMARY ====================
Execution Time Baseline: 570.62 s
Average Execution Time: 474.83 s
============================================================
Execution Time Difference: 16.7800%
Difference exceeds the maximum allowed difference (16.7800%      > 10%)!

mahfouz72 · 2025-03-22T15:57:59Z

Since the Javadoc grammar contains many ambiguities and many nested rules, it may not be safe to rely on single lookahead parsing. However, if we can rewrite the grammar to reduce nesting and ambiguity, we could significantly improve parsing time by using SLL parsing

@nrmancuso @rnveach @romani
What do you think?

rnveach · 2025-03-22T17:26:19Z

This is a 16% deduction right? Maybe consider running the performance multiple times to confirm it is a stable deduction.

What are the downsides of this mode? I assume they didn't enable it by default for a reason.

Just curious if we also seen what this does on the Java side?

mahfouz72 · 2025-03-22T17:49:06Z

This is a 16% deduction right? Maybe consider running the performance multiple times to confirm it is a stable deduction.

Yes, 100 seconds deduction which is 16%. I restarted CI by pushing again to see if this reduction is stable.

What are the downsides of this mode? I assume they didn't enable it by default for a reason.

From Javadoc of this option:

If a syntax error is encountered when using the {@link #SLL} prediction mode, it may be due to either an actual syntax error in
the input or indicate that the particular combination of grammar and input requires the more powerful {@link #LL} prediction
abilities to complete successfully

This prediction mode does not provide any guarantees for prediction
behavior for syntactically-incorrect inputs.

As per my understanding SLL mode doesn't handle ambiguities well. If a grammar contains multiple possible parse paths for a given input, SLL mode will fail. and It doesn't backtrack, once it hits an ambiguity, it stops. As it works with a single lookahead and not taking the whole parser context into account

Just curious if we also seen what this does on the Java side?

I didn't try this may ne we should try it in another PR but I think that Java can be more complex than Javadoc which might make it require the full LL approach for correct parsing. @nrmancuso can confirm this

We can use SLL mode as the default parsing strategy, and if it encounters any issues or fails to parse, we can switch to LL mode.

mahfouz72 · 2025-03-22T17:54:11Z

Github, generate report

rnveach · 2025-03-22T18:10:34Z

If a syntax error is encountered ... indicate that the particular combination of grammar and input requires the more powerful {https://github.com/link #LL} prediction abilities to complete successfully

I believe we need regression without suppressing grammar failures on all our regression projects. We need to know if this change is now increasing grammar failures. Since I believe CI was passing, it seems its not really big concern.

github-actions · 2025-03-22T19:05:31Z

https://checkstyle-diff-reports.s3.us-east-2.amazonaws.com/7475a27_2025185723/reports/diff/index.html

mahfouz72 · 2025-03-22T21:09:52Z

Github, generate report

mahfouz72 · 2025-03-22T22:11:48Z

Github, generate report

romani · 2025-03-22T23:31:59Z

if you think this config is frequently to use you can put it as folder to https://github.com/checkstyle/test-configs and re-use at any time.

github-actions · 2025-03-22T23:36:36Z

https://checkstyle-diff-reports.s3.us-east-2.amazonaws.com/111fddc_2025232331/reports/diff/index.html

mahfouz72 · 2025-03-23T03:33:37Z

Time decreased by 16% so I reduced the baseline.
The report (without suppressing grammar failures) shows no difference, so parsing is unaffected.
I think it is ok to suppress this surviving mutation as we just use a setter and can't think of a test case that specific to this line

please see if this is good and update is approved I can do similar approach for java parsing

romani · 2025-03-23T14:48:17Z

We are going to zero mutation phase, some most weird should be covered by pure unit testing, if no reasonable coverage can be provided.

nrmancuso

Very good, I tried this when I implemented the Java grammar and it did not work at the time. Maybe some improvements have been made since then, we should at least try it out again.

I’m don’t see any point in holding up this PR over a pitest suppression.

romani

Items

romani · 2025-03-25T01:28:54Z

src/main/java/com/puppycrawl/tools/checkstyle/JavadocDetailNodeParser.java

@@ -112,6 +113,7 @@ public ParseStatus parseJavadocAsDetailNode(DetailAST javadocCommentAst) {

        try {
            final JavadocParser javadocParser = createJavadocParser(javadocComment, errorListener);
+            javadocParser.getInterpreter().setPredictionMode(PredictionMode.SLL);


Please move it inside create..... method.

Let try to update pitest to avoid call interpreter
Like

checkstyle/pom.xml

Line 3100 in f123b09

<avoidCallsTo>org.apache.commons.logging</avoidCallsTo>

We need to find way avoid pitest suppression.

Last resort is approach like

checkstyle/pom.xml

Line 4453 in f123b09

<param>lazyLoad</param>

done with avoidCallsTo and xwiki is unrelated

romani

ok to merge,
thanks a lot

mahfouz72 added a commit to mahfouz72/checkstyle that referenced this pull request Mar 22, 2025

Pull checkstyle#16628: Try SLL prediction mode for fast javadoc parsing

7475a27

mahfouz72 force-pushed the try-sll branch from af9b47b to 7475a27 Compare March 22, 2025 17:33

mahfouz72 added a commit to mahfouz72/checkstyle that referenced this pull request Mar 22, 2025

Pull checkstyle#16628: Try SLL prediction mode for fast javadoc parsing

111fddc

mahfouz72 force-pushed the try-sll branch from 7475a27 to 111fddc Compare March 22, 2025 21:09

mahfouz72 added a commit to mahfouz72/checkstyle that referenced this pull request Mar 23, 2025

Pull checkstyle#16628: Try SLL prediction mode for fast javadoc parsing

5fe23e1

mahfouz72 force-pushed the try-sll branch from 111fddc to 5fe23e1 Compare March 23, 2025 00:19

mahfouz72 added a commit to mahfouz72/checkstyle that referenced this pull request Mar 23, 2025

Pull checkstyle#16628: Try SLL prediction mode for fast javadoc parsing

f123b09

mahfouz72 force-pushed the try-sll branch from 5fe23e1 to f123b09 Compare March 23, 2025 02:42

nrmancuso approved these changes Mar 24, 2025

View reviewed changes

rnveach approved these changes Mar 24, 2025

View reviewed changes

nrmancuso assigned romani Mar 24, 2025

romani requested changes Mar 25, 2025

View reviewed changes

mahfouz72 added a commit to mahfouz72/checkstyle that referenced this pull request Mar 25, 2025

Pull checkstyle#16628: Try SLL prediction mode for fast javadoc parsing

26a0d2e

mahfouz72 force-pushed the try-sll branch from f123b09 to 26a0d2e Compare March 25, 2025 02:41

mahfouz72 added a commit to mahfouz72/checkstyle that referenced this pull request Mar 25, 2025

Pull checkstyle#16628: Try SLL prediction mode for fast javadoc parsing

aee57dc

mahfouz72 force-pushed the try-sll branch from 26a0d2e to aee57dc Compare March 25, 2025 03:35

romani added the bug label Mar 25, 2025

Pull checkstyle#16628: Try SLL prediction mode for fast javadoc parsing

9b3d973

romani force-pushed the try-sll branch from aee57dc to 9b3d973 Compare March 25, 2025 12:24

romani approved these changes Mar 25, 2025

View reviewed changes

romani merged commit 1a88f34 into checkstyle:master Mar 25, 2025
50 of 101 checks passed

romani changed the title ~~Pull #16628: Try SLL prediction mode for fast javadoc parsing~~ Pull #16628: use SLL prediction mode for fast javadoc parsing to improve performance Mar 25, 2025

github-actions bot added this to the 10.22.0 milestone Mar 25, 2025

Abdelrhmansersawy pushed a commit to Abdelrhmansersawy/checkstyle that referenced this pull request Mar 28, 2025

Pull checkstyle#16628: Try SLL prediction mode for fast javadoc parsing

03d3014

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Pull #16628: use SLL prediction mode for fast javadoc parsing to improve performance #16628

Pull #16628: use SLL prediction mode for fast javadoc parsing to improve performance #16628

mahfouz72 commented Mar 22, 2025 •

edited

Loading

mahfouz72 commented Mar 22, 2025

mahfouz72 commented Mar 22, 2025

rnveach commented Mar 22, 2025 •

edited

Loading

mahfouz72 commented Mar 22, 2025

mahfouz72 commented Mar 22, 2025

rnveach commented Mar 22, 2025 •

edited

Loading

github-actions bot commented Mar 22, 2025

mahfouz72 commented Mar 22, 2025

mahfouz72 commented Mar 22, 2025

romani commented Mar 22, 2025

github-actions bot commented Mar 22, 2025

mahfouz72 commented Mar 23, 2025

romani commented Mar 23, 2025

nrmancuso left a comment •

edited

Loading

romani left a comment

romani Mar 25, 2025

romani Mar 25, 2025

mahfouz72 Mar 25, 2025

romani left a comment

Pull #16628: use SLL prediction mode for fast javadoc parsing to improve performance #16628

Pull #16628: use SLL prediction mode for fast javadoc parsing to improve performance #16628

Conversation

mahfouz72 commented Mar 22, 2025 • edited Loading

mahfouz72 commented Mar 22, 2025

mahfouz72 commented Mar 22, 2025

rnveach commented Mar 22, 2025 • edited Loading

mahfouz72 commented Mar 22, 2025

mahfouz72 commented Mar 22, 2025

rnveach commented Mar 22, 2025 • edited Loading

github-actions bot commented Mar 22, 2025

mahfouz72 commented Mar 22, 2025

mahfouz72 commented Mar 22, 2025

romani commented Mar 22, 2025

github-actions bot commented Mar 22, 2025

mahfouz72 commented Mar 23, 2025

romani commented Mar 23, 2025

nrmancuso left a comment • edited Loading

Choose a reason for hiding this comment

romani left a comment

Choose a reason for hiding this comment

romani Mar 25, 2025

Choose a reason for hiding this comment

romani Mar 25, 2025

Choose a reason for hiding this comment

mahfouz72 Mar 25, 2025

Choose a reason for hiding this comment

romani left a comment

Choose a reason for hiding this comment

mahfouz72 commented Mar 22, 2025 •

edited

Loading

rnveach commented Mar 22, 2025 •

edited

Loading

rnveach commented Mar 22, 2025 •

edited

Loading

nrmancuso left a comment •

edited

Loading