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 helps 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",
}
config := eval.NewConfig(eval.RegVarAndOp(vars))
program, err := eval.Compile(config, expr)
res, err := program.Eval(eval.NewCtxFromVars(config, vars))
if err != nil {
panic(err)
}
fmt.Printf("%v", res)
}
Useful Features
-
TryEval tries to execute the expression when only partial variables are fetched. It skips sub-expressions where no variables were fetched, tries to find at least one sub-branch that can be fully executed with the currently fetched variables, and returns the final result.
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.
-
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
, >
.
- push
age
to stack.
- push
18
to stack.
- 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
.
- 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.