diff options
author | Eric Eisner <eric.d.eisner@gmail.com> | 2011-09-19 11:03:43 -0700 |
---|---|---|
committer | Robert Griesemer <gri@golang.org> | 2011-09-19 11:03:43 -0700 |
commit | 6f18233373454eae26386f0ca11cefe41106e7a0 (patch) | |
tree | b8b3bc31cde0d2243ce81167a41b4896e3ecb7e4 | |
parent | 6b6cb725e99da3bf74be53489521636ee8ee4798 (diff) | |
download | go-6f18233373454eae26386f0ca11cefe41106e7a0.tar.gz go-6f18233373454eae26386f0ca11cefe41106e7a0.zip |
suffixarray: generate less garbage during construction
Minorly improves runtime by about 2-3%
R=gri, jeff
CC=golang-dev
https://golang.org/cl/5052045
-rw-r--r-- | src/pkg/index/suffixarray/qsufsort.go | 6 |
1 files changed, 4 insertions, 2 deletions
diff --git a/src/pkg/index/suffixarray/qsufsort.go b/src/pkg/index/suffixarray/qsufsort.go index b6aa99bca3..f4ec3a1037 100644 --- a/src/pkg/index/suffixarray/qsufsort.go +++ b/src/pkg/index/suffixarray/qsufsort.go @@ -37,7 +37,7 @@ func qsufsort(data []byte) []int32 { inv := initGroups(sa, data) // the index starts 1-ordered - sufSortable := &suffixSortable{sa, inv, 1} + sufSortable := &suffixSortable{sa: sa, inv: inv, h: 1} for int(sa[0]) > -len(sa) { // until all suffixes are one big sorted group // The suffixes are h-ordered, make them 2*h-ordered @@ -135,6 +135,7 @@ type suffixSortable struct { sa []int32 inv []int32 h int32 + buf []int // common scratch space } func (x *suffixSortable) Len() int { return len(x.sa) } @@ -142,7 +143,7 @@ func (x *suffixSortable) Less(i, j int) bool { return x.inv[x.sa[i]+x.h] < x.inv func (x *suffixSortable) Swap(i, j int) { x.sa[i], x.sa[j] = x.sa[j], x.sa[i] } func (x *suffixSortable) updateGroups(offset int) { - bounds := make([]int, 0, 4) + bounds := x.buf[0:0] group := x.inv[x.sa[0]+x.h] for i := 1; i < len(x.sa); i++ { if g := x.inv[x.sa[i]+x.h]; g > group { @@ -151,6 +152,7 @@ func (x *suffixSortable) updateGroups(offset int) { } } bounds = append(bounds, len(x.sa)) + x.buf = bounds // update the group numberings after all new groups are determined prev := 0 |