code review 7458043: strings: optimized "explode" method to be 3 times faster.

windows 7/amd64
benchmark          old ns/op    new ns/op    delta
BenchmarkSplit1     77984460     24131380  -69.06%
BenchmarkSplit2      5222298      5802331  +11.11%
BenchmarkSplit3      4038231      4024230   -0.35%

[rsc, 2013-03-01 14:26:26]

If you write string(utf8.RuneError) you'll get rid of the remaining
allocation too.

[Ewan Chou, 2013-03-01 15:34:51]

On 2013/03/01 14:26:26, rsc wrote:
> If you write string(utf8.RuneError) you'll get rid of the remaining
> allocation too.

This is my first time to make a CL, and I tried to change it again by ran "hg
update 7458043", but it only changes description, no delta is added.

[Ewan Chou, 2013-03-01 15:37:05]

On 2013/03/01 15:34:51, Ewan Chou wrote:
> On 2013/03/01 14:26:26, rsc wrote:
> > If you write string(utf8.RuneError) you'll get rid of the remaining
> > allocation too.
> 
> This is my first time to make a CL, and I tried to change it again by ran "hg
> update 7458043", but it only changes description, no delta is added.

it was "hg change 7458043" actually, sorry

[Ewan Chou, 2013-03-01 16:16:40]

On 2013/03/01 15:37:05, Ewan Chou wrote:
> On 2013/03/01 15:34:51, Ewan Chou wrote:
> > On 2013/03/01 14:26:26, rsc wrote:
> > > If you write string(utf8.RuneError) you'll get rid of the remaining
> > > allocation too.
> > 
> > This is my first time to make a CL, and I tried to change it again by ran
"hg
> > update 7458043", but it only changes description, no delta is added.
> 
> it was "hg change 7458043" actually, sorry

finally added new patch set by "hg upload 7458043"

I only read http://golang.org/doc/contribute.html

forgot to read "hg help codereview".

[minux1, 2013-03-01 19:12:38]

On Fri, Mar 1, 2013 at 11:37 PM, <coocood@gmail.com> wrote:

> On 2013/03/01 15:34:51, Ewan Chou wrote:
>
>> On 2013/03/01 14:26:26, rsc wrote:
>> > If you write string(utf8.RuneError) you'll get rid of the remaining
>> > allocation too.
>>
>
>  This is my first time to make a CL, and I tried to change it again by
>>
> ran "hg
>
>> update 7458043", but it only changes description, no delta is added.
>>
>
> it was "hg change 7458043" actually, sorry

use "hg upload 7458043" to upload new patchset.

btw, please include benchmark results in the description, the misc/benchcmp
script will help generate delta between benchmark results.

go test -bench=. strings > old.txt
# edit your changes
go test -bench=. strings > new.txt
$GOROOT/misc/benchcmp old.txt new.txt

and paste the output into the CL description.

[dave_cheney.net, 2013-03-01 20:51:37]

Use 

hg upload 7458043

To upload a new diff. Use

hg mail 7458043

When you are ready for review. Please also provide some before/after benchmarks
as evidence. You can use the test.benchmem flag to benchmark allocations per
run, and the benchcmp tool to produce a delta between benchmarks.

BetweeSent from my iPad
 
On 02/03/2013, at 2:34 AM, coocood@gmail.com wrote:
As supporting 
> On 2013/03/01 14:26:26, rsc wrote:
>> If you write string(utf8.RuneError) you'll get rid of the remaining
>> allocation too.
> 
> This is my first time to make a CL, and I tried to change it again by
> ran "hg update 7458043", but it only changes description, no delta is
> added.
> 
> https://codereview.appspot.com/7458043/
> 
> -- 
> 
> ---You received this message because you are subscribed to the Google Groups
"golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
email to golang-dev+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
> 
> 

[Ewan Chou, 2013-03-02 02:33:12]

On 2013/03/01 19:12:38, minux wrote:
> On Fri, Mar 1, 2013 at 11:37 PM, <mailto:coocood@gmail.com> wrote:
> 
> > On 2013/03/01 15:34:51, Ewan Chou wrote:
> >
> >> On 2013/03/01 14:26:26, rsc wrote:
> >> > If you write string(utf8.RuneError) you'll get rid of the remaining
> >> > allocation too.
> >>
> >
> >  This is my first time to make a CL, and I tried to change it again by
> >>
> > ran "hg
> >
> >> update 7458043", but it only changes description, no delta is added.
> >>
> >
> > it was "hg change 7458043" actually, sorry
> 
> use "hg upload 7458043" to upload new patchset.
> 
> btw, please include benchmark results in the description, the misc/benchcmp
> script will help generate delta between benchmark results.
> 
> go test -bench=. strings > old.txt
> # edit your changes
> go test -bench=. strings > new.txt
> $GOROOT/misc/benchcmp old.txt new.txt
> 
> and paste the output into the CL description.

benchmark result updated, but "explode" doesn't has benchmark function in
"strings_test.go" so run "go test -bench=. strings" doesn't show any difference.

[dave_cheney.net, 2013-03-02 02:37:22]

Oh, could you please add some benchmarks as part of this CL?

Sent from my iPad

On 02/03/2013, at 1:33 PM, coocood@gmail.com wrote:

> On 2013/03/01 19:12:38, minux wrote:
>> On Fri, Mar 1, 2013 at 11:37 PM, <mailto:coocood@gmail.com> wrote:
> 
>> > On 2013/03/01 15:34:51, Ewan Chou wrote:
>> >
>> >> On 2013/03/01 14:26:26, rsc wrote:
>> >> > If you write string(utf8.RuneError) you'll get rid of the
> remaining
>> >> > allocation too.
>> >>
>> >
>> >  This is my first time to make a CL, and I tried to change it again
> by
>> >>
>> > ran "hg
>> >
>> >> update 7458043", but it only changes description, no delta is
> added.
>> >>
>> >
>> > it was "hg change 7458043" actually, sorry
> 
>> use "hg upload 7458043" to upload new patchset.
> 
>> btw, please include benchmark results in the description, the
> misc/benchcmp
>> script will help generate delta between benchmark results.
> 
>> go test -bench=. strings > old.txt
>> # edit your changes
>> go test -bench=. strings > new.txt
>> $GOROOT/misc/benchcmp old.txt new.txt
> 
>> and paste the output into the CL description.
> 
> benchmark result updated, but "explode" doesn't has benchmark function
> in "strings_test.go" so run "go test -bench=. strings" doesn't show any
> difference.
> 
> https://codereview.appspot.com/7458043/

[Ewan Chou, 2013-03-02 03:08:13]

Added three benchmark functions for Split method.

On 2013/03/02 02:37:22, dfc wrote:
> Oh, could you please add some benchmarks as part of this CL?
> 
> Sent from my iPad
> 
>

[dave_cheney.net, 2013-03-02 03:14:29]

Can you please do this to report the benchmark delta.

1. go test -bench=Split > old.txt
// apply your change
2. go test -bench=Split > new.txt
3. $GOROOT/misc/benchcmp {old,new}.txt 

Do this a few times to ensure the results are stable, then attach the output to
the issue description.

[Ewan Chou, 2013-03-02 04:17:08]

On 2013/03/02 03:14:29, dfc wrote:
> Can you please do this to report the benchmark delta.
> 
> 1. go test -bench=Split > old.txt
> // apply your change
> 2. go test -bench=Split > new.txt
> 3. $GOROOT/misc/benchcmp {old,new}.txt 
> 
> Do this a few times to ensure the results are stable, then attach the output
to
> the issue description.

It turns out that new explode method makes BenchmarkSplit2 about 5% slower, it's
unreasonable, as explode didn't even get called.

[Ewan Chou, 2013-03-02 06:36:30]

On 2013/03/02 04:17:08, Ewan Chou wrote:
> On 2013/03/02 03:14:29, dfc wrote:
> > Can you please do this to report the benchmark delta.
> > 
> > 1. go test -bench=Split > old.txt
> > // apply your change
> > 2. go test -bench=Split > new.txt
> > 3. $GOROOT/misc/benchcmp {old,new}.txt 
> > 
> > Do this a few times to ensure the results are stable, then attach the output
> to
> > the issue description.
> 
> It turns out that new explode method makes BenchmarkSplit2 about 5% slower,
it's
> unreasonable, as explode didn't even get called.

This happens just randomly, after I removed "if n == 0 {return nil}"
Every Split benchmark get faster.

[dave_cheney.net, 2013-03-02 06:51:20]

What OS are you benchmarking on ?

On 02/03/2013, at 17:36, coocood@gmail.com wrote:

> On 2013/03/02 04:17:08, Ewan Chou wrote:
>> On 2013/03/02 03:14:29, dfc wrote:
>> > Can you please do this to report the benchmark delta.
>> >
>> > 1. go test -bench=Split > old.txt
>> > // apply your change
>> > 2. go test -bench=Split > new.txt
>> > 3. $GOROOT/misc/benchcmp {old,new}.txt
>> >
>> > Do this a few times to ensure the results are stable, then attach
> the output
>> to
>> > the issue description.
> 
>> It turns out that new explode method makes BenchmarkSplit2 about 5%
> slower, it's
>> unreasonable, as explode didn't even get called.
> 
> This happens just randomly, after I removed "if n == 0 {return nil}"
> Every Split benchmark get faster.
> 
> https://codereview.appspot.com/7458043/

[Ewan Chou, 2013-03-02 06:53:57]

On 2013/03/02 06:51:20, dfc wrote:
> What OS are you benchmarking on ?

Windows 7 64bit GOARCH amd64

[dave_cheney.net, 2013-03-02 06:56:23]

Fair enough, using pprof on windows is quite hard, I was going to say do a
profile and see why the breakdown is. 

On 02/03/2013, at 17:53, coocood@gmail.com wrote:

> On 2013/03/02 06:51:20, dfc wrote:
>> What OS are you benchmarking on ?
> 
> Windows 7 64bit GOARCH amd64
> 
> 
> https://codereview.appspot.com/7458043/

[rsc, 2013-03-04 15:05:51]

The code looks fine to me, and the benchmarks are fine too. 5% due to code
moving around is sadly not uncommon. 

However, please change the allocation to make([]string, n), dropping the +1 and
adjusting the indices accordingly. The first entry is just wasted space, and
while it's small, this is library code so it's best to do things right.

[Ewan Chou, 2013-03-04 15:15:33]

On 2013/03/04 15:05:51, rsc wrote:
> The code looks fine to me, and the benchmarks are fine too. 5% due to code
> moving around is sadly not uncommon. 
> 
> However, please change the allocation to make([]string, n), dropping the +1
and
> adjusting the indices accordingly. The first entry is just wasted space, and
> while it's small, this is library code so it's best to do things right.

I created another issue to optimize Replace method, and that includes this two
files too, can I update changes to that issue instead?

https://codereview.appspot.com/7432050/

[rsc, 2013-03-04 15:36:20]

No, see my comments on the other issue. I'm willing to get the explode
change in because it's very straightforward, but in general it's too close
to Go 1.1 to be rewriting other core pieces and possibly introducing bugs.

Russ

[Ewan Chou, 2013-03-04 15:43:13]

On 2013/03/04 15:36:20, rsc wrote:
> No, see my comments on the other issue. I'm willing to get the explode
> change in because it's very straightforward, but in general it's too close
> to Go 1.1 to be rewriting other core pieces and possibly introducing bugs.
> 
> Russ

If I avoid the extra memory space, a compare operation have be added in the
loop, I'm not sure is it really worth it.

[Ewan Chou, 2013-03-04 15:59:05]

On 2013/03/04 15:43:13, Ewan Chou wrote:
> On 2013/03/04 15:36:20, rsc wrote:
> > No, see my comments on the other issue. I'm willing to get the explode
> > change in because it's very straightforward, but in general it's too close
> > to Go 1.1 to be rewriting other core pieces and possibly introducing bugs.
> > 
> > Russ
> 
> If I avoid the extra memory space, a compare operation have be added in the
> loop, I'm not sure is it really worth it.

I fingured out how to remove the extra memory without adding compare operation.

[Ewan Chou, 2013-03-04 16:59:13]

On 2013/03/04 15:59:05, Ewan Chou wrote:
> On 2013/03/04 15:43:13, Ewan Chou wrote:
> > On 2013/03/04 15:36:20, rsc wrote:
> > > No, see my comments on the other issue. I'm willing to get the explode
> > > change in because it's very straightforward, but in general it's too close
> > > to Go 1.1 to be rewriting other core pieces and possibly introducing bugs.
> > > 
> > > Russ
> > 
> > If I avoid the extra memory space, a compare operation have be added in the
> > loop, I'm not sure is it really worth it.
> 
> I fingured out how to remove the extra memory without adding compare
operation.

although I still added a assignment operation in the loop but I think the code
is more straightforward now.

[Ewan Chou, 2013-03-05 09:54:25]

Hello golang-dev@googlegroups.com, rsc@golang.org, minux.ma@gmail.com,
dave@cheney.net (cc: golang-dev@googlegroups.com),

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

[dave_cheney.net, 2013-03-06 03:09:41]

linux/amd64, tip

lucky(~/go/src/pkg/strings) % ~/go/misc/benchcmp {old,new}.txt
benchmark          old ns/op    new ns/op    delta
BenchmarkSplit1    100105364     27815460  -72.21%
BenchmarkSplit2      6565986      6491111   -1.14%
BenchmarkSplit3      4638642      4890052   +5.42%

[dave_cheney.net, 2013-03-06 03:12:43]

While this is a great speedup in Split1 (and also a huge reduction in
allocs/op), how common is split("") ? We pay a 5% penalty for split("hello")
which is probably a more common case (not "hello", but maybe "xml:", for
example).

[Ewan Chou, 2013-03-06 03:32:53]

On 2013/03/06 03:12:43, dfc wrote:
> While this is a great speedup in Split1 (and also a huge reduction in
> allocs/op), how common is split("") ? We pay a 5% penalty for split("hello")
> which is probably a more common case (not "hello", but maybe "xml:", for
> example).

I beleive this penalty varies on different platform.
On both my windows7/amd64 and ubuntu12.04/64bit(vmware) the overall benchmark
result for Split2 and Split3 is better.

[Ewan Chou, 2013-03-06 03:40:33]

On 2013/03/06 03:32:53, Ewan Chou wrote:
> On 2013/03/06 03:12:43, dfc wrote:
> > While this is a great speedup in Split1 (and also a huge reduction in
> > allocs/op), how common is split("") ? We pay a 5% penalty for split("hello")
> > which is probably a more common case (not "hello", but maybe "xml:", for
> > example).
> 
> I beleive this penalty varies on different platform.
> On both my windows7/amd64 and ubuntu12.04/64bit(vmware) the overall benchmark
> result for Split2 and Split3 is better.

And on my Ubuntu 12.04 64bit Vmware, the Split2 got 10% speed up after the
change.

A wild guess is that this is compiler issue which can be addressed in the
future.

[dave_cheney.net, 2013-03-06 03:44:42]

I think it is benchmarking inside a VM.

On Tue, Mar 5, 2013 at 10:40 PM,  <coocood@gmail.com> wrote:
> On 2013/03/06 03:32:53, Ewan Chou wrote:
>>
>> On 2013/03/06 03:12:43, dfc wrote:
>> > While this is a great speedup in Split1 (and also a huge reduction
>
> in
>>
>> > allocs/op), how common is split("") ? We pay a 5% penalty for
>
> split("hello")
>>
>> > which is probably a more common case (not "hello", but maybe "xml:",
>
> for
>>
>> > example).
>
>
>> I beleive this penalty varies on different platform.
>> On both my windows7/amd64 and ubuntu12.04/64bit(vmware) the overall
>
> benchmark
>>
>> result for Split2 and Split3 is better.
>
>
> And on my Ubuntu 12.04 64bit Vmware, the Split2 got 10% speed up after
> the change.
>
> A wild guess is that this is compiler issue which can be addressed in
> the future.
>
> https://codereview.appspot.com/7458043/

[Ewan Chou, 2013-03-06 03:46:55]

On 2013/03/06 03:44:42, dfc wrote:
> I think it is benchmarking inside a VM.
> 
> On Tue, Mar 5, 2013 at 10:40 PM,  <mailto:coocood@gmail.com> wrote:
> > On 2013/03/06 03:32:53, Ewan Chou wrote:
> >>
> >> On 2013/03/06 03:12:43, dfc wrote:
> >> > While this is a great speedup in Split1 (and also a huge reduction
> >
> > in
> >>
> >> > allocs/op), how common is split("") ? We pay a 5% penalty for
> >
> > split("hello")
> >>
> >> > which is probably a more common case (not "hello", but maybe "xml:",
> >
> > for
> >>
> >> > example).
> >
> >
> >> I beleive this penalty varies on different platform.
> >> On both my windows7/amd64 and ubuntu12.04/64bit(vmware) the overall
> >
> > benchmark
> >>
> >> result for Split2 and Split3 is better.
> >
> >
> > And on my Ubuntu 12.04 64bit Vmware, the Split2 got 10% speed up after
> > the change.
> >
> > A wild guess is that this is compiler issue which can be addressed in
> > the future.
> >
> > https://codereview.appspot.com/7458043/

Sorry, that vm result shold not take into consideration, that was not Tip.

[Ewan Chou, 2013-03-06 04:02:05]

I know some Chinese applications use explode extensively.

For none-ASCII text, there is no other better way to process it.

[Ewan Chou, 2013-03-06 04:13:03]

On 2013/03/06 04:02:05, Ewan Chou wrote:
> I know some Chinese applications use explode extensively.
> 
> For none-ASCII text, there is no other better way to process it.

And Split2 is used much more than Split3, more than 5x.

[rsc, 2013-03-06 04:26:43]

I'm sorry, but this is too much fine detail to worry about this close to a
release. The only truly important change here is the elimination of the
allocation, which can be done by starting with the original version and changing

a[i] = string(ch)

to

if ch == utf8.RuneError {
    a[i] = string(utf8.RuneError)
} else {
    a[i] = s[cur:cur+size]
}

If you want to apply that 1->5 line change in this CL, then we can move forward
with it and get it in before Go 1.1. The rest of the rewrites are less important
and more subtle than I want to review before Go 1.1. If you insist on including
them, then let's wait until after Go 1.1 has been released.

Thanks.

[Ewan Chou, 2013-03-06 04:31:59]

On 2013/03/06 04:26:43, rsc wrote:
> I'm sorry, but this is too much fine detail to worry about this close to a
> release. The only truly important change here is the elimination of the
> allocation, which can be done by starting with the original version and
changing
> 
> a[i] = string(ch)
> 
> to
> 
> if ch == utf8.RuneError {
>     a[i] = string(utf8.RuneError)
> } else {
>     a[i] = s[cur:cur+size]
> }
> 
> If you want to apply that 1->5 line change in this CL, then we can move
forward
> with it and get it in before Go 1.1. The rest of the rewrites are less
important
> and more subtle than I want to review before Go 1.1. If you insist on
including
> them, then let's wait until after Go 1.1 has been released.
> 
> Thanks.

OK, I changed to "range s" because it get better speed, if that make the review
harder, I can drop it for Go 1.1 release.

[Ewan Chou, 2013-03-06 04:37:38]

Hello golang-dev@googlegroups.com, rsc@golang.org, minux.ma@gmail.com,
dave@cheney.net (cc: golang-dev@googlegroups.com),

Please take another look.

[rsc, 2013-03-06 04:46:28]

Looks good. Please update the benchmarks.

[Ewan Chou, 2013-03-06 05:10:24]

On 2013/03/06 04:46:28, rsc wrote:
> Looks good. Please update the benchmarks.

benchmark updated, sadly 11.1% penalty for Split2 on windows.

[extemporalgenome, 2013-03-06 05:50:01]

Even though it's an error case, would globally setting:

const runeErrString = string(utf8.RuneError)

have any measurable benefit for error-laden inputs?

On Tuesday, March 5, 2013 10:10:24 PM UTC-7, Ewan Chou wrote:
>
> On 2013/03/06 04:46:28, rsc wrote: 
> > Looks good. Please update the benchmarks. 
>
> benchmark updated, sadly 11.1% penalty for Split2 on windows. 
>
> https://codereview.appspot.com/7458043/ 
>

[extemporalgenome, 2013-03-06 07:08:35]

I didn't actually mean "globally" -- just meant constant.

On Tuesday, March 5, 2013 10:50:00 PM UTC-7, extempor...@gmail.com wrote:
>
> Even though it's an error case, would globally setting:
>
> const runeErrString = string(utf8.RuneError)
>
> have any measurable benefit for error-laden inputs?
>

[Ewan Chou, 2013-03-06 08:28:02]

On 2013/03/06 07:08:35, extemporalgenome wrote:
> I didn't actually mean "globally" -- just meant constant.
> 
> On Tuesday, March 5, 2013 10:50:00 PM UTC-7, mailto:extempor...@gmail.com
wrote:
> >
> > Even though it's an error case, would globally setting:
> >
> > const runeErrString = string(utf8.RuneError)
> >
> > have any measurable benefit for error-laden inputs?
> >

I think the compiler will evaluated "string(constant)" to constant value at
compile time.

[Ewan Chou, 2013-03-06 13:04:06]

If I moves the declaration of "ch" and "size" into the loop, the delta drops to
+5.84%.

I just realized benchmark on changing unrelated code blindly is just waste of
time, I would never do this again.

[rsc, 2013-03-06 20:21:11]

LGTM

Don't worry about Split2. That's not this CL.

[rsc, 2013-03-06 20:21:25]

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

strings: remove allocations in Split(s, "")

BenchmarkSplit1     77984460     24131380  -69.06%

R=golang-dev, rsc, minux.ma, dave, extemporalgenome
CC=golang-dev
https://codereview.appspot.com/7458043

Committer: Russ Cox <rsc@golang.org>