code review 5451116: bytes: faster Count, Index, Equal

bytes: faster Count, Index, Equal

Benchmarks are from GOARCH=amd64 on a MacPro5,1.

benchmark                                    old MB/s     new MB/s  speedup
bytes_test.BenchmarkEqual32                    452.89       891.07    1.97x
bytes_test.BenchmarkEqual4K                    852.71      1700.44    1.99x
bytes_test.BenchmarkEqual4M                    841.53      1587.93    1.89x
bytes_test.BenchmarkEqual64M                   838.22      1578.14    1.88x

bytes_test.BenchmarkIndex32                     58.02        48.99    0.84x
bytes_test.BenchmarkIndex4K                     48.26        41.32    0.86x
bytes_test.BenchmarkIndex4M                     48.20        41.24    0.86x
bytes_test.BenchmarkIndex64M                    48.08        41.21    0.86x
bytes_test.BenchmarkIndexEasy32                410.04       546.82    1.33x
bytes_test.BenchmarkIndexEasy4K                849.26     14257.37   16.79x
bytes_test.BenchmarkIndexEasy4M                854.54     17222.15   20.15x
bytes_test.BenchmarkIndexEasy64M               843.57     11060.40   13.11x

bytes_test.BenchmarkCount32                     57.24        50.68    0.89x
bytes_test.BenchmarkCount4K                     48.19        41.82    0.87x
bytes_test.BenchmarkCount4M                     48.18        41.74    0.87x
bytes_test.BenchmarkCount64M                    48.17        41.71    0.87x
bytes_test.BenchmarkCountEasy32                433.11       547.44    1.26x
bytes_test.BenchmarkCountEasy4K               1130.59     14194.06   12.55x
bytes_test.BenchmarkCountEasy4M               1131.23     17231.18   15.23x
bytes_test.BenchmarkCountEasy64M              1111.40     11068.88    9.96x

The non-easy Count/Index benchmarks are a worst case input.

regexp.BenchmarkMatchEasy0_32                  237.46       221.47    0.93x
regexp.BenchmarkMatchEasy0_1K                  553.53      1019.72    1.84x
regexp.BenchmarkMatchEasy0_32K                 693.99      1672.06    2.41x
regexp.BenchmarkMatchEasy0_1M                  688.72      1611.68    2.34x
regexp.BenchmarkMatchEasy0_32M                 680.70      1565.05    2.30x
regexp.BenchmarkMatchEasy1_32                  165.56       243.08    1.47x
regexp.BenchmarkMatchEasy1_1K                  336.45       496.32    1.48x
regexp.BenchmarkMatchEasy1_32K                 302.80       425.63    1.41x
regexp.BenchmarkMatchEasy1_1M                  300.42       414.20    1.38x
regexp.BenchmarkMatchEasy1_32M                 299.64       413.47    1.38x

[rsc, 2011-12-07 16:35:23]

Hello golang-dev@googlegroups.com,

I'd like you to review this change to
https://go.googlecode.com/hg/

[r, 2011-12-07 17:06:58]

REP LGTM

http://codereview.appspot.com/5451116/diff/1003/src/pkg/bytes/bytes_test.go
File src/pkg/bytes/bytes_test.go (right):

http://codereview.appspot.com/5451116/diff/1003/src/pkg/bytes/bytes_test.go#n...
src/pkg/bytes/bytes_test.go:411: println("bad count", j)
this has been bugging me for a while. note to self: put the Log and Logf
functions etc. into testing.B.

[iant, 2011-12-07 19:14:03]

LGTM

http://codereview.appspot.com/5451116/diff/1003/src/pkg/bytes/asm_386.s
File src/pkg/bytes/asm_386.s (right):

http://codereview.appspot.com/5451116/diff/1003/src/pkg/bytes/asm_386.s#newco...
src/pkg/bytes/asm_386.s:27: CLD
You don't really need the CLD here or elsewhere.  The x86 ABI specifies that CLD
is always clear at function entry or exit.  The Go code never executes STD. 
There shouldn't be any way that the direction flag could be set at this point.

Some older versions of Linux and FreeBSD kernels fail to clear the direction
flag when entering a signal handler, but 1) that has been fixed for a couple of
years; 2) I don't think it is relevant here because this code will not be called
from a signal handler.

http://codereview.appspot.com/5451116/diff/1003/src/pkg/bytes/asm_386.s#newco...
src/pkg/bytes/asm_386.s:28: REP; CMPSB
I think this should be REPE, not REP.  Unless this is funny 8a syntax.

http://codereview.appspot.com/5451116/diff/1003/src/pkg/bytes/asm_amd64.s
File src/pkg/bytes/asm_amd64.s (right):

http://codereview.appspot.com/5451116/diff/1003/src/pkg/bytes/asm_amd64.s#new...
src/pkg/bytes/asm_amd64.s:97: MOVL	$1, DX
The MOVL to DX can be after the JNE.

http://codereview.appspot.com/5451116/diff/1003/src/pkg/bytes/asm_amd64.s#new...
src/pkg/bytes/asm_amd64.s:102: CLD
Here again the CLD should be unnecessary.

http://codereview.appspot.com/5451116/diff/1003/src/pkg/bytes/asm_amd64.s#new...
src/pkg/bytes/asm_amd64.s:103: REP; CMPSB
Here again it seems to me this should be REPE.

http://codereview.appspot.com/5451116/diff/1003/src/pkg/bytes/bytes.go
File src/pkg/bytes/bytes.go (right):

http://codereview.appspot.com/5451116/diff/1003/src/pkg/bytes/bytes.go#newcode81
src/pkg/bytes/bytes.go:81: return utf8.RuneCount(s) + 1
I know it has nothing to do with this CL but I don't understand why the correct
answer when len(sep) == 0 is not len(s) + 1.  Nothing else in this function
worries about runes.

[rsc, 2011-12-07 20:09:40]

On Wed, Dec 7, 2011 at 14:14,  <iant@golang.org> wrote:
> You don't really need the CLD here or elsewhere.  The x86 ABI specifies
> that CLD is always clear at function entry or exit.  The Go code never
> executes STD.  There shouldn't be any way that the direction flag could
> be set at this point.

I know that in theory but I have not gotten up the
courage to define that D is always clear in the Go ABI.
There are TODOs in various places but for now the
convention is to keep the CLD instructions explicit.

> The MOVL to DX can be after the JNE.

Thanks.  I was trying to space out the set and the use
but I agree that is at the least premature optimization.
I have no evidence that it matters.

> I think this should be REPE, not REP.  Unless this is funny 8a syntax.

I suppose it is funny 8a syntax.
REPE and REP are the same instruction
so it only has one name.

> I know it has nothing to do with this CL but I don't understand why the
> correct answer when len(sep) == 0 is not len(s) + 1.  Nothing else in
> this function worries about runes.

Yeah, this could go either way.
If you are assuming the input is UTF-8 then I assert
you don't want to count empty strings in the middle
of UTF-8 sequences, but it's true that this does not
have to make any other assumptions about UTF-8.
Maybe we should change it.

Russ

[rsc, 2011-12-07 20:09:59]

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

bytes: faster Count, Index, Equal

Benchmarks are from GOARCH=amd64 on a MacPro5,1.

benchmark                                    old MB/s     new MB/s  speedup
bytes_test.BenchmarkEqual32                    452.89       891.07    1.97x
bytes_test.BenchmarkEqual4K                    852.71      1700.44    1.99x
bytes_test.BenchmarkEqual4M                    841.53      1587.93    1.89x
bytes_test.BenchmarkEqual64M                   838.22      1578.14    1.88x

bytes_test.BenchmarkIndex32                     58.02        48.99    0.84x
bytes_test.BenchmarkIndex4K                     48.26        41.32    0.86x
bytes_test.BenchmarkIndex4M                     48.20        41.24    0.86x
bytes_test.BenchmarkIndex64M                    48.08        41.21    0.86x
bytes_test.BenchmarkIndexEasy32                410.04       546.82    1.33x
bytes_test.BenchmarkIndexEasy4K                849.26     14257.37   16.79x
bytes_test.BenchmarkIndexEasy4M                854.54     17222.15   20.15x
bytes_test.BenchmarkIndexEasy64M               843.57     11060.40   13.11x

bytes_test.BenchmarkCount32                     57.24        50.68    0.89x
bytes_test.BenchmarkCount4K                     48.19        41.82    0.87x
bytes_test.BenchmarkCount4M                     48.18        41.74    0.87x
bytes_test.BenchmarkCount64M                    48.17        41.71    0.87x
bytes_test.BenchmarkCountEasy32                433.11       547.44    1.26x
bytes_test.BenchmarkCountEasy4K               1130.59     14194.06   12.55x
bytes_test.BenchmarkCountEasy4M               1131.23     17231.18   15.23x
bytes_test.BenchmarkCountEasy64M              1111.40     11068.88    9.96x

The non-easy Count/Index benchmarks are a worst case input.

regexp.BenchmarkMatchEasy0_32                  237.46       221.47    0.93x
regexp.BenchmarkMatchEasy0_1K                  553.53      1019.72    1.84x
regexp.BenchmarkMatchEasy0_32K                 693.99      1672.06    2.41x
regexp.BenchmarkMatchEasy0_1M                  688.72      1611.68    2.34x
regexp.BenchmarkMatchEasy0_32M                 680.70      1565.05    2.30x
regexp.BenchmarkMatchEasy1_32                  165.56       243.08    1.47x
regexp.BenchmarkMatchEasy1_1K                  336.45       496.32    1.48x
regexp.BenchmarkMatchEasy1_32K                 302.80       425.63    1.41x
regexp.BenchmarkMatchEasy1_1M                  300.42       414.20    1.38x
regexp.BenchmarkMatchEasy1_32M                 299.64       413.47    1.38x

R=golang-dev, r, iant
CC=golang-dev
http://codereview.appspot.com/5451116