opt: reduce allocations in Implicator and JoinOrderBuilder by mgartner · Pull Request #54159 · cockroachdb/cockroach

mgartner · 2020-09-10T01:25:15Z

partialidx: lazily initialize the implicator constraint cache

This commit makes the constructing of the Implicator's constrain cache
map lazy. Instead of making the map in the Init method, it is made
only when it is needed.

This fixes performance regressions in microbenchmarks.

name                                  old time/op  new time/op  delta
Phases/kv-read-const/Normalize-16      170ns ± 0%   139ns ± 0%  -18.66%  (p=0.008 n=5+5)
Phases/kv-read-const/OptBuild-16       173ns ± 1%   141ns ± 1%  -18.38%  (p=0.008 n=5+5)
Phases/kv-read-const/Explore-16        183ns ± 1%   151ns ± 0%  -17.70%  (p=0.008 n=5+5)
Phases/kv-read-const/ExecBuild-16      674ns ± 2%   636ns ± 1%   -5.58%  (p=0.008 n=5+5)
Phases/kv-read/ExecBuild-16           13.3µs ± 1%  13.1µs ± 1%   -1.78%  (p=0.008 n=5+5)
Phases/tpcc-delivery/ExecBuild-16     29.4µs ± 1%  28.9µs ± 0%   -1.64%  (p=0.016 n=5+4)
Phases/tpcc-stock-level/Explore-16     153µs ± 1%   151µs ± 1%   -1.24%  (p=0.008 n=5+5)
Phases/kv-read-no-prep/Explore-16     42.3µs ± 1%  41.9µs ± 0%   -0.85%  (p=0.008 n=5+5)
Phases/tpcc-delivery/OptBuild-16      12.1µs ± 1%  12.1µs ± 0%   -0.65%  (p=0.032 n=5+5)
Phases/kv-read/Parse-16               2.49ns ± 1%  2.48ns ± 0%     ~     (p=0.413 n=5+4)
Phases/kv-read/OptBuild-16            6.46µs ± 2%  6.44µs ± 1%     ~     (p=0.841 n=5+5)
Phases/kv-read/Normalize-16           6.48µs ± 3%  6.48µs ± 2%     ~     (p=1.000 n=5+5)
Phases/kv-read/Explore-16             12.1µs ± 1%  11.9µs ± 2%     ~     (p=0.056 n=5+5)
Phases/kv-read-no-prep/OptBuild-16    32.4µs ± 3%  32.2µs ± 1%     ~     (p=1.000 n=5+5)
Phases/kv-read-no-prep/Normalize-16   34.9µs ± 1%  34.7µs ± 2%     ~     (p=0.222 n=5+5)
Phases/kv-read-no-prep/ExecBuild-16   44.0µs ± 3%  43.7µs ± 1%     ~     (p=0.310 n=5+5)
Phases/kv-read-const/Parse-16         2.60ns ± 1%  2.60ns ± 1%     ~     (p=0.643 n=5+5)
Phases/tpcc-new-order/Normalize-16    12.8µs ± 1%  13.9µs ±10%     ~     (p=0.690 n=5+5)
Phases/tpcc-new-order/ExecBuild-16    38.5µs ± 1%  38.6µs ± 2%     ~     (p=1.000 n=5+5)
Phases/tpcc-delivery/Parse-16         2.55ns ± 1%  2.56ns ± 1%     ~     (p=0.921 n=5+5)
Phases/tpcc-delivery/Normalize-16     12.6µs ± 2%  12.5µs ± 1%     ~     (p=0.151 n=5+5)
Phases/tpcc-delivery/Explore-16       28.0µs ± 2%  27.6µs ± 1%     ~     (p=0.063 n=5+5)
Phases/tpcc-stock-level/OptBuild-16   52.8µs ± 1%  52.9µs ± 1%     ~     (p=1.000 n=5+5)
Phases/tpcc-stock-level/Normalize-16  53.7µs ± 1%  53.7µs ± 1%     ~     (p=1.000 n=5+5)
Phases/tpcc-stock-level/ExecBuild-16   160µs ± 1%   161µs ± 1%     ~     (p=0.222 n=5+5)
Phases/tpcc-new-order/Explore-16      36.2µs ± 0%  36.7µs ± 1%   +1.47%  (p=0.016 n=4+5)
Phases/kv-read-no-prep/Parse-16       12.6µs ± 1%  12.8µs ± 1%   +1.58%  (p=0.016 n=4+5)
Phases/tpcc-new-order/Parse-16        2.58ns ± 1%  2.67ns ± 7%   +3.33%  (p=0.048 n=5+5)
Phases/tpcc-stock-level/Parse-16      2.52ns ± 1%  2.63ns ± 4%   +4.29%  (p=0.016 n=5+5)
Phases/tpcc-new-order/OptBuild-16     13.0µs ± 1%  14.7µs ± 2%  +12.50%  (p=0.008 n=5+5)

Release note: None

opt: embed JoinOrderBuilder in Optimizer

This commit embeds the JoinOrderBuilder in the Optimizer struct. This
avoids allocating a new JoinOrderBuilder on the heap every time
Optimizer.Init is called.

BenchmarkPhase microbenchmarks comparing the current master branch to
this commit:

name                                  old time/op  new time/op  delta
Phases/kv-read-const/Normalize-16      171ns ± 1%    77ns ± 1%  -55.11%  (p=0.008 n=5+5)
Phases/kv-read-const/OptBuild-16       175ns ± 1%    79ns ± 2%  -54.83%  (p=0.008 n=5+5)
Phases/kv-read-const/Explore-16        189ns ± 7%    89ns ± 0%  -53.14%  (p=0.008 n=5+5)
Phases/tpcc-new-order/OptBuild-16     16.6µs ± 6%  12.7µs ± 2%  -23.47%  (p=0.008 n=5+5)
Phases/tpcc-new-order/Normalize-16    14.7µs ± 8%  12.4µs ± 1%  -15.39%  (p=0.008 n=5+5)
Phases/kv-read-const/ExecBuild-16      687ns ± 4%   592ns ± 1%  -13.89%  (p=0.008 n=5+5)
Phases/tpcc-new-order/Parse-16        2.94ns ± 8%  2.58ns ± 2%  -12.23%  (p=0.008 n=5+5)
Phases/tpcc-delivery/Parse-16         2.86ns ± 8%  2.54ns ± 1%  -11.33%  (p=0.008 n=5+5)
Phases/tpcc-new-order/ExecBuild-16    43.0µs ±10%  38.6µs ± 0%  -10.21%  (p=0.016 n=5+4)
Phases/tpcc-new-order/Explore-16      39.0µs ± 3%  36.6µs ± 0%   -6.12%  (p=0.008 n=5+5)
Phases/tpcc-delivery/OptBuild-16      12.4µs ± 1%  12.0µs ± 0%   -3.49%  (p=0.008 n=5+5)
Phases/kv-read/ExecBuild-16           13.4µs ± 0%  12.9µs ± 0%   -3.37%  (p=0.008 n=5+5)
Phases/kv-read/Explore-16             12.1µs ± 1%  11.7µs ± 2%   -3.04%  (p=0.008 n=5+5)
Phases/tpcc-delivery/Normalize-16     12.8µs ± 1%  12.4µs ± 1%   -3.00%  (p=0.008 n=5+5)
Phases/kv-read-no-prep/ExecBuild-16   44.1µs ± 2%  43.2µs ± 1%   -2.16%  (p=0.008 n=5+5)
Phases/kv-read/Normalize-16           6.48µs ± 1%  6.36µs ± 1%   -1.73%  (p=0.008 n=5+5)
Phases/kv-read-no-prep/Explore-16     42.6µs ± 1%  41.9µs ± 1%   -1.55%  (p=0.032 n=5+5)
Phases/tpcc-delivery/ExecBuild-16     29.5µs ± 1%  29.1µs ± 0%   -1.41%  (p=0.008 n=5+5)
Phases/kv-read-no-prep/OptBuild-16    32.2µs ± 0%  31.7µs ± 1%   -1.34%  (p=0.008 n=5+5)
Phases/kv-read-no-prep/Normalize-16   34.8µs ± 1%  34.4µs ± 1%   -1.25%  (p=0.016 n=5+4)
Phases/tpcc-stock-level/OptBuild-16   53.1µs ± 0%  52.7µs ± 0%   -0.83%  (p=0.016 n=5+5)
Phases/kv-read/Parse-16               2.49ns ± 0%  2.49ns ± 1%     ~     (p=0.952 n=4+5)
Phases/kv-read/OptBuild-16            6.48µs ± 0%  6.44µs ± 1%     ~     (p=0.310 n=5+5)
Phases/kv-read-no-prep/Parse-16       12.7µs ± 2%  12.7µs ± 1%     ~     (p=0.508 n=5+5)
Phases/kv-read-const/Parse-16         2.59ns ± 1%  2.59ns ± 1%     ~     (p=0.857 n=5+5)
Phases/tpcc-delivery/Explore-16       27.9µs ± 0%  27.9µs ± 2%     ~     (p=0.310 n=5+5)
Phases/tpcc-stock-level/Parse-16      2.57ns ± 2%  2.54ns ± 3%     ~     (p=0.254 n=5+5)
Phases/tpcc-stock-level/Normalize-16  53.8µs ± 0%  53.5µs ± 2%     ~     (p=0.151 n=5+5)
Phases/tpcc-stock-level/Explore-16     153µs ± 0%   152µs ± 3%     ~     (p=0.151 n=5+5)
Phases/tpcc-stock-level/ExecBuild-16   162µs ± 1%   161µs ± 1%     ~     (p=0.095 n=5+5)

Release note: None

cockroach-teamcity · 2020-09-10T01:25:22Z

This change is

This commit makes the constructing of the Implicator's constrain cache map lazy. Instead of making the map in the `Init` method, it is made only when it is needed. This fixes performance regressions in microbenchmarks. name old time/op new time/op delta Phases/kv-read-const/Normalize-16 170ns ± 0% 139ns ± 0% -18.66% (p=0.008 n=5+5) Phases/kv-read-const/OptBuild-16 173ns ± 1% 141ns ± 1% -18.38% (p=0.008 n=5+5) Phases/kv-read-const/Explore-16 183ns ± 1% 151ns ± 0% -17.70% (p=0.008 n=5+5) Phases/kv-read-const/ExecBuild-16 674ns ± 2% 636ns ± 1% -5.58% (p=0.008 n=5+5) Phases/kv-read/ExecBuild-16 13.3µs ± 1% 13.1µs ± 1% -1.78% (p=0.008 n=5+5) Phases/tpcc-delivery/ExecBuild-16 29.4µs ± 1% 28.9µs ± 0% -1.64% (p=0.016 n=5+4) Phases/tpcc-stock-level/Explore-16 153µs ± 1% 151µs ± 1% -1.24% (p=0.008 n=5+5) Phases/kv-read-no-prep/Explore-16 42.3µs ± 1% 41.9µs ± 0% -0.85% (p=0.008 n=5+5) Phases/tpcc-delivery/OptBuild-16 12.1µs ± 1% 12.1µs ± 0% -0.65% (p=0.032 n=5+5) Phases/kv-read/Parse-16 2.49ns ± 1% 2.48ns ± 0% ~ (p=0.413 n=5+4) Phases/kv-read/OptBuild-16 6.46µs ± 2% 6.44µs ± 1% ~ (p=0.841 n=5+5) Phases/kv-read/Normalize-16 6.48µs ± 3% 6.48µs ± 2% ~ (p=1.000 n=5+5) Phases/kv-read/Explore-16 12.1µs ± 1% 11.9µs ± 2% ~ (p=0.056 n=5+5) Phases/kv-read-no-prep/OptBuild-16 32.4µs ± 3% 32.2µs ± 1% ~ (p=1.000 n=5+5) Phases/kv-read-no-prep/Normalize-16 34.9µs ± 1% 34.7µs ± 2% ~ (p=0.222 n=5+5) Phases/kv-read-no-prep/ExecBuild-16 44.0µs ± 3% 43.7µs ± 1% ~ (p=0.310 n=5+5) Phases/kv-read-const/Parse-16 2.60ns ± 1% 2.60ns ± 1% ~ (p=0.643 n=5+5) Phases/tpcc-new-order/Normalize-16 12.8µs ± 1% 13.9µs ±10% ~ (p=0.690 n=5+5) Phases/tpcc-new-order/ExecBuild-16 38.5µs ± 1% 38.6µs ± 2% ~ (p=1.000 n=5+5) Phases/tpcc-delivery/Parse-16 2.55ns ± 1% 2.56ns ± 1% ~ (p=0.921 n=5+5) Phases/tpcc-delivery/Normalize-16 12.6µs ± 2% 12.5µs ± 1% ~ (p=0.151 n=5+5) Phases/tpcc-delivery/Explore-16 28.0µs ± 2% 27.6µs ± 1% ~ (p=0.063 n=5+5) Phases/tpcc-stock-level/OptBuild-16 52.8µs ± 1% 52.9µs ± 1% ~ (p=1.000 n=5+5) Phases/tpcc-stock-level/Normalize-16 53.7µs ± 1% 53.7µs ± 1% ~ (p=1.000 n=5+5) Phases/tpcc-stock-level/ExecBuild-16 160µs ± 1% 161µs ± 1% ~ (p=0.222 n=5+5) Phases/tpcc-new-order/Explore-16 36.2µs ± 0% 36.7µs ± 1% +1.47% (p=0.016 n=4+5) Phases/kv-read-no-prep/Parse-16 12.6µs ± 1% 12.8µs ± 1% +1.58% (p=0.016 n=4+5) Phases/tpcc-new-order/Parse-16 2.58ns ± 1% 2.67ns ± 7% +3.33% (p=0.048 n=5+5) Phases/tpcc-stock-level/Parse-16 2.52ns ± 1% 2.63ns ± 4% +4.29% (p=0.016 n=5+5) Phases/tpcc-new-order/OptBuild-16 13.0µs ± 1% 14.7µs ± 2% +12.50% (p=0.008 n=5+5) Release note: None

RaduBerinde · 2020-09-10T03:48:17Z

Can you also make the other fix I mentioned in another commit? (making JoinOrderBuilder a non-pointer member of Optimizer). Would be easier to backport a single PR.

This commit embeds the JoinOrderBuilder in the Optimizer struct. This avoids allocating a new JoinOrderBuilder on the heap every time `Optimizer.Init` is called. BenchmarkPhase microbenchmarks comparing the current master branch to this commit: name old time/op new time/op delta Phases/kv-read-const/Normalize-16 171ns ± 1% 77ns ± 1% -55.11% (p=0.008 n=5+5) Phases/kv-read-const/OptBuild-16 175ns ± 1% 79ns ± 2% -54.83% (p=0.008 n=5+5) Phases/kv-read-const/Explore-16 189ns ± 7% 89ns ± 0% -53.14% (p=0.008 n=5+5) Phases/tpcc-new-order/OptBuild-16 16.6µs ± 6% 12.7µs ± 2% -23.47% (p=0.008 n=5+5) Phases/tpcc-new-order/Normalize-16 14.7µs ± 8% 12.4µs ± 1% -15.39% (p=0.008 n=5+5) Phases/kv-read-const/ExecBuild-16 687ns ± 4% 592ns ± 1% -13.89% (p=0.008 n=5+5) Phases/tpcc-new-order/Parse-16 2.94ns ± 8% 2.58ns ± 2% -12.23% (p=0.008 n=5+5) Phases/tpcc-delivery/Parse-16 2.86ns ± 8% 2.54ns ± 1% -11.33% (p=0.008 n=5+5) Phases/tpcc-new-order/ExecBuild-16 43.0µs ±10% 38.6µs ± 0% -10.21% (p=0.016 n=5+4) Phases/tpcc-new-order/Explore-16 39.0µs ± 3% 36.6µs ± 0% -6.12% (p=0.008 n=5+5) Phases/tpcc-delivery/OptBuild-16 12.4µs ± 1% 12.0µs ± 0% -3.49% (p=0.008 n=5+5) Phases/kv-read/ExecBuild-16 13.4µs ± 0% 12.9µs ± 0% -3.37% (p=0.008 n=5+5) Phases/kv-read/Explore-16 12.1µs ± 1% 11.7µs ± 2% -3.04% (p=0.008 n=5+5) Phases/tpcc-delivery/Normalize-16 12.8µs ± 1% 12.4µs ± 1% -3.00% (p=0.008 n=5+5) Phases/kv-read-no-prep/ExecBuild-16 44.1µs ± 2% 43.2µs ± 1% -2.16% (p=0.008 n=5+5) Phases/kv-read/Normalize-16 6.48µs ± 1% 6.36µs ± 1% -1.73% (p=0.008 n=5+5) Phases/kv-read-no-prep/Explore-16 42.6µs ± 1% 41.9µs ± 1% -1.55% (p=0.032 n=5+5) Phases/tpcc-delivery/ExecBuild-16 29.5µs ± 1% 29.1µs ± 0% -1.41% (p=0.008 n=5+5) Phases/kv-read-no-prep/OptBuild-16 32.2µs ± 0% 31.7µs ± 1% -1.34% (p=0.008 n=5+5) Phases/kv-read-no-prep/Normalize-16 34.8µs ± 1% 34.4µs ± 1% -1.25% (p=0.016 n=5+4) Phases/tpcc-stock-level/OptBuild-16 53.1µs ± 0% 52.7µs ± 0% -0.83% (p=0.016 n=5+5) Phases/kv-read/Parse-16 2.49ns ± 0% 2.49ns ± 1% ~ (p=0.952 n=4+5) Phases/kv-read/OptBuild-16 6.48µs ± 0% 6.44µs ± 1% ~ (p=0.310 n=5+5) Phases/kv-read-no-prep/Parse-16 12.7µs ± 2% 12.7µs ± 1% ~ (p=0.508 n=5+5) Phases/kv-read-const/Parse-16 2.59ns ± 1% 2.59ns ± 1% ~ (p=0.857 n=5+5) Phases/tpcc-delivery/Explore-16 27.9µs ± 0% 27.9µs ± 2% ~ (p=0.310 n=5+5) Phases/tpcc-stock-level/Parse-16 2.57ns ± 2% 2.54ns ± 3% ~ (p=0.254 n=5+5) Phases/tpcc-stock-level/Normalize-16 53.8µs ± 0% 53.5µs ± 2% ~ (p=0.151 n=5+5) Phases/tpcc-stock-level/Explore-16 153µs ± 0% 152µs ± 3% ~ (p=0.151 n=5+5) Phases/tpcc-stock-level/ExecBuild-16 162µs ± 1% 161µs ± 1% ~ (p=0.095 n=5+5) Release note: None

RaduBerinde · 2020-09-10T16:54:04Z

Thank you sir, LGTM!

mgartner · 2020-09-10T17:45:11Z

bors r=RaduBerinde

craig · 2020-09-10T19:03:46Z

Build succeeded:

GitHub CI (Cockroach)

mgartner requested review from RaduBerinde and rytaft September 10, 2020 01:25

mgartner requested a review from a team as a code owner September 10, 2020 01:25

mgartner mentioned this pull request Sep 10, 2020

opt: 20.2 release checklist #46599

Closed

8 tasks

mgartner force-pushed the lazy-init-constraint-cache branch from 489056c to 45a277b Compare September 10, 2020 01:45

mgartner changed the title ~~partialidx: lazily initialize the implicator constraint cache~~ opt: reduce allocations in Implicator and JoinOrderBuilder Sep 10, 2020

craig bot merged commit 8547a97 into cockroachdb:master Sep 10, 2020

mgartner deleted the lazy-init-constraint-cache branch September 10, 2020 19:46

mgartner mentioned this pull request Sep 10, 2020

release-20.2: opt: reduce allocations in Implicator and JoinOrderBuilder #54214

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

opt: reduce allocations in Implicator and JoinOrderBuilder#54159

opt: reduce allocations in Implicator and JoinOrderBuilder#54159
craig[bot] merged 2 commits intocockroachdb:masterfrom
mgartner:lazy-init-constraint-cache

mgartner commented Sep 10, 2020 •

edited

Loading

Uh oh!

cockroach-teamcity commented Sep 10, 2020

Uh oh!

RaduBerinde commented Sep 10, 2020

Uh oh!

RaduBerinde commented Sep 10, 2020

Uh oh!

mgartner commented Sep 10, 2020

Uh oh!

craig bot commented Sep 10, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Conversation

mgartner commented Sep 10, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

partialidx: lazily initialize the implicator constraint cache

opt: embed JoinOrderBuilder in Optimizer

Uh oh!

cockroach-teamcity commented Sep 10, 2020

Uh oh!

RaduBerinde commented Sep 10, 2020

Uh oh!

RaduBerinde commented Sep 10, 2020

Uh oh!

mgartner commented Sep 10, 2020

Uh oh!

craig bot commented Sep 10, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

mgartner commented Sep 10, 2020 •

edited

Loading