klogr: optimize trimDuplicates

[pohly]

/kind feature

Describe the solution you'd like

This function looks very complex and probably does a lot of memory allocations in its append calls:

klog/klogr/klogr.go

Lines 73 to 116 in e7e4115

	// trimDuplicates will deduplicate elements provided in multiple KV tuple
	// slices, whilst maintaining the distinction between where the items are
	// contained.
	func trimDuplicates(kvLists ...[]interface{}) [][]interface{} {
	// maintain a map of all seen keys
	seenKeys := map[interface{}]struct{}{}
	// build the same number of output slices as inputs
	outs := make([][]interface{}, len(kvLists))
	// iterate over the input slices backwards, as 'later' kv specifications
	// of the same key will take precedence over earlier ones
	for i := len(kvLists) - 1; i >= 0; i-- {
	// initialise this output slice
	outs[i] = []interface{}{}
	// obtain a reference to the kvList we are processing
	kvList := kvLists[i]
	// start iterating at len(kvList) - 2 (i.e. the 2nd last item) for
	// slices that have an even number of elements.
	// We add (len(kvList) % 2) here to handle the case where there is an
	// odd number of elements in a kvList.
	// If there is an odd number, then the last element in the slice will
	// have the value 'null'.
	for i2 := len(kvList) - 2 + (len(kvList) % 2); i2 >= 0; i2 -= 2 {
	k := kvList[i2]
	// if we have already seen this key, do not include it again
	if _, ok := seenKeys[k]; ok {
	continue
	}
	// make a note that we've observed a new key
	seenKeys[k] = struct{}{}
	// attempt to obtain the value of the key
	var v interface{}
	// i2+1 should only ever be out of bounds if we handling the first
	// iteration over a slice with an odd number of elements
	if i2+1 < len(kvList) {
	v = kvList[i2+1]
	}
	// add this KV tuple to the *start* of the output list to maintain
	// the original order as we are iterating over the slice backwards
	outs[i] = append([]interface{}{k, v}, outs[i]...)
	}
	}
	return outs
	}

It removes duplicates also from the parameters of a call, something that the static logcheck utility can warn about. Therefore a simpler implementation which only removes obsolete entries from a prior WithValues should be sufficient.

Code was optimized in PR #324. Left todo: static code analysis.

[pohly]

/assign

[k8s-triage-robot]

The Kubernetes project currently lacks enough contributors to adequately respond to all issues and PRs.

This bot triages issues and PRs according to the following rules:

• After 90d of inactivity, lifecycle/stale is applied
• After 30d of inactivity since lifecycle/stale was applied, lifecycle/rotten is applied
• After 30d of inactivity since lifecycle/rotten was applied, the issue is closed

You can:

• Mark this issue or PR as fresh with /remove-lifecycle stale
• Mark this issue or PR as rotten with /lifecycle rotten
• Close this issue or PR with /close
• Offer to help out with Issue Triage

Please send feedback to sig-contributor-experience at kubernetes/community.

/lifecycle stale

[pohly]

/remove-lifecycle stale

[pohly]

The updated implementation no longer de-duplicates keys that get passed in the same call (WithValues, InfoS, etc.). logcheck should get extended to detect such duplicate keys:

klog/hack/tools/logcheck/pkg/logcheck.go

Lines 325 to 326 in 7a827a0

	// isKeysValid check if all keys in keyAndValues is string type
	func isKeysValid(keyValues []ast.Expr, fun ast.Expr, pass *analysis.Pass, funName string) {

[pohly]

Resolved by PR #324

/close

[k8s-ci-robot]

@pohly: Closing this issue.

In response to this:

Resolved by PR #324

/close

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes/test-infra repository.