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

runtime: BenchmarkMapDelete is non-linear and slow #21546

Closed
josharian opened this issue Aug 21, 2017 · 5 comments

Comments

Projects
None yet
3 participants
@josharian
Copy link
Contributor

commented Aug 21, 2017

$ go test -bench=MapDelete/Int64/4 -run=NONE -benchtime=100ms runtime
BenchmarkMapDelete/Int64/4-8       	 1000000	       129 ns/op
ok  	runtime	0.974s
$ go test -bench=MapDelete/Int64/4 -run=NONE -benchtime=1000ms runtime
BenchmarkMapDelete/Int64/4-8       	10000000	       164 ns/op
ok  	runtime	12.528s

Note that the ns/op increases as the benchtime goes up. This indicates that the benchmark is not well-formed. Beyond that, it causes problems because (1) minor performance changes that trigger a change in the number of iterations appear to be significant performance changes and (2) when the number of iterations that fits in benchtime is on the edge it causes a bimodal ns/op distribution.

Note also that it takes 12s to run a 1s benchmark. Ouch.

IIRC, some other recently added map benchmarks share these problems. (They also should have been added to mapspeed_test.go instead of map_test.go.)

cc @randall77 @huguesb @bcmills

@josharian josharian added this to the Go1.10 milestone Aug 21, 2017

@gopherbot

This comment has been minimized.

Copy link

commented Aug 21, 2017

Change https://golang.org/cl/57611 mentions this issue: runtime: strength reduce key pointer calculation in mapdelete_fast*

@huguesb

This comment has been minimized.

Copy link
Contributor

commented Aug 21, 2017

(pprof) top10
Showing nodes accounting for 17.94s, 98.52% of 18.21s total
Dropped 38 nodes (cum <= 0.09s)
Showing top 10 nodes out of 25
      flat  flat%   sum%        cum   cum%
    12.37s 67.93% 67.93%     13.13s 72.10%  runtime.mapassign_fast64 /Users/hugues/go/src/runtime/hashmap_fast.go
     2.61s 14.33% 82.26%      2.84s 15.60%  runtime.mapdelete_fast64 /Users/hugues/go/src/runtime/hashmap_fast.go
     1.15s  6.32% 88.58%      1.15s  6.32%  runtime.memclrNoHeapPointers /Users/hugues/go/src/runtime/memclr_amd64.s
     0.52s  2.86% 91.43%      0.52s  2.86%  runtime.aeshash64 /Users/hugues/go/src/runtime/asm_amd64.s
     0.50s  2.75% 94.18%      0.50s  2.75%  runtime.usleep /Users/hugues/go/src/runtime/sys_darwin_amd64.s
     0.26s  1.43% 95.61%      0.26s  1.43%  runtime.mapassign_fast64 /Users/hugues/go/src/runtime/hashmap.go
     0.18s  0.99% 96.60%      0.23s  1.26%  runtime.typedmemmove /Users/hugues/go/src/runtime/mbarrier.go
     0.16s  0.88% 97.47%     17.63s 96.81%  runtime_test.benchmarkMapDeleteInt64 /Users/hugues/go/src/runtime/map_test.go
     0.12s  0.66% 98.13%      0.12s  0.66%  runtime.mapassign_fast64 /Users/hugues/go/src/runtime/stubs.go
     0.07s  0.38% 98.52%      0.12s  0.66%  runtime.typedmemclr /Users/hugues/go/src/runtime/mbarrier.go

Looks like the initialization needs to be reworked. I'll take a stab at it today

@gopherbot

This comment has been minimized.

Copy link

commented Aug 21, 2017

Change https://golang.org/cl/57630 mentions this issue: runtime: only clear pointer-containing memory during map delete

@huguesb

This comment has been minimized.

Copy link
Contributor

commented Aug 21, 2017

I have a reworked benchmark which runs faster and is stable wrt increased benchtime

hugues@neosynchronicity:src $PATH=~/go/bin:$PATH go test -bench=MapDelete -run=NONE -benchtime=100ms runtime
goos: darwin
goarch: amd64
pkg: runtime
BenchmarkMapDelete/Int32/100-8     	 5000000	        37.4 ns/op
BenchmarkMapDelete/Int32/1000-8    	 3000000	        43.5 ns/op
BenchmarkMapDelete/Int32/10000-8   	 3000000	        48.6 ns/op
BenchmarkMapDelete/Int64/100-8     	 5000000	        35.6 ns/op
BenchmarkMapDelete/Int64/1000-8    	 3000000	        43.5 ns/op
BenchmarkMapDelete/Int64/10000-8   	 3000000	        49.6 ns/op
BenchmarkMapDelete/Str/100-8       	 3000000	        49.0 ns/op
BenchmarkMapDelete/Str/1000-8      	 3000000	        54.4 ns/op
BenchmarkMapDelete/Str/10000-8     	 2000000	        63.1 ns/op
PASS
ok  	runtime	4.983s
hugues@neosynchronicity:src $PATH=~/go/bin:$PATH go test -bench=MapDelete -run=NONE -benchtime=1000ms runtime
goos: darwin
goarch: amd64
pkg: runtime
BenchmarkMapDelete/Int32/100-8     	50000000	        35.7 ns/op
BenchmarkMapDelete/Int32/1000-8    	30000000	        43.0 ns/op
BenchmarkMapDelete/Int32/10000-8   	30000000	        49.1 ns/op
BenchmarkMapDelete/Int64/100-8     	50000000	        35.4 ns/op
BenchmarkMapDelete/Int64/1000-8    	30000000	        43.8 ns/op
BenchmarkMapDelete/Int64/10000-8   	30000000	        49.7 ns/op
BenchmarkMapDelete/Str/100-8       	30000000	        48.7 ns/op
BenchmarkMapDelete/Str/1000-8      	30000000	        55.3 ns/op
BenchmarkMapDelete/Str/10000-8     	20000000	        64.0 ns/op
PASS
ok  	runtime	39.122s

I'll send a CL shortly

@gopherbot

This comment has been minimized.

Copy link

commented Aug 21, 2017

Change https://golang.org/cl/57650 mentions this issue: runtime: more reliable mapdelete benchmark

gopherbot pushed a commit that referenced this issue Aug 23, 2017

runtime: strength reduce key pointer calculation in mapdelete_fast*
Move the tophash checks after the equality/length checks.

For fast32/fast64, since we've done a full equality check already,
just check whether tophash is empty instead of checking tophash.
This is cheaper and allows us to skip calculating tophash.

These changes are modeled on the changes in CL 57590,
which were polished based on benchmarking.
Benchmarking directly is impeded by #21546.

Change-Id: I0e17163028e34720310d1bf8f95c5ef42d223e00
Reviewed-on: https://go-review.googlesource.com/57611
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>

gopherbot pushed a commit that referenced this issue Aug 23, 2017

runtime: only clear pointer-containing memory during map delete
When deleting entries from a map, only clear the key and value
if they contain pointers. And use memclrHasPointers to do so.

While we're here, specialize key clearing in mapdelete_faststr,
and fix another missed usage of add in mapdelete.

Benchmarking impeded by #21546.

Change-Id: I3f6f924f738d6b899b722d6438e9e63f52359b84
Reviewed-on: https://go-review.googlesource.com/57630
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>

@gopherbot gopherbot closed this in e769c9d Oct 21, 2017

@golang golang locked and limited conversation to collaborators Oct 21, 2018

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
You can’t perform that action at this time.