[C++] possible optimization of ParserATNSimulator

[garzon]

I have found that antlr4::atn::ATNConfigSet::add takes 25.76% of whole CPU time in my parsing-intensive program. And I am wondering if I can modify ParserATNSimulator.cpp(line 726) to the following, which
significantly reduces the time of antlr4::atn::ATNConfigSet::add to 8.76%. In this way the time-consuming memory allocation and hash calculating and tracking of config in ATNConfigSet::add could be prevented.

If there is no problem with it, I could make a PR later.

size_t ParserATNSimulator::getSynValidOrSemInvalidAltThatFinishedDecisionEntryRule(ATNConfigSet *configs,
  ParserRuleContext *outerContext)
{
  std::pair<size_t, size_t> sets = splitAccordingToSemanticValidity(configs, outerContext);
  //std::unique_ptr<ATNConfigSet> semValidConfigs(sets.first);
  //std::unique_ptr<ATNConfigSet> semInvalidConfigs(sets.second);
  size_t alt = sets.first;//getAltThatFinishedDecisionEntryRule(semValidConfigs.get());
  if (alt != ATN::INVALID_ALT_NUMBER) { // semantically/syntactically viable path exists
    return alt;
  }
  // Is there a syntactically valid path with a failed pred?
  /*if (!semInvalidConfigs->configs.empty()) {
    alt = getAltThatFinishedDecisionEntryRule(semInvalidConfigs.get());
    if (alt != ATN::INVALID_ALT_NUMBER) { // syntactically viable path exists
      return alt;
    }
  }
  return ATN::INVALID_ALT_NUMBER;*/
  return sets.second;
}

/*size_t ParserATNSimulator::getAltThatFinishedDecisionEntryRule(ATNConfigSet *configs) {
  misc::IntervalSet alts;
  for (auto &c : configs->configs) {
    if (c->getOuterContextDepth() > 0 || (is<RuleStopState *>(c->state) && c->context->hasEmptyPath())) {
      alts.add(c->alt);
    }
  }
  if (alts.size() == 0) {
    return ATN::INVALID_ALT_NUMBER;
  }
  return alts.getMinElement();
}*/

inline static void add_alts(misc::IntervalSet &alts, const Ref<ATNConfig> &c) {
	if (c->getOuterContextDepth() > 0 || (is<RuleStopState *>(c->state) && c->context->hasEmptyPath())) {
      alts.add(c->alt);
    }
}

std::pair<size_t, size_t> ParserATNSimulator::splitAccordingToSemanticValidity(ATNConfigSet *configs,
  ParserRuleContext *outerContext) {

  // mem-check: both pointers must be freed by the caller.
  //ATNConfigSet *succeeded(new ATNConfigSet(configs->fullCtx));
  //ATNConfigSet *failed(new ATNConfigSet(configs->fullCtx));
  
  misc::IntervalSet succ_alts, fail_alts;
  
  for (Ref<ATNConfig> &c : configs->configs) {
    if (c->semanticContext != SemanticContext::NONE) {
      bool predicateEvaluationResult = evalSemanticContext(c->semanticContext, outerContext, c->alt, configs->fullCtx);
      if (predicateEvaluationResult) {
        //succeeded->add(c);
		add_alts(succ_alts, c);
      } else {
        //failed->add(c);
		add_alts(fail_alts, c);
      }
    } else {
      //succeeded->add(c);
	  add_alts(succ_alts, c);
    }
  }
  
  size_t succeeded = antlr4::atn::ATN::INVALID_ALT_NUMBER, failed = antlr4::atn::ATN::INVALID_ALT_NUMBER;
  if (succ_alts.size()) succeeded = succ_alts.getMinElement();
  if (fail_alts.size()) failed = fail_alts.getMinElement();
  return { succeeded, failed };
}

[mike-lischke]

You should definitely make a PR instead. Otherwise reviewing the code is too difficult.

[garzon]

You should definitely make a PR instead. Otherwise reviewing the code is too difficult.

Yeah, you could check it out now #2471

[mike-lischke]

@garzon I've compiled your patch in and to my surprise that code isn't even called once in my parser (MySQL, which is fairly complex and large). So I cannot validate the speed improvements you claimed.

I see you significantly lowered the number of copies that are done for Ref<ATNConfigSet> instances, which certainly has a positive effect on performance, but I don't know how to prove it.

All ANTLR4 tests passed in your PR, but comparing the entire build times (which include all unit test execution times) with previous builds don't show improvements, e.g.

Your optimization:
Compiler: clang JDK: openjdk7 Java TARGET=cpp CXX=g++-5 GROUP=LEXER 11 min 33 sec
Compiler: clang JDK: openjdk7 Java TARGET=cpp CXX=g++-5 GROUP=PARSER 20 min 17 sec
Compiler: clang JDK: openjdk7 Java TARGET=cpp CXX=g++-5 GROUP=RECURSION 15 min 44 sec

The last successful build from my ANTLR4 fork
Compiler: clang JDK: openjdk7 Java TARGET=cpp CXX=g++-5 GROUP=LEXER 11 min 47 sec
Compiler: clang JDK: openjdk7 Java TARGET=cpp CXX=g++-5 GROUP=PARSER 17 min 48 sec
Compiler: clang JDK: openjdk7 Java TARGET=cpp CXX=g++-5 GROUP=RECURSION 15 min 51 sec

That's 2% for the LEXER part (which actually does not use the ParserATNSimulator), while the PARSER group even performed 23% slower. That shouldn't be overvalued, since there can be other influences for the time results, but it's an indication. Can you provide a prove where we can see the improvement?

What's also interesting is that getSynValidOrSemInvalidAltThatFinishedDecisionEntryRule is only called in error cases (no reach set in execATNWithFullContext and no existing target state in execATN) which means your patch only improves the (rarely seen) error cases, not normal parsing.

[garzon]

Forgot to mention that, in fact in my use case MOST of the text being parsed contains syntax errors(or, not being parsed as the language it actually is) so it is really a big deal, at least in my case. I have such millions data and parsing them as MySQL and other programming languages (to detect the actual language of the text), and it shows 15%+ improvements.

It seems that the times of the CI tests are quite unstable if you check out the times in other code-irrelevant PRs. And, you can find the actual time of execution(without initializing the CI test environment) by clicking in to check the "Job Log" and find the times are almost the same in current and patched version, which makes sense if the text being parsed are all valid, according to your description above.

So I think a formal benchmarking is necessary in both situations(text with and without syntax errors)

[mike-lischke]

OK, I see. However, we need a prove that the change doesn't break functionality. Best would be you add a test case to the test suite dedicated to this problem. Unfortunately, adding a test case and running the test suite is a pretty lengthy process (even though @parrt improved it significantly). Writing the test will probably take significantly more time than what was required to write the patch.

[sharwell]

📝 This is not really a change that can be verified by testing. It will require a manual review to verify that the new algorithm is either equivalent to the original or acceptably correct.

[mike-lischke]

OK, then this issue can be closed. Everything else is handled in the PR.

[parrt]

Closing and jumping over to PR.