code review 7432050: strings: Optimized Replace to be 2x faster.

strings: Optimized Replace to be 2x faster.

The main idea is to avoid replace count calculation.
If len(old) <= len(new) , we make a string with 0 length and a cap of len(s), otherwise we make a string with 0 length and a cap of len(s)*1.5.

The downside is a small proportion of memory will be wasted. but if the len(old) == len(new), there would be no tradeoff at all.

benchmark                    old ns/op    new ns/op    delta
BenchmarkByteByteReplaces         8480         1364  -83.92%
BenchmarkReplaceByteByte         10015         3806  -62.00%
BenchmarkReplaceDefault          13495         7356  -45.49%
BenchmarkReplaceOldEmpty        101105        45022  -55.47%

benchmark                     old MB/s     new MB/s  speedup
BenchmarkReplaceByteByte        149.77       394.09    2.63x
BenchmarkReplaceDefault         111.15       203.90    1.83x
BenchmarkReplaceOldEmpty         14.84        33.32    2.25x

[Ewan Chou, 2013-03-03 08:41:53]

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

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

[bradfitz, 2013-03-03 17:00:28]

https://codereview.appspot.com/7432050/diff/18001/src/pkg/strings/strings.go
File src/pkg/strings/strings.go (right):

https://codereview.appspot.com/7432050/diff/18001/src/pkg/strings/strings.go#...
src/pkg/strings/strings.go:644: func Replace(s, old, new string, n int) string {
Maybe this whole function should be rewritten as:

return NewReplacer(old, new).ReplaceN(new, n)

Or at least when n == -1.

Because I feel like we've already done some of these optimizations in that code
path.

[Ewan Chou, 2013-03-04 01:12:48]

On 2013/03/03 17:00:28, bradfitz wrote:
> https://codereview.appspot.com/7432050/diff/18001/src/pkg/strings/strings.go
> File src/pkg/strings/strings.go (right):
> 
>
https://codereview.appspot.com/7432050/diff/18001/src/pkg/strings/strings.go#...
> src/pkg/strings/strings.go:644: func Replace(s, old, new string, n int) string
{
> Maybe this whole function should be rewritten as:
> 
> return NewReplacer(old, new).ReplaceN(new, n)
> 
> Or at least when n == -1.
> 
> Because I feel like we've already done some of these optimizations in that
code
> path.
Actually I started with optimizing singleStringReplacer first, but the result is
not as good, so I drop that.

I think maybe because allocating a Replacer is heavy, maybe Replacer should only
be used when multiple replacement on a string need to be done.

[bradfitz, 2013-03-04 01:27:18]

I'm afraid it's probably a little too close to Go 1.1's release right now
to be spending too much time optimizing library functions which don't have
a large and/or global effect.

Optimizing strings functions more seems marginal and local at best.

Feel free to file bugs, though, so this isn't forgotten for Go 1.2.  (or Go
1.1, if people find time to review this, but a lot of people are busy right
now...)


On Sun, Mar 3, 2013 at 5:12 PM, <coocood@gmail.com> wrote:

> On 2013/03/03 17:00:28, bradfitz wrote:
>
> https://codereview.appspot.**com/7432050/diff/18001/src/**
>
pkg/strings/strings.go<https://codereview.appspot.com/7432050/diff/18001/src/pkg/strings/strings.go>
>
>> File src/pkg/strings/strings.go (right):
>>
>
>
> https://codereview.appspot.**com/7432050/diff/18001/src/**
>
pkg/strings/strings.go#**newcode644<https://codereview.appspot.com/7432050/diff/18001/src/pkg/strings/strings.go#newcode644>
>
>> src/pkg/strings/strings.go:**644: func Replace(s, old, new string, n
>>
> int) string {
>
>> Maybe this whole function should be rewritten as:
>>
>
>  return NewReplacer(old, new).ReplaceN(new, n)
>>
>
>  Or at least when n == -1.
>>
>
>  Because I feel like we've already done some of these optimizations in
>>
> that code
>
>> path.
>>
> Actually I started with optimizing singleStringReplacer first, but the
> result is not as good, so I drop that.
>
> I think maybe because allocating a Replacer is heavy, maybe Replacer
> should only be used when multiple replacement on a string need to be
> done.
>
>
https://codereview.appspot.**com/7432050/<https://codereview.appspot.com/7432...
>

[Ewan Chou, 2013-03-04 01:28:02]

On 2013/03/04 01:12:48, Ewan Chou wrote:
> On 2013/03/03 17:00:28, bradfitz wrote:
> > https://codereview.appspot.com/7432050/diff/18001/src/pkg/strings/strings.go
> > File src/pkg/strings/strings.go (right):
> > 
> >
>
https://codereview.appspot.com/7432050/diff/18001/src/pkg/strings/strings.go#...
> > src/pkg/strings/strings.go:644: func Replace(s, old, new string, n int)
string
> {
> > Maybe this whole function should be rewritten as:
> > 
> > return NewReplacer(old, new).ReplaceN(new, n)
> > 
> > Or at least when n == -1.
> > 
> > Because I feel like we've already done some of these optimizations in that
> code
> > path.
> Actually I started with optimizing singleStringReplacer first, but the result
is
> not as good, so I drop that.
> 
> I think maybe because allocating a Replacer is heavy, maybe Replacer should
only
> be used when multiple replacement on a string need to be done.

I mean singleStringReplacer is not fast when s is short or N is small.

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

I agree with Brad. I appreciate the effort, but it's too late to be rewriting
core library routines like this. It's too easy for bugs to creep in. The explode
change was relatively straightforward, and it can still get finished, but let's
stop there.

[bradfitz, 2013-06-17 21:19:35]

Q=wait

Ewan, did you still want to get this in?

[Ewan Chou, 2013-06-17 23:34:50]

On 2013/06/17 21:19:35, bradfitz wrote:
> Q=wait
> 
> Ewan, did you still want to get this in?

Yes, do you have time to review it now?

[bradfitz, 2013-06-21 20:29:49]

I think this is starting to overlap too much with strings.NewReplacer and its
selection of an algorithm.

Whatever we do in strings.Replace, it seems like there will compromises: wasted
CPU before, and wasted memory with this CL.

I'd rather we not change the compromises.

Users who find this to be a bottleneck can use strings.NewReplacer.

Perhaps we could make strings.Replace transparently call NewReplacer and keeps
its result in a timed cached.  But I think that's even overkill.  If users
profile and see the problem is Replace, they can switch to NewReplacer.

[bradfitz, 2013-06-21 20:30:05]

Q=wait

[Ewan Chou, 2013-06-22 00:58:38]

On 2013/06/21 20:30:05, bradfitz wrote:
> Q=wait

OK, I understand, but there would be no wasted memory when the old and new
string has the same length.
How about I change it to only optimize same length cases?

[rsc, 2013-07-02 00:52:38]

Please drop this CL. This is not important enough to be worth the complexity of
maintaining more code.

[Ewan Chou, 2013-07-02 02:21:26]

On 2013/07/02 00:52:38, rsc wrote:
> Please drop this CL. This is not important enough to be worth the complexity
of
> maintaining more code.

Yes, it is a little too complex.
Dropped.