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

Keyboard Shortcuts

	File
u :	up to issue
m :	publish + mail comments
M :	edit review message
j / k :	jump to file after / before current file
J / K :	jump to next file with a comment after / before current file
	Side-by-side diff
i :	toggle intra-line diffs
e :	expand all comments
c :	collapse all comments
s :	toggle showing all comments
n / p :	next / previous diff chunk or comment
N / P :	next / previous comment
<Up> / <Down> :	next / previous line
<Enter> :	respond to / edit current comment
d :	mark current comment as done

	Issue
u :	up to list of issues
m :	publish + mail comments
j / k :	jump to patch after / before current patch
o / <Enter> :	open current patch in side-by-side view
i :	open current patch in unified diff view

	Issue List
j / k :	jump to issue after / before current issue
o / <Enter> :	open current issue
# :	close issue

	Comment/message editing
<Ctrl> + s or <Ctrl> + Enter :	save comment
<Esc> :	cancel edit

Issue 121600043: code review 121600043: [release-branch.go1.3] cmd/gc: make liveness ~10x faster (Closed)

Can't Edit
Can't Publish+Mail
Start Review

Created:
9 years, 8 months ago by adg

Modified:
9 years, 8 months ago

Reviewers:

CC:
rsc, golang-codereviews

Visibility:
Public.

Description

[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 issue 8259. Fixes issue 8354. LGTM=iant, r R=golang-codereviews, iant, r CC=golang-codereviews https://codereview.appspot.com/125720043 »»»

Patch Set 1 #

Patch Set 2 : diff -r 5794f7185ba0c1f78e0235bfa8eff83bb19e7a66 https://code.google.com/p/go #

Created: 9 years, 8 months ago

Download [raw] [tar.bz2]

	Unified diffs	Side-by-side diffs	Delta from patch set	Stats (+69 lines, -35 lines)			Patch
M	src/cmd/gc/array.c	View	1	1 chunk	+0 lines, -14 lines	0 comments	Download
M	src/cmd/gc/bv.c	View	1	3 chunks	+30 lines, -6 lines	0 comments	Download
M	src/cmd/gc/go.h	View	1	2 chunks	+1 line, -1 line	0 comments	Download
M	src/cmd/gc/plive.c	View	1	7 chunks	+38 lines, -14 lines	0 comments	Download

Messages

Total messages: 2

Expand All Messages | Collapse All Messages

adg

Hello rsc (cc: golang-codereviews@googlegroups.com), I'd like you to review this change to https://code.google.com/p/go

9 years, 8 months ago (2014-08-12 20:34:34 UTC) #1

adg

9 years, 8 months ago (2014-08-12 20:34:51 UTC) #2

*** Submitted as https://code.google.com/p/go/source/detail?r=23f1ebe74d90 ***

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

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

TBR=rsc
CC=golang-codereviews
https://codereview.appspot.com/121600043

Expand All Messages | Collapse All Messages