-
Notifications
You must be signed in to change notification settings - Fork 17.9k
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
expvar: overhead cost of Map.Add when the number of entries grows #31414
Comments
If you were to resolve the bottleneck in |
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 do an insertion if any. It also fixes an error that duplicate key will be inserted in high concurrent cases. Fixes golang#31414
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 golang#31414
Change https://golang.org/cl/171718 mentions this issue: |
@bcmills thanks for your quick reponse. Actually I only want to avoid The code and benchmark of #31418 may help explain what I say. |
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. Fixes golang#31414
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
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
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
What version of Go are you using (
go version
)?Does this issue reproduce with the latest release?
Yes.
What operating system and processor architecture are you using (
go env
)?go env
OutputWhat did you do?
I tried to use
Map
in package theexpvar
to collect some metrics but I found it would be very slow to callAdd
method of it when the number of entries in the map grew. As for the concurrent case most of goroutines calling theAdd
of the sameMap
instance would be blocked.And the source code of the
Add
method tells that in theAdd
method a sorting for all the keys will be executed holding the lock:What did you expect to see?
Map
even if the number of the keys is large.What did you see instead?
Holding the lock do a sort for all the entries.
The text was updated successfully, but these errors were encountered: