eval

package module
v1.2.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 26, 2023 License: Apache-2.0 Imports: 10 Imported by: 7

README

Eval Logo

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",
	}

	// 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 variables
	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, >.

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

Documentation

Index

Constants

View Source 
const (
	ConstantNode     = NodeType(constant)
	VariableNode     = NodeType(variable)
	OperatorNode     = NodeType(operator)
	FastOperatorNode = NodeType(fastOperator)
	CondNode         = NodeType(cond)
	EventNode        = NodeType(event)
)

Variables

View Source 
var (
	EnableUndefinedVariable Option = func(c *Config) {
		c.CompileOptions[AllowUndefinedVariable] = true
	}
	EnableDebug Option = func(c *Config) {
		c.CompileOptions[Debug] = true
	}
	EnableReportEvent Option = func(c *Config) {
		c.CompileOptions[ReportEvent] = true
	}
	Optimizations = func(enable bool, opts ...CompileOption) Option {
		return func(c *Config) {
			if len(opts) == 0 || (len(opts) == 1 && opts[0] == Optimize) {
				opts = optimizations
			}

			for _, opt := range opts {
				if optimizerMap[opt] != nil {
					c.CompileOptions[opt] = enable
				}
			}
		}
	}
	EnableInfixNotation Option = func(c *Config) {
		c.CompileOptions[InfixNotation] = true
	}

	// RegVarAndOp registers variables and operators to config
	RegVarAndOp = func(vals map[string]interface{}) Option {
		return func(c *Config) {
			for k, v := range vals {
				switch a := v.(type) {
				case Operator:
					c.OperatorMap[k] = a
				case func(*Ctx, []Value) (Value, error):
					c.OperatorMap[k] = a
				default:
					GetOrRegisterKey(c, k)
				}
			}
		}
	}

	// ExtendConf extends source config
	ExtendConf = func(src *Config) Option {
		return func(c *Config) {
			if src != nil {
				copyConfig(c, src)
			}
		}
	}
)
View Source 
var DNE = dne{DoesNotExist: "DNE"}
View Source 
var ErrDNE = errors.New("DNE")

Functions

func DestructParamsInt2 added in v1.1.0 

func DestructParamsInt2(opName string, params []Value) (a, b int64, e error)

func DestructParamsStr2 added in v1.1.0 

func DestructParamsStr2(opName string, params []Value) (a, b string, e error)

func Dump 

func Dump(e *Expr) string

func DumpTable 

func DumpTable(expr *Expr, skipEventNode bool) string

func GenerateTestCase 

func GenerateTestCase(expr string, want Value, valMap map[string]interface{}) string

func HandleDebugEvent 

func HandleDebugEvent(e *Expr)

func IndentByParentheses 

func IndentByParentheses(s string) string

func OpExecError 

func OpExecError(opName string, err error) error

func ParamTypeError 

func ParamTypeError(opName string, want string, got Value) error

func ParamsCountError 

func ParamsCountError(opName string, want, got int) error

func RegisterOperator 

func RegisterOperator(cc *Config, name string, op Operator) error

func ToValueMap 

func ToValueMap(m map[string]interface{}) map[string]Value

Types

type CompileOption 

type CompileOption string
const (
	Optimize        CompileOption = "optimize" // switch for all optimizations
	Reordering      CompileOption = "reordering"
	FastEvaluation  CompileOption = "fast_evaluation"
	ReduceNesting   CompileOption = "reduce_nesting"
	ConstantFolding CompileOption = "constant_folding"

	Debug                  CompileOption = "debug"
	ReportEvent            CompileOption = "report_event"
	InfixNotation          CompileOption = "infix_notation"
	AllowUndefinedVariable CompileOption = "allow_undefined_variable"
)

type Config added in v1.2.0 

type Config struct {
	ConstantMap    map[string]Value
	OperatorMap    map[string]Operator
	VariableKeyMap map[string]VariableKey

	// cost of performance
	CostsMap map[string]float64

	// compile options
	CompileOptions map[CompileOption]bool

	StatelessOperators []string
}

func CopyConfig added in v1.2.0 

func CopyConfig(origin *Config) *Config

func NewConfig added in v1.2.0 

func NewConfig(opts ...Option) *Config

type Ctx 

type Ctx struct {
	VariableFetcher
	Ctx context.Context
}

func NewCtxFromVars added in v1.2.0 

func NewCtxFromVars(cc *Config, vals map[string]interface{}) *Ctx

type Event 

type Event struct {
	EventType EventType
	Stack     []Value
	Data      interface{}
}

type EventType 

type EventType string
const (
	LoopEvent   EventType = "LOOP"
	OpExecEvent EventType = "OP_EXEC"
)

type Expr 

type Expr struct {
	EventChan chan Event
	// contains filtered or unexported fields
}

func Compile 

func Compile(originConf *Config, exprStr string) (*Expr, error)

func (*Expr) Eval 

func (e *Expr) Eval(ctx *Ctx) (res Value, err error)

func (*Expr) EvalBool 

func (e *Expr) EvalBool(ctx *Ctx) (bool, error)

func (*Expr) TryEval 

func (e *Expr) TryEval(ctx *Ctx) (res Value, err error)

func (*Expr) TryEvalBool 

func (e *Expr) TryEvalBool(ctx *Ctx) (bool, error)

type GenExprConfig 

type GenExprConfig struct {
	EnableVariable  bool
	EnableCondition bool
	EnableTryEval   bool
	WantError       bool
	GenType         GenExprType
	NumVariables    []GenExprResult
	BoolVariables   []GenExprResult
	DneVariables    []GenExprResult
}

type GenExprOption 

type GenExprOption func(conf *GenExprConfig)
var (
	EnableVariable GenExprOption = func(c *GenExprConfig) {
		c.EnableVariable = true
	}
	EnableCondition GenExprOption = func(c *GenExprConfig) {
		c.EnableCondition = true
	}
	EnableTryEval GenExprOption = func(c *GenExprConfig) {
		c.EnableTryEval = true
	}

	GenType = func(genType GenExprType) GenExprOption {
		return func(c *GenExprConfig) {
			c.GenType = genType
		}
	}

	GenVariables = func(m map[string]interface{}) GenExprOption {
		return func(c *GenExprConfig) {
			var (
				numVars  []GenExprResult
				boolVars []GenExprResult
				dneVars  []GenExprResult
			)
			for k, v := range m {
				if v == DNE {
					dneVars = append(dneVars, GenExprResult{Expr: k, Res: v})
					continue
				}
				v = UnifyType(v)
				switch v.(type) {
				case int64:
					numVars = append(numVars, GenExprResult{Expr: k, Res: v})
				case bool:
					boolVars = append(boolVars, GenExprResult{Expr: k, Res: v})
				}
			}
			c.NumVariables = append(c.NumVariables, numVars...)
			c.BoolVariables = append(c.BoolVariables, boolVars...)
			c.DneVariables = append(c.DneVariables, dneVars...)
		}
	}
)

type GenExprResult 

type GenExprResult struct {
	Expr string
	Res  Value
}

func GenerateRandomExpr 

func GenerateRandomExpr(level int, random *rand.Rand, opts ...GenExprOption) GenExprResult

GenerateRandomExpr generate random expression

type GenExprType 

type GenExprType int
const (
	GenBool GenExprType = iota
	GenNumber
)

type LoopEventData added in v1.1.0 

type LoopEventData struct {
	CurtIdx   int16
	NodeType  NodeType
	NodeValue Value
}

type MapVarFetcher added in v1.2.0 

type MapVarFetcher map[string]Value

func NewMapVarFetcher added in v1.2.0 

func NewMapVarFetcher(vals map[string]interface{}) MapVarFetcher

func (MapVarFetcher) Cached added in v1.2.0 

func (s MapVarFetcher) Cached(_ VariableKey, key string) bool

func (MapVarFetcher) Get added in v1.2.0 

func (s MapVarFetcher) Get(_ VariableKey, key string) (Value, error)

func (MapVarFetcher) Set added in v1.2.0 

func (s MapVarFetcher) Set(_ VariableKey, key string, val Value) error

type NodeType added in v1.1.0 

type NodeType uint8

func (NodeType) String added in v1.1.0 

func (t NodeType) String() string

type OpEventData 

type OpEventData struct {
	IsFastOp bool
	OpName   string
	Params   []Value
	Res      Value
	Err      error
}

type Operator 

type Operator func(ctx *Ctx, params []Value) (res Value, err error)

type Option 

type Option func(conf *Config)

type SliceVarFetcher added in v1.2.0 

type SliceVarFetcher []Value

func NewSliceVarFetcher added in v1.2.0 

func NewSliceVarFetcher(cc *Config, vals map[string]interface{}) SliceVarFetcher

func (SliceVarFetcher) Cached added in v1.2.0 

func (s SliceVarFetcher) Cached(key VariableKey, _ string) bool

func (SliceVarFetcher) Get added in v1.2.0 

func (s SliceVarFetcher) Get(key VariableKey, _ string) (Value, error)

func (SliceVarFetcher) Set added in v1.2.0 

func (s SliceVarFetcher) Set(key VariableKey, _ string, val Value) error

type Value 

type Value interface{}

func Eval 

func Eval(expr string, vals map[string]interface{}, opts ...Option) (Value, error)

func UnifyType 

func UnifyType(val Value) Value

type VariableFetcher added in v1.2.0 

type VariableFetcher interface {
	// Get gets a value from the variable
	Get(varKey VariableKey, strKey string) (Value, error)
	// Set sets the value and the associated key to the variable
	Set(varKey VariableKey, strKey string, val Value) error
	// Cached returns whether the value of the key has been cached
	Cached(varKey VariableKey, strKey string) bool
}

VariableFetcher is used to fetch values of the expression variables. Note that there are two types of keys in each method parameters, varKey is of type VariableKey, strKey is of type string, varKey offers better performance, strKey offers more flexibility, we can use any of them, as they will all be passed in during the expression execution. we recommend using varKey (if it satisfies your requirements) to get better performance.

type VariableKey added in v1.2.0 

type VariableKey int16
const UndefinedVarKey VariableKey = math.MinInt16

UndefinedVarKey means that the current key is undefined in the VariableKey type In this case you should use the string type key

func GetOrRegisterKey 

func GetOrRegisterKey(cc *Config, name string) VariableKey

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.