Repository: rancher/fleet
Pull request #1915 (2023-10-30 13:06:42)

Replace json-based implementation of DeepCopy on GenericMap
<!-- Specify the issue ID that this pull request is solving -->
Relates to #1842

The current `GenericMap`'s `DeepCopy` method is calling `wrangler/pkg/convert.ToObj` in order to be a copy of the map. This function uses `encoding/json` to serialize and deserialize in order to get a new independent copy of the entire map. However, since `encoding/json` uses reflection, this approach is more CPU-intensive than other alternatives, like using native recursion.

<p align="center">
  <img src="https://github.com/rancher/fleet/assets/4057165/3ea175bc-1645-406b-ace7-f913c2405f87" width="90%">
</p>
This shows how up to a 9% of the time from a 30s profile is spent on `convert.ToObj`.
Also, I ran a simple benchmark to get an estimation on how both implementations behave:

```
BenchmarkDeepCopy/json-small-12         	  160172	      7147 ns/op
BenchmarkDeepCopy/native-small-12       	 1204741	       994.6 ns/op
BenchmarkDeepCopy/json-big-12           	     781	   1510766 ns/op
BenchmarkDeepCopy/native-big-12         	    4351	    254641 ns/op
BenchmarkDeepCopy/json-huge-12          	       4	 299542114 ns/op
BenchmarkDeepCopy/native-huge-12        	      32	  36687546 ns/op
```

where:
- `small` is the contents of a sample `values.yaml` with just a handful of keys.
- `big` is an arbitrary ~280KB JSON file
- `huge` is a ~25MB JSON file I found on GitHub with random data

This means that using this implementation could be one order of magnitude faster than using `convert.ToObj` , hence causing an speedup proportional to the amount and size of `GenericMap`s used.

## Test

To test this pull request, you can run the following commands:

```shell
cd pkg/apis/fleet.cattle.io/v1alpha1/
go test
```

## Additional Information

### Trade-off

Possible none, just the chance of introducing a bug for a non-tested corner case.

<!-- Please describe, if any, the trade-offs that you found acceptable in this pull request -->

### Potential improvement

Review other possible usages of `convert.ToObj` and migrate to this approach if applicable.

<!-- Please describe, if any, potential improvement that you are envisioning -->


<!-- Please Uncomment following block if looking for QA validation

## Additional QA
### Issue: <link the issue or issues this PR resolves here>
< If your PR depends on changes from another pr link them here and describe why they are needed on your solution section. >
 
### Problem
< Describe the root cause of the issue you are resolving. This may include what behavior is observed and why it is not desirable. If this is a new feature describe why we need this feature and how it will be used. >
 
### Solution
< Describe what you changed to fix the issue. Relate your changes back to the original issue / feature and explain why this addresses the issue.>
 
### Testing
< Note: Confirm if the repro steps in the GitHub issue are valid, if not, please update the issue with accurate repro steps. >

### Engineering Testing
#### Manual Testing
< Describe what manual testing you did (if no testing was done, explain why). >

#### Automated Testing
<If you added/updated unit/integration/validation tests, describe what cases they cover and do not cover. >

### QA Testing Considerations
< Highlight areas or (additional) cases that QA should test w.r.t a fresh install as well as the upgrade scenarios >
 
#### Regressions Considerations
< Dedicated section to specifically call out any areas that with higher chance of regressions caused by this change, include estimation of probability of regressions >

-->


aruiz14: > LGTM, thanks!
> 
> > This shows how up to a 9% of the time from a 30s profile is spent on `convert.ToObj`
> 
> Do we know how many times this method was called? It looks to me like if this method is impacting the performance it's because it's being called more times than it should

Sadly, CPU profiles do not contain that information, only a measure of time spent in each method. Nonetheless, I could observe many parts of the code (including generated controllers' code) perform calls to `DeepCopy` on top-level entities, which ultimately end up executing this code if any nested field contain a `GenericMap`.

Patch:
diff --git a/pkg/apis/fleet.cattle.io/v1alpha1/generic_map.go b/pkg/apis/fleet.cattle.io/v1alpha1/generic_map.go
new file mode 100644
index 00000000..15a303e4
--- /dev/null
+++ b/pkg/apis/fleet.cattle.io/v1alpha1/generic_map.go
@@ -0,0 +1,63 @@
+package v1alpha1
+
+import (
+	"encoding/json"
+)
+
+type GenericMap struct {
+	Data map[string]interface{} `json:"-"`
+}
+
+func (in GenericMap) MarshalJSON() ([]byte, error) {
+	return json.Marshal(in.Data)
+}
+
+func (in *GenericMap) UnmarshalJSON(data []byte) error {
+	in.Data = map[string]interface{}{}
+	return json.Unmarshal(data, &in.Data)
+}
+
+func (in *GenericMap) DeepCopyInto(out *GenericMap) {
+	out.Data = make(map[string]interface{}, len(in.Data))
+	deepCopyMap(in.Data, out.Data)
+}
+
+// deepCopyMap will recursively copy each entry from src into dest, ensuring that nested maps and slices are copied as well
+//
+// NOTE: The implementation relies on GenericMap's data being loaded from a JSON or YAML via Unmarshal, which produces map[string]interface{} and []interface{} types.
+// The recursive copy won't work with other variants as pointers or specific value types.
+func deepCopyMap(src, dest map[string]interface{}) {
+	for key := range src {
+		switch value := src[key].(type) {
+		case map[string]interface{}:
+			destValue := make(map[string]interface{}, len(value))
+			deepCopyMap(value, destValue)
+			dest[key] = destValue
+		case []interface{}:
+			destValue := make([]interface{}, len(value))
+			deepCopySlice(value, destValue)
+			dest[key] = destValue
+		default:
+			dest[key] = value
+		}
+	}
+}
+
+// deepCopySlice will recursively copy each entry from src into dest, ensuring that nested maps and slices are copied as well
+// It assumes that both slices have the same capacity.
+func deepCopySlice(src, dest []interface{}) {
+	for i := range src {
+		switch value := src[i].(type) {
+		case map[string]interface{}:
+			destValue := make(map[string]interface{}, len(value))
+			deepCopyMap(value, destValue)
+			dest[i] = destValue
+		case []interface{}:
+			destValue := make([]interface{}, len(value))
+			deepCopySlice(value, destValue)
+			dest[i] = destValue
+		default:
+			dest[i] = value
+		}
+	}
+}
diff --git a/pkg/apis/fleet.cattle.io/v1alpha1/values.go b/pkg/apis/fleet.cattle.io/v1alpha1/values.go
deleted file mode 100644
index cc1b2ee9..00000000
--- a/pkg/apis/fleet.cattle.io/v1alpha1/values.go
+++ /dev/null
@@ -1,27 +0,0 @@
-package v1alpha1
-
-import (
-	"encoding/json"
-
-	"github.com/rancher/wrangler/v2/pkg/data/convert"
-)
-
-type GenericMap struct {
-	Data map[string]interface{} `json:"-"`
-}
-
-func (in GenericMap) MarshalJSON() ([]byte, error) {
-	return json.Marshal(in.Data)
-}
-
-func (in *GenericMap) UnmarshalJSON(data []byte) error {
-	in.Data = map[string]interface{}{}
-	return json.Unmarshal(data, &in.Data)
-}
-
-func (in *GenericMap) DeepCopyInto(out *GenericMap) {
-	out.Data = map[string]interface{}{}
-	if err := convert.ToObj(in.Data, &out.Data); err != nil {
-		panic(err)
-	}
-}


Test patch:
diff --git a/pkg/apis/fleet.cattle.io/v1alpha1/generic_map_test.go b/pkg/apis/fleet.cattle.io/v1alpha1/generic_map_test.go
new file mode 100644
index 00000000..a8d56ff1
--- /dev/null
+++ b/pkg/apis/fleet.cattle.io/v1alpha1/generic_map_test.go
@@ -0,0 +1,92 @@
+package v1alpha1
+
+import (
+	"testing"
+
+	"k8s.io/apimachinery/pkg/api/equality"
+)
+
+func Test_deepCopyMap(t *testing.T) {
+	type fixture func(map[string]any)
+	tests := []struct {
+		name string
+		src  map[string]interface{}
+		// perform changes after creation and ensure the original does not change
+		fixtures []fixture
+	}{
+		{name: "copies top-level keys", src: map[string]interface{}{
+			"str":     "value",
+			"list":    []any{1, "dos", true},
+			"boolean": false,
+		}},
+		{name: "copies nested values", src: map[string]interface{}{
+			"first": map[string]any{
+				"second": map[string]any{
+					"third": map[string]any{
+						"str":     "value",
+						"boolean": false,
+					},
+					"list":    []any{1, "dos", true},
+					"boolean": false,
+				},
+			},
+		}},
+		{name: "changing top-level values preserves the original map", src: map[string]interface{}{
+			"str":      "value",
+			"number":   3,
+			"boolean":  false,
+			"todelete": "foo",
+		}, fixtures: []fixture{
+			func(m map[string]interface{}) {
+				m["str"] = "anotherValue"
+			},
+			func(m map[string]interface{}) {
+				m["number"] = "anotherValue"
+			},
+			func(m map[string]interface{}) {
+				m["boolean"] = true
+			},
+			func(m map[string]interface{}) {
+				m["boolean"] = "notanymore"
+			},
+			func(m map[string]interface{}) {
+				delete(m, "todelete")
+			},
+		}},
+		{name: "modifying maps inside a slice preserves the original map", src: map[string]interface{}{
+			"list": []any{map[string]any{
+				"original": "value",
+			}},
+		}, fixtures: []fixture{
+			func(m map[string]interface{}) {
+				list := m["list"].([]any)
+				mapInList := list[0].(map[string]any)
+				mapInList["original"] = "newvalue"
+			},
+			func(m map[string]interface{}) {
+				list := m["list"].([]any)
+				mapInList := list[0].(map[string]any)
+				mapInList["modified"] = "another"
+			},
+		}},
+	}
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			res := map[string]interface{}{}
+			deepCopyMap(tt.src, res)
+
+			if got, want := res, tt.src; !equality.Semantic.DeepEqual(got, want) {
+				t.Errorf("the produced copy is not identical, got: %s, want: %s", got, want)
+			}
+
+			for _, modify := range tt.fixtures {
+				modify(res)
+				if equality.Semantic.DeepEqual(tt.src, res) {
+					t.Errorf("original was modified after modifying the copy")
+				}
+				// Apply same modifications to the original after comparing, to only test the delta
+				modify(tt.src)
+			}
+		})
+	}
+}