mirror of https://github.com/pulumi/pulumi.git
ece5ba0282
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%
```
|
||
|---|---|---|
| .. | ||
| display | ||
| filestate | ||
| httpstate | ||
| state | ||
| apply.go | ||
| apply_test.go | ||
| backend.go | ||
| backend_test.go | ||
| doc.go | ||
| errors.go | ||
| mock.go | ||
| policypack.go | ||
| query.go | ||
| snapshot.go | ||
| snapshot_test.go | ||
| stack.go | ||
| updates.go | ||
| watch.go | ||