Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(321)

Issue 6492076: code review 6492076: strings: implement a faster generic Replacer (Closed)

Can't Edit
Can't Publish+Mail
Start Review
Created:
11 years, 6 months ago by Eric Roshan Eisner
Modified:
11 years, 6 months ago
Reviewers:
CC:
nigeltao, rsc, golang-dev
Visibility:
Public.

Description

strings: implement a faster generic Replacer This also fixes the semantics of some corner cases with the empty match. TODOs for genericReplacer in the tests are fixed. benchmark old ns/op new ns/op delta BenchmarkGenericNoMatch 71395 3132 -95.61% BenchmarkGenericMatch1 75610 20280 -73.18% BenchmarkGenericMatch2 837995 86725 -89.65%

Patch Set 1 #

Patch Set 2 : diff -r 5c4859bc123f https://go.googlecode.com/hg #

Patch Set 3 : diff -r 5c4859bc123f https://go.googlecode.com/hg #

Total comments: 12

Patch Set 4 : diff -r 5c4859bc123f https://go.googlecode.com/hg #

Total comments: 2

Patch Set 5 : diff -r 5c4859bc123f https://go.googlecode.com/hg #

Total comments: 1

Patch Set 6 : diff -r df382f6986cf https://code.google.com/p/go #

Patch Set 7 : diff -r df382f6986cf https://code.google.com/p/go #

Patch Set 8 : diff -r df382f6986cf https://code.google.com/p/go #

Patch Set 9 : diff -r df382f6986cf https://code.google.com/p/go #

Total comments: 2

Patch Set 10 : diff -r df382f6986cf https://code.google.com/p/go #

Total comments: 1

Patch Set 11 : diff -r df382f6986cf https://code.google.com/p/go #

Total comments: 4

Patch Set 12 : diff -r c99aad44d76c https://code.google.com/p/go #

Total comments: 1

Patch Set 13 : diff -r 46a4f787e8b7 https://code.google.com/p/go #

Total comments: 2

Patch Set 14 : diff -r 46a4f787e8b7 https://code.google.com/p/go #

Patch Set 15 : diff -r cdee8bf43694 https://code.google.com/p/go #

Total comments: 5

Patch Set 16 : diff -r cdee8bf43694 https://code.google.com/p/go #

Total comments: 10

Patch Set 17 : diff -r cdee8bf43694 https://code.google.com/p/go #

Patch Set 18 : diff -r cdee8bf43694 https://code.google.com/p/go #

Patch Set 19 : diff -r cdee8bf43694 https://code.google.com/p/go #

Total comments: 12

Patch Set 20 : diff -r cdee8bf43694 https://code.google.com/p/go #

Total comments: 3
Unified diffs Side-by-side diffs Delta from patch set Stats (+346 lines, -75 lines) Patch
M src/pkg/strings/export_test.go View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 chunk +27 lines, -0 lines 0 comments Download
M src/pkg/strings/replace.go View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2 chunks +233 lines, -67 lines 2 comments Download
M src/pkg/strings/replace_test.go View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 3 chunks +86 lines, -8 lines 1 comment Download

Messages

Total messages: 46
Eric Roshan Eisner
Hello golang-dev@googlegroups.com, I'd like you to review this change to https://go.googlecode.com/hg
11 years, 6 months ago (2012-09-03 23:15:49 UTC) #1
nigeltao
https://codereview.appspot.com/6492076/diff/5001/src/pkg/strings/replace.go File src/pkg/strings/replace.go (right): https://codereview.appspot.com/6492076/diff/5001/src/pkg/strings/replace.go#newcode143 src/pkg/strings/replace.go:143: if len(key) == 0 { if key == "" ...
11 years, 6 months ago (2012-09-04 04:29:59 UTC) #2
Eric Roshan Eisner
Hello nigeltao@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
11 years, 6 months ago (2012-09-04 06:27:36 UTC) #3
Eric Roshan Eisner
https://codereview.appspot.com/6492076/diff/5001/src/pkg/strings/replace.go File src/pkg/strings/replace.go (right): https://codereview.appspot.com/6492076/diff/5001/src/pkg/strings/replace.go#newcode143 src/pkg/strings/replace.go:143: if len(key) == 0 { On 2012/09/04 04:29:59, nigeltao ...
11 years, 6 months ago (2012-09-04 06:27:52 UTC) #4
rog
LGTM A couple of trivial comments below. http://codereview.appspot.com/6492076/diff/8001/src/pkg/strings/replace.go File src/pkg/strings/replace.go (right): http://codereview.appspot.com/6492076/diff/8001/src/pkg/strings/replace.go#newcode172 src/pkg/strings/replace.go:172: } else ...
11 years, 6 months ago (2012-09-04 09:14:06 UTC) #5
remyoudompheng
Can you compare the allocation pattern before and after? (allocation count + bytes per iteration)
11 years, 6 months ago (2012-09-04 09:29:16 UTC) #6
Eric Roshan Eisner
On 2012/09/04 09:29:16, remyoudompheng wrote: > Can you compare the allocation pattern before and after? ...
11 years, 6 months ago (2012-09-04 16:18:02 UTC) #7
rsc
I am concerned about the amount of memory this will consume. [256]*trie is 2 kB ...
11 years, 6 months ago (2012-09-04 20:59:23 UTC) #8
Eric Roshan Eisner
On 2012/09/04 20:59:23, rsc wrote: > I am concerned about the amount of memory this ...
11 years, 6 months ago (2012-09-04 21:11:18 UTC) #9
Eric Roshan Eisner
Hello nigeltao@golang.org, rogpeppe@gmail.com, remyoudompheng@gmail.com, rsc@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
11 years, 6 months ago (2012-09-05 04:34:53 UTC) #10
nigeltao
https://codereview.appspot.com/6492076/diff/11001/src/pkg/strings/replace.go File src/pkg/strings/replace.go (right): https://codereview.appspot.com/6492076/diff/11001/src/pkg/strings/replace.go#newcode178 src/pkg/strings/replace.go:178: } else if node.prefix != "" && node.prefix == ...
11 years, 6 months ago (2012-09-05 07:27:14 UTC) #11
Eric Roshan Eisner
Hello nigeltao@golang.org, rogpeppe@gmail.com, remyoudompheng@gmail.com, rsc@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
11 years, 6 months ago (2012-09-05 15:36:49 UTC) #12
Eric Roshan Eisner
On 2012/09/05 07:27:14, nigeltao wrote: > https://codereview.appspot.com/6492076/diff/11001/src/pkg/strings/replace.go > File src/pkg/strings/replace.go (right): > > https://codereview.appspot.com/6492076/diff/11001/src/pkg/strings/replace.go#newcode178 > ...
11 years, 6 months ago (2012-09-05 15:40:53 UTC) #13
Eric Roshan Eisner
Hello nigeltao@golang.org, rogpeppe@gmail.com, remyoudompheng@gmail.com, rsc@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
11 years, 6 months ago (2012-09-05 15:43:22 UTC) #14
Eric Roshan Eisner
Hello nigeltao@golang.org, rogpeppe@gmail.com, remyoudompheng@gmail.com, rsc@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
11 years, 6 months ago (2012-09-05 17:42:27 UTC) #15
rsc
I'm sorry, but while I am still worried about the memory usage, To get the ...
11 years, 6 months ago (2012-09-05 22:11:43 UTC) #16
Eric Roshan Eisner
Hello nigeltao@golang.org, rogpeppe@gmail.com, remyoudompheng@gmail.com, rsc@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
11 years, 6 months ago (2012-09-06 00:03:02 UTC) #17
Eric Roshan Eisner
On 2012/09/05 22:11:43, rsc wrote: > I'm sorry, but while I am still worried about ...
11 years, 6 months ago (2012-09-06 00:05:56 UTC) #18
rsc
> This is a clever trick. I added this mapping using a [256]int (otherwise > ...
11 years, 6 months ago (2012-09-06 00:47:05 UTC) #19
nigeltao
The original post says > BenchmarkGenericNoMatch 2482 ns/op -96.36% > BenchmarkGenericMatch 6995 ns/op -90.42% but ...
11 years, 6 months ago (2012-09-06 03:23:58 UTC) #20
Eric Roshan Eisner
On 2012/09/06 03:23:58, nigeltao wrote: > The original post says > > > BenchmarkGenericNoMatch 2482 ...
11 years, 6 months ago (2012-09-06 07:53:54 UTC) #21
dsymonds
On Thu, Sep 6, 2012 at 5:53 PM, <eric.d.eisner@gmail.com> wrote: > Quick question: what tool/option ...
11 years, 6 months ago (2012-09-06 08:21:08 UTC) #22
nigeltao
On 6 September 2012 17:53, <eric.d.eisner@gmail.com> wrote: > I had updated the numbers in the ...
11 years, 6 months ago (2012-09-07 00:03:17 UTC) #23
nigeltao
https://codereview.appspot.com/6492076/diff/13004/src/pkg/strings/replace.go File src/pkg/strings/replace.go (right): https://codereview.appspot.com/6492076/diff/13004/src/pkg/strings/replace.go#newcode244 src/pkg/strings/replace.go:244: // Write wrights to the buffer to satisfy io.Writer. ...
11 years, 6 months ago (2012-09-07 00:05:08 UTC) #24
Eric Roshan Eisner
On 2012/09/07 00:03:17, nigeltao wrote: > On 6 September 2012 17:53, <mailto:eric.d.eisner@gmail.com> wrote: > > ...
11 years, 6 months ago (2012-09-07 00:42:10 UTC) #25
Eric Roshan Eisner
Hello nigeltao@golang.org, rogpeppe@gmail.com, remyoudompheng@gmail.com, rsc@golang.org, dsymonds@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
11 years, 6 months ago (2012-09-07 00:43:36 UTC) #26
nigeltao
https://codereview.appspot.com/6492076/diff/8005/src/pkg/strings/replace.go File src/pkg/strings/replace.go (right): https://codereview.appspot.com/6492076/diff/8005/src/pkg/strings/replace.go#newcode93 src/pkg/strings/replace.go:93: // If this node has no children, the previous ...
11 years, 6 months ago (2012-09-07 08:17:35 UTC) #27
Eric Roshan Eisner
On 2012/09/07 08:17:35, nigeltao wrote: > https://codereview.appspot.com/6492076/diff/8005/src/pkg/strings/replace.go > File src/pkg/strings/replace.go (right): > > https://codereview.appspot.com/6492076/diff/8005/src/pkg/strings/replace.go#newcode93 > ...
11 years, 6 months ago (2012-09-07 18:03:20 UTC) #28
Eric Roshan Eisner
Hello nigeltao@golang.org, rogpeppe@gmail.com, remyoudompheng@gmail.com, rsc@golang.org, dsymonds@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
11 years, 6 months ago (2012-09-07 18:03:48 UTC) #29
nigeltao
https://codereview.appspot.com/6492076/diff/7005/src/pkg/strings/replace_test.go File src/pkg/strings/replace_test.go (right): https://codereview.appspot.com/6492076/diff/7005/src/pkg/strings/replace_test.go#newcode83 src/pkg/strings/replace_test.go:83: // Added here for initialization. You might as well ...
11 years, 6 months ago (2012-09-11 03:14:41 UTC) #30
Eric Roshan Eisner
Hello nigeltao@golang.org, rogpeppe@gmail.com, remyoudompheng@gmail.com, rsc@golang.org, dsymonds@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
11 years, 6 months ago (2012-09-11 05:08:55 UTC) #31
nigeltao
I think that the data structure is generally OK, but the code could be re-written ...
11 years, 6 months ago (2012-09-11 08:56:32 UTC) #32
Eric Roshan Eisner
> I think that the data structure is generally OK, but the code could be ...
11 years, 6 months ago (2012-09-11 20:08:31 UTC) #33
rsc
You can add exported helpers to export_test.go and they will be available during testing. Russ
11 years, 6 months ago (2012-09-11 20:40:35 UTC) #34
Eric Roshan Eisner
Hello nigeltao@golang.org, rsc@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
11 years, 6 months ago (2012-09-11 21:57:29 UTC) #35
Eric Roshan Eisner
Hello nigeltao@golang.org, rsc@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
11 years, 6 months ago (2012-09-12 01:11:41 UTC) #36
nigeltao
http://codereview.appspot.com/6492076/diff/2008/src/pkg/strings/export_test.go File src/pkg/strings/export_test.go (right): http://codereview.appspot.com/6492076/diff/2008/src/pkg/strings/export_test.go#newcode29 src/pkg/strings/export_test.go:29: index := int(m) You don't really need this variable. ...
11 years, 6 months ago (2012-09-12 12:23:57 UTC) #37
Eric Roshan Eisner
On 2012/09/12 12:23:57, nigeltao wrote: > http://codereview.appspot.com/6492076/diff/2008/src/pkg/strings/export_test.go > File src/pkg/strings/export_test.go (right): > > http://codereview.appspot.com/6492076/diff/2008/src/pkg/strings/export_test.go#newcode29 > ...
11 years, 6 months ago (2012-09-12 15:33:14 UTC) #38
nigeltao
https://codereview.appspot.com/6492076/diff/12011/src/pkg/strings/replace.go File src/pkg/strings/replace.go (right): https://codereview.appspot.com/6492076/diff/12011/src/pkg/strings/replace.go#newcode83 src/pkg/strings/replace.go:83: type trie struct { s/trie/trieNode/ might be a better ...
11 years, 6 months ago (2012-09-13 08:05:58 UTC) #39
nigeltao
https://codereview.appspot.com/6492076/diff/12011/src/pkg/strings/replace_test.go File src/pkg/strings/replace_test.go (right): https://codereview.appspot.com/6492076/diff/12011/src/pkg/strings/replace_test.go#newcode305 src/pkg/strings/replace_test.go:305: testCases := []struct{ in, out string }{ On 2012/09/13 ...
11 years, 6 months ago (2012-09-13 09:06:42 UTC) #40
nigeltao
http://codereview.appspot.com/6492076/diff/12011/src/pkg/strings/replace.go File src/pkg/strings/replace.go (right): http://codereview.appspot.com/6492076/diff/12011/src/pkg/strings/replace.go#newcode204 src/pkg/strings/replace.go:204: root *trie Dropping the * would also save you ...
11 years, 6 months ago (2012-09-13 10:47:53 UTC) #41
Eric Roshan Eisner
On 2012/09/13 08:05:58, nigeltao wrote: > https://codereview.appspot.com/6492076/diff/12011/src/pkg/strings/replace.go > File src/pkg/strings/replace.go (right): > > https://codereview.appspot.com/6492076/diff/12011/src/pkg/strings/replace.go#newcode83 > ...
11 years, 6 months ago (2012-09-13 16:27:48 UTC) #42
nigeltao
This is getting pretty close. https://codereview.appspot.com/6492076/diff/13010/src/pkg/strings/replace.go File src/pkg/strings/replace.go (right): https://codereview.appspot.com/6492076/diff/13010/src/pkg/strings/replace.go#newcode128 src/pkg/strings/replace.go:128: // 'y', which remap ...
11 years, 6 months ago (2012-09-14 04:10:28 UTC) #43
Eric Roshan Eisner
On 2012/09/14 04:10:28, nigeltao wrote: > This is getting pretty close. > > https://codereview.appspot.com/6492076/diff/13010/src/pkg/strings/replace.go > ...
11 years, 6 months ago (2012-09-14 07:15:30 UTC) #44
nigeltao
LGTM, submitting... Thanks for your patience in this code review. https://codereview.appspot.com/6492076/diff/6006/src/pkg/strings/replace.go File src/pkg/strings/replace.go (right): https://codereview.appspot.com/6492076/diff/6006/src/pkg/strings/replace.go#newcode113 ...
11 years, 6 months ago (2012-09-17 01:49:24 UTC) #45
nigeltao
11 years, 6 months ago (2012-09-17 01:50:55 UTC) #46
*** Submitted as http://code.google.com/p/go/source/detail?r=23b89fb47d66 ***

strings: implement a faster generic Replacer

This also fixes the semantics of some corner cases with the empty
match. TODOs for genericReplacer in the tests are fixed.

benchmark                  old ns/op    new ns/op    delta
BenchmarkGenericNoMatch        71395         3132  -95.61%
BenchmarkGenericMatch1         75610        20280  -73.18%
BenchmarkGenericMatch2        837995        86725  -89.65%

R=nigeltao, rsc
CC=golang-dev
http://codereview.appspot.com/6492076

Committer: Nigel Tao <nigeltao@golang.org>
Sign in to reply to this message.

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b