tree b5f47517cd3115e23b29e878d13a08b4fd287771
parent 31f2f8d62441206136943740681b7cefc7a4eb14
author Andrew Gerrand <adg@golang.org> 1407875678 +1000
committer Andrew Gerrand <adg@golang.org> 1407875678 +1000
golang-hg 23f1ebe74d90e411b24839938fd73b8c65c3b8b2

[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