commit 69dc3a910f5fbd37d9ead0147ca8bc8c998c7d01
author Andrew Gerrand <adg@golang.org> Wed Aug 13 06:34:38 2014 +1000
committer Andrew Gerrand <adg@golang.org> Wed Aug 13 06:34:38 2014 +1000
tree b5f47517cd3115e23b29e878d13a08b4fd287771
parent 31f2f8d62441206136943740681b7cefc7a4eb14

[release-branch.go1.3] cmd/gc: make liveness ~10x faster

««« CL 125720043 / b92e5df7d3ba
cmd/gc: make liveness ~10x faster

1) The arrayindexof lookup function is O(n). Replace with O(1) lookups.

2) The checkptxt function is O(n²) and is purely for debugging.
Only run when the debugging flags are turned on.

3) Iterating over sparse bitmaps can be done faster word by word.
Introduce and use bvnext for that.

Run times before and after, on my 2.5 GHz Core i5 MacBook Pro.

x.go       9.48  0.84  issue 8259

x100.go    0.01  0.01  issue 8354
x1000.go   0.10  0.10
x2000.go   0.62  0.19
x3000.go   1.33  0.34
x4000.go   2.29  0.49
x5000.go   3.89  0.67
x6000.go   5.00  0.90
x7000.go   6.70  1.13
x8000.go   9.44  1.38
x9000.go  11.23  1.87
x10000.go 13.78  2.09

Fixes #8259.
Fixes #8354.

LGTM=iant, r
R=golang-codereviews, iant, r
CC=golang-codereviews
https://golang.org/cl/125720043
»»»

TBR=rsc
CC=golang-codereviews
https://golang.org/cl/121600043