To the extent possible under law, Dmitrii Okunev has waived all copyright and related or neighboring rights to Reverse Polish Notation for Go. This work is published from: Ireland.

About

github.com/xaionaro-go/rpn is an implementation of Reverse Polish Notation. The implementation is focused on fast evaluation (but slow parsing).

Quick start

package main

import (
	"fmt"

	"github.com/xaionaro-go/rpn"
	"github.com/xaionaro-go/rpn/types"
)

type variables struct {
	X float64
}

func (r *variables) Resolve(sym string) (types.ValueLoader, error) {
	switch sym {
	case "x":
		return types.FuncValue(func() float64 {
			return r.X
		}), nil
	}
	return nil, fmt.Errorf("symbol '%s' not found", sym)
}

func main() {
	vars := &variables{}
	expr, err := rpn.Parse("x 2 *", vars)
	if err != nil {
		panic(err)
	}

	vars.X = 1
	_, _ = fmt.Println(expr.Eval())

	vars.X = 3
	_, _ = fmt.Println(expr.Eval())
}

The output is:

2
6

Benchmark

There are 5 approaches implemented (callslice, calltree, exprtree, compile and tokenslice):

goos: linux
goarch: amd64
pkg: github.com/xaionaro-go/rpn/tests
BenchmarkExpr_Eval/cache_true/3_constant_values/callslice-4             1000000000               4.00 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/3_constant_values/calltree-4              1000000000               4.00 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/3_constant_values/exprtree-4              1000000000               3.72 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/3_constant_values/compile-4               1000000000               4.06 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/3_constant_values/tokenslice-4            1000000000               3.99 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/3_constant_values/default-4               1000000000               4.01 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/3_variables/default-4                     1000000000               3.99 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/3_variables/callslice-4                   1000000000               4.00 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/3_variables/calltree-4                    1000000000               4.00 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/3_variables/exprtree-4                    1000000000               3.73 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/3_variables/compile-4                     1000000000               4.08 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/3_variables/tokenslice-4                  1000000000               3.99 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/10_variables/callslice-4                  1000000000               4.02 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/10_variables/calltree-4                   1000000000               4.01 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/10_variables/exprtree-4                   1000000000               3.72 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/10_variables/compile-4                    1000000000               4.05 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/10_variables/tokenslice-4                 1000000000               4.05 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/10_variables/default-4                    1000000000               4.00 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/100_variables/callslice-4                 1000000000               4.03 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/100_variables/calltree-4                  1000000000               4.01 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/100_variables/exprtree-4                  1000000000               3.73 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/100_variables/compile-4                   1000000000               4.06 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/100_variables/tokenslice-4                1000000000               4.00 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/100_variables/default-4                   1000000000               4.00 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/1000_variables/exprtree-4                 1000000000               3.73 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/1000_variables/compile-4                  1000000000               4.04 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/1000_variables/tokenslice-4               1000000000               4.00 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/1000_variables/default-4                  1000000000               3.99 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/1000_variables/callslice-4                1000000000               4.00 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/1000_variables/calltree-4                 1000000000               4.00 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/10000_variables/calltree-4                1000000000               4.06 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/10000_variables/exprtree-4                1000000000               3.72 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/10000_variables/compile-4                 1000000000               4.05 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/10000_variables/tokenslice-4              1000000000               4.00 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/10000_variables/default-4                 1000000000               3.99 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_true/10000_variables/callslice-4               1000000000               4.01 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/3_constant_values/callslice-4            579179106               10.4 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/3_constant_values/calltree-4             1000000000               5.51 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/3_constant_values/exprtree-4             376218780               15.9 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/3_constant_values/compile-4              451313248               13.3 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/3_constant_values/tokenslice-4           285631948               21.0 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/3_constant_values/default-4              1000000000               5.52 ns/op            0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/3_variables/callslice-4                  331783568               18.1 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/3_variables/calltree-4                   495298591               12.1 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/3_variables/exprtree-4                   287268447               20.9 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/3_variables/compile-4                    256272177               23.3 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/3_variables/tokenslice-4                 229319173               26.4 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/3_variables/default-4                    494261940               12.1 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/10_variables/callslice-4                 100000000               52.9 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/10_variables/calltree-4                  122009749               49.0 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/10_variables/exprtree-4                  75151573                73.8 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/10_variables/compile-4                   90459986                66.6 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/10_variables/tokenslice-4                69911527                85.7 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/10_variables/default-4                   121929210               48.9 ns/op             0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/100_variables/calltree-4                 10963188               548 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/100_variables/exprtree-4                  7401158               808 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/100_variables/compile-4                   8893951               678 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/100_variables/tokenslice-4                6937212               865 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/100_variables/default-4                  12024320               491 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/100_variables/callslice-4                11103020               529 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/1000_variables/callslice-4                1000000              5396 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/1000_variables/calltree-4                  885706              6453 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/1000_variables/exprtree-4                  650157              9065 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/1000_variables/compile-4                   876373              6829 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/1000_variables/tokenslice-4                694416              8591 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/1000_variables/default-4                  1000000              5400 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/10000_variables/compile-4                   84819             70461 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/10000_variables/tokenslice-4                68793             86768 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/10000_variables/default-4                  104406             57272 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/10000_variables/callslice-4                104284             57153 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/10000_variables/calltree-4                  77030             77918 ns/op               0 B/op          0 allocs/op
BenchmarkExpr_Eval/cache_false/10000_variables/exprtree-4                  60081             99462 ns/op               0 B/op          0 allocs/op
PASS
ok      github.com/xaionaro-go/rpn/tests        407.949s

The default approach for small expressions is calltree, and for larger expression is callslice, so if you will import github.com/xaionaro-go/rpn then if you will use them.