Eval Logo

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.

• 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.

go get github.com/onheap/eval

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)
}

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")))

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 are functions in expressions. Below is a list of the built-in operators. Customized operators can be registered or pre-defined into the OperatorMap.

• 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.

• 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)))

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 →.

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 →.

{
 `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 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

❯ 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

 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

Released under the Apache License.