Client-side apply has a pathological case with deeply nested identical objects

[DirectXMan12]

Test case

1. Strip the description fields from https://raw.githubusercontent.com/kubernetes-sigs/kubebuilder/master/docs/book/src/multiversion-tutorial/testdata/project/config/crd/bases/batch.tutorial.kubebuilder.io_cronjobs.yaml (to make it fit in an annotation)
2. kubectl apply -f the above
3. kubectl apply -f the above again

Underlying issue

Deeply nested (e.g. validation for podspec) identical issues hit a pathological case in the json-patch library's merge patch generator, which recursively traverses every sub-tree to check if two json trees are identical

Evidence

You can attach an execution trace and use go tool trace to see this for yourself

(that's me stopping the attempt after 30s, not it taking 30s total)

runtime trace call patch

diff --git a/cmd/kubectl/kubectl.go b/cmd/kubectl/kubectl.go
index 53934ac2b0..fab992ad95 100644
--- a/cmd/kubectl/kubectl.go
+++ b/cmd/kubectl/kubectl.go
@@ -21,6 +21,9 @@ import (
 	"math/rand"
 	"os"
 	"time"
+	"runtime/trace"
+	"os/signal"
+	"syscall"
 
 	"github.com/spf13/pflag"
 
@@ -33,6 +36,16 @@ import (
 )
 
 func main() {
+	traceOut, err := os.Create("/tmp/kubectl.trace")
+	if err != nil {
+		panic(err)
+	}
+	defer traceOut.Close()
+	if err := trace.Start(traceOut); err != nil {
+		panic(err)
+	}
+	defer trace.Stop()
+		
 	rand.Seed(time.Now().UnixNano())
 
 	command := cmd.NewDefaultKubectlCommand()
@@ -46,7 +59,17 @@ func main() {
 	logs.InitLogs()
 	defer logs.FlushLogs()
 
+	sigCh := make(chan os.Signal)
+	go func() {
+		<-sigCh
+		trace.Stop()
+		traceOut.Close()
+		panic("at the disco!")
+	}()
+	signal.Notify(sigCh, syscall.SIGINT, syscall.SIGTERM)
+
 	if err := command.Execute(); err != nil {
-		os.Exit(1)
+		//os.Exit(1)
+		return
 	}
 }

Potential fixes

EDIT: See below -- moving around some conditions in the jsonpatch library seems to fix things.

Also, this may be kind-of moot, since we'll be getting server-side apply, which doesn't suffer from this particular issue.

[DirectXMan12]

/assign @seans3

[seans3]

/sig cli
/area kubectl
/kind bug
/priority P2

This performance bug should be fixed by server-side apply.

[DirectXMan12]

double-edit: bug in some of my test code (thanks to @logicalhan for pointing out something was really off here), so ignore what was previously in this comment :-/ That explains one of the bizarre results. Now on to the other...

[DirectXMan12]

evanphx/json-patch#87 <-- should fix the issue. The dual traversal of maps was causing an exponential time complexity, which really only manifested seriously with lots of nested maps.

[fejta-bot]

Issues go stale after 90d of inactivity.
Mark the issue as fresh with /remove-lifecycle stale.
Stale issues rot after an additional 30d of inactivity and eventually close.

If this issue is safe to close now please do so with /close.

Send feedback to sig-testing, kubernetes/test-infra and/or fejta.
/lifecycle stale