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

Issue 6262051: code review 6262051: exp/html/atom: faster Lookup with smaller tables (Closed)

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

Description

exp/html/atom: faster Lookup with smaller tables Use perfect cuckoo hash, to avoid binary search. Define Atom bits as offset+len in long string instead of enumeration, to avoid string headers. Before: 1909 string bytes + 6060 tables = 7969 total data After: 1406 string bytes + 2048 tables = 3454 total data benchmark old ns/op new ns/op delta BenchmarkLookup 83878 64681 -22.89%

Patch Set 1 #

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

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

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

Total comments: 9

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

Patch Set 6 : diff -r ef2c01ba22d1 https://go.googlecode.com/hg/ #

Patch Set 7 : diff -r ef2c01ba22d1 https://go.googlecode.com/hg/ #

Total comments: 3

Patch Set 8 : diff -r 31e36672e3df https://go.googlecode.com/hg/ #

Unified diffs Side-by-side diffs Delta from patch set Stats (+1213 lines, -1078 lines) Patch
M src/pkg/exp/html/atom/atom.go View 1 2 3 4 5 6 7 1 chunk +38 lines, -43 lines 0 comments Download
M src/pkg/exp/html/atom/atom_test.go View 1 2 2 chunks +21 lines, -6 lines 0 comments Download
M src/pkg/exp/html/atom/gen.go View 1 2 3 4 5 6 7 2 chunks +225 lines, -88 lines 0 comments Download
M src/pkg/exp/html/atom/table.go View 1 2 3 4 5 6 7 1 chunk +620 lines, -941 lines 0 comments Download
A src/pkg/exp/html/atom/table_test.go View 1 2 3 4 5 1 chunk +309 lines, -0 lines 0 comments Download

Messages

Total messages: 12
rsc
Hello nigeltao (cc: golang-dev@googlegroups.com), I'd like you to review this change to https://go.googlecode.com/hg/
11 years, 10 months ago (2012-06-01 14:06:33 UTC) #1
r
nice http://codereview.appspot.com/6262051/diff/5002/src/pkg/exp/html/atom/atom.go File src/pkg/exp/html/atom/atom.go (right): http://codereview.appspot.com/6262051/diff/5002/src/pkg/exp/html/atom/atom.go#newcode75 src/pkg/exp/html/atom/atom.go:75: // equivalent to string(s), but it may be ...
11 years, 10 months ago (2012-06-01 16:05:07 UTC) #2
nigeltao
http://codereview.appspot.com/6262051/diff/5002/src/pkg/exp/html/atom/atom.go File src/pkg/exp/html/atom/atom.go (right): http://codereview.appspot.com/6262051/diff/5002/src/pkg/exp/html/atom/atom.go#newcode50 src/pkg/exp/html/atom/atom.go:50: for i := range t { for i, c ...
11 years, 10 months ago (2012-06-02 10:25:15 UTC) #3
rsc
On Sat, Jun 2, 2012 at 6:25 AM, <nigeltao@golang.org> wrote: > http://codereview.appspot.com/6262051/diff/5002/src/pkg/exp/html/atom/atom.go#newcode50 > src/pkg/exp/html/atom/atom.go:50: for ...
11 years, 10 months ago (2012-06-02 18:04:16 UTC) #4
rsc
Hello nigeltao@golang.org, r@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
11 years, 10 months ago (2012-06-02 18:15:04 UTC) #5
r
you didn't address my question about moving the test data into a separate _test.go file.
11 years, 10 months ago (2012-06-02 18:41:00 UTC) #6
rsc
On Sat, Jun 2, 2012 at 2:41 PM, <r@golang.org> wrote: > you didn't address my ...
11 years, 10 months ago (2012-06-02 18:51:01 UTC) #7
rsc
Hello nigeltao@golang.org, r@golang.org (cc: golang-dev@googlegroups.com), Please take another look.
11 years, 10 months ago (2012-06-02 18:51:05 UTC) #8
r
LGTM but wait for nigeltao
11 years, 10 months ago (2012-06-02 20:07:07 UTC) #9
nigeltao
http://codereview.appspot.com/6262051/diff/10003/src/pkg/exp/html/atom/gen.go File src/pkg/exp/html/atom/gen.go (right): http://codereview.appspot.com/6262051/diff/10003/src/pkg/exp/html/atom/gen.go#newcode9 src/pkg/exp/html/atom/gen.go:9: // This program generates table.go Add "and table_test.go" http://codereview.appspot.com/6262051/diff/10003/src/pkg/exp/html/atom/gen.go#newcode13 ...
11 years, 10 months ago (2012-06-03 00:43:19 UTC) #10
nigeltao
LGTM.
11 years, 10 months ago (2012-06-03 00:44:00 UTC) #11
rsc
11 years, 10 months ago (2012-06-03 02:43:19 UTC) #12
*** Submitted as http://code.google.com/p/go/source/detail?r=d604b3c0962b ***

exp/html/atom: faster Lookup with smaller tables

Use perfect cuckoo hash, to avoid binary search.
Define Atom bits as offset+len in long string instead
of enumeration, to avoid string headers.

Before: 1909 string bytes + 6060 tables = 7969 total data
After: 1406 string bytes + 2048 tables = 3454 total data

benchmark          old ns/op    new ns/op    delta
BenchmarkLookup        83878        64681  -22.89%

R=nigeltao, r
CC=golang-dev
http://codereview.appspot.com/6262051
Sign in to reply to this message.

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