Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

C++ Mathematical Expression Parser Benchmark

NotificationsYou must be signed in to change notification settings

ArashPartow/math-parser-benchmark-project

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

This is a benchmark suite for different implementations of open source mathexpression parsers and evaluators written in C++. Currently the followingexpression parsers are part of this benchmark:

#LibraryAuthorLicenseNumeric Type
00ATMSPHeinz van SaanenGPL v3double, MPFR
01ExprTkArash PartowMITdouble, float, MPFR
02FParserJuha Nieminen & Joel YliluomaLGPLdouble
03LeptonPeter EastmanMITdouble
04MathExprYann OllivierCopyright Notice 1997-2000double
05METLTill HeinzelApachedouble
06MTParserMathieu JacquesCPOLdouble
07muParserIngo BergMITdouble, float
08muParserXIngo BergMITdouble, float
09TinyExprLewis Van WinkleZlibdouble

Note: The terms double, float etc found in the table above are defined as follows:

Note: This archive is not meant as a primary source for any of the librarieslisted above as it may contain outdated versions of said libraries.

Objectives

All the parsers in this benchmark suite are in one way or another POEM(Parse Once Evaluate Many times) in nature. As such the primaryobjectives for this benchmark are to ascertain the followingproperties for each of the denoted parsers in following order ofpriority:

  1. Correctness and precision of results relative to thefloating point type used
  2. Robustness of the parser given various mathematical expressions
  3. Evaluation efficiency of 'compiled/parsed' expressions

The Setup

The benchmark takes two parameters:

  1. Number of iterations (N)
  2. Benchmark Test File

The mathematical expression benchmark files are as follows:

  1. bench_expr.txt
  2. bench_expr_all.txt
  3. bench_expr_all_permutations.txt
  4. bench_expr_complete.txt
  5. bench_expr_extensive.txt
  6. bench_expr_precedence.txt
  7. bench_expr_random_with_functions.txt
  8. bench_expr_random_without_functions.txt
  9. bench_expr_weird.txt

The following is a short sampling of expressions taken from thebench_expr.txtexpression suite:

  • a+1.1
  • a*2.2
  • 2.2*a+1.1
  • (2.2*a+1.1)*3.3
  • sin(2.2 * a) + cos(pi / b)
  • 1 - sin(2.2 * a) + cos(pi / b)
  • sqrt(1 - sin(2.2 * a) + cos(pi / b) / 3.3)
  • (a^2 / sin(2 * pi / b)) -a / 2.2
  • 1-(a/b*0.5)
  • e^log(7*a)
  • 10^log(3+b)
  • (cos(2.41)/b)
  • -(sin(pi+a)+1)
  • a-(e^(log(7+b)))

As an example, the following execution will use the"bench_expr_all.txt"set of expressions, executing each expression 100000 times:

ParserBench.exe 100000 bench_expr_all.txt

The Rounds

For every expression in the benchmark file, every parser evaluates the givenexpression N times, this is known as a round. The total time each parser takesto evaluate the expression N times is recorded. Ranking of the parsers forthe round is done from the fastest to the slowest. The following is an examplesummary for the expression '(a^2/sin(2*pi/b))-a/2':

Expression 64 of 70: "(a^2/sin(2*pi/b))-a/2"; Progress: #############[01] ExprTkFloat          ( 34.144 ns, 3.744852304458618164, -15768714.994192123413085938)[02] ExprTk               ( 39.963 ns, 3.744853294789905362, -15768714.840563148260116577)[03] muparserSSE          ( 40.698 ns, 3.744852304458618164, -15768715.739250183105468750)[04] muparser 2.2.4       ( 47.358 ns, 3.744853294789905362, -15768714.840563148260116577)[05] muparser 2.2.4 (omp) ( 53.252 ns, 3.744853294789905362, -15768714.840563148260116577)[06] FParser 4.5          ( 60.614 ns, 3.744853294789905362, -15768714.840563148260116577)[07] atmsp 1.0.4          ( 64.374 ns, 3.744853294789905362, -15768714.840563148260116577)[08] METL                 ( 79.018 ns, 3.744853294789905362, -15768714.840563148260116577)[09] MTParser             ( 80.352 ns, 3.744853294789905362, -15768714.840563148260116577)[10] MathExpr             (114.392 ns, 3.744853294789905362, -15768714.840563148260116577)[11] TinyExpr             (121.184 ns, 3.744853294789905362, -15768714.840563148260116577)[12] Lepton               (297.673 ns, 3.744853294789905362, -15768714.840563148260116577)[13] muparserx            (498.809 ns, 3.744853294789905362, -15768714.840563148260116577)

Parsers that can't parse the given expression or produce a resultdifferentto the expected result (based on a normalized epsilon approach) are disqualifiedfor the round and do not participate in point accumulation. The following is anexample where a few of the parsers failed to either parse or evaluate the givenexpression of '+1.1+a^b' correctly:

Expression 63 of 96: "+a^+b+1.1"; Progress: #############[01] ExprTkFloat          ( 44.579 ns, 2.333286285400390625, 14534422.159194946289062500)[02] muparserSSE          ( 44.846 ns, 2.333286285400390625, 14534422.159194946289062500)[03] ExprTk               ( 47.162 ns, 2.333286300554663129, 14534421.395495440810918808)[04] atmsp 1.0.4          ( 47.428 ns, 2.333286300554663129, 14534421.395495440810918808)[05] METL                 ( 48.233 ns, 2.333286300554663129, 14534421.395495440810918808)[06] TinyExpr             ( 53.620 ns, 2.333286300554663129, 14534421.395495440810918808)[07] MTParser             ( 61.204 ns, 2.333286300554663129, 14534421.395495440810918808)[08] muparser 2.2.4       ( 66.387 ns, 2.333286300554663129, 14534421.395495440810918808)[09] muparser 2.2.4 (omp) ( 71.118 ns, 2.333286300554663129, 14534421.395495440810918808)[10] muparserx            (236.111 ns, 2.333286300554663129, 14534421.395495440810918808)DNQ List[01] FParser 4.5          (Syntax error)[02] MathExpr             (parsing error)[03] Lepton               (Parse error in expression "+a^+b+1.1 ": unexpected token: +)**** ERROR ****   Excessive number of evaluation failures!  [3]

The meanings of each of the columns are as follows:

  1. Rank
  2. Parser
  3. Average time(in nano-seconds) to evaluate the expression once, taken over N-times
  4. Result of evaluating the expression
  5. Sum of N-evaluations of the given expression

The Final Summary

Once all the expressions have been completed, a summary is provided,that includes information relating to the build parameters of thebenchmark binary, the architecture which the benchmark was run upon,a final ranking of the parsers, and a listing of expressions per parserthat were deemed as having been disqualified during the benchmark.

The following is an example summary generated at the completion of the benchmark:

Benchmark settings:  - Expressions File is "bench_expr.txt"  - Reference parser is ExprTk  - Iterations per expression: 5000000  - Number of expressions: 74  - Number of excessive failures: 2  - Release build  - Compiled with MSVC Version 1913  - IEEE 754 (IEC 559) is Available  - 32-bit build  - CPU Name      : Intel(R) Xeon(R) CPU E5-2687W 0 @ 3.10GHz  - Num. cores    : 8  - Num. logical  : 16  - Total logical : 16  - L1 D cache    : 32 KB  - L1 I cache    : 32 KB  - L2 cache      : 256 KB  - L3 cache      : 20480 KB  - L1D assoc.    : 8-way  - L2 assoc.     : 8-way  - L3 assoc.     : 20-way  - L1D line size : 64 bytes  - L2 line size  : 64 bytes  - L3 line size  : 64 bytes  - CPU clock     : 3092 MHz  - Features      : acpi aes apic avx clflush cmov constant_tsc cx16 cx8 dca                    de ds_cpl dts dts64 est fpu fxsr ht lahf_lm lm mca mce                    mmx monitor msr mtrr osxsave pae pat pbe pclmul pdcm pge                    pni popcnt pse pse36 rdtscp sep smx ss sse sse2 sse4_1                    sse4_2 ssse3 tm tm2 tsc vme vmx x2apic xd xsave xtprScores:  #     Parser                  Type            Points   Score   Failures  -----------------------------------------------------------------------  00    ExprTk                  double          901      100     0  01    ExprTkFloat             float           740       82     9  02    muparserSSE             float           726       93     9  03    METL                    double          686       52     0  04    FParser 4.5             double          584       43     0  05    atmsp 1.0.4             double          530       38     2  06    muparser 2.2.4          double          517       37     0  07    muparser 2.2.4 (omp)    double          444       35     0  08    MTParser                double          381       34     0  09    MathExpr                double          360       29     2  10    TinyExpr                double          354       31     2  11    Lepton                  double          134        8     2  12    muparserx               double           86        5     0

The Results

The summaries of runs of the benchmark suite upon various architectures can be found here:Results

Example Results

The following is a chart depicting the results as executions persecond obtained by running the'bench_expr_random_without_functions.txt'benchmark, using the double type, 5000000 iterations per expression onan Intel Xeon E5-2687W 3GHz. The horizontal measure on the chart isthe length of the expression in bytes.

ScreenShot

Note: The parsersmuParserSSE andExprTKFloat were excludeddue to their use of the float type, and theLepton andmuParserXparsers were excluded due to the fact that their results wereconsistently 2-3 orders of magnitude slower than all the others.

Note: The command executed to generate the above results is as follows:

ParserBenchmark.exe 5000000 bench_expr_random_without_functions.txt write_table

Native Mode

The benchmark has a special mode called"Native". In this mode apredefined set of expressions are employed, and benchmarked againstboth native equivalent implementations and the standardparsers/evaluators.

The command to execute the benchmark in native mode is as follows:

ParserBenchmark.exe 1000000 native

Customised Tests

Creating a customised test is very simple. All that is required is tocreate a utf-8 encoded text file, and pass it as the 2nd parameter tothe benchmark executable.

Each line can only have one expression, comprised of the following:

  • Operators: +, -, *, /, ^
  • Variables: a, b, c, x, y, z, w
  • Constants: e and pi
  • Functions: sin, cos, tan, abs, exp, sqrt, log, pow
  • Parentheses: Round '(' and ')'

Furthermore blank lines or lines beginning with a#-symbol will be ignored (aka comments or white-space).

The following is a simple example of a custom test:

---- snip ----# My first expression:(x + 1) / 2 * b# Pythagorasa^2 + b^2# A constant expression1 + (2 * 3) / 7# Definition of tan in terms of sine and cosinesin(x) / cos(x)---- snip ----

New Parsers

The addition of new or unlisted C++ mathematical expression parsers is always welcome.If you know of a parser and would like it included in the suite feel free to make arequest. Additionally if the associated benchmark implementation(eg: src/BenchXYZW.cpp)could be made available as part of the request that would very helpful.

About

C++ Mathematical Expression Parser Benchmark

Topics

Resources

Stars

Watchers

Forks

Contributors3

  •  
  •  
  •  
[8]ページ先頭
©2009-2025 Movatter.jp