code review 125720043: cmd/gc: make liveness ~10x faster

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 issue 8259.
Fixes issue 8354.

[rsc, 2014-08-06 14:38:39]

Hello golang-codereviews@googlegroups.com (cc: iant, r),

I'd like you to review this change to
https://code.google.com/p/go/

[iant, 2014-08-06 15:54:04]

LGTM

https://codereview.appspot.com/125720043/diff/40001/src/cmd/gc/bv.c
File src/cmd/gc/bv.c (right):

https://codereview.appspot.com/125720043/diff/40001/src/cmd/gc/bv.c#newcode115
src/cmd/gc/bv.c:115: while(i < bv->n && bv->b[i>>WORDSHIFT] == 0)
If this is important you could tighten it up a bit more.  i>>WORDSHIFT can't
really turn into an induction variable because it's signed.
    uint32_t *p = bv->b + (i>>WORDSHIFT) + 1;
    uint32_t *pend = bv->b + (bv->n>>WORDSHIFT);
    while (1) {
        if (p > pend)
            return -1;
        if (*p == 0)
            break;
        p++;
    }
    i = (pend - p) << WORDSHIFT;

https://codereview.appspot.com/125720043/diff/40001/src/cmd/gc/plive.c
File src/cmd/gc/plive.c (right):

https://codereview.appspot.com/125720043/diff/40001/src/cmd/gc/plive.c#newcod...
src/cmd/gc/plive.c:286: ll->n->opt = nil;
A comment about these fields would be nice.

[r, 2014-08-06 15:56:46]

LGTM
nice

[rsc, 2014-08-06 16:18:03]

https://codereview.appspot.com/125720043/diff/40001/src/cmd/gc/bv.c
File src/cmd/gc/bv.c (right):

https://codereview.appspot.com/125720043/diff/40001/src/cmd/gc/bv.c#newcode115
src/cmd/gc/bv.c:115: while(i < bv->n && bv->b[i>>WORDSHIFT] == 0)
Thanks. I'm not sure it's that important. I'm really just going for the 32x
reduction in function calls.

[rsc, 2014-08-06 19:46:40]

*** Submitted as https://code.google.com/p/go/source/detail?r=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 issue 8259.
Fixes issue 8354.

LGTM=iant, r
R=golang-codereviews, iant, r
CC=golang-codereviews
https://codereview.appspot.com/125720043