Why is the function call speed of expr very slow

[p1g3]

I did a benchmark test on several expression parsing libraries, including function calls and injecting structs, and I found that expr's function calls were much slower compared to the other products. I want to figure out the reason for this.

$ go test -bench=. -benchtime=10s
goos: darwin
goarch: amd64
pkg: github.com/antonmedv/golang-expression-evaluation-comparison
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
Benchmark_bexpr-12                 	 5676273	      2089 ns/op
Benchmark_celgo-12                 	77683569	       153.0 ns/op
Benchmark_celgo_startswith-12      	42621015	       278.7 ns/op
Benchmark_celgo_funccall-12        	69535796	       172.7 ns/op
Benchmark_celgo_struct-12          	16101632	       748.2 ns/op
Benchmark_evalfilter-12            	 7971537	      1508 ns/op
Benchmark_expr-12                  	93287458	       126.6 ns/op
Benchmark_expr_startswith-12       	48665090	       246.6 ns/op
Benchmark_expr_funccall-12         	22060058	       544.6 ns/op
Benchmark_expr_struct-12           	39742920	       300.1 ns/op
Benchmark_goja-12                  	41479744	       286.4 ns/op
Benchmark_govaluate-12             	55276390	       213.1 ns/op
Benchmark_govaluate_funccall-12    	87888637	       125.8 ns/op
Benchmark_govaluate_struct-12      	19006689	       629.2 ns/op
Benchmark_gval-12                  	20624302	       579.2 ns/op
Benchmark_otto-12                  	19031895	       630.9 ns/op
Benchmark_starlark-12              	 2717073	      4394 ns/op
PASS
ok  	github.com/antonmedv/golang-expression-evaluation-comparison	215.618s

test code

func Benchmark_expr_funccall(b *testing.B) {
	params := map[string]interface{}{
		"hello": func(str string) string { return "hello " + str },
	}

	program, err := expr.Compile(`hello("world")`)
	if err != nil {
		b.Fatal(err)
	}

	var out interface{}

	b.ResetTimer()
	for n := 0; n < b.N; n++ {
		out, err = expr.Run(program, params)
	}
	b.StopTimer()

	if err != nil {
		b.Fatal(err)
	}
	if out.(string) != "hello world" {
		b.Fail()
	}
}

[p1g3]

I already fixed it. Code in master branch. Will release soon. Please show full bench code.

You can find the complete test cases here: https://github.com/p1g3/golang-expression-evaluation-comparison

[antonmedv]

I see. Switch to this type for expr as well: func(args ...interface{}) interface{}

For celgo and govaluate you are using predefined type. In expr it called fast call.

[p1g3]

I modified the code to:

params := map[string]interface{}{
		"hello": func(args ...interface{}) interface{} { return "hello " + args[0].(string) },
	}

However, the benchmark results show that this has not been very helpful.

cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
Benchmark_bexpr-12                 	 2863442	      2137 ns/op
Benchmark_celgo-12                 	37168993	       162.3 ns/op
Benchmark_celgo_startswith-12      	21123087	       303.4 ns/op
Benchmark_celgo_funccall-12        	31582498	       174.8 ns/op
Benchmark_celgo_struct-12          	 7351293	       793.6 ns/op
Benchmark_evalfilter-12            	 3684661	      1610 ns/op
Benchmark_expr-12                  	45209746	       133.1 ns/op
Benchmark_expr_startswith-12       	19628127	       275.4 ns/op
Benchmark_expr_funccall-12         	 7748418	       776.4 ns/op
Benchmark_expr_struct-12           	13065194	       450.5 ns/op
Benchmark_goja-12                  	19866393	       303.6 ns/op
Benchmark_govaluate-12             	26049186	       229.4 ns/op
Benchmark_govaluate_funccall-12    	47708176	       128.9 ns/op
Benchmark_govaluate_struct-12      	 9306738	       680.0 ns/op
Benchmark_gval-12                  	 9127659	       644.7 ns/op
Benchmark_otto-12                  	 9173085	       643.4 ns/op
Benchmark_starlark-12              	 1322638	      4534 ns/op
PASS
ok  	github.com/antonmedv/golang-expression-evaluation-comparison	121.264s

[p1g3]

I see. Switch to this type for expr as well: func(args ...interface{}) interface{}

For celgo and govaluate you are using predefined type. In expr it called fast call.

Is it true that while expr is much more concise and clear than go-cel and govaluate, the cost of doing so is sacrificing some performance?

[p1g3]

Expr should be faster than cel-go and govaluate (definitely faster it). Let's try to figure our what the issue is: benchmark of expr call code.

So you think modifying the funccall benchmark to what would make it run faster?

[gitperson1980]

I modified the code to:

params := map[string]interface{}{
		"hello": func(args ...interface{}) interface{} { return "hello " + args[0].(string) },
	}

However, the benchmark results show that this has not been very helpful.

cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
Benchmark_bexpr-12                 	 2863442	      2137 ns/op
Benchmark_celgo-12                 	37168993	       162.3 ns/op
Benchmark_celgo_startswith-12      	21123087	       303.4 ns/op
Benchmark_celgo_funccall-12        	31582498	       174.8 ns/op
Benchmark_celgo_struct-12          	 7351293	       793.6 ns/op
Benchmark_evalfilter-12            	 3684661	      1610 ns/op
Benchmark_expr-12                  	45209746	       133.1 ns/op
Benchmark_expr_startswith-12       	19628127	       275.4 ns/op
Benchmark_expr_funccall-12         	 7748418	       776.4 ns/op
Benchmark_expr_struct-12           	13065194	       450.5 ns/op
Benchmark_goja-12                  	19866393	       303.6 ns/op
Benchmark_govaluate-12             	26049186	       229.4 ns/op
Benchmark_govaluate_funccall-12    	47708176	       128.9 ns/op
Benchmark_govaluate_struct-12      	 9306738	       680.0 ns/op
Benchmark_gval-12                  	 9127659	       644.7 ns/op
Benchmark_otto-12                  	 9173085	       643.4 ns/op
Benchmark_starlark-12              	 1322638	      4534 ns/op
PASS
ok  	github.com/antonmedv/golang-expression-evaluation-comparison	121.264s

The culprit with fastfunc although faster is fetchfn.. I just fetch the func directly from fetcher. fetchFN uses reflection and that is a killer.

call := vm.constant().(Call)
funcs := fetcher.Fetch(call.Name)

In my case I ensure all the fast funcs are not defined as methods.

Anton .. would love to see you re-instill fetcher as an option for those that can use it.

[antonmedv]

@gitperson1980 those bench are made at @master?

[gitperson1980]

I did the benchmarks many moons back. I did it against v1.9.0. I still use v1.9.0 as it provides fetcher and fetcher is infinitely hackable to gain performance in my use cases. I love the fetcher functionality!

[gitperson1980]

Also above 3 switch/case statements in fetcher.. Go compiler switches to binary search from a linear search.

[antonmedv]

Go compiler switches to binary search from a linear search.

Only for big switches.

[gitperson1980]

What is the definition of big? Some of my fetchers have 50 case statements. It goes from O(n) to O(log n) with binary search.

[antonmedv]

I did some investigation. I added updated benchmarks in antonmedv/golang-expression-evaluation-comparison@6a03e5c

It is true, cel-go func calls now are faster. The reason for this is that Expr fetches function from the environment on the eval step, and cel-go does it on compile step. So Expr does an additional step, but this can be improved and Expr can also do such optimization on compile step.

Another huge difference is how functions are configured.

It's super easy to declare a function in Expr:

	params := map[string]interface{}{
		"join": func(a, b string) string {
			return a + b
		},
	}

And hot it's done in cel-go:

	env, err := cel.NewEnv(
		cel.Function("join",
			cel.Overload("join_string_string",
				[]*cel.Type{cel.StringType, cel.StringType},
				cel.StringType,
				cel.BinaryBinding(func(lhs, rhs ref.Val) ref.Val {
					return types.String(lhs.Value().(string) + rhs.Value().(string))
				}))))

[antonmedv]

Here is my first attempt to implement such behavior: #314