Speed improvement ? when parsing more doubles than integers

[JaredDavis22]

Hi -

Thanks again for writing this library. It is great.

I profiled a run which has about 350K evaluates. The entire run was about 5.5 seconds. There was 0.5 seconds of time spent filling the exception stack. I traced it back to class Literals where parseDecimal was calling parseInteger when the string to parse contained a decimal point. This would throw an exception which was swallowed.

If the formula only contains integers this change will increase the time a little bit for the test for the decimal point.

JaredDavis22@4568f05

[JaredDavis22]

I also tried a probably unsafe Operator finder change. The combination of reducing the number of operators and the hash map method to find operators dropped my test run down to 3.5 seconds ish.

List<Operator> ops = Operators.standardList();
            ops.removeAll(Arrays.asList( Operators.DOT,
                    Operators.TRANSPOSE,
                    Operators.DOT_TRANSPOSE,
                    Operators.DOT_POW,
                    Operators.DOT_MUL,
                    Operators.DOT_DIV,
                    Operators.DOT_RIGHT_DIV,
                    Operators.LEFT_SHIFT,
                    Operators.RIGHT_SHIFT,
                    Operators.UNSIGNED_RIGHT_SHIFT,
                    Operators.INSTANCEOF,
                    Operators.BITWISE_AND,
                    Operators.BITWISE_OR,
                    Operators.DOT_POW_ASSIGN,
                    Operators.DOT_DIV_ASSIGN,
                    Operators.DOT_RIGHT_DIV_ASSIGN,
                    Operators.LEFT_SHIFT_ASSIGN,
                    Operators.RIGHT_SHIFT_ASSIGN,
                    Operators.UNSIGNED_RIGHT_SHIFT_ASSIGN));

and the very much a POC WIP commit:

JaredDavis22@21f7ae2

[JaredDavis22]

still a WIP.

Try #3 on matching an operator. Thoughts? Method buildOperatorNode is in the wrong class. It should move to ExpressionParse since it is tied to the operators list.

https://github.com/JaredDavis22/parsingtonFork/blob/throwvsnullreturn/src/main/java/org/scijava/parsington/ParsingNode.java

https://github.com/JaredDavis22/parsingtonFork/blob/db125b89daf342616391a7dea07d39e390416b93/src/main/java/org/scijava/parsington/ParseOperation.java#L46-L60

https://github.com/JaredDavis22/parsingtonFork/blob/db125b89daf342616391a7dea07d39e390416b93/src/main/java/org/scijava/parsington/ParseOperation.java#L260-L275

[JaredDavis22]

I moved all the ParsingNode etc changes outside of parsington for now.

The dot change was about a .55 second impact. The ParsingNode approach was about .6 second impact. I can do a pull request on that change (refactored from the test/wip stuff) if you want to incorporate that change into parsington.

The placement of initialization code in ParseOperation was a noob mistake on my part.

My test case is 7556 groups of formulae. Just about 400K lines of formulae with about 53K being optimized out prior to running evaluate(). Down to about 2.8 seconds ish.

[JaredDavis22]

Summary so far:

https://github.com/JaredDavis22/parsingtonFork/tree/matcherUsingThreadLocalguess

Includes all of the Open PRs plus a change to Literals to allow for re-use of Matcher instance.

The changes are ugly in spots. The changes I made to pass references from ExpressionParser to ParseOperation feel wrong as is.

Ran POC code and data through a JMH benchmark app created with jmh-java-benchmark-archetype.

test 1: 3.2.0 parsington + POC
test 2: matcherUsingThreadLocalguess branch + POC

About a 51% improvement in throughput.

[ctrueden]

@JaredDavis22 How can I run the JMH benchmark on my local machine? Is it pushed anywhere? Would it make sense to add such a benchmark to the Parsington codebase? It would make it easier to quantify future performance-related PRs.

[JaredDavis22]

How can I run the JMH benchmark on my local machine?

I didn't see a simple way to benchmark across branches.

I just created a project using jmh-java-benchmark-archetype. It was simply running jar 1 vs jar 2. jar 1 was using version x of parsington and jar2 was using a different version of parsington.

The benchmark read a 350mb ish text file which was sent to the evaluator. The output was summed and compared against a known value.

Below is the jmh benchmark code. The pom was not altered much either.

import com.davisprogramming.xxxx.formula.engine.MainB;
import org.openjdk.jmh.annotations.Benchmark;

import java.util.concurrent.ExecutionException;

public class MyBenchmark {

    @Benchmark
    public void testMethod() throws ExecutionException, InterruptedException {
        MainB.main(null);
    }

}

[JaredDavis22]

I'm testing a change that replaces the regular expressions with custom methods. It adds more lines of code, but is about 10-15% faster so far.

The flow has these steps:

1. one method identifies the potential type of literal (Hex, Binary, or Decimal)
2. extract details from string (3 methods)
3. process extracted details to Number (4 methods)

The separate Octal parser was replaced by post processing the results of the decimal extractor.

Literals.parseString now takes the most parsing time for my test case.

eg Here is the Binary extractor WIP. It can be optimized further.

    /**
     * Parses a binary literal (e.g., {@code 0b010101000011}).
     *
     * @param s The string from which the numeric literal should be parsed.
     * @param start The index of the string to start the parsing after the sign and 0[Bb] prefix.
     * @param end The index of the last char to parse.
     * @param results contains the parsing details calculated in this method.
     * @return true if a potential binary literal is found, false otherwise

     * based on Regular Expression (([-+]?)0[Bb]([01]+)([Ll]?)).*
     * group 1 = entire matching string. NB: re has .* postfix but this method does not include .* in this group.
     * group 2 [-+]?  This is processed by the caller and placed into ParseNumberResults ndxSign.
     * group none 0[Bb] must exist. This is processed by the caller.
     * group 3 [01]+
     * group 4 [lL]?
     */

    private static boolean extractBinaryNumber(String s, int start, int end, ParseNumberResults results) {
        char c;
        results.setSignGroup(2);

        int group = 3;
        results.beginGroup[group] = start;

        bigWhile:
        while (start <= end) {
            if (start == end) {
                results.endGroup[group] = start;
                break;
            }
            c = s.charAt(start);
            switch (group) {
                case 3: // [01]+
                    if (isBinaryDigit(c)) {
                        start++;
                    } else {
                        results.endGroup[group] = start;
                        group = 4;
                    }
                    break;
                case 4: // [Ll]?
                    if (isL(c)) {
                        results.beginGroup[group] = start;
                        results.endGroup[group] = ++start;
                    }
                    // ok - we are done
                    break bigWhile;
            } // switch group
        } // while bigWhile
        results.endGroup[1] = start;
        // need at least 1 digit in group 3
        if (results.endGroup[3] - results.beginGroup[3] == 0)
            results.numberType = NumberType.NOT_A_NUMBER;
        return (results.numberType == NumberType.BINARY);
    }