[−][src]Crate fasteval

A fast algebraic expression evaluation library.

Built-in Functions and Constants

  * print(...strings and values...) -- Prints to stderr.  Very useful to 'probe' an expression.
                                       Evaluates to the last value.
                                       Example: `print("x is", x, "and y is", y)`
                                       Example: `x + print("y:",y) + z == x+y+z`

  * log(base=10, val) -- Logarithm with optional 'base' as first argument.
                         Example: `log(100) + log(e(),100)`

  * e()  -- Euler's number (2.718281828459045)
  * pi() -- π (3.141592653589793)

  * int(val)
  * ceil(val)
  * floor(val)
  * round(modulus=1, val) -- Round with optional 'modulus' as first argument.
                             Example: `round(1.23456) == 1  &&  round(0.001, 1.23456) == 1.235`

  * abs(val)
  * sign(val)

  * min(val, ...) -- Example: `min(1,-2,3,-4) == -4`
  * max(val, ...) -- Example: `max(1,-2,3,-4) == 3`

  * sin(radians)    * asin(val)
  * cos(radians)    * acos(val)
  * tan(radians)    * atan(val)
  * sinh(val)       * asinh(val)
  * cosh(val)       * acosh(val)
  * tanh(val)       * atanh(val)

Examples

Easy evaluation of constant expressions

The ez_eval() function performs the entire allocation-parse-eval process for you. It is a little bit inefficient because it always allocates a fresh Slab, but it is very simple to use:

fn main() -> Result<(), fasteval::Error> {
    let val = fasteval::ez_eval(
        "1+2*3/4^5%6 + log(100) + log(e(),100) + [3*(3-3)/3] + (2<3) && 1.23",    &mut fasteval::EmptyNamespace)?;
    //    |            |          |   |          |               |   |
    //    |            |          |   |          |               |   boolean logic with ternary support
    //    |            |          |   |          |               comparisons
    //    |            |          |   |          square-brackets act like parenthesis
    //    |            |          |   built-in constants: e(), pi()
    //    |            |          'log' can take an optional first 'base' argument, defaults to 10
    //    |            many built-in functions: print, int, ceil, floor, abs, sign, log, round, min, max, sin, asin, ...
    //    standard binary operators

    assert_eq!(val, 1.23);

    Ok(())
}

Simple variables

Several namespace types are supported, each designed for different situations. (See the various Namespace types here.) For simple cases, you can define variables with a BTreeMap:

use std::collections::BTreeMap;
fn main() -> Result<(), fasteval::Error> {
    let mut map : BTreeMap<String,f64> = BTreeMap::new();
    map.insert("x".to_string(), 1.0);
    map.insert("y".to_string(), 2.0);
    map.insert("z".to_string(), 3.0);

    let val = fasteval::ez_eval(r#"x + print("y:",y) + z"#,    &mut map)?;
    //                           |
    //                           prints "y: 2" to stderr and then evaluates to 2.0

    assert_eq!(val, 6.0);

    Ok(())
}

Advanced variables and custom functions

This time, instead of using a map, we will use a namespace with a callback function, which enables us to do advanced things, like define custom functions and array-like objects:

fn main() -> Result<(), fasteval::Error> {
    let mut ns = fasteval::CachedFlatNamespace::new(|name:&str, args:Vec<f64>| -> Option<f64> {
        let mydata : [f64; 3] = [11.1, 22.2, 33.3];
        match name {
            "x" => Some(3.0),
            "y" => Some(4.0),
            "sum" => Some(args.into_iter().fold(0.0, |s,f| s+f)),
            "data" => args.get(0).and_then(|f| mydata.get(*f as usize).copied()),
            _ => None,
        }
    });

    let val = fasteval::ez_eval("sum(x^2, y^2)^0.5 + data[0]",    &mut ns)?;
    //                     |   |               |
    //                     |   |               square-brackets act like parenthesis
    //                     |   variables are like custom functions with zero args
    //                     custom function

    assert_eq!(val, 16.1);

    Ok(())
}

Re-use the Slab to go faster

If we perform the parse and eval ourselves (without relying on the 'ez' interface), then we can re-use the Slab allocation for subsequent parsing and evaluations. This avoids a significant amount of slow memory operations:

use std::collections::BTreeMap;
use fasteval::Evaler;  // import this trait so we can call eval().
fn main() -> Result<(), fasteval::Error> {
    let mut slab = fasteval::Slab::new();

    let expr_ref = fasteval::parse("x + 1", &mut slab.ps)?.from(&slab.ps);

    // Let's evaluate the expression a couple times with different 'x' values:

    let mut map : BTreeMap<String,f64> = BTreeMap::new();
    map.insert("x".to_string(), 1.0);
    let val = expr_ref.eval(&slab, &mut map)?;
    assert_eq!(val, 2.0);

    map.insert("x".to_string(), 2.5);
    let val = expr_ref.eval(&slab, &mut map)?;
    assert_eq!(val, 3.5);

    // Now, let's re-use the Slab for a new expression.
    // (This is much cheaper than allocating a new Slab.)

    slab.clear();
    let expr_ref = fasteval::parse("x * 10", &mut slab.ps)?.from(&slab.ps);

    let val = expr_ref.eval(&slab, &mut map)?;
    assert_eq!(val, 25.0);

    Ok(())
}

Compile to go super fast!

If you plan to evaluate an expression just one or two times, then you should parse-eval as shown in previous examples. But if you expect to evaluate an expression three or more times, you can dramatically improve your performance by compiling. The compiled form is usually more than 10 times faster than the un-compiled form, and for constant expressions it is usually more than 200 times faster.

use std::collections::BTreeMap;
use fasteval::Compiler;  // import this trait so we can call compile().
use fasteval::Evaler;    // import this trait so we can call eval().
fn main() -> Result<(), fasteval::Error> {
    let mut slab = fasteval::Slab::new();
    let mut map = BTreeMap::new();

    let expr_str = "sin(deg/360 * 2*pi())";
    let compiled = fasteval::parse(expr_str, &mut slab.ps)?.from(&slab.ps).compile(&slab.ps, &mut slab.cs);
    for deg in 0..360 {
        map.insert("deg".to_string(), deg as f64);
        // When working with compiled constant expressions, you can use the
        // eval_compiled*!() macros to save a function call:
        let val = fasteval::eval_compiled!(compiled, &slab, &mut map);
        eprintln!("sin({}°) = {}", deg, val);
    }

    Ok(())
}

Unsafe Variables

If your variables must be as fast as possible and you are willing to be very careful, you can build with the unsafe-vars feature (cargo build --features unsafe-vars), which enables pointer-based variables. These unsafe variables perform 2x-4x faster than the compiled form above. This feature is not enabled by default because it slightly slows down other non-variable operations.

use fasteval::Compiler;  // import this trait so we can call compile().
use fasteval::Evaler;    // import this trait so we can call eval().
fn main() -> Result<(), fasteval::Error> {
    let mut slab = fasteval::Slab::new();
    let mut deg : f64 = 0.0;
    unsafe { slab.ps.add_unsafe_var("deg".to_string(), &deg); }  // Saves a pointer to 'deg'.

    let mut ns = fasteval::EmptyNamespace;  // We only define unsafe variables, not normal variables,
                                      // so EmptyNamespace is fine.

    let expr_str = "sin(deg/360 * 2*pi())";
    let compiled = fasteval::parse(expr_str, &mut slab.ps)?.from(&slab.ps).compile(&slab.ps, &mut slab.cs);
    for d in 0..360 {
        deg = d as f64;
        let val = fasteval::eval_compiled!(compiled, &slab, &mut ns);
        eprintln!("sin({}°) = {}", deg, val);
    }

    Ok(())
}

Performance Benchmarks

These benchmarks were performed on 2019-12-16.

Here are links to all the libraries/tools included in these benchmarks: * fasteval (this library) * caldyn * rsc * meval * calc * tinyexpr (Rust) * tinyexpr (C) * bc * python3

Summary & Analysis

Benchmark Descriptions

    * simple = `3 * 3 - 3 / 3`
      This is a simple test with primitive binary operators.
      Since the expression is quite simple, it does a good job of showing
      the intrinsic performance costs of a library.
      Results:
          * For compiled expressions, 'fasteval' is 5x as fast as the closest
            competitor (caldyn) because the eval_compiled!() macro is able to
            eliminate all function calls.
          * For interpreted expressions, 'fasteval' is 1.6x as fast as the
            tinyexpr C lib, and 2.3x as fast as the tinyexpr Rust lib.
            This is because 'al' eliminates redundant work and memory
            allocation during the parse phase.

    * power = `2 ^ 3 ^ 4`
              `2 ^ (3 ^ 4)` for 'tinyexpr' and 'rsc'
      This test shows the associativity of the exponent operator.
      Most libraries (including 'fasteval') use right-associativity,
      but some libraries (particularly tinyexpr and rsc) use
      left-associativity.
      This test is also interesting because it shows the precision of a
      library's number system.  'fasteval' just uses f64 and therefore truncates
      the result (2417851639229258300000000), while python, bc, and the
      tinyexpr C library produce a higher precision result
      (2417851639229258349412352).
      Results:
          Same as the 'simple' case.

    * variable = `x * 2`
      This is a simple test of variable support.
      Since the expression is quite simple, it shows the intrinsic
      performance costs of a library.
      Results:
          * The tinyexpr Rust library does not currently support variables.
          * For safe compiled evaluation, 'fasteval' is 3x as fast as the closest
            competitor (caldyn).
          * For safe interpretation, 'fasteval' is 2.4x as fast as the closest
            competitor (caldyn).
          * For unsafe operations, 'fasteval' performance is similar to the
            tinyexpr C library.

    * trig = `sin(x)`
      This is a test of variables, built-in function calls, and trigonometry.
      Results:
          * The tinyexpr Rust library does not currently support variables.
          * The 'calc' library does not support trigonometry.
          * For safe compiled evaluation, 'fasteval' is 1.9x as fast as the
            closest competitor (caldyn).
          * For safe interpretation, 'fasteval' is 1.6x as fast as the closest
            competitor (caldyn).
          * For unsafe operation, 'fasteval' performance is similar to the
            tinyexpr C library.

    * quadratic = `(-z + (z^2 - 4*x*y)^0.5) / (2*x)`
      This test demonstrates a more complex expression, involving several
      variables, some of which are accessed more than once.
      Results:
          * 

    * big = `((((87))) - 73) + (97 + (((15 / 55 * ((31)) + 35))) + (15 - (9)) - (39 / 26) / 20 / 91 + 27 / (33 * 26 + 28 - (7) / 10 + 66 * 6) + 60 / 35 - ((29) - (69) / 44 / (92)) / (89) + 2 + 87 / 47 * ((2)) * 83 / 98 * 42 / (((67)) * ((97))) / (34 / 89 + 77) - 29 + 70 * (20)) + ((((((92))) + 23 * (98) / (95) + (((99) * (41))) + (5 + 41) + 10) - (36) / (6 + 80 * 52 + (90))))`

Charts

Note that the following charts use logarithmic scales. Therefore, tiny visual differences actually represent very significant performance differences.

Performance of evaluation of a compiled expression: abc

Performance of one-time interpretation (parse and eval): abc

Performance of Unsafe Variables, compared to the tinyexpr C library (the only other library in our test set that supports this mode): abc

Methodology

I am benchmarking on an Asus G55V (a 2012 laptop with Intel(R) Core(TM) i7-3610QM CPU @ 2.30GHz).

I run

All numeric results can be found in fasteval/benches/bench.rs.

How is fasteval so fast?

A variety of techniques are used to improve performance:

  • Minimization of memory allocations/deallocations; I just pre-allocate a large slab during initialization.
  • Elimination of redundant work, especially when parsing.
  • Compilation: Constant Folding and Expression Simplification. Boosts performance up to 1000x.
  • Profile-driven application of inlining. Don't inline too much or too little.
  • Use of macros to eliminate call overhead for the most-frequently-used functions.
  • Don't panic.
  • Localize variables. Use "--emit asm" as a guide.

Re-exports

pub use self::error::Error;
pub use self::parser::parse;
pub use self::parser::Parser;
pub use self::parser::Expression;
pub use self::parser::ExpressionI;
pub use self::parser::Value;
pub use self::parser::ValueI;
pub use self::compiler::Compiler;
pub use self::compiler::Instruction;
pub use self::compiler::Instruction::IConst;
pub use self::compiler::InstructionI;
pub use self::evaler::Evaler;
pub use self::slab::Slab;
pub use self::evalns::EvalNamespace;
pub use self::evalns::Layered;
pub use self::evalns::EmptyNamespace;
pub use self::evalns::CachedFlatNamespace;
pub use self::evalns::CachedScopedNamespace;
pub use self::evalns::Bubble;
pub use self::ez::ez_eval;

Modules

compiler
error

This module contains fasteval's Error type: an enum that contains all errors that can be produced by the fasteval API.

evaler
evalns
ez
parser
slab

A Slab is a pre-allocated block of memory, used during the parse/compile/eval phases to reduce memory allocation/deallocation.

Macros

bool_to_f64
eval_compiled
eval_compiled_ref
f64_eq
f64_ne