pulumi/pkg
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
..
authhelpers make linter happy 2023-02-08 10:30:10 -08:00
backend [snapshot] Use a newer diff package 2023-05-10 17:13:20 -07:00
cmd/pulumi gRPC for GenerateProject/Program/Package 2023-05-06 13:14:59 +01:00
codegen Fix panic on component type traversal 2023-05-04 17:02:38 +02:00
engine [snapshot] Add diff benchmarks and more tests 2023-05-10 17:13:20 -07:00
graph all: Assert => Assertf 2023-03-03 14:37:43 -08:00
importer all: Reformat with gofumpt 2023-03-03 09:00:24 -08:00
operations all: Reformat with gofumpt 2023-03-03 09:00:24 -08:00
resource Fix targeted-replace and update plans. 2023-05-09 07:48:53 -07:00
secrets all: Assert => Assertf 2023-03-03 14:37:43 -08:00
testing/integration Fix failure to load Pulumi.yaml when RelativeWorkDir provided. 2023-04-26 16:14:46 -04:00
util Fix convert pcl copy 2023-04-14 22:04:50 +01:00
version duplicate version to ensure linking is properly handled 2020-03-19 12:49:34 -07:00
README.md export codegen tests for internal use (#8928) 2022-02-07 12:10:04 +01:00
go.mod [snapshot] Use a newer diff package 2023-05-10 17:13:20 -07:00
go.sum [snapshot] Use a newer diff package 2023-05-10 17:13:20 -07:00

README.md

pulumi/pkg

While pulumi/sdk maintains strict backwards compatibility guarantees, code under pkg/ is handled more informally: while breaking changes are still discouraged they may happen when they make sense.