Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

expvar: improve Map.addKey for large number of keys #31418

Closed
wants to merge 2 commits into from
Closed

expvar: improve Map.addKey for large number of keys #31418

wants to merge 2 commits into from

Conversation

ShiKaiWi
Copy link
Contributor

The existing implementation has poor performance for large number of
keys because it chooses to append the new key to the sorted keys array
and sort the new array again.

The improvement tries to utilize the sorted keys array by searching the
index and doing an insertion if any. It also fixes an error that
duplicate keys may be inserted in high concurrent scenes.

Fixes #31414

@googlebot googlebot added the cla: yes Used by googlebot to label PRs as having a valid CLA. The text of this label should not change. label Apr 11, 2019
@ShiKaiWi
Copy link
Contributor Author

benchmark(old)

goos: darwin
goarch: amd64
pkg: std/expvar
BenchmarkMapSet-4                               20000000                96.4 ns/op            32 B/op          2 allocs/op
BenchmarkMapSetDifferent-4                       5000000               365 ns/op             128 B/op          8 allocs/op
BenchmarkMapSetString-4                         20000000               107 ns/op              32 B/op          2 allocs/op
BenchmarkMapAddSame-4                            2000000               624 ns/op             480 B/op         11 allocs/op
BenchmarkMapAddDifferent-4                       1000000              1585 ns/op            1088 B/op         31 allocs/op
BenchmarkMapAddDifferentRandom-4                   10000            170760 ns/op           20560 B/op        523 allocs/op
BenchmarkMapAddSameSteadyState-4                50000000                28.1 ns/op             0 B/op          0 allocs/op
BenchmarkMapAddDifferentSteadyState-4           20000000               102 ns/op               0 B/op          0 allocs/op
PASS
ok      std/expvar      16.344s

benchmark(new)

goos: darwin
goarch: amd64
pkg: std/expvar
BenchmarkMapSet-4                               20000000                93.9 ns/op            32 B/op          2 allocs/op
BenchmarkMapSetDifferent-4                       5000000               346 ns/op             128 B/op          8 allocs/op
BenchmarkMapSetString-4                         20000000                93.8 ns/op            32 B/op          2 allocs/op
BenchmarkMapAddSame-4                            3000000               521 ns/op             448 B/op         10 allocs/op
BenchmarkMapAddDifferent-4                       1000000              1526 ns/op             960 B/op         27 allocs/op
BenchmarkMapAddDifferentRandom-4                   50000             33741 ns/op           17361 B/op        423 allocs/op
BenchmarkMapAddSameSteadyState-4                50000000                32.6 ns/op             0 B/op          0 allocs/op
BenchmarkMapAddDifferentSteadyState-4           10000000               130 ns/op               0 B/op          0 allocs/op
PASS
ok      std/expvar      14.856s

And there is big improvement for the new added benchamrk BenchmarkMapAddDifferentRandom:

BenchmarkMapAddDifferentRandom-4(old)                  10000            170760 ns/op           20560 B/op        523 allocs/op
BenchmarkMapAddDifferentRandom-4(new)                  50000             33741 ns/op           17361 B/op        423 allocs/op

@gopherbot
Copy link

This PR (HEAD: 202ddc1) has been imported to Gerrit for code review.

Please visit https://go-review.googlesource.com/c/go/+/171718 to see it.

Tip: You can toggle comments from me using the comments slash command (e.g. /comments off)
See the Wiki page for more info

@gopherbot
Copy link

Message from Gobot Gobot:

Patch Set 1:

Congratulations on opening your first change. Thank you for your contribution!

Next steps:
Within the next week or so, a maintainer will review your change and provide
feedback. See https://golang.org/doc/contribute.html#review for more info and
tips to get your patch through code review.

Most changes in the Go project go through a few rounds of revision. This can be
surprising to people new to the project. The careful, iterative review process
is our way of helping mentor contributors and ensuring that their contributions
have a lasting impact.

During May-July and Nov-Jan the Go project is in a code freeze, during which
little code gets reviewed or merged. If a reviewer responds with a comment like
R=go1.11, it means that this CL will be reviewed as part of the next development
cycle. See https://golang.org/s/release for more details.

Please don’t reply on this GitHub thread. Visit golang.org/cl/171718.
After addressing review feedback, remember to publish your drafts!

@ShiKaiWi ShiKaiWi mentioned this pull request Apr 11, 2019
Closed
@gopherbot
Copy link

This PR (HEAD: 0dd3733) has been imported to Gerrit for code review.

Please visit https://go-review.googlesource.com/c/go/+/171718 to see it.

Tip: You can toggle comments from me using the comments slash command (e.g. /comments off)
See the Wiki page for more info

@gopherbot
Copy link

Message from WEI XIKAI:

Patch Set 3: Commit message was updated.

Please don’t reply on this GitHub thread. Visit golang.org/cl/171718.
After addressing review feedback, remember to publish your drafts!

@gopherbot
Copy link

Message from Brad Fitzpatrick:

Patch Set 4: Run-TryBot+1 Code-Review+1

Please don’t reply on this GitHub thread. Visit golang.org/cl/171718.
After addressing review feedback, remember to publish your drafts!

@gopherbot
Copy link

Message from Gobot Gobot:

Patch Set 4:

TryBots beginning. Status page: https://farmer.golang.org/try?commit=58137f0c

Please don’t reply on this GitHub thread. Visit golang.org/cl/171718.
After addressing review feedback, remember to publish your drafts!

@gopherbot
Copy link

Message from Bryan C. Mills:

Patch Set 4: Run-TryBot+1

(3 comments)

Thanks for sending a patch. The code change seems reasonable to me, but it would be useful to have more documentation describing its motivation and effect.

Please don’t reply on this GitHub thread. Visit golang.org/cl/171718.
After addressing review feedback, remember to publish your drafts!

@gopherbot
Copy link

Message from Gobot Gobot:

Patch Set 4: TryBot-Result+1

TryBots are happy.

Please don’t reply on this GitHub thread. Visit golang.org/cl/171718.
After addressing review feedback, remember to publish your drafts!

@gopherbot
Copy link

Message from Brad Fitzpatrick:

Patch Set 4:

(3 comments)

Please don’t reply on this GitHub thread. Visit golang.org/cl/171718.
After addressing review feedback, remember to publish your drafts!

@gopherbot
Copy link

This PR (HEAD: 2c41498) has been imported to Gerrit for code review.

Please visit https://go-review.googlesource.com/c/go/+/171718 to see it.

Tip: You can toggle comments from me using the comments slash command (e.g. /comments off)
See the Wiki page for more info

@ShiKaiWi
expvar: improve Map.addKey for large number of keys
a33b076 
The existing implementation has poor performance for large number of
keys because it chooses to append the new key to the sorted keys array
and sort the new array again.

The improvement tries to utilize the sorted keys array by searching the
index and doing an insertion if any.

Benchmarked on 4-core machine with `go test -cpu 1,2,4,8 -count 5
-benchmem -bench.`:

name                          old time/op    new time/op    delta
MapAddDifferentRandom-8          158ms ± 4%       0ms ± 7%   -99.98%  (p=0.008 n=5+5)
MapSetDifferentRandom-8          154ms ± 5%       0ms ±10%   -99.90%  (p=0.008 n=5+5)
MapAddDifferentRandom-4         25.6ms ±80%     0.0ms ± 9%   -99.87%  (p=0.008 n=5+5)
MapSetDifferentRandom-4         35.0ms ± 2%     0.2ms ±24%   -99.56%  (p=0.008 n=5+5)
MapAddSame-8                     641ns ±10%     540ns ± 0%   -15.83%  (p=0.016 n=5+4)
StringSet-8                     43.8ns ±14%    37.5ns ± 5%   -14.37%  (p=0.016 n=5+5)
MapAddSame-4                     630ns ± 6%     549ns ± 5%   -12.77%  (p=0.008 n=5+5)
IntAdd                          9.84ns ± 7%    8.59ns ± 4%   -12.73%  (p=0.008 n=5+5)
MapAddDifferentRandom-2         44.2µs ±15%    39.3µs ± 4%   -11.02%  (p=0.008 n=5+5)
StringSet                       47.8ns ±13%    43.6ns ± 2%    -8.90%  (p=0.008 n=5+5)
IntSet-8                        17.9ns ± 9%    16.6ns ± 3%    -7.38%  (p=0.016 n=5+5)
RealworldExpvarUsage            44.2µs ± 6%    42.0µs ± 3%    -5.04%  (p=0.032 n=5+5)
IntAdd-2                        17.3ns ±16%    20.2ns ±19%      ~     (p=0.421 n=5+5)
IntAdd-8                        18.4ns ± 5%    19.5ns ± 7%      ~     (p=0.143 n=5+5)
IntSet                          8.85ns ± 1%    8.76ns ± 6%      ~     (p=0.333 n=5+5)
IntSet-2                        15.9ns ±11%    15.7ns ±13%      ~     (p=1.000 n=5+5)
IntSet-4                        17.1ns ± 1%    17.8ns ± 6%      ~     (p=0.492 n=5+5)
FloatAdd                        14.0ns ± 5%    13.6ns ± 3%      ~     (p=0.095 n=5+5)
FloatAdd-2                      42.9ns ±13%    41.3ns ± 9%      ~     (p=0.381 n=5+5)
FloatAdd-4                      56.4ns ±10%    57.3ns ±22%      ~     (p=0.548 n=5+5)
FloatAdd-8                      55.0ns ±23%    57.1ns ±19%      ~     (p=0.524 n=5+5)
FloatSet                        9.68ns ±13%    9.16ns ± 3%      ~     (p=0.524 n=5+5)
FloatSet-2                      15.4ns ±20%    15.1ns ± 4%      ~     (p=0.873 n=5+5)
FloatSet-4                      16.6ns ± 2%    16.8ns ± 3%      ~     (p=0.476 n=5+5)
FloatSet-8                      16.5ns ± 5%    18.0ns ±12%      ~     (p=0.270 n=5+5)
StringSet-2                     44.6ns ± 6%    42.9ns ± 2%      ~     (p=0.159 n=5+5)
StringSet-4                     39.6ns ±13%    36.5ns ±11%      ~     (p=0.421 n=5+5)
MapSet                           151ns ± 2%     148ns ± 2%      ~     (p=0.246 n=5+5)
MapSet-2                         113ns ±19%     112ns ±10%      ~     (p=0.937 n=5+5)
MapSet-8                         110ns ± 9%     112ns ± 8%      ~     (p=0.690 n=5+5)
MapSetDifferent                  740ns ±10%     754ns ±12%      ~     (p=0.548 n=5+5)
MapSetDifferent-2                376ns ± 7%     414ns ±17%      ~     (p=0.111 n=5+5)
MapSetDifferent-8                378ns ± 6%     403ns ± 6%      ~     (p=0.167 n=5+5)
MapSetDifferentRandom            221µs ± 6%     223µs ± 4%      ~     (p=0.841 n=5+5)
MapSetDifferentRandom-2          151µs ±16%     132µs ±11%      ~     (p=0.056 n=5+5)
MapSetString                     159ns ± 2%     165ns ± 3%      ~     (p=0.143 n=5+5)
MapSetString-2                   116ns ± 5%     121ns ±21%      ~     (p=0.857 n=5+5)
MapAddSame                      1.16µs ± 2%    1.26µs ±13%      ~     (p=0.087 n=5+5)
MapAddSame-2                     689ns ±14%     666ns ±11%      ~     (p=1.000 n=5+5)
MapAddDifferent                  182ns ± 7%     171ns ± 5%      ~     (p=0.222 n=5+5)
MapAddDifferent-2                119ns ±10%     121ns ±18%      ~     (p=1.000 n=5+5)
MapAddDifferent-4                131ns ±15%     109ns ±12%      ~     (p=0.063 n=5+5)
MapAddDifferent-8                116ns ±22%     101ns ±16%      ~     (p=0.056 n=5+5)
MapAddDifferentRandom           68.2µs ± 4%    69.8µs ± 6%      ~     (p=0.421 n=5+5)
MapAddSameSteadyState-2         38.2ns ± 5%    38.0ns ± 6%      ~     (p=1.000 n=5+5)
MapAddSameSteadyState-4         31.0ns ±21%    33.5ns ± 5%      ~     (p=0.310 n=5+5)
MapAddSameSteadyState-8         29.4ns ± 8%    30.4ns ± 3%      ~     (p=0.254 n=5+5)
MapAddDifferentSteadyState-2     113ns ±15%     130ns ±22%      ~     (p=0.056 n=5+5)
MapAddDifferentSteadyState-4    95.6ns ±10%    96.8ns ± 5%      ~     (p=0.730 n=5+5)
MapAddDifferentSteadyState-8    92.0ns ± 7%    95.8ns ±10%      ~     (p=0.206 n=5+5)
RealworldExpvarUsage-2          26.8µs ±11%    25.4µs ±17%      ~     (p=0.421 n=5+5)
RealworldExpvarUsage-4          20.6µs ± 9%    19.1µs ± 6%      ~     (p=0.222 n=5+5)
RealworldExpvarUsage-8          21.6µs ± 6%    21.7µs ± 6%      ~     (p=0.548 n=5+5)
MapSetDifferent-4                371ns ± 7%     403ns ± 5%    +8.46%  (p=0.032 n=5+5)
IntAdd-4                        17.8ns ± 4%    19.8ns ± 8%   +10.87%  (p=0.016 n=5+5)
MapAddSameSteadyState           42.7ns ± 3%    48.5ns ± 6%   +13.44%  (p=0.008 n=5+5)
MapAddDifferentSteadyState       163ns ± 1%     189ns ± 4%   +15.81%  (p=0.008 n=5+5)
MapSetString-8                   105ns ± 6%     129ns ±12%   +22.81%  (p=0.008 n=5+5)
MapSetString-4                   109ns ± 8%     140ns ±23%   +28.44%  (p=0.008 n=5+5)
MapSet-4                         103ns ± 7%     146ns ±20%   +41.88%  (p=0.008 n=5+5)

name                          old alloc/op   new alloc/op   delta
MapAddDifferentRandom-4         28.3kB ±79%     0.0kB ±13%   -99.92%  (p=0.008 n=5+5)
MapAddDifferentRandom-8         85.8kB ± 5%     0.1kB ±43%   -99.92%  (p=0.008 n=5+5)
MapSetDifferentRandom-8          107kB ± 4%      32kB ± 0%   -69.88%  (p=0.008 n=5+5)
MapSetDifferentRandom-4         66.0kB ± 0%    32.1kB ± 0%   -51.41%  (p=0.029 n=4+4)
MapAddDifferentRandom            11.0B ± 0%     10.0B ± 0%    -9.09%  (p=0.008 n=5+5)
MapAddSame                        480B ± 0%      448B ± 0%    -6.67%  (p=0.008 n=5+5)
MapAddSame-2                      480B ± 0%      448B ± 0%    -6.67%  (p=0.008 n=5+5)
MapAddSame-4                      480B ± 0%      448B ± 0%    -6.67%  (p=0.008 n=5+5)
MapAddSame-8                      480B ± 0%      448B ± 0%    -6.67%  (p=0.008 n=5+5)
IntAdd                           0.00B          0.00B           ~     (all equal)
IntAdd-2                         0.00B          0.00B           ~     (all equal)
IntAdd-4                         0.00B          0.00B           ~     (all equal)
IntAdd-8                         0.00B          0.00B           ~     (all equal)
IntSet                           0.00B          0.00B           ~     (all equal)
IntSet-2                         0.00B          0.00B           ~     (all equal)
IntSet-4                         0.00B          0.00B           ~     (all equal)
IntSet-8                         0.00B          0.00B           ~     (all equal)
FloatAdd                         0.00B          0.00B           ~     (all equal)
FloatAdd-2                       0.00B          0.00B           ~     (all equal)
FloatAdd-4                       0.00B          0.00B           ~     (all equal)
FloatAdd-8                       0.00B          0.00B           ~     (all equal)
FloatSet                         0.00B          0.00B           ~     (all equal)
FloatSet-2                       0.00B          0.00B           ~     (all equal)
FloatSet-4                       0.00B          0.00B           ~     (all equal)
FloatSet-8                       0.00B          0.00B           ~     (all equal)
StringSet                        16.0B ± 0%     16.0B ± 0%      ~     (all equal)
StringSet-2                      16.0B ± 0%     16.0B ± 0%      ~     (all equal)
StringSet-4                      16.0B ± 0%     16.0B ± 0%      ~     (all equal)
StringSet-8                      16.0B ± 0%     16.0B ± 0%      ~     (all equal)
MapSet                           32.0B ± 0%     32.0B ± 0%      ~     (all equal)
MapSet-2                         32.0B ± 0%     32.0B ± 0%      ~     (all equal)
MapSet-4                         32.0B ± 0%     32.0B ± 0%      ~     (all equal)
MapSet-8                         32.0B ± 0%     32.0B ± 0%      ~     (all equal)
MapSetDifferent                   128B ± 0%      128B ± 0%      ~     (all equal)
MapSetDifferent-2                 128B ± 0%      128B ± 0%      ~     (all equal)
MapSetDifferent-4                 128B ± 0%      128B ± 0%      ~     (all equal)
MapSetDifferent-8                 128B ± 0%      128B ± 0%      ~     (all equal)
MapSetDifferentRandom           32.0kB ± 0%    32.0kB ± 0%      ~     (p=0.079 n=4+5)
MapSetDifferentRandom-2         32.0kB ± 0%    32.0kB ± 0%      ~     (p=0.143 n=4+4)
MapSetString                     32.0B ± 0%     32.0B ± 0%      ~     (all equal)
MapSetString-2                   32.0B ± 0%     32.0B ± 0%      ~     (all equal)
MapSetString-4                   32.0B ± 0%     32.0B ± 0%      ~     (all equal)
MapSetString-8                   32.0B ± 0%     32.0B ± 0%      ~     (all equal)
MapAddDifferent                  0.00B          0.00B           ~     (all equal)
MapAddDifferent-2                0.00B          0.00B           ~     (all equal)
MapAddDifferent-4                0.00B          0.00B           ~     (all equal)
MapAddDifferent-8                0.00B          0.00B           ~     (all equal)
MapAddDifferentRandom-2          21.4B ±36%     15.8B ±30%      ~     (p=0.159 n=5+5)
MapAddSameSteadyState            0.00B          0.00B           ~     (all equal)
MapAddSameSteadyState-2          0.00B          0.00B           ~     (all equal)
MapAddSameSteadyState-4          0.00B          0.00B           ~     (all equal)
MapAddSameSteadyState-8          0.00B          0.00B           ~     (all equal)
MapAddDifferentSteadyState       0.00B          0.00B           ~     (all equal)
MapAddDifferentSteadyState-2     0.00B          0.00B           ~     (all equal)
MapAddDifferentSteadyState-4     0.00B          0.00B           ~     (all equal)
MapAddDifferentSteadyState-8     0.00B          0.00B           ~     (all equal)
RealworldExpvarUsage             0.00B          0.00B           ~     (all equal)
RealworldExpvarUsage-2           0.00B          0.00B           ~     (all equal)
RealworldExpvarUsage-4           0.00B          0.00B           ~     (all equal)
RealworldExpvarUsage-8           0.00B          0.00B           ~     (all equal)

name                          old allocs/op  new allocs/op  delta
MapAddDifferentRandom-4            505 ±80%         0       -100.00%  (p=0.008 n=5+5)
MapAddDifferentRandom-8          1.35k ± 0%     0.00k       -100.00%  (p=0.000 n=5+4)
MapSetDifferentRandom-8          2.55k ± 0%     2.00k ± 0%   -21.42%  (p=0.008 n=5+5)
MapSetDifferentRandom-4          2.27k ± 0%     2.00k ± 0%   -12.00%  (p=0.008 n=5+5)
MapAddSame                        11.0 ± 0%      10.0 ± 0%    -9.09%  (p=0.008 n=5+5)
MapAddSame-2                      11.0 ± 0%      10.0 ± 0%    -9.09%  (p=0.008 n=5+5)
MapAddSame-4                      11.0 ± 0%      10.0 ± 0%    -9.09%  (p=0.008 n=5+5)
MapAddSame-8                      11.0 ± 0%      10.0 ± 0%    -9.09%  (p=0.008 n=5+5)
IntAdd                            0.00           0.00           ~     (all equal)
IntAdd-2                          0.00           0.00           ~     (all equal)
IntAdd-4                          0.00           0.00           ~     (all equal)
IntAdd-8                          0.00           0.00           ~     (all equal)
IntSet                            0.00           0.00           ~     (all equal)
IntSet-2                          0.00           0.00           ~     (all equal)
IntSet-4                          0.00           0.00           ~     (all equal)
IntSet-8                          0.00           0.00           ~     (all equal)
FloatAdd                          0.00           0.00           ~     (all equal)
FloatAdd-2                        0.00           0.00           ~     (all equal)
FloatAdd-4                        0.00           0.00           ~     (all equal)
FloatAdd-8                        0.00           0.00           ~     (all equal)
FloatSet                          0.00           0.00           ~     (all equal)
FloatSet-2                        0.00           0.00           ~     (all equal)
FloatSet-4                        0.00           0.00           ~     (all equal)
FloatSet-8                        0.00           0.00           ~     (all equal)
StringSet                         1.00 ± 0%      1.00 ± 0%      ~     (all equal)
StringSet-2                       1.00 ± 0%      1.00 ± 0%      ~     (all equal)
StringSet-4                       1.00 ± 0%      1.00 ± 0%      ~     (all equal)
StringSet-8                       1.00 ± 0%      1.00 ± 0%      ~     (all equal)
MapSet                            2.00 ± 0%      2.00 ± 0%      ~     (all equal)
MapSet-2                          2.00 ± 0%      2.00 ± 0%      ~     (all equal)
MapSet-4                          2.00 ± 0%      2.00 ± 0%      ~     (all equal)
MapSet-8                          2.00 ± 0%      2.00 ± 0%      ~     (all equal)
MapSetDifferent                   8.00 ± 0%      8.00 ± 0%      ~     (all equal)
MapSetDifferent-2                 8.00 ± 0%      8.00 ± 0%      ~     (all equal)
MapSetDifferent-4                 8.00 ± 0%      8.00 ± 0%      ~     (all equal)
MapSetDifferent-8                 8.00 ± 0%      8.00 ± 0%      ~     (all equal)
MapSetDifferentRandom            2.00k ± 0%     2.00k ± 0%      ~     (all equal)
MapSetDifferentRandom-2          2.00k ± 0%     2.00k ± 0%      ~     (all equal)
MapSetString                      2.00 ± 0%      2.00 ± 0%      ~     (all equal)
MapSetString-2                    2.00 ± 0%      2.00 ± 0%      ~     (all equal)
MapSetString-4                    2.00 ± 0%      2.00 ± 0%      ~     (all equal)
MapSetString-8                    2.00 ± 0%      2.00 ± 0%      ~     (all equal)
MapAddDifferent                   0.00           0.00           ~     (all equal)
MapAddDifferent-2                 0.00           0.00           ~     (all equal)
MapAddDifferent-4                 0.00           0.00           ~     (all equal)
MapAddDifferent-8                 0.00           0.00           ~     (all equal)
MapAddDifferentRandom             0.00           0.00           ~     (all equal)
MapAddDifferentRandom-2           0.00           0.00           ~     (all equal)
MapAddSameSteadyState             0.00           0.00           ~     (all equal)
MapAddSameSteadyState-2           0.00           0.00           ~     (all equal)
MapAddSameSteadyState-4           0.00           0.00           ~     (all equal)
MapAddSameSteadyState-8           0.00           0.00           ~     (all equal)
MapAddDifferentSteadyState        0.00           0.00           ~     (all equal)
MapAddDifferentSteadyState-2      0.00           0.00           ~     (all equal)
MapAddDifferentSteadyState-4      0.00           0.00           ~     (all equal)
MapAddDifferentSteadyState-8      0.00           0.00           ~     (all equal)
RealworldExpvarUsage              0.00           0.00           ~     (all equal)
RealworldExpvarUsage-2            0.00           0.00           ~     (all equal)
RealworldExpvarUsage-4            0.00           0.00           ~     (all equal)
RealworldExpvarUsage-8            0.00           0.00           ~     (all equal)

Fixes golang#31414
@gopherbot
Copy link

This PR (HEAD: a33b076) has been imported to Gerrit for code review.

Please visit https://go-review.googlesource.com/c/go/+/171718 to see it.

Tip: You can toggle comments from me using the comments slash command (e.g. /comments off)
See the Wiki page for more info

@ShiKaiWi
expvar: improve Map.addKey for large number of keys
a816fe3 
The existing implementation has poor performance for large number of
keys because it chooses to append the new key to the sorted keys array
and sort the new array again.

The improvement tries to utilize the sorted keys array by searching the
index and doing an insertion if any.

Benchmarked on 4-core machine with `go test -cpu 1,2,4,8 -count 5
-benchmem -bench.`(the equal results has been removed):

name                          old time/op    new time/op    delta
MapAddDifferentRandom-8          158ms ± 4%       0ms ± 7%   -99.98%  (p=0.008 n=5+5)
MapSetDifferentRandom-8          154ms ± 5%       0ms ±10%   -99.90%  (p=0.008 n=5+5)
MapAddDifferentRandom-4         25.6ms ±80%     0.0ms ± 9%   -99.87%  (p=0.008 n=5+5)
MapSetDifferentRandom-4         35.0ms ± 2%     0.2ms ±24%   -99.56%  (p=0.008 n=5+5)
MapAddSame-8                     641ns ±10%     540ns ± 0%   -15.83%  (p=0.016 n=5+4)
StringSet-8                     43.8ns ±14%    37.5ns ± 5%   -14.37%  (p=0.016 n=5+5)
MapAddSame-4                     630ns ± 6%     549ns ± 5%   -12.77%  (p=0.008 n=5+5)
IntAdd                          9.84ns ± 7%    8.59ns ± 4%   -12.73%  (p=0.008 n=5+5)
MapAddDifferentRandom-2         44.2µs ±15%    39.3µs ± 4%   -11.02%  (p=0.008 n=5+5)
StringSet                       47.8ns ±13%    43.6ns ± 2%    -8.90%  (p=0.008 n=5+5)
IntSet-8                        17.9ns ± 9%    16.6ns ± 3%    -7.38%  (p=0.016 n=5+5)
RealworldExpvarUsage            44.2µs ± 6%    42.0µs ± 3%    -5.04%  (p=0.032 n=5+5)
MapSetDifferent-4                371ns ± 7%     403ns ± 5%    +8.46%  (p=0.032 n=5+5)
IntAdd-4                        17.8ns ± 4%    19.8ns ± 8%   +10.87%  (p=0.016 n=5+5)
MapAddSameSteadyState           42.7ns ± 3%    48.5ns ± 6%   +13.44%  (p=0.008 n=5+5)
MapAddDifferentSteadyState       163ns ± 1%     189ns ± 4%   +15.81%  (p=0.008 n=5+5)
MapSetString-8                   105ns ± 6%     129ns ±12%   +22.81%  (p=0.008 n=5+5)
MapSetString-4                   109ns ± 8%     140ns ±23%   +28.44%  (p=0.008 n=5+5)
MapSet-4                         103ns ± 7%     146ns ±20%   +41.88%  (p=0.008 n=5+5)

name                          old alloc/op   new alloc/op   delta
MapAddDifferentRandom-4         28.3kB ±79%     0.0kB ±13%   -99.92%  (p=0.008 n=5+5)
MapAddDifferentRandom-8         85.8kB ± 5%     0.1kB ±43%   -99.92%  (p=0.008 n=5+5)
MapSetDifferentRandom-8          107kB ± 4%      32kB ± 0%   -69.88%  (p=0.008 n=5+5)
MapSetDifferentRandom-4         66.0kB ± 0%    32.1kB ± 0%   -51.41%  (p=0.029 n=4+4)
MapAddDifferentRandom            11.0B ± 0%     10.0B ± 0%    -9.09%  (p=0.008 n=5+5)
MapAddSame                        480B ± 0%      448B ± 0%    -6.67%  (p=0.008 n=5+5)
MapAddSame-2                      480B ± 0%      448B ± 0%    -6.67%  (p=0.008 n=5+5)
MapAddSame-4                      480B ± 0%      448B ± 0%    -6.67%  (p=0.008 n=5+5)
MapAddSame-8                      480B ± 0%      448B ± 0%    -6.67%  (p=0.008 n=5+5)

name                          old allocs/op  new allocs/op  delta
MapAddDifferentRandom-4            505 ±80%         0       -100.00%  (p=0.008 n=5+5)
MapAddDifferentRandom-8          1.35k ± 0%     0.00k       -100.00%  (p=0.000 n=5+4)
MapSetDifferentRandom-8          2.55k ± 0%     2.00k ± 0%   -21.42%  (p=0.008 n=5+5)
MapSetDifferentRandom-4          2.27k ± 0%     2.00k ± 0%   -12.00%  (p=0.008 n=5+5)
MapAddSame                        11.0 ± 0%      10.0 ± 0%    -9.09%  (p=0.008 n=5+5)
MapAddSame-2                      11.0 ± 0%      10.0 ± 0%    -9.09%  (p=0.008 n=5+5)
MapAddSame-4                      11.0 ± 0%      10.0 ± 0%    -9.09%  (p=0.008 n=5+5)
MapAddSame-8                      11.0 ± 0%      10.0 ± 0%    -9.09%  (p=0.008 n=5+5)

Fixes golang#31414
@gopherbot
Copy link

This PR (HEAD: a816fe3) has been imported to Gerrit for code review.

Please visit https://go-review.googlesource.com/c/go/+/171718 to see it.

Tip: You can toggle comments from me using the comments slash command (e.g. /comments off)
See the Wiki page for more info

@gopherbot
Copy link

Message from WEI XIKAI:

Uploaded patch set 8: Commit message was updated.

Please don’t reply on this GitHub thread. Visit golang.org/cl/171718.
After addressing review feedback, remember to publish your drafts!

@gopherbot
Copy link

Message from WEI XIKAI:

Uploaded patch set 9: Commit message was updated.

Please don’t reply on this GitHub thread. Visit golang.org/cl/171718.
After addressing review feedback, remember to publish your drafts!

@gopherbot
Copy link

Message from WEI XIKAI:

Uploaded patch set 11: Commit message was updated.

Please don’t reply on this GitHub thread. Visit golang.org/cl/171718.
After addressing review feedback, remember to publish your drafts!

@ShiKaiWi ShiKaiWi closed this Apr 14, 2019
gopherbot pushed a commit that referenced this pull request Apr 16, 2019
@ShiKaiWi @bradfitz
expvar: improve Map.addKey for large number of keys
518ee55 
The existing implementation has poor performance for inserting large
number of keys because it chooses to append the new key to the sorted
keys array and then sort the new array again (time complexity is
O(nlogn)).

The improvement tries to utilize the sorted keys array by searching the
index and doing an insertion if any (time complexity is O(logn)).

Benchmarked on 4-core machine with `go test -cpu 1,2,4,8 -count 5
-benchmem -bench=.`(the equal results are omitted):

name                          old time/op    new time/op    delta
MapAddDifferentRandom-8          408µs ±11%      69µs ± 3%  -82.95%  (p=0.008 n=5+5)
MapAddDifferentRandom-4          389µs ±19%      69µs ± 2%  -82.28%  (p=0.008 n=5+5)
MapAddDifferentRandom-2          365µs ± 4%      75µs ± 6%  -79.51%  (p=0.008 n=5+5)
MapSetDifferentRandom-8          365µs ± 4%      76µs ±40%  -79.07%  (p=0.008 n=5+5)
MapAddDifferentRandom            366µs ± 3%      78µs ± 6%  -78.66%  (p=0.008 n=5+5)
MapSetDifferentRandom            369µs ± 2%      81µs ±34%  -77.99%  (p=0.008 n=5+5)
MapSetDifferentRandom-2          378µs ±10%     100µs ±32%  -73.47%  (p=0.008 n=5+5)
MapSetDifferentRandom-4          352µs ± 4%     108µs ± 7%  -69.40%  (p=0.008 n=5+5)
IntAdd-2                        23.1ns ±21%    15.5ns ±23%  -32.79%  (p=0.032 n=5+5)
IntSet-2                        21.4ns ±14%    16.7ns ±17%  -22.00%  (p=0.016 n=5+5)
FloatAdd-8                      88.8ns ± 9%    70.8ns ±25%  -20.23%  (p=0.024 n=5+5)
FloatSet-2                      22.3ns ±15%    17.8ns ±14%  -20.14%  (p=0.008 n=5+5)
IntAdd-8                        21.7ns ± 3%    18.7ns ± 4%  -14.00%  (p=0.008 n=5+5)
MapAddDifferent-8               1.58µs ± 7%    1.42µs ± 6%  -10.06%  (p=0.016 n=5+5)
StringSet-2                     42.4ns ± 1%    43.7ns ± 5%   +3.07%  (p=0.048 n=4+5)
FloatSet                        8.27ns ± 2%    8.60ns ± 1%   +3.94%  (p=0.008 n=5+5)
FloatAdd                        12.5ns ± 2%    13.0ns ± 4%   +4.33%  (p=0.032 n=5+5)
MapSetString-4                  94.6ns ± 0%   101.7ns ± 4%   +7.55%  (p=0.016 n=4+5)
MapAddSameSteadyState-2         34.9ns ± 3%    37.7ns ± 5%   +8.14%  (p=0.008 n=5+5)
StringSet-4                     34.5ns ± 0%    37.6ns ± 9%   +9.02%  (p=0.016 n=4+5)
MapSetDifferent-8                377ns ± 3%     411ns ± 7%   +9.07%  (p=0.008 n=5+5)
MapAddSameSteadyState           39.1ns ± 2%    42.8ns ± 6%   +9.36%  (p=0.008 n=5+5)
MapAddDifferentSteadyState       172ns ± 4%     190ns ± 9%  +10.96%  (p=0.016 n=5+5)
MapSet                           143ns ± 4%     159ns ± 2%  +11.06%  (p=0.008 n=5+5)
MapSet-4                        96.9ns ± 5%   107.8ns ± 6%  +11.25%  (p=0.008 n=5+5)
MapSet-2                         102ns ± 6%     114ns ± 8%  +11.94%  (p=0.008 n=5+5)
IntSet                          8.18ns ± 1%   12.78ns ±13%  +56.31%  (p=0.008 n=5+5)

name                          old alloc/op   new alloc/op   delta
MapSetDifferentRandom-4         19.8kB ± 0%    16.6kB ± 0%  -16.21%  (p=0.008 n=5+5)
MapSetDifferentRandom           19.8kB ± 0%    16.6kB ± 0%  -16.21%  (p=0.008 n=5+5)
MapSetDifferentRandom-8         19.8kB ± 0%    16.6kB ± 0%  -16.20%  (p=0.008 n=5+5)
MapSetDifferentRandom-2         19.8kB ± 0%    16.6kB ± 0%  -16.20%  (p=0.008 n=5+5)
MapAddDifferentRandom           20.6kB ± 0%    17.4kB ± 0%  -15.57%  (p=0.008 n=5+5)
MapAddDifferentRandom-8         20.6kB ± 0%    17.4kB ± 0%  -15.57%  (p=0.008 n=5+5)
MapAddDifferentRandom-2         20.6kB ± 0%    17.4kB ± 0%  -15.56%  (p=0.008 n=5+5)
MapAddDifferentRandom-4         20.6kB ± 0%    17.4kB ± 0%  -15.56%  (p=0.008 n=5+5)
MapAddDifferent                 1.09kB ± 0%    0.96kB ± 0%  -11.76%  (p=0.008 n=5+5)
MapAddDifferent-2               1.09kB ± 0%    0.96kB ± 0%  -11.76%  (p=0.008 n=5+5)
MapAddDifferent-4               1.09kB ± 0%    0.96kB ± 0%  -11.76%  (p=0.008 n=5+5)
MapAddDifferent-8               1.09kB ± 0%    0.96kB ± 0%  -11.76%  (p=0.008 n=5+5)
MapAddSame                        480B ± 0%      448B ± 0%   -6.67%  (p=0.008 n=5+5)
MapAddSame-2                      480B ± 0%      448B ± 0%   -6.67%  (p=0.008 n=5+5)
MapAddSame-4                      480B ± 0%      448B ± 0%   -6.67%  (p=0.008 n=5+5)
MapAddSame-8                      480B ± 0%      448B ± 0%   -6.67%  (p=0.008 n=5+5)

name                          old allocs/op  new allocs/op  delta
MapSetDifferentRandom              423 ± 0%       323 ± 0%  -23.64%  (p=0.008 n=5+5)
MapSetDifferentRandom-2            423 ± 0%       323 ± 0%  -23.64%  (p=0.008 n=5+5)
MapSetDifferentRandom-4            423 ± 0%       323 ± 0%  -23.64%  (p=0.008 n=5+5)
MapSetDifferentRandom-8            423 ± 0%       323 ± 0%  -23.64%  (p=0.008 n=5+5)
MapAddDifferentRandom              523 ± 0%       423 ± 0%  -19.12%  (p=0.008 n=5+5)
MapAddDifferentRandom-2            523 ± 0%       423 ± 0%  -19.12%  (p=0.008 n=5+5)
MapAddDifferentRandom-4            523 ± 0%       423 ± 0%  -19.12%  (p=0.008 n=5+5)
MapAddDifferentRandom-8            523 ± 0%       423 ± 0%  -19.12%  (p=0.008 n=5+5)
MapAddDifferent                   31.0 ± 0%      27.0 ± 0%  -12.90%  (p=0.008 n=5+5)
MapAddDifferent-2                 31.0 ± 0%      27.0 ± 0%  -12.90%  (p=0.008 n=5+5)
MapAddDifferent-4                 31.0 ± 0%      27.0 ± 0%  -12.90%  (p=0.008 n=5+5)
MapAddDifferent-8                 31.0 ± 0%      27.0 ± 0%  -12.90%  (p=0.008 n=5+5)
MapAddSame                        11.0 ± 0%      10.0 ± 0%   -9.09%  (p=0.008 n=5+5)
MapAddSame-2                      11.0 ± 0%      10.0 ± 0%   -9.09%  (p=0.008 n=5+5)
MapAddSame-4                      11.0 ± 0%      10.0 ± 0%   -9.09%  (p=0.008 n=5+5)
MapAddSame-8                      11.0 ± 0%      10.0 ± 0%   -9.09%  (p=0.008 n=5+5)

Fixes #31414

Change-Id: I2dd655dec9dbbf8d7881a0f3f8edcb3d29199a48
GitHub-Last-Rev: a816fe3
GitHub-Pull-Request: #31418
Reviewed-on: https://go-review.googlesource.com/c/go/+/171718
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@jsign jsign mentioned this pull request Sep 2, 2019
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
cla: yes Used by googlebot to label PRs as having a valid CLA. The text of this label should not change.
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

expvar: overhead cost of Map.Add when the number of entries grows
3 participants
@ShiKaiWi @gopherbot @googlebot