Pat Gavlin ece5ba0282 [snapshot] Use a newer diff package ... The version of gopls that gotextdiff is derived from is over three years old. In the intervening time, the differ used by gopls has improved tremendously, and the language has grown new features like generics. These changes use a different diff package that is derived from an up-to-date version of gopls and exposes an API that is parameterized over the storage of the text. Taken together, this allows us to use a much faster and more memory-efficient algorithm for diffing while safely avoiding string copies when invoking the differ. The more efficient algorithm operates on arbitrary slices whose elements are comparable. Naive use of this algorithm--passing byte slices in--can cause increased time spent diffing, as the sequences being compared are longer. In order to avoid this, these changes record spans of marshaled deployments as the deployments are marshaled. These spans are strings that cover the diffable elements of the deployment: its header, its resources, and its pending operations. The output of the newer algorithm is converible to the format we currently send to the service, so these changes should not require service-side changes. These changes also remove MarshalUntypedDeployment, as it is no longer necessary. These changes improve CPU time, allocation volume, and the compression ratio by 54%, 82%, and 56%, respectively. Benchmark results and analysis: httpstate ❯ go test -count=10 -run none -benchmem -bench . | tee spanned.txt httpstate ❯ benchstat unsafe-string.txt spanned.txt >stat.txt ``` │ unsafe-string.txt │ spanned.txt │ │ sec/op │ sec/op vs base │ DiffStack/1_x_2_B-10 42.17µ ± 2% 21.98µ ± 0% -47.88% (p=0.000 n=10) DiffStack/2_x_2_B-10 77.33µ ± 1% 38.56µ ± 1% -50.14% (p=0.000 n=10) DiffStack/4_x_2_B-10 165.57µ ± 0% 79.87µ ± 1% -51.76% (p=0.000 n=10) DiffStack/8_x_2_B-10 436.6µ ± 1% 197.7µ ± 1% -54.72% (p=0.000 n=10) DiffStack/16_x_2_B-10 1307.6µ ± 1% 571.0µ ± 1% -56.33% (p=0.000 n=10) DiffStack/32_x_2_B-10 4.176m ± 1% 1.776m ± 1% -57.48% (p=0.000 n=10) DiffStack/48_x_2_B-10 8.043m ± 0% 3.581m ± 1% -55.48% (p=0.000 n=10) DiffStack/64_x_2_B-10 13.303m ± 0% 5.659m ± 0% -57.46% (p=0.000 n=10) DiffStack/1_x_8.2_kB-10 96.66µ ± 0% 46.17µ ± 1% -52.23% (p=0.000 n=10) DiffStack/2_x_8.2_kB-10 287.5µ ± 0% 118.1µ ± 0% -58.92% (p=0.000 n=10) DiffStack/4_x_8.2_kB-10 794.6µ ± 0% 335.9µ ± 0% -57.72% (p=0.000 n=10) DiffStack/8_x_8.2_kB-10 2.392m ± 0% 1.122m ± 0% -53.09% (p=0.000 n=10) DiffStack/16_x_8.2_kB-10 8.571m ± 2% 4.036m ± 0% -52.91% (p=0.000 n=10) DiffStack/32_x_8.2_kB-10 31.01m ± 2% 15.16m ± 0% -51.13% (p=0.000 n=10) DiffStack/48_x_8.2_kB-10 61.06m ± 2% 30.20m ± 0% -50.53% (p=0.000 n=10) DiffStack/64_x_8.2_kB-10 98.35m ± 3% 51.48m ± 0% -47.66% (p=0.000 n=10) DiffStack/1_x_33_kB-10 233.35µ ± 2% 73.18µ ± 0% -68.64% (p=0.000 n=10) DiffStack/2_x_33_kB-10 791.4µ ± 0% 301.2µ ± 1% -61.94% (p=0.000 n=10) DiffStack/4_x_33_kB-10 2.159m ± 2% 1.067m ± 0% -50.57% (p=0.000 n=10) DiffStack/8_x_33_kB-10 7.752m ± 1% 3.707m ± 0% -52.18% (p=0.000 n=10) DiffStack/16_x_33_kB-10 26.56m ± 0% 12.55m ± 0% -52.73% (p=0.000 n=10) DiffStack/32_x_33_kB-10 90.66m ± 1% 44.21m ± 0% -51.24% (p=0.000 n=10) DiffStack/48_x_33_kB-10 187.86m ± 0% 92.91m ± 0% -50.54% (p=0.000 n=10) DiffStack/64_x_33_kB-10 326.0m ± 0% 162.1m ± 0% -50.29% (p=0.000 n=10) DiffStack/2_x_131_kB-10 2.536m ± 0% 1.050m ± 0% -58.61% (p=0.000 n=10) DiffStack/4_x_131_kB-10 7.808m ± 0% 3.470m ± 0% -55.56% (p=0.000 n=10) DiffStack/8_x_131_kB-10 24.61m ± 0% 11.70m ± 0% -52.45% (p=0.000 n=10) DiffStack/16_x_131_kB-10 83.45m ± 0% 40.93m ± 0% -50.95% (p=0.000 n=10) DiffStack/32_x_131_kB-10 298.7m ± 0% 150.0m ± 0% -49.77% (p=0.000 n=10) DiffStack/48_x_131_kB-10 648.8m ± 0% 333.7m ± 0% -48.56% (p=0.000 n=10) DiffStack/64_x_131_kB-10 1129.3m ± 0% 581.9m ± 1% -48.48% (p=0.000 n=10) DiffStack/1_x_524_kB-10 3.115m ± 0% 1.057m ± 0% -66.08% (p=0.000 n=10) DiffStack/2_x_524_kB-10 9.244m ± 0% 3.891m ± 0% -57.91% (p=0.000 n=10) DiffStack/4_x_524_kB-10 27.76m ± 0% 12.60m ± 0% -54.62% (p=0.000 n=10) DiffStack/8_x_524_kB-10 88.63m ± 0% 43.19m ± 0% -51.27% (p=0.000 n=10) DiffStack/16_x_524_kB-10 305.0m ± 0% 154.4m ± 0% -49.39% (p=0.000 n=10) DiffStackRecorded/two-large-checkpoints.json-10 46.08m ± 1% 20.50m ± 0% -55.52% (p=0.000 n=10) DiffStackRecorded/checkpoints.json-10 788.9m ± 5% 395.8m ± 0% -49.84% (p=0.000 n=10) geomean 9.742m 4.479m -54.02% │ unsafe-string.txt │ spanned.txt │ │ ratio │ ratio vs base │ DiffStack/1_x_2_B-10 700.5m ± 0% 1402.0m ± 0% +100.14% (p=0.000 n=10) DiffStack/2_x_2_B-10 1.034 ± 0% 2.206 ± 0% +113.35% (p=0.000 n=10) DiffStack/4_x_2_B-10 1.576 ± 0% 3.592 ± 0% +127.92% (p=0.000 n=10) DiffStack/8_x_2_B-10 2.883 ± 0% 6.639 ± 0% +130.28% (p=0.000 n=10) DiffStack/16_x_2_B-10 5.362 ± 0% 12.560 ± 0% +134.24% (p=0.000 n=10) DiffStack/32_x_2_B-10 9.859 ± 0% 23.710 ± 0% +140.49% (p=0.000 n=10) DiffStack/48_x_2_B-10 13.60 ± 0% 34.24 ± 0% +151.76% (p=0.000 n=10) DiffStack/64_x_2_B-10 17.56 ± 0% 41.60 ± 0% +136.90% (p=0.000 n=10) DiffStack/1_x_8.2_kB-10 950.9m ± 0% 1955.0m ± 0% +105.59% (p=0.000 n=10) DiffStack/2_x_8.2_kB-10 1.902 ± 0% 2.324 ± 0% +22.19% (p=0.000 n=10) DiffStack/4_x_8.2_kB-10 3.050 ± 0% 3.972 ± 0% +30.23% (p=0.000 n=10) DiffStack/8_x_8.2_kB-10 5.350 ± 0% 7.925 ± 0% +48.13% (p=0.000 n=10) DiffStack/16_x_8.2_kB-10 10.56 ± 0% 15.84 ± 0% +50.00% (p=0.000 n=10) DiffStack/32_x_8.2_kB-10 20.60 ± 0% 32.03 ± 0% +55.49% (p=0.000 n=10) DiffStack/48_x_8.2_kB-10 28.39 ± 0% 43.50 ± 0% +53.22% (p=0.000 n=10) DiffStack/64_x_8.2_kB-10 34.87 ± 0% 56.68 ± 0% +62.55% (p=0.000 n=10) DiffStack/1_x_33_kB-10 986.0m ± 0% 1014.0m ± 0% +2.84% (p=0.000 n=10) DiffStack/2_x_33_kB-10 1.973 ± 0% 2.331 ± 0% +18.14% (p=0.000 n=10) DiffStack/4_x_33_kB-10 2.878 ± 0% 4.561 ± 0% +58.48% (p=0.000 n=10) DiffStack/8_x_33_kB-10 5.809 ± 0% 8.511 ± 0% +46.51% (p=0.000 n=10) DiffStack/16_x_33_kB-10 10.66 ± 0% 15.09 ± 0% +41.56% (p=0.000 n=10) DiffStack/32_x_33_kB-10 18.88 ± 0% 27.75 ± 0% +46.98% (p=0.000 n=10) DiffStack/48_x_33_kB-10 26.53 ± 0% 39.66 ± 0% +49.49% (p=0.000 n=10) DiffStack/64_x_33_kB-10 35.09 ± 0% 52.54 ± 0% +49.73% (p=0.000 n=10) DiffStack/2_x_131_kB-10 1.993 ± 0% 2.665 ± 0% +33.72% (p=0.000 n=10) DiffStack/4_x_131_kB-10 3.263 ± 0% 4.426 ± 0% +35.64% (p=0.000 n=10) DiffStack/8_x_131_kB-10 5.421 ± 0% 7.662 ± 0% +41.34% (p=0.000 n=10) DiffStack/16_x_131_kB-10 9.466 ± 0% 13.670 ± 0% +44.41% (p=0.000 n=10) DiffStack/32_x_131_kB-10 17.28 ± 0% 25.35 ± 0% +46.70% (p=0.000 n=10) DiffStack/48_x_131_kB-10 25.21 ± 0% 37.57 ± 0% +49.03% (p=0.000 n=10) DiffStack/64_x_131_kB-10 33.10 ± 0% 49.30 ± 0% +48.94% (p=0.000 n=10) DiffStack/1_x_524_kB-10 1.498 ± 0% 1.999 ± 0% +33.44% (p=0.000 n=10) DiffStack/2_x_524_kB-10 1.998 ± 0% 2.666 ± 0% +33.43% (p=0.000 n=10) DiffStack/4_x_524_kB-10 3.089 ± 0% 4.285 ± 0% +38.72% (p=0.000 n=10) DiffStack/8_x_524_kB-10 5.127 ± 0% 7.399 ± 0% +44.31% (p=0.000 n=10) DiffStack/16_x_524_kB-10 9.016 ± 0% 13.220 ± 0% +46.63% (p=0.000 n=10) DiffStackRecorded/two-large-checkpoints.json-10 1.997 ± 0% 1.999 ± 0% +0.10% (p=0.000 n=10) DiffStackRecorded/checkpoints.json-10 36.60 ± 0% 40.42 ± 0% +10.44% (p=0.000 n=10) geomean 5.933 9.226 +55.52% │ unsafe-string.txt │ spanned.txt │ │ B/op │ B/op vs base │ DiffStack/1_x_2_B-10 25.64Ki ± 0% 13.82Ki ± 0% -46.08% (p=0.000 n=10) DiffStack/2_x_2_B-10 52.00Ki ± 0% 25.99Ki ± 0% -50.02% (p=0.000 n=10) DiffStack/4_x_2_B-10 120.72Ki ± 0% 52.36Ki ± 0% -56.63% (p=0.000 n=10) DiffStack/8_x_2_B-10 340.9Ki ± 0% 109.9Ki ± 0% -67.76% (p=0.000 n=10) DiffStack/16_x_2_B-10 1118.1Ki ± 0% 292.2Ki ± 0% -73.87% (p=0.000 n=10) DiffStack/32_x_2_B-10 3834.0Ki ± 0% 866.9Ki ± 0% -77.39% (p=0.000 n=10) DiffStack/48_x_2_B-10 7.608Mi ± 0% 1.688Mi ± 0% -77.81% (p=0.000 n=10) DiffStack/64_x_2_B-10 12.880Mi ± 0% 2.591Mi ± 0% -79.88% (p=0.000 n=10) DiffStack/1_x_8.2_kB-10 122.59Ki ± 0% 41.00Ki ± 0% -66.55% (p=0.000 n=10) DiffStack/2_x_8.2_kB-10 372.9Ki ± 0% 105.8Ki ± 0% -71.62% (p=0.000 n=10) DiffStack/4_x_8.2_kB-10 930.9Ki ± 0% 243.5Ki ± 0% -73.85% (p=0.000 n=10) DiffStack/8_x_8.2_kB-10 2471.1Ki ± 0% 534.0Ki ± 0% -78.39% (p=0.000 n=10) DiffStack/16_x_8.2_kB-10 7.576Mi ± 0% 1.144Mi ± 0% -84.90% (p=0.000 n=10) DiffStack/32_x_8.2_kB-10 25.445Mi ± 0% 2.624Mi ± 0% -89.69% (p=0.000 n=10) DiffStack/48_x_8.2_kB-10 50.793Mi ± 0% 4.912Mi ± 0% -90.33% (p=0.000 n=10) DiffStack/64_x_8.2_kB-10 80.106Mi ± 0% 6.215Mi ± 0% -92.24% (p=0.000 n=10) DiffStack/1_x_33_kB-10 436.08Ki ± 0% 94.80Ki ± 0% -78.26% (p=0.000 n=10) DiffStack/2_x_33_kB-10 1470.3Ki ± 0% 388.5Ki ± 0% -73.58% (p=0.000 n=10) DiffStack/4_x_33_kB-10 3556.1Ki ± 0% 889.2Ki ± 0% -75.00% (p=0.000 n=10) DiffStack/8_x_33_kB-10 10.177Mi ± 0% 1.856Mi ± 0% -81.76% (p=0.000 n=10) DiffStack/16_x_33_kB-10 30.152Mi ± 0% 3.870Mi ± 0% -87.16% (p=0.000 n=10) DiffStack/32_x_33_kB-10 92.738Mi ± 0% 8.089Mi ± 0% -91.28% (p=0.000 n=10) DiffStack/48_x_33_kB-10 186.46Mi ± 0% 14.93Mi ± 0% -91.99% (p=0.000 n=10) DiffStack/64_x_33_kB-10 312.57Mi ± 0% 17.04Mi ± 0% -94.55% (p=0.000 n=10) DiffStack/2_x_131_kB-10 5.614Mi ± 0% 1.253Mi ± 0% -77.69% (p=0.000 n=10) DiffStack/4_x_131_kB-10 13.695Mi ± 0% 2.992Mi ± 1% -78.15% (p=0.000 n=10) DiffStack/8_x_131_kB-10 35.031Mi ± 0% 6.347Mi ± 0% -81.88% (p=0.000 n=10) DiffStack/16_x_131_kB-10 96.82Mi ± 0% 13.16Mi ± 0% -86.41% (p=0.000 n=10) DiffStack/32_x_131_kB-10 295.20Mi ± 0% 26.33Mi ± 1% -91.08% (p=0.000 n=10) DiffStack/48_x_131_kB-10 604.44Mi ± 0% 48.79Mi ± 1% -91.93% (p=0.000 n=10) DiffStack/64_x_131_kB-10 999.34Mi ± 0% 53.50Mi ± 1% -94.65% (p=0.000 n=10) DiffStack/1_x_524_kB-10 9.254Mi ± 0% 1.605Mi ± 0% -82.66% (p=0.000 n=10) DiffStack/2_x_524_kB-10 23.723Mi ± 1% 4.996Mi ± 1% -78.94% (p=0.000 n=10) DiffStack/4_x_524_kB-10 56.75Mi ± 1% 11.40Mi ± 1% -79.91% (p=0.000 n=10) DiffStack/8_x_524_kB-10 141.08Mi ± 0% 24.08Mi ± 1% -82.93% (p=0.000 n=10) DiffStack/16_x_524_kB-10 381.16Mi ± 1% 49.52Mi ± 2% -87.01% (p=0.000 n=10) DiffStackRecorded/two-large-checkpoints.json-10 59.95Mi ± 0% 27.46Mi ± 0% -54.19% (p=0.000 n=10) DiffStackRecorded/checkpoints.json-10 618.57Mi ± 0% 50.42Mi ± 1% -91.85% (p=0.000 n=10) geomean 11.14Mi 1.964Mi -82.38% │ unsafe-string.txt │ spanned.txt │ │ allocs/op │ allocs/op vs base │ DiffStack/1_x_2_B-10 316.0 ± 0% 180.0 ± 0% -43.04% (p=0.000 n=10) DiffStack/2_x_2_B-10 600.0 ± 0% 291.0 ± 0% -51.50% (p=0.000 n=10) DiffStack/4_x_2_B-10 1353.0 ± 0% 519.0 ± 0% -61.64% (p=0.000 n=10) DiffStack/8_x_2_B-10 3.929k ± 0% 1.022k ± 0% -73.99% (p=0.000 n=10) DiffStack/16_x_2_B-10 12.829k ± 0% 2.214k ± 0% -82.74% (p=0.000 n=10) DiffStack/32_x_2_B-10 43.951k ± 0% 5.285k ± 0% -87.98% (p=0.000 n=10) DiffStack/48_x_2_B-10 88.816k ± 0% 9.218k ± 0% -89.62% (p=0.000 n=10) DiffStack/64_x_2_B-10 150.76k ± 0% 13.50k ± 0% -91.05% (p=0.000 n=10) DiffStack/1_x_8.2_kB-10 298.0 ± 0% 182.0 ± 0% -38.93% (p=0.000 n=10) DiffStack/2_x_8.2_kB-10 595.0 ± 0% 292.0 ± 0% -50.92% (p=0.000 n=10) DiffStack/4_x_8.2_kB-10 1300.0 ± 0% 520.0 ± 0% -60.00% (p=0.000 n=10) DiffStack/8_x_8.2_kB-10 3.342k ± 0% 1.024k ± 0% -69.36% (p=0.000 n=10) DiffStack/16_x_8.2_kB-10 10.504k ± 0% 2.222k ± 0% -78.85% (p=0.000 n=10) DiffStack/32_x_8.2_kB-10 35.934k ± 0% 5.406k ± 0% -84.96% (p=0.000 n=10) DiffStack/48_x_8.2_kB-10 71.361k ± 0% 9.185k ± 0% -87.13% (p=0.000 n=10) DiffStack/64_x_8.2_kB-10 114.48k ± 0% 13.91k ± 0% -87.85% (p=0.000 n=10) DiffStack/1_x_33_kB-10 297.5 ± 0% 180.0 ± 0% -39.50% (p=0.000 n=10) DiffStack/2_x_33_kB-10 588.0 ± 0% 293.0 ± 0% -50.17% (p=0.000 n=10) DiffStack/4_x_33_kB-10 1246.0 ± 0% 526.0 ± 0% -57.78% (p=0.000 n=10) DiffStack/8_x_33_kB-10 3.466k ± 0% 1.036k ± 0% -70.11% (p=0.000 n=10) DiffStack/16_x_33_kB-10 10.381k ± 0% 2.201k ± 0% -78.80% (p=0.000 n=10) DiffStack/32_x_33_kB-10 32.650k ± 0% 5.133k ± 0% -84.28% (p=0.000 n=10) DiffStack/48_x_33_kB-10 65.627k ± 0% 8.797k ± 0% -86.59% (p=0.000 n=10) DiffStack/64_x_33_kB-10 112.41k ± 0% 13.34k ± 0% -88.13% (p=0.000 n=10) DiffStack/2_x_131_kB-10 619.5 ± 0% 294.0 ± 0% -52.54% (p=0.000 n=10) DiffStack/4_x_131_kB-10 1369.5 ± 0% 528.0 ± 0% -61.45% (p=0.000 n=10) DiffStack/8_x_131_kB-10 3.433k ± 0% 1.029k ± 0% -70.02% (p=0.000 n=10) DiffStack/16_x_131_kB-10 9.704k ± 0% 2.170k ± 0% -77.64% (p=0.000 n=10) DiffStack/32_x_131_kB-10 30.628k ± 0% 4.985k ± 0% -83.72% (p=0.000 n=10) DiffStack/48_x_131_kB-10 63.030k ± 0% 8.613k ± 0% -86.34% (p=0.000 n=10) DiffStack/64_x_131_kB-10 106.83k ± 0% 12.93k ± 0% -87.89% (p=0.000 n=10) DiffStack/1_x_524_kB-10 343.0 ± 0% 183.0 ± 0% -46.65% (p=0.000 n=10) DiffStack/2_x_524_kB-10 648.0 ± 0% 296.0 ± 0% -54.32% (p=0.000 n=10) DiffStack/4_x_524_kB-10 1413.5 ± 0% 528.0 ± 0% -62.65% (p=0.000 n=10) DiffStack/8_x_524_kB-10 3.478k ± 0% 1.025k ± 0% -70.53% (p=0.000 n=10) DiffStack/16_x_524_kB-10 9.697k ± 0% 2.153k ± 0% -77.80% (p=0.000 n=10) DiffStackRecorded/two-large-checkpoints.json-10 512.09k ± 0% 73.64k ± 0% -85.62% (p=0.000 n=10) DiffStackRecorded/checkpoints.json-10 7236.1k ± 0% 857.6k ± 0% -88.15% (p=0.000 n=10) geomean 7.797k 1.914k -75.46% ```		2023-05-10 17:13:20 -07:00
..
snapshot_test.json	[snapshot] Use a newer diff package	2023-05-10 17:13:20 -07:00
two-large-checkpoints.json	[snapshot] Add diff benchmarks and more tests	2023-05-10 17:13:20 -07:00