Source file src/github.com/launchdarkly/go-server-sdk-evaluation/v2/evaluator_benchmarks_test.go

Documentation: github.com/launchdarkly/go-server-sdk-evaluation/v2

     1  package evaluation
     2  
     3  import (
     4  	"fmt"
     5  	"testing"
     6  
     7  	"github.com/launchdarkly/go-server-sdk-evaluation/v2/ldbuilders"
     8  	"github.com/launchdarkly/go-server-sdk-evaluation/v2/ldmodel"
     9  
    10  	"github.com/launchdarkly/go-sdk-common/v3/ldattr"
    11  	"github.com/launchdarkly/go-sdk-common/v3/ldcontext"
    12  	"github.com/launchdarkly/go-sdk-common/v3/ldvalue"
    13  )
    14  
    15  // Note about heap allocations:
    16  //
    17  // Benchmarks whose names end in "NoAlloc" are expected _not_ to cause any heap allocations (not counting
    18  // setup work done before ResetTimer()). This is enforced by the Makefile's benchmarks target.
    19  //
    20  // See notes about heap allocations in CONTRIBUTING.md.
    21  
    22  var evalBenchmarkResult Result
    23  var evalBenchmarkErr error
    24  
    25  const evalBenchmarkSegmentKey = "segment-key"
    26  
    27  func discardPrerequisiteEvents(params PrerequisiteFlagEvent) {}
    28  
    29  type evalBenchmarkEnv struct {
    30  	evaluator        Evaluator
    31  	user             ldcontext.Context
    32  	targetFlag       *ldmodel.FeatureFlag
    33  	otherFlags       map[string]*ldmodel.FeatureFlag
    34  	targetSegment    *ldmodel.Segment
    35  	targetFeatureKey string
    36  	targetUsers      []ldcontext.Context
    37  }
    38  
    39  type evalBenchmarkCase struct {
    40  	numTargets        int
    41  	numRules          int
    42  	numClauses        int
    43  	extraClauseValues int
    44  	withSegments      bool
    45  	prereqsWidth      int
    46  	prereqsDepth      int
    47  	operator          ldmodel.Operator
    48  	shouldMatchClause bool
    49  }
    50  
    51  func newEvalBenchmarkEnv() *evalBenchmarkEnv {
    52  	return &evalBenchmarkEnv{}
    53  }
    54  
    55  func (env *evalBenchmarkEnv) setUp(bc evalBenchmarkCase) {
    56  	env.evaluator = basicEvaluator()
    57  
    58  	env.user = makeEvalBenchmarkUser(bc)
    59  
    60  	env.targetFlag, env.otherFlags, env.targetSegment = makeEvalBenchmarkFlagData(bc)
    61  
    62  	dataProvider := &simpleDataProvider{
    63  		getFlag: func(key string) *ldmodel.FeatureFlag {
    64  			return env.otherFlags[key]
    65  		},
    66  		getSegment: func(key string) *ldmodel.Segment {
    67  			if key == evalBenchmarkSegmentKey {
    68  				return env.targetSegment
    69  			}
    70  			return nil
    71  		},
    72  	}
    73  	env.evaluator = NewEvaluator(dataProvider)
    74  
    75  	env.targetUsers = make([]ldcontext.Context, bc.numTargets)
    76  	for i := 0; i < bc.numTargets; i++ {
    77  		env.targetUsers[i] = ldcontext.New(makeEvalBenchmarkTargetUserKey(i))
    78  	}
    79  }
    80  
    81  func makeEvalBenchmarkUser(bc evalBenchmarkCase) ldcontext.Context {
    82  	if bc.shouldMatchClause {
    83  		builder := ldcontext.NewBuilder("user-match")
    84  		switch bc.operator {
    85  		case ldmodel.OperatorGreaterThan:
    86  			builder.SetInt("numAttr", 10000)
    87  		case ldmodel.OperatorContains:
    88  			builder.Name("name-0")
    89  		case ldmodel.OperatorMatches:
    90  			builder.SetString("stringAttr", "stringAttr-0")
    91  		case ldmodel.OperatorAfter:
    92  			builder.SetString("dateAttr", "2999-12-31T00:00:00.000-00:00")
    93  		case ldmodel.OperatorSemVerEqual:
    94  			builder.SetString("semVerAttr", "1.0.0")
    95  		case ldmodel.OperatorIn:
    96  			builder.SetString("stringAttr", "stringAttr-0")
    97  		}
    98  		return builder.Build()
    99  	}
   100  	// default is that the user will not be matched by any clause or target
   101  	return ldcontext.NewBuilder("user-nomatch").
   102  		Name("name-nomatch").
   103  		SetString("stringAttr", "stringAttr-nomatch").
   104  		SetInt("numAttr", 0).
   105  		SetString("dateAttr", "1980-01-01T00:00:00.000-00:00").
   106  		SetString("semVerAttr", "0.0.5").
   107  		Build()
   108  }
   109  
   110  func benchmarkEval(b *testing.B, cases []evalBenchmarkCase, action func(*evalBenchmarkEnv)) {
   111  	env := newEvalBenchmarkEnv()
   112  	for _, bc := range cases {
   113  		env.setUp(bc)
   114  
   115  		b.Run(fmt.Sprintf("%+v", bc), func(b *testing.B) {
   116  			for i := 0; i < b.N; i++ {
   117  				action(env)
   118  			}
   119  		})
   120  	}
   121  }
   122  
   123  func BenchmarkEvaluationFallthroughNoAlloc(b *testing.B) {
   124  	benchmarkEval(b, makeEvalBenchmarkCases(false), func(env *evalBenchmarkEnv) {
   125  		evalBenchmarkResult = env.evaluator.Evaluate(env.targetFlag, env.user, discardPrerequisiteEvents)
   126  		if evalBenchmarkResult.Detail.Value.BoolValue() { // verify that we did not get a match
   127  			b.FailNow()
   128  		}
   129  	})
   130  }
   131  
   132  func BenchmarkEvaluationRuleMatchNoAlloc(b *testing.B) {
   133  	benchmarkEval(b, makeEvalBenchmarkCases(true), func(env *evalBenchmarkEnv) {
   134  		evalBenchmarkResult = env.evaluator.Evaluate(env.targetFlag, env.user, discardPrerequisiteEvents)
   135  		if !evalBenchmarkResult.Detail.Value.BoolValue() { // verify that we got a match
   136  			b.FailNow()
   137  		}
   138  	})
   139  }
   140  
   141  func BenchmarkEvaluationUserFoundInTargetsNoAlloc(b *testing.B) {
   142  	// This attempts to match a user from the middle of the target list. As long as the flag has been
   143  	// preprocessed, which it always should be in normal usage, this is a simple map lookup and should
   144  	// not increase linearly with the length of the list.
   145  	benchmarkEval(b, makeTargetMatchBenchmarkCases(), func(env *evalBenchmarkEnv) {
   146  		user := env.targetUsers[len(env.targetUsers)/2]
   147  		evalBenchmarkResult := env.evaluator.Evaluate(env.targetFlag, user, discardPrerequisiteEvents)
   148  		if !evalBenchmarkResult.Detail.Value.BoolValue() {
   149  			b.FailNow()
   150  		}
   151  	})
   152  }
   153  
   154  func BenchmarkEvaluationUsersNotFoundInTargetsNoAlloc(b *testing.B) {
   155  	// This attempts to match a user who is not in the list.  As long as the flag has been preprocessed,
   156  	// which it always should be in normal usage, this is a simple map lookup and should not increase
   157  	// linearly with the length of the list.
   158  	benchmarkEval(b, makeTargetMatchBenchmarkCases(), func(env *evalBenchmarkEnv) {
   159  		evalBenchmarkResult := env.evaluator.Evaluate(env.targetFlag, env.user, discardPrerequisiteEvents)
   160  		if evalBenchmarkResult.Detail.Value.BoolValue() {
   161  			b.FailNow()
   162  		}
   163  	})
   164  }
   165  
   166  func BenchmarkEvaluationUserIncludedInSegmentNoAlloc(b *testing.B) {
   167  	// This attempts to match a user from the middle of the segment's include list. As long as the segment
   168  	// has been preprocessed, which it should always be in normal usage, this is a simple map lookup and
   169  	// should not increase linearly with the length of the list.
   170  	benchmarkEval(b, makeSegmentIncludeExcludeBenchmarkCases(), func(env *evalBenchmarkEnv) {
   171  		user := ldcontext.New(env.targetSegment.Included[len(env.targetSegment.Included)/2])
   172  		evalBenchmarkResult := env.evaluator.Evaluate(env.targetFlag, user, discardPrerequisiteEvents)
   173  		if !evalBenchmarkResult.Detail.Value.BoolValue() {
   174  			b.FailNow()
   175  		}
   176  	})
   177  }
   178  
   179  func BenchmarkEvaluationUserExcludedFromSegmentNoAlloc(b *testing.B) {
   180  	// This attempts to match a user who is explicitly excluded from the segment.  As long as the segment
   181  	// has been preprocessed, which it should always be in normal usage, this is a simple map lookup and
   182  	// should not increase linearly with the length of the list.
   183  	benchmarkEval(b, makeSegmentIncludeExcludeBenchmarkCases(), func(env *evalBenchmarkEnv) {
   184  		user := ldcontext.New(env.targetSegment.Excluded[len(env.targetSegment.Excluded)/2])
   185  		evalBenchmarkResult := env.evaluator.Evaluate(env.targetFlag, user, discardPrerequisiteEvents)
   186  		if evalBenchmarkResult.Detail.Value.BoolValue() {
   187  			b.FailNow()
   188  		}
   189  	})
   190  }
   191  
   192  func BenchmarkEvaluationUserMatchedBySegmentRuleNoAlloc(b *testing.B) {
   193  	benchmarkEval(b, makeSegmentRuleMatchBenchmarkCases(), func(env *evalBenchmarkEnv) {
   194  		evalBenchmarkResult := env.evaluator.Evaluate(env.targetFlag, env.user, discardPrerequisiteEvents)
   195  		if !evalBenchmarkResult.Detail.Value.BoolValue() {
   196  			b.FailNow()
   197  		}
   198  	})
   199  }
   200  
   201  func makeEvalBenchmarkCases(shouldMatch bool) []evalBenchmarkCase {
   202  	ret := []evalBenchmarkCase{}
   203  	for _, op := range []ldmodel.Operator{
   204  		ldmodel.OperatorIn,
   205  		ldmodel.OperatorGreaterThan,
   206  		ldmodel.OperatorContains,
   207  		ldmodel.OperatorMatches,
   208  		ldmodel.OperatorAfter,
   209  		ldmodel.OperatorSemVerEqual,
   210  	} {
   211  		ret = append(ret, evalBenchmarkCase{
   212  			numRules:          1,
   213  			numClauses:        1,
   214  			operator:          op,
   215  			shouldMatchClause: shouldMatch,
   216  		})
   217  		if shouldMatch {
   218  			// Add a case where we have to iterate through a lot of clauses, all of which match; this is
   219  			// meant to detect any inefficiencies in how we're iterating
   220  			ret = append(ret, evalBenchmarkCase{
   221  				numRules:          1,
   222  				numClauses:        100,
   223  				operator:          op,
   224  				shouldMatchClause: true,
   225  			})
   226  		} else {
   227  			// Add a case where we have to iterate through a lot of rules (each with one clause, since a
   228  			// single non-matching clause short-circuits the rule) before falling through
   229  			ret = append(ret, evalBenchmarkCase{
   230  				numRules:   100,
   231  				numClauses: 1,
   232  				operator:   op,
   233  			})
   234  		}
   235  		// Add a case where there is just one clause, but it has non-matching values before the last value
   236  		ret = append(ret, evalBenchmarkCase{
   237  			numRules:          1,
   238  			numClauses:        1,
   239  			extraClauseValues: 99,
   240  			operator:          op,
   241  			shouldMatchClause: shouldMatch,
   242  		})
   243  
   244  		// prereqs
   245  		ret = append(ret, evalBenchmarkCase{
   246  			numRules:          1,
   247  			numClauses:        1,
   248  			operator:          op,
   249  			shouldMatchClause: shouldMatch,
   250  			prereqsWidth:      5,
   251  			prereqsDepth:      1,
   252  		})
   253  		ret = append(ret, evalBenchmarkCase{
   254  			numRules:          1,
   255  			numClauses:        1,
   256  			operator:          op,
   257  			shouldMatchClause: shouldMatch,
   258  			prereqsWidth:      1,
   259  			prereqsDepth:      5,
   260  		})
   261  	}
   262  	return ret
   263  }
   264  
   265  func makeEvalBenchmarkSegmentKey(i int) string {
   266  	return fmt.Sprintf("segment-%d", i)
   267  }
   268  
   269  func makeEvalBenchmarkTargetUserKey(i int) string {
   270  	return fmt.Sprintf("user-%d", i)
   271  }
   272  
   273  func makeEvalBenchmarkClauses(numClauses int, extraClauseValues int, op ldmodel.Operator) []ldmodel.Clause {
   274  	clauses := make([]ldmodel.Clause, 0, numClauses)
   275  	for i := 0; i < numClauses; i++ {
   276  		clause := ldmodel.Clause{Op: op}
   277  		var value ldvalue.Value
   278  		var name string
   279  		switch op {
   280  		case ldmodel.OperatorGreaterThan:
   281  			name = "numAttr"
   282  			value = ldvalue.Int(i)
   283  		case ldmodel.OperatorContains:
   284  			name = "name"
   285  			value = ldvalue.String("name-0")
   286  		case ldmodel.OperatorMatches:
   287  			name = "stringAttr"
   288  			value = ldvalue.String("stringAttr-0")
   289  		case ldmodel.OperatorAfter:
   290  			name = "dateAttr"
   291  			value = ldvalue.String("2000-01-01T00:00:00.000-00:00")
   292  		case ldmodel.OperatorSemVerEqual:
   293  			name = "semVerAttr"
   294  			value = ldvalue.String("1.0.0")
   295  		case ldmodel.OperatorSegmentMatch:
   296  			value = ldvalue.String(evalBenchmarkSegmentKey)
   297  		default:
   298  			clause.Op = ldmodel.OperatorIn
   299  			name = "stringAttr"
   300  			value = ldvalue.String("stringAttr-0")
   301  		}
   302  		if name != "" {
   303  			clause.Attribute = ldattr.NewLiteralRef(name)
   304  		}
   305  		if extraClauseValues == 0 {
   306  			clause.Values = []ldvalue.Value{value}
   307  		} else {
   308  			for i := 0; i < extraClauseValues; i++ {
   309  				clause.Values = append(clause.Values, ldvalue.String("not-a-match"))
   310  			}
   311  			clause.Values = append(clause.Values, value)
   312  		}
   313  		clauses = append(clauses, clause)
   314  	}
   315  	return clauses
   316  }
   317  
   318  func makeTargetMatchBenchmarkCases() []evalBenchmarkCase {
   319  	return []evalBenchmarkCase{
   320  		{numTargets: 10},
   321  		{numTargets: 100},
   322  		{numTargets: 1000},
   323  	}
   324  }
   325  
   326  func makeSegmentIncludeExcludeBenchmarkCases() []evalBenchmarkCase {
   327  	// Add cases to verify the performance of include/exclude matching, regardless of segment rules
   328  	ret := []evalBenchmarkCase{}
   329  	for _, n := range []int{10, 100, 1000} {
   330  		ret = append(ret, evalBenchmarkCase{
   331  			withSegments:      true,
   332  			numTargets:        n,
   333  			numRules:          1,
   334  			numClauses:        1,
   335  			shouldMatchClause: false,
   336  		})
   337  	}
   338  	return ret
   339  }
   340  
   341  func makeSegmentRuleMatchBenchmarkCases() []evalBenchmarkCase {
   342  	// Add cases to verify the performance of segment rules, with no include/exclude matching
   343  	ret := []evalBenchmarkCase{}
   344  	for _, operator := range []ldmodel.Operator{ldmodel.OperatorIn, ldmodel.OperatorMatches} {
   345  		ret = append(ret, evalBenchmarkCase{
   346  			withSegments:      true,
   347  			numTargets:        0,
   348  			numRules:          1,
   349  			numClauses:        1,
   350  			operator:          operator,
   351  			shouldMatchClause: true,
   352  		})
   353  	}
   354  	return ret
   355  }
   356  
   357  func buildEvalBenchmarkFlag(bc evalBenchmarkCase, key string) *ldbuilders.FlagBuilder {
   358  	// All of the flags in these benchmarks are boolean flags with variations [false, true]. This is
   359  	// because the process of evaluation at this level does not differ in any way based on the type or
   360  	// number of the variations; that only affects the higher-level SDK logic.
   361  	builder := ldbuilders.NewFlagBuilder("flag-0").
   362  		Version(1).
   363  		On(true).
   364  		FallthroughVariation(0).
   365  		Variations(ldvalue.Bool(false), ldvalue.Bool(true))
   366  	if bc.numTargets > 0 {
   367  		values := make([]string, bc.numTargets)
   368  		for k := 0; k < bc.numTargets; k++ {
   369  			values[k] = makeEvalBenchmarkTargetUserKey(k)
   370  		}
   371  		builder.AddTarget(1, values...)
   372  	}
   373  	for j := 0; j < bc.numRules; j++ {
   374  		operator := bc.operator
   375  		if bc.withSegments {
   376  			operator = ldmodel.OperatorSegmentMatch
   377  		}
   378  		builder.AddRule(ldbuilders.NewRuleBuilder().
   379  			ID(fmt.Sprintf("%s-%d", key, j)).
   380  			Clauses(makeEvalBenchmarkClauses(bc.numClauses, bc.extraClauseValues, operator)...).
   381  			Variation(1))
   382  	}
   383  	return builder
   384  }
   385  
   386  func makeEvalBenchmarkFlagData(bc evalBenchmarkCase) (*ldmodel.FeatureFlag, map[string]*ldmodel.FeatureFlag, *ldmodel.Segment) {
   387  	mainFlag := buildEvalBenchmarkFlag(bc, "flag-0")
   388  
   389  	otherFlags := make(map[string]*ldmodel.FeatureFlag)
   390  	if bc.prereqsDepth > 0 && bc.prereqsWidth > 0 {
   391  		flagCounter := 1
   392  		makeEvalBenchmarkPrerequisites(mainFlag, &flagCounter, otherFlags, bc, bc.prereqsDepth)
   393  	}
   394  
   395  	var segment *ldmodel.Segment
   396  	if bc.withSegments {
   397  		sb := ldbuilders.NewSegmentBuilder(evalBenchmarkSegmentKey).Version(1)
   398  		included := make([]string, bc.numTargets)
   399  		for i := range included {
   400  			included[i] = makeEvalBenchmarkTargetUserKey(i)
   401  		}
   402  		sb.Included(included...)
   403  		excluded := make([]string, bc.numTargets)
   404  		for i := range excluded {
   405  			excluded[i] = makeEvalBenchmarkTargetUserKey(i + bc.numTargets)
   406  		}
   407  		sb.Excluded(excluded...)
   408  		sb.AddRule(ldbuilders.NewSegmentRuleBuilder().
   409  			Clauses(makeEvalBenchmarkClauses(bc.numClauses, bc.extraClauseValues, bc.operator)...))
   410  		s := sb.Build()
   411  		segment = &s
   412  	}
   413  
   414  	f := mainFlag.Build()
   415  	return &f, otherFlags, segment
   416  }
   417  
   418  // When we test prerequisite matching, we want all of the prerequisite flags to be a match, because
   419  // otherwise they will short-circuit evaluation of the main flag and we won't really be testing
   420  // anything except the first prerequisite. Since we already test rule and target matching in other
   421  // benchmarks, the prerequisites can just be fallthroughs.
   422  func makeEvalBenchmarkPrerequisites(
   423  	mainFlag *ldbuilders.FlagBuilder,
   424  	flagCounter *int,
   425  	otherFlags map[string]*ldmodel.FeatureFlag,
   426  	bc evalBenchmarkCase,
   427  	remainingDepth int,
   428  ) {
   429  	for i := 0; i < bc.prereqsWidth; i++ {
   430  		prereqBuilder := ldbuilders.NewFlagBuilder(fmt.Sprintf("flag-%d", *flagCounter)).
   431  			Version(1).
   432  			On(true).
   433  			FallthroughVariation(1).
   434  			Variations(ldvalue.Bool(false), ldvalue.Bool(true))
   435  		*flagCounter++
   436  		if remainingDepth > 1 {
   437  			makeEvalBenchmarkPrerequisites(prereqBuilder, flagCounter, otherFlags, bc, remainingDepth-1)
   438  		}
   439  		prereqFlag := prereqBuilder.Build()
   440  		otherFlags[prereqFlag.Key] = &prereqFlag
   441  		mainFlag.AddPrerequisite(prereqFlag.Key, 1)
   442  	}
   443  }
   444  

View as plain text