code review 4121045: suffixarray: fix construction bug

suffixarray: fix construction bug

Previously, group numbers were updated while being read,
sometimes leading to inconsistencies.

[Eric Roshan Eisner, 2011-01-31 15:00:58]

Hello gri (cc: golang-dev@googlegroups.com),

I'd like you to review this change.

[gri1, 2011-01-31 19:45:44]

LGTM

http://codereview.appspot.com/4121045/diff/4/src/pkg/index/suffixarray/qsufso...
File src/pkg/index/suffixarray/qsufsort.go (right):

http://codereview.appspot.com/4121045/diff/4/src/pkg/index/suffixarray/qsufso...
src/pkg/index/suffixarray/qsufsort.go:154: defer markGroup(x.sa[first:i], x.inv,
offset+i-1)
cute!

I don't have a good understanding of this algorithm, so if this is called a lot
(relative to all the rest), using defer may not be optimal (though my
preliminary runs showed no problems)

[Eric Roshan Eisner, 2011-01-31 19:56:13]

On Mon, Jan 31, 2011 at 14:45, <gri@google.com> wrote:

> LGTM
>
>
>
>
http://codereview.appspot.com/4121045/diff/4/src/pkg/index/suffixarray/qsufso...
> File src/pkg/index/suffixarray/qsufsort.go (right):
>
>
>
http://codereview.appspot.com/4121045/diff/4/src/pkg/index/suffixarray/qsufso...
> src/pkg/index/suffixarray/qsufsort.go:154: defer
>
> markGroup(x.sa[first:i], x.inv, offset+i-1)
> cute!
>
> I don't have a good understanding of this algorithm, so if this is
> called a lot (relative to all the rest), using defer may not be optimal
> (though my preliminary runs showed no problems)


I'm not completely sure of the performance (and memory) implications of
using defer here. It was simply the most intuitive way to 'defer' all the
updating to the end. An alternative implementation would be to append to an
[]int all of the boundaries when finding them, and then update them all
afterwards.

Either way, we're generating some garbage where there was no garbage before,
and there is some [probably small] hit to the constant factor of the
algorithm. In brief benchmarking I didn't find any issues though.


>

 http://codereview.appspot.com/4121045/
>

[Eric Roshan Eisner, 2011-01-31 20:55:12]

Hello gri, gri1 (cc: golang-dev@googlegroups.com),

I'd like you to review this change.

[Eric Roshan Eisner, 2011-01-31 20:55:35]

Hello gri, gri1 (cc: golang-dev@googlegroups.com),

Please take another look.

[Eric Roshan Eisner, 2011-01-31 20:57:41]

Here's the alternative implementation without defer. The
runtimes probably aren't very different, but this one should generate a
little less garbage.

On Mon, Jan 31, 2011 at 15:55, <eric.d.eisner@gmail.com> wrote:

> Hello gri, gri1 (cc: golang-dev@googlegroups.com),
>
> Please take another look.
>
>
>
> http://codereview.appspot.com/4121045/
>

[gri, 2011-01-31 21:13:05]

*** Submitted as http://code.google.com/p/go/source/detail?r=28e01f39cba9 ***

suffixarray: fix construction bug

Previously, group numbers were updated while being read,
sometimes leading to inconsistencies.

R=gri, gri1
CC=golang-dev
http://codereview.appspot.com/4121045

Committer: Robert Griesemer <gri@golang.org>

[gri1, 2011-01-31 21:13:13]

LGTM

I liked the defer code, but this code looks equally straightforward and
probably a bit more efficient, both in execution and memory consumption; and
it's not longer, either. Let's stick to this version. Thanks.
- gri

On Mon, Jan 31, 2011 at 12:57 PM, Eric Eisner <eric.d.eisner@gmail.com>wrote:

> Here's the alternative implementation without defer. The
> runtimes probably aren't very different, but this one should generate a
> little less garbage.
>
>
> On Mon, Jan 31, 2011 at 15:55, <eric.d.eisner@gmail.com> wrote:
>
>> Hello gri, gri1 (cc: golang-dev@googlegroups.com),
>>
>> Please take another look.
>>
>>
>>
>> http://codereview.appspot.com/4121045/
>>
>
>

[rsc, 2011-02-01 12:52:43]

FYI

http://codereview.appspot.com/4121045/diff/9001/src/pkg/index/suffixarray/qsu...
File src/pkg/index/suffixarray/qsufsort.go (right):

http://codereview.appspot.com/4121045/diff/9001/src/pkg/index/suffixarray/qsu...
src/pkg/index/suffixarray/qsufsort.go:149: bounds := make([]int, 0, 4)
If you can't measure the difference, then it doesn't matter,
but the old code (using defer) was more efficient wrt 
memory allocation, because memory allocated to hold
the defer stack is cleaned up immediately after use, while 
memory allocated with make or new is left for the
garbage collector.

[Eric Roshan Eisner, 2011-02-01 15:45:10]

On Tue, Feb 1, 2011 at 07:52, <rsc@golang.org> wrote:

> FYI
>
>
>
>
>
http://codereview.appspot.com/4121045/diff/9001/src/pkg/index/suffixarray/qsu...
>
> File src/pkg/index/suffixarray/qsufsort.go (right):
>
>
>
http://codereview.appspot.com/4121045/diff/9001/src/pkg/index/suffixarray/qsu...
> src/pkg/index/suffixarray/qsufsort.go:149: bounds := make([]int, 0, 4)
> If you can't measure the difference, then it doesn't matter,
> but the old code (using defer) was more efficient wrt
> memory allocation, because memory allocated to hold
> the defer stack is cleaned up immediately after use, while
> memory allocated with make or new is left for the
> garbage collector.
>
>
> http://codereview.appspot.com/4121045/
>

Indexing about 1M random data showed the following results:

-The committed code using make/append is ~25% slower than the previous
release.
-The defer-based code is ~60% slower than the previous release.

The timing probably doesn't take into account the extra garbage collection
from the make/append approach, but it still seems like a better choice to
me.