]> Cypherpunks repositories - gostls13.git/commit
cmd/compile: reorg copyelim to avoid O(n^2) problem
authorKeith Randall <khr@golang.org>
Wed, 27 Apr 2016 23:58:50 +0000 (16:58 -0700)
committerKeith Randall <khr@golang.org>
Thu, 28 Apr 2016 17:40:08 +0000 (17:40 +0000)
commitd610d304f86021cc5f388b8f02d99bc73fca0d9b
tree128ec7a4ebab229ae9f6c6cb26ed6bbf2347dd86
parent5ec87ba554c2a83cdc188724f815e53fede91b66
cmd/compile: reorg copyelim to avoid O(n^2) problem

Make sure we don't do O(n^2) work to eliminate a chain
of n copies.

benchmark                     old ns/op       new ns/op     delta
BenchmarkCopyElim1-8          1418            1406          -0.85%
BenchmarkCopyElim10-8         5289            5162          -2.40%
BenchmarkCopyElim100-8        52618           41684         -20.78%
BenchmarkCopyElim1000-8       2473878         424339        -82.85%
BenchmarkCopyElim10000-8      269373954       6367971       -97.64%
BenchmarkCopyElim100000-8     31272781165     104357244     -99.67%

Change-Id: I680f906f70f2ee1a8615cb1046bc510c77d59284
Reviewed-on: https://go-review.googlesource.com/22535
Reviewed-by: Alexandru Moșoi <alexandru@mosoi.ro>
src/cmd/compile/internal/ssa/copyelim.go
src/cmd/compile/internal/ssa/copyelim_test.go [new file with mode: 0644]
src/cmd/compile/internal/ssa/export_test.go
src/cmd/compile/internal/ssa/rewrite.go