Skip to content

runtime: BenchmarkMapDelete is non-linear and slow #21546

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.

Sign up for GitHub

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
Closed
josharian opened this issue Aug 21, 2017 · 5 comments
Closed

runtime: BenchmarkMapDelete is non-linear and slow #21546

josharian opened this issue Aug 21, 2017 · 5 comments
Labels
FrozenDueToAge
Milestone
Go1.10

Comments

@josharian
Copy link
Contributor 

$ 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
Copy link
Contributor

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

@huguesb
Copy link
Contributor

huguesb 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
Copy link
Contributor

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

@huguesb
Copy link
Contributor

huguesb 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
Copy link
Contributor

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
@josharian
runtime: strength reduce key pointer calculation in mapdelete_fast*
29e6bdc 
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
@josharian
runtime: only clear pointer-containing memory during map delete
0c7fd56 
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>
@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.
Assignees
No one assigned
Labels
FrozenDueToAge
Projects
None yet
Milestone
Go1.10
Development

No branches or pull requests
3 participants
@josharian @huguesb @gopherbot