delta/go-git.git/src/bytes/bytes.go, branch dev.inline

bytes, strings: optimize for ASCII sets

2016-10-28T17:37:04+00:00

In a large codebase within Google, there are thousands of uses of:
	ContainsAny|IndexAny|LastIndexAny|Trim|TrimLeft|TrimRight

An analysis of their usage shows that over 97% of them only use character
sets consisting of only ASCII symbols.

Uses of ContainsAny|IndexAny|LastIndexAny:
	 6% are 1   character  (e.g., "\n" or " ")
	58% are 2-4 characters (e.g., "<>" or "\r\n\t ")
	24% are 5-9 characters (e.g., "()[]*^$")
	10% are 10+ characters (e.g., "+-=&|>
TryBot-Result: Gobot Gobot 
Reviewed-by: Brad Fitzpatrick 
Reviewed-by: Martin Möhrmann

bytes, strings: fix regression in IndexRune

2016-10-26T23:02:27+00:00

In all previous versions of Go, the behavior of IndexRune(s, r)
where r was utf.RuneError was that it would effectively return the
index of any invalid UTF-8 byte sequence (include RuneError).
Optimizations made in http://golang.org/cl/28537 and
http://golang.org/cl/28546 altered this undocumented behavior such
that RuneError would only match on the RuneError rune itself.

Although, the new behavior is arguably reasonable, it did break code
that depended on the previous behavior. Thus, we add special checks
to ensure that we preserve the old behavior.

There is a slight performance hit for correctness:
	benchmark                   old ns/op     new ns/op     delta
	BenchmarkIndexRune/10-4     19.3          21.6          +11.92%
	BenchmarkIndexRune/32-4     33.6          35.2          +4.76%
This only occurs on small strings. The performance hit for larger strings
is neglible and not shown.

Fixes #17611

Change-Id: I1d863a741213d46c40b2e1724c41245df52502a5
Reviewed-on: https://go-review.googlesource.com/32123
Run-TryBot: Joe Tsai 
TryBot-Result: Gobot Gobot 
Reviewed-by: Brad Fitzpatrick

bytes, strings: fix snake-case in variable name

2016-10-26T21:51:48+00:00

Change-Id: I40896fffbffefa359d08abda346933aa996f628d
Reviewed-on: https://go-review.googlesource.com/32124
Reviewed-by: Brad Fitzpatrick 
Run-TryBot: Brad Fitzpatrick 
TryBot-Result: Gobot Gobot

strings, bytes: panic if Repeat overflows or if given a negative count

2016-10-01T15:47:35+00:00

Panic if Repeat is given a negative count or
if the value of (len(*) * count) is detected
to overflow.
We panic because we cannot change the
signature of Repeat to return an error.

Fixes #16237

Change-Id: I9f5ba031a5b8533db0582d7a672ffb715143f3fb
Reviewed-on: https://go-review.googlesource.com/29954
Run-TryBot: Brad Fitzpatrick 
TryBot-Result: Gobot Gobot 
Reviewed-by: Brad Fitzpatrick

bytes: make IndexRune faster

2016-09-06T23:32:57+00:00

re-implement IndexRune by IndexByte and Index which are well optimized
to get performance gain.

name                  old time/op   new time/op     delta
IndexRune/10-4         53.2ns ± 1%     29.1ns ± 1%    -45.32%  (p=0.008 n=5+5)
IndexRune/32-4          191ns ± 1%       27ns ± 1%    -85.75%  (p=0.008 n=5+5)
IndexRune/4K-4         23.5µs ± 1%      1.0µs ± 1%    -95.77%  (p=0.008 n=5+5)
IndexRune/4M-4         23.8ms ± 0%      1.0ms ± 2%    -95.90%  (p=0.008 n=5+5)
IndexRune/64M-4         384ms ± 1%       15ms ± 1%    -95.98%  (p=0.008 n=5+5)
IndexRuneASCII/10-4    61.5ns ± 0%     10.3ns ± 4%    -83.17%  (p=0.008 n=5+5)
IndexRuneASCII/32-4     203ns ± 0%       11ns ± 5%    -94.68%  (p=0.008 n=5+5)
IndexRuneASCII/4K-4    23.4µs ± 0%      0.3µs ± 2%    -98.60%  (p=0.008 n=5+5)
IndexRuneASCII/4M-4    24.0ms ± 1%      0.3ms ± 1%    -98.60%  (p=0.008 n=5+5)
IndexRuneASCII/64M-4    386ms ± 2%        6ms ± 1%    -98.57%  (p=0.008 n=5+5)

name                  old speed     new speed       delta
IndexRune/10-4        188MB/s ± 1%    344MB/s ± 1%    +82.91%  (p=0.008 n=5+5)
IndexRune/32-4        167MB/s ± 0%   1175MB/s ± 1%   +603.52%  (p=0.008 n=5+5)
IndexRune/4K-4        174MB/s ± 1%   4117MB/s ± 1%  +2262.71%  (p=0.008 n=5+5)
IndexRune/4M-4        176MB/s ± 0%   4299MB/s ± 2%  +2340.46%  (p=0.008 n=5+5)
IndexRune/64M-4       175MB/s ± 1%   4354MB/s ± 1%  +2388.57%  (p=0.008 n=5+5)
IndexRuneASCII/10-4   163MB/s ± 0%    968MB/s ± 4%   +494.66%  (p=0.008 n=5+5)
IndexRuneASCII/32-4   157MB/s ± 0%   2974MB/s ± 4%  +1788.59%  (p=0.008 n=5+5)
IndexRuneASCII/4K-4   175MB/s ± 0%  12481MB/s ± 2%  +7027.71%  (p=0.008 n=5+5)
IndexRuneASCII/4M-4   175MB/s ± 1%  12510MB/s ± 1%  +7061.15%  (p=0.008 n=5+5)
IndexRuneASCII/64M-4  174MB/s ± 2%  12143MB/s ± 1%  +6881.70%  (p=0.008 n=5+5)

Change-Id: I0632eadb83937c2a9daa7f0ce79df1dee64f992e
Reviewed-on: https://go-review.googlesource.com/28537
Run-TryBot: Brad Fitzpatrick 
TryBot-Result: Gobot Gobot 
Reviewed-by: Brad Fitzpatrick

bytes: Use the same algorithm as strings for Index

2016-09-01T18:05:50+00:00

name                     old time/op    new time/op      delta
IndexByte32-48             9.05ns ± 7%      9.59ns ±11%     +5.93%  (p=0.001 n=19+20)
IndexByte4K-48              118ns ± 4%       122ns ± 8%     +3.52%  (p=0.002 n=19+19)
IndexByte4M-48              172µs ±13%       188µs ±12%     +9.49%  (p=0.000 n=20+20)
IndexByte64M-48            8.00ms ±14%      8.05ms ±23%       ~     (p=0.799 n=20+20)
IndexBytePortable32-48     41.7ns ±15%      42.5ns ±12%       ~     (p=0.372 n=20+20)
IndexBytePortable4K-48     3.08µs ±16%      3.26µs ±10%     +5.77%  (p=0.018 n=20+20)
IndexBytePortable4M-48     3.12ms ±17%      3.20ms ±10%       ~     (p=0.157 n=20+20)
IndexBytePortable64M-48    54.0ms ±14%      55.3ms ±14%       ~     (p=0.640 n=20+20)
Index32-48                  230ns ±12%        46ns ± 6%    -79.87%  (p=0.000 n=20+19)
Index4K-48                 43.2µs ± 9%       3.2µs ±12%    -92.58%  (p=0.000 n=19+20)
Index4M-48                 44.4ms ± 7%       3.3ms ±13%    -92.59%  (p=0.000 n=19+20)
Index64M-48                 714ms ±10%        56ms ± 8%    -92.22%  (p=0.000 n=19+19)
IndexEasy32-48             52.7ns ±10%      31.0ns ±11%    -41.21%  (p=0.000 n=20+20)
IndexEasy4K-48              139ns ± 5%      1598ns ± 6%  +1046.37%  (p=0.000 n=19+19)
IndexEasy4M-48              179µs ± 8%      1674µs ±10%   +834.31%  (p=0.000 n=19+20)
IndexEasy64M-48            8.56ms ±10%     27.82ms ±16%   +225.14%  (p=0.000 n=19+20)

name                     old speed      new speed        delta
IndexByte32-48           3.52GB/s ± 7%    3.35GB/s ±11%     -4.99%  (p=0.001 n=20+20)
IndexByte4K-48           34.5GB/s ± 7%    33.2GB/s ±10%     -3.67%  (p=0.002 n=20+20)
IndexByte4M-48           24.6GB/s ±14%    22.4GB/s ±14%     -8.73%  (p=0.000 n=20+20)
IndexByte64M-48          8.42GB/s ±16%    8.42GB/s ±19%       ~     (p=0.799 n=20+20)
IndexBytePortable32-48    770MB/s ±13%     756MB/s ±11%       ~     (p=0.383 n=20+20)
IndexBytePortable4K-48   1.34GB/s ±14%    1.26GB/s ±10%     -5.76%  (p=0.018 n=20+20)
IndexBytePortable4M-48   1.35GB/s ±15%    1.31GB/s ±11%       ~     (p=0.157 n=20+20)
IndexBytePortable64M-48  1.25GB/s ±16%    1.22GB/s ±13%       ~     (p=0.640 n=20+20)
Index32-48                138MB/s ± 8%     687MB/s ± 8%   +398.57%  (p=0.000 n=19+20)
Index4K-48               94.9MB/s ± 9%  1280.5MB/s ±11%  +1249.11%  (p=0.000 n=19+20)
Index4M-48               94.6MB/s ± 7%  1278.5MB/s ±12%  +1250.99%  (p=0.000 n=19+20)
Index64M-48              94.2MB/s ±10%  1210.9MB/s ± 8%  +1185.04%  (p=0.000 n=19+19)
IndexEasy32-48            608MB/s ±10%    1035MB/s ±10%    +70.15%  (p=0.000 n=20+20)
IndexEasy4K-48           29.3GB/s ± 6%     2.6GB/s ± 6%    -91.24%  (p=0.000 n=19+19)
IndexEasy4M-48           23.3GB/s ±10%     2.5GB/s ± 9%    -89.23%  (p=0.000 n=20+20)
IndexEasy64M-48          7.86GB/s ±11%    2.42GB/s ±14%    -69.18%  (p=0.000 n=19+20)

Change-Id: Ia191f0a6ca80e113397d9ed98d25f195768b65bc
Reviewed-on: https://go-review.googlesource.com/22550
Run-TryBot: Ilya Tocar 
TryBot-Result: Gobot Gobot 
Reviewed-by: Keith Randall

bytes: add ContainsRune

2016-04-08T20:24:57+00:00

Make package bytes consistent with strings
by adding missing function ContainsRune.

Fixes #15189

Change-Id: Ie09080b389e55bbe070c57aa3bd134053a805423
Reviewed-on: https://go-review.googlesource.com/21710
Run-TryBot: Rob Pike 
TryBot-Result: Gobot Gobot 
Reviewed-by: Rob Pike

bytes: add ContainsAny

2016-04-06T21:17:08+00:00

This function is present in the strings package but missing from bytes,
and we would like to keep the two packages consistent.

Add it to bytes, and copy the test over as well.

Fixes #15140

Change-Id: I5dbd28da83a9fe741885794ed15f2af2f826cb3c
Reviewed-on: https://go-review.googlesource.com/21562
Reviewed-by: Brad Fitzpatrick

all: single space after period.

2016-03-02T00:13:47+00:00

The tree's pretty inconsistent about single space vs double space
after a period in documentation. Make it consistently a single space,
per earlier decisions. This means contributors won't be confused by
misleading precedence.

This CL doesn't use go/doc to parse. It only addresses // comments.
It was generated with:

$ perl -i -npe 's,^(\s*// .+[a-z]\.)  +([A-Z]),$1 $2,' $(git grep -l -E '^\s*//(.+\.)  +([A-Z])')
$ go test go/doc -update

Change-Id: Iccdb99c37c797ef1f804a94b22ba5ee4b500c4f7
Reviewed-on: https://go-review.googlesource.com/20022
Reviewed-by: Rob Pike 
Reviewed-by: Dave Day 
Run-TryBot: Brad Fitzpatrick 
TryBot-Result: Gobot Gobot

bytes, strings: add LastIndexByte

2015-04-30T07:13:18+00:00

Currently the packages have the following index functions:

func Index(s, sep []byte) int
func IndexAny(s []byte, chars string) int
func IndexByte(s []byte, c byte) int
func IndexFunc(s []byte, f func(r rune) bool) int
func IndexRune(s []byte, r rune) int

func LastIndex(s, sep []byte) int
func LastIndexAny(s []byte, chars string) int
func LastIndexFunc(s []byte, f func(r rune) bool) int

Searching for the last occurrence of a byte is quite common
for string parsing algorithms (e.g. find the last paren on a line).
Also addition of LastIndexByte makes the set more orthogonal.

Change-Id: Ida168849acacf8e78dd70c1354bef9eac5effafe
Reviewed-on: https://go-review.googlesource.com/9500
Reviewed-by: Rob Pike