code review 102550043: strings: speed up byteReplacer.Replace

strings: speed up byteReplacer.Replace

benchmark                         old ns/op    new ns/op    delta
BenchmarkByteReplacerWriteString       7359         3661  -50.25%

[ruiu, 2014-06-20 03:14:56]

Hello golang-codereviews@googlegroups.com,

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

[dave_cheney.net, 2014-06-20 06:37:07]

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.go
File src/pkg/strings/replace.go (right):

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.g...
src/pkg/strings/replace.go:55: bb := &byteReplacer{}
var bb byteReplacer

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.g...
src/pkg/strings/replace.go:57: bb.new[i] = byte(i)
j := byte(i)
bb.new[j] = j // will avoid bounds checking

could this package keep a global [256]byte with these settings, then copy it
into bb.new at this point ?

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.g...
src/pkg/strings/replace.go:68: return &Replacer{r: bb}
return &Replacer{r: &bb}

[ruiu, 2014-06-20 06:52:28]

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.go
File src/pkg/strings/replace.go (right):

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.g...
src/pkg/strings/replace.go:55: bb := &byteReplacer{}
What's the point of this change? I guess bb is allocated in the heap. We have
&byteStringReplacer{} etc in this function, so I'd like to keep it consistent
with others if there's no reason to make a change.

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.g...
src/pkg/strings/replace.go:57: bb.new[i] = byte(i)
I tried but didn't observe any performance difference. Maybe it's too cheap to
intialize 256 byte memory chunk.

[dave_cheney.net, 2014-06-20 06:57:52]

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.go
File src/pkg/strings/replace.go (right):

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.g...
src/pkg/strings/replace.go:55: bb := &byteReplacer{}
On 2014/06/20 06:52:28, ruiu wrote:
> What's the point of this change? I guess bb is allocated in the heap. We have
> &byteStringReplacer{} etc in this function, so I'd like to keep it consistent
> with others if there's no reason to make a change.

Just a nit, the current style of the stdlib is moving towards declaring values
with var and returning a pointer to them if required. From the POV of the
compiler, it doesn't care. Feel free to ignore this if you don't care.

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.g...
src/pkg/strings/replace.go:57: bb.new[i] = byte(i)
On 2014/06/20 06:52:28, ruiu wrote:
> I tried but didn't observe any performance difference. Maybe it's too cheap to
> intialize 256 byte memory chunk.

Maybe the bounds check is already elided, but I thought that the type of the
index value had to be within the bounds of the array to be elided. The usual
trick is b.new[i&0xff]

What about my suggestion of copying a prepared [256]byte, that _has_ to be
faster than the loop.

[ruiu, 2014-06-20 07:01:00]

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.go
File src/pkg/strings/replace.go (right):

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.g...
src/pkg/strings/replace.go:55: bb := &byteReplacer{}
Sounds like it's a good thing to do, but we probably should do in a different
patch to do it all at once for this file.

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.g...
src/pkg/strings/replace.go:57: bb.new[i] = byte(i)
Copying a prepared [256]byte is exactly what I did. I added the following code
and then copy byteReplacerDefault to bb.new.

var byteReplacerDefault [256]byte
func init() {
        for i := 0; i < 256; i++ {
                byteReplacerDefault[i] = byte(i)
        }
}

[dave_cheney.net, 2014-06-20 07:31:27]

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.go
File src/pkg/strings/replace.go (right):

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.g...
src/pkg/strings/replace.go:57: bb.new[i] = byte(i)
on linux/arm, changing this to bb.new[i&0xff] = byte(i)

before:
benchmark                            old ns/op     new ns/op     delta       
BenchmarkByteReplacerWriteString     100814        68033         -32.52%     

after:
benchmark                            old ns/op     new ns/op     delta       
BenchmarkByteReplacerWriteString     100814        64779         -35.74%  

doing j := byte(i); bb.new[j] = j gives

benchmark                            old ns/op     new ns/op     delta       
BenchmarkByteReplacerWriteString     100814        64866         -35.66%   

Using the preprepared buffer gives, 

benchmark                            old ns/op     new ns/op     delta       
BenchmarkByteReplacerWriteString     100814        68012         -32.54%

[ruiu, 2014-06-20 07:58:05]

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.go
File src/pkg/strings/replace.go (right):

https://codereview.appspot.com/102550043/diff/60001/src/pkg/strings/replace.g...
src/pkg/strings/replace.go:57: bb.new[i] = byte(i)
Why did that change make such huge difference on ARM? On my Xeon (Nehalem) I
observe only marginal difference like 1%.

Also the results shows that your machine is about 20 times slower than mine. Is
that that slow?

I'm a bit uncomfortable to add a global variable for the prepared buffer because
the variable and the initializer makes the code uglier. I'd like you to see why
this has so much difference on ARM if you have time.

[dave_cheney.net, 2014-06-20 07:59:40]

I think I was not clear, the best result came from

bb.new[i&0xff] = byte(i)

but it's only 3% better than the version you have proposed here.

[ruiu, 2014-06-20 08:06:50]

Ah, my interpretation was wrong. I misinterpreted "old" column is the result of
this patch and "new" is this patch + your suggestion. I see now that "old" is
really old -- the default main branch.

0xff hack looks too hacky to me, so I'd want to wait for compiler improvements
and leave it as is.

As to the prepared buffer approach, I wouldn't make such change for 3%
improvement if there's a similar code in other place. So let's leave as is too.

[dave_cheney.net, 2014-06-20 08:13:06]

LGTM. That sounds fair

On Fri, Jun 20, 2014 at 6:06 PM,  <ruiu@google.com> wrote:
> Ah, my interpretation was wrong. I misinterpreted "old" column is the
> result of this patch and "new" is this patch + your suggestion. I see
> now that "old" is really old -- the default main branch.
>
> 0xff hack looks too hacky to me, so I'd want to wait for compiler
> improvements and leave it as is.
>
> As to the prepared buffer approach, I wouldn't make such change for 3%
> improvement if there's a similar code in other place. So let's leave as
> is too.
>
> https://codereview.appspot.com/102550043/

[ruiu, 2014-06-20 19:18:48]

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

strings: speed up byteReplacer.Replace

benchmark                         old ns/op    new ns/op    delta
BenchmarkByteReplacerWriteString       7359         3661  -50.25%

LGTM=dave
R=golang-codereviews, dave
CC=golang-codereviews
https://codereview.appspot.com/102550043