Eval

Eval is an expression evaluation engine purely written in golang with only go stand libraries. It takes a string expression, compiles the expression into a highly optimized structure, then efficiently evaluates the result of the expression.

Highlights

• Fast, probably the fastest expression evaluation engine in the go world (benchmark).
• Easy to use, support for registering custom operators, variables, constants and writing comments in expressions.
• Useful tools:
  • Debug Panel: a Terminal UI to help you understand how your expressions are executed.
  • Expression Cost Optimizer: it uses Machine Learning algorithms to optimize your expressions and make them even faster.

Basic Usage

Install

go get github.com/onheap/eval

Example

Play Online

package main

import (
    "fmt"
    "github.com/onheap/eval"
)

func main() {
    expr := `(and (>= age 30) (= gender "Male"))`

    vars := map[string]interface{}{
        "age":    30,
        "gender": "Male",
    }

    // new config and register variables
    config := eval.NewConfig(eval.RegVarAndOp(vars))

    // compile string expression to program
    program, err := eval.Compile(config, expr)
    
    // evaluation expression with the variables
    res, err := program.Eval(eval.NewCtxFromVars(config, vars))

    if err != nil {
        panic(err)
    }

    fmt.Printf("%v", res)
}

Key Concepts

Expressions

Currently, the evaluation expressions should be written in S-Expression syntax, also known as Lisp-like syntax. The implementation of Infix Notation is still a work in progress. Please let me know if you require this feature urgently.

Below are some example expressions.

One line string expression:

(and (>= age 30) (= gender "Male"))

Multi-line string expression (two semicolons ;; starts a comment):

(and
  (>= age 18) ;; Adult
  (= locale "en-US"))

Example of creating a list with parentheses:

(in locale 
  ("en-US" "en-CA")) ;; List of North America locales

Example of if-else statement:

(if is_student
  (> balance 100) ;; Students only require a $100 balance
  (> balance 3000))

Example of using Constant and Operator. The IOS is a customized constant which can be pre-defined in ConstantMap. The sub-expression (to_version "2.3.4") calls the to_version operator to parse the string literal "2.3.4" into a specially formatted number for the outer comparison expression.

(and           
  (= platform IOS) ;; IOS is a constant  
  (>= app_version 
    (to_version "2.3.4")))

Variables

In the above example expressions you have already seen the variables. For example, in the expression: (and (>= age 30) (= gender "Male")). The age and gender are variables. The variable associated values are retrieved through the VariableFetcher during the expression evaluation.

type VariableFetcher interface {
    Get(varKey VariableKey, strKey string) (Value, error)
}

Please note that there are two types of keys in method parameters. The varKey is of type VariableKey, the strKey is of type string.

The VariableKey typed keys are required to be registered or pre-defined into the VariableKeyMap explicitly, to build the connections between varKey and variable string literal in expressions. String typed keys can be used directly without the registration step. the value of a strKey the string literal in expressions.

The varKey offers better performance, the strKey offers more flexibility. You can use any of them (or hybrid), as they both are passed in during the expression evaluation. But we recommend using the varKey to get better performance.

Operators

Operators are functions in expressions. Below is a list of the built-in operators. Customized operators can be registered or pre-defined into the OperatorMap.

Operator	Alias	Example	Description
add	+	(+ 1 1)	Addition operation for two or more numbers.
sub	-	(- 3 2)	Subtraction operation for two or more numbers.
mul	*	(* 1 2 3)	Multiplication operation for two or more numbers.
div	/	(/ 6 3)	Division operation for two or more numbers.
mod	%	(% 3 7)	Modulus operation for two or more numbers.
and	&, &&	(and (>= age 30) (= gender "Male"))	Logical AND operation for two or more booleans.
or	|, ||	(or (< age 18) (> age 80))	Logical OR operation for two or more booleans.
not	!	(not is_student))	Logical NOT operation for a boolean value.
xor	N/A	(xor true false)	Logical OR operation for two or more booleans.
eq	=, ==	(= gender "Female")	Two values are equal.
ne	!=	(!= gender "Female")	Two values are not equal.
gt	>	(> 2 1)	Greater than.
ge	>=	(>= age 18)	Greater than or equal to.
lt	<	(< 3 5)	Less than.
le	<=	(<= score 80)	Less than or equal to.
between	N/A	(between age 18 80)	Checking if the value is between the range. The between operator is inclusive: begin and end values are included.
in	N/A	(in locale ("en-US" "en-CA"))	Checking if the value is in the list.
overlap	N/A	(overlap languages ("en" "zh"))	Checking if the two lists are overlapped.
date	t_date, to_date	(date "2021-01-01") (date "2021-01-01" "2006-01-02")	Parse a string literal into date. The second parameter represents for layout and is optional.
datetime	t_datetime, to_datetime	(datetime "2021-01-01 11:58:56") (date "2021-01-01 11:58:56" "2006-01-02 15:04:05")	Parse a string literal into datetime. The second parameter represents for layout and is optional.
version	t_version, to_version	(to_version "2.3.4") (to_version "2.3" 2)	Parse a string literal into a version. The second parameter represents the count of valid version numbers and is optional.

Useful Features

• TryEval tries to execute the expression when only partial variables are available. It skips sub-expressions where variables are not all fetched, tries to find at least one sub-branch that can be fully executed with the currently available variables, and returns the result when the result of the sub-expressoin determines the final result of the whole expression.

  For example, in the following expression. There are two variables in the expression: locale and age. Currently, only the variable age is fetched. In that case, TryEval function will skip executing the sub-expression (= locale "en-US") , and execute (>= age 18) first, if value of age is less then 18, the sub-expression returns false, then the result of this sub-expression determines the final result of the entire expression.

  (and
   (= locale "en-US")  ;; this sub-expression is skiped due to the `locale` variable is not available
   (>= age 18))        ;; when this sub-expression returns `false`, the result of the entire expression is `false`

  It is typically used for the scenarios that fetching variables is expansive and the root operator is bool operators.

• ReportEvent is a configuration option. If it is enabled, the evaluation engine will send events to the EventChannel for each execution step. We can use this feature to observe the internal execution of the engine and to collect statistics on the execution of expressions. Debug Panel and Expression Cost Optimizer are two example usages of this feature.

• Dump / DumpTable / IndentByParentheses

  • Dump decompiles the compiled expressions into the corresponding string expressions.
  • DumpTable dumps the compiled expressions into an easy-to-understand format.
  • IndentByParentheses formats string expressions.

Compile Options

• ConstantFolding evaluates constant subexpressions at compile time to reduce the complicity of the expression.

  Examples

  Original Expression	Decompiled Expression
  (< (- (now) registered_time) (* 7 24 3600) ;; one week seconds )	(< (- (now) registered_time) 604800)
  (< (+ v1 (- 2 3) (/ 6 3) 4) (* 5 6 7))	(< (+ v1 -1 2 4) 210)

• ReduceNesting flattens and and or operators to reduce the nesting level of the expression. Makes short circuits more efficient.

  Examples

  Original Expression	Decompiled Expression
  (and ;; US adult users (and (> age 18) (= address.country "US")) ;; With good credit and enough balance (and (>= credit Good) (>= balance 4000)))	(and (> age 18) (= address.country "US") (>= credit Good) (>= balance 4000))
  (or (and (and a b) (and c d)) (or (or e f) (or h (or j k l))))	(or (and a b c d) (or e f h j k l))

• FastEvaluation optimizes hot path subexpressions to reduce the number of loops and stack operations in the evaluation engine.

  Examples

  The idea behind the FastEvaluation is similar to the inlining optimisation. When the FastEvaluation enabled, the optimise-able subexpression be compiled in prefix notation instead of the postfix notation like the original Reverse Polish notation, so that the operators can directly get the parameters from the following nodes.

  Expression: (> age 18)
  Without FastEvaluation	node size: 3 stack size: 2 idx: | 0| 1| 2| node: | age| 18| >| pIdx: | 2| 2| -1| flag: | V| C| OP| cCnt: | 0| 0| 2| scIdx: | 0| 1| -1| scVal: | | | | osTop: | 0| 1| 0|
  With FastEvaluation	node size: 3 stack size: 1 idx: | 0| 1| 2| node: | >| age| 18| pIdx: | -1| 0| 0| flag: | OPf| V| C| cCnt: | 2| 0| 0| scIdx: | 0| 1| -1| scVal: | | | | osTop: | 0| 0| 0|

  When the FastEvaluation disabled, the execution sequence of the expression will be age, 18, >.

  1. push age to stack.
  2. push 18 to stack.
  3. execute the > operator with the parameters (age, 18) that popped from stack

  When the FastEvaluation enabled, the execution sequence of the expression will be >, age, 18.

  1. execute the > operator with the parameters (age, 18) that directly inlined from the expression

  Expression: (and (> age 18) (= address.country "US") (>= credit Good) (>= balance 4000))
  Without FastEvaluation	node size: 13 stack size: 5 idx: | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11| 12| node: | age| 18| >|addr…| US| =|bala…| 4000| >=|cred…| Good| >=| and| pIdx: | 2| 2| 12| 5| 5| 12| 8| 8| 12| 11| 11| 12| -1| flag: | V| C| OP| V| C| OP| V| C| OP| V| V| OP| OP| cCnt: | 0| 0| 2| 0| 0| 2| 0| 0| 2| 0| 0| 2| 4| scIdx: | 0| 1| -1| 3| 4| -1| 6| 7| -1| 9| 10| -1| -1| scVal: | | | F| | | F| | | F| | | TF| | osTop: | 0| 1| 0| 1| 2| 1| 2| 3| 2| 3| 4| 3| 0|
  With FastEvaluation	node size: 13 stack size: 4 idx: | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11| 12| node: | >| age| 18| =|addr…| US| >=|bala…| 4000| >=|cred…| Good| and| pIdx: | 12| 0| 0| 12| 3| 3| 12| 6| 6| 12| 9| 9| -1| flag: | OPf| V| C| OPf| V| C| OPf| V| C| OPf| V| V| OP| cCnt: | 2| 0| 0| 2| 0| 0| 2| 0| 0| 2| 0| 0| 4| scIdx: | -1| 1| 2| -1| 4| 5| -1| 7| 8| -1| 10| 11| -1| scVal: | F| | | F| | | F| | | TF| | | | osTop: | 0| 0| 0| 1| 1| 1| 2| 2| 2| 3| 3| 3| 0|

• Reordering reorders subexpressions based on the execution cost. Priory to execute subexpression with less cost, trigger short circuit earlier.

  Examples

  Original Expression	Decompiled Expression
  (and (> age 18) ;; costs 20 (= country "US") ;; costs 40 (>= credit Good) ;; costs 30 (>= balance 4000)) ;; costs 10	;; reordered based on subexpression costs (and (>= balance 4000) ;; costs 10 (> age 18) ;; costs 20 (= country "US") ;; costs 30 (>= credit Good)) ;; costs 40
  Fetching value of variable credit costs 100, others cost 7. (and (or (>= credit Good) ;; costs 100 (overlap ("top" "high_value") user_tags)) (not (in "F" user_tags)))	The or subexpression is moved to a later position because the cost of fetching credit is higher than the other subexpressions. (and (not (in "F" user_tags)) (or (overlap ("top" "high_value") user_tags) (>= credit Good)))

Tools

Debug Panel

A Terminal UI that shows compiled expression structural and step-by-step execution progress. Helps you understand how your expression is executed.

Learn more →.

Expression Cost Optimizer

It uses Genetic Algorithms (others are optional) to optimize the over all expressions execution time, generates the best scores for the CostsMap.

As shown in the figure below, the total number of executing all rules over all users decreases from 600398 to 558686, reduced by ~7% after ten generations.

initial execution count: 600398
Best fitness at generation 0: 587977.000000
Best fitness at generation 1: 585488.000000
Best fitness at generation 2: 583040.000000
Best fitness at generation 3: 560880.000000
Best fitness at generation 4: 560880.000000
Best fitness at generation 5: 560880.000000
Best fitness at generation 6: 560880.000000
Best fitness at generation 7: 559697.000000
Best fitness at generation 8: 557820.000000
Best fitness at generation 9: 556075.000000
Best fitness at generation 10: 556075.000000

Learn more →.

Generated CostsMap scores

{
        `address`: 257.5637323444525,
        `address.city`: -29.732067230828733,
        `address.country`: -4.445875953501092,
        `address.state`: -2.733315237719508,
        `age`: 13.534118456114095,
        `app_version`: 81.96361572619793,
        `balance`: 6.5089373401145805,
        `birth_date`: 29.504377681831215,
        `created_at`: 1.8939662469501435,
        `credit`: -14.994423737587496,
        `credit_limit`: -20.952782417744316,
        `discount`: 1.516122498612845,
        `distance`: -2.461526385425413,
        `gender`: -20.00951321901351,
        `interests`: -1.9843024344711226,
        `is_birthday`: 2.0701165078726405,
        `is_student`: -6.213750700033799,
        `is_vip`: 222.7708005914785,
        `language`: -60.04923908428884,
        `now`: 85.7151642404042,
        `os_version`: -0.0051749009548118785,
        `platform`: -8.66752799417992,
        `updated_at`: 36.56643865523681,
        `user_id`: 20.934025789111697,
        `user_tags`: -6.7672454401690025,
}

Benchmark

Benchmark between different Go Expression Evaluation projects.

❯ go test -bench=. -run=none -benchtime=3s -benchmem
goos: darwin
goarch: amd64
pkg: github.com/onheap/eval_lab/benchmark/projects
cpu: Intel(R) Core(TM) i9-9980HK CPU @ 2.40GHz
 Benchmark_bexpr-16              1748103          2033 ns/op           888 B/op          45 allocs/op
 Benchmark_celgo-16             26671797           134.9 ns/op          16 B/op           1 allocs/op
┌────────────────────────────────────────────────────────────────────────────────────────────────────┐
│Benchmark_eval-16              53657851            63.31 ns/op         32 B/op           1 allocs/op│
└────────────────────────────────────────────────────────────────────────────────────────────────────┘
 Benchmark_tryEval-16           27411960           126.4 ns/op          32 B/op           1 allocs/op
 Benchmark_evalfilter-16         2012268          1796 ns/op           848 B/op          24 allocs/op
 Benchmark_expr-16              27877728           122.5 ns/op          32 B/op           1 allocs/op
 Benchmark_goja-16              12890437           283.3 ns/op          96 B/op           2 allocs/op
 Benchmark_govaluate-16         16873670           207.6 ns/op          24 B/op           2 allocs/op
 Benchmark_gval-16               6209001           570.2 ns/op         240 B/op           8 allocs/op
 Benchmark_otto-16               5466194           656.4 ns/op         336 B/op           7 allocs/op
 Benchmark_starlark-16            784425          4467 ns/op          3568 B/op          68 allocs/op
PASS
ok      github.com/onheap/eval_lab/benchmark/projects    45.613s

Other Benchmarks

Benchmark between Eval and Itoa

❯ go test -bench=. -benchtime=3s -benchmem
goos: darwin
goarch: amd64
pkg: github.com/onheap/eval_lab/benchmark/itoa
cpu: Intel(R) Core(TM) i9-9980HK CPU @ 2.40GHz
Benchmark_eval-16    	50816451	        63.58 ns/op	      32 B/op	       1 allocs/op
Benchmark_itoa-16    	74626735	        46.48 ns/op	      24 B/op	       2 allocs/op
PASS
ok  	github.com/onheap/eval_lab/benchmark/itoa	6.981s

The cost of executing an expression is at the same level as strconv.Itoa(12345678). it should be worry free to use this project.

                   200ps - 4.6GHz single cycle time
                1ns      - L1 cache latency
               10ns      - L2/L3 cache SRAM latency
               20ns      - DDR4 CAS, first byte from memory latency
               20ns      - C++ raw hardcoded structs access
               46ns      - Go itoa an 8-digtal number
  ---------->  64ns      - Eval execute an expression
               80ns      - C++ FlatBuffers decode/traverse/dealloc
              150ns      - PCIe bus latency
              171ns      - cgo call boundary, 2015
              200ns      - HFT FPGA
              475ns      - 2020 MLPerf winner recommendation inference time per sample
              800ns      - Go Protocol Buffers Marshal
              837ns      - Go json-iterator/go json unmarshal
           1µs           - Go protocol buffers unmarshal
           3µs           - Go JSON Marshal
           7µs           - Go JSON Unmarshal
          10µs           - PCIe/NVLink startup time
          17µs           - Python JSON encode/decode times
          30µs           - UNIX domain socket; eventfd; fifo pipes
         100µs           - Redis intrinsic latency; KDB+; HFT direct market access
         200µs           - 1GB/s network air latency; Go garbage collector pauses interval 2018
         230µs           - San Francisco to San Jose at speed of light
         500µs           - NGINX/Kong added latency
     10ms                - AWS DynamoDB; WIFI6 "air" latency
     15ms                - AWS Sagemaker latency; "Flash Boys" 300million USD HFT drama
     30ms                - 5G "air" latency
     36ms                - San Francisco to Hong-Kong at speed of light
    100ms                - typical roundtrip from mobile to backend
    200ms                - AWS RDS MySQL/PostgreSQL; AWS Aurora
 10s                     - AWS Cloudfront 1MB transfer time

License

Released under the Apache License.