code review 6999045: go.net/publicsuffix: tighten the encoding from 8 bytes ...

go.net/publicsuffix: tighten the encoding from 8 bytes per node to 4.

On the full list (running gen.go with -subset=false):

Before, there were 6086 nodes (at 8 bytes per node) before. After,
there were 6086 nodes (at 4 bytes per node) plus 354 children entries
(at 4 bytes per node). The difference is 22928 bytes.

In comparison, the (crushed) text is 21082 bytes, and for the curious,
the longest label is 36 bytes: "xn--correios-e-telecomunicaes-ghc29a".

All 32 bits in the nodes table are used, but there's wiggle room to
accomodate future changes to effective_tld_names.dat:

The largest children index is 353 (in 9 bits, so max is 511).
The largest node type is 2 (in 2 bits, so max is 3).
The largest text offset is 21080 (in 15 bits, so max is 32767).
The largest text length is 36 (in 6 bits, so max is 63).

benchmark                old ns/op    new ns/op    delta
BenchmarkPublicSuffix        19948        19744   -1.02%

[nigeltao, 2012-12-21 10:03:35]

Hello dr.volker.dobler@gmail.com (cc: golang-dev@googlegroups.com),

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

[volker.dobler, 2012-12-21 22:36:54]

LGTM

https://codereview.appspot.com/6999045/diff/3/publicsuffix/gen.go
File publicsuffix/gen.go (right):

https://codereview.appspot.com/6999045/diff/3/publicsuffix/gen.go#newcode271
publicsuffix/gen.go:271: // Nodes is the list of nodes. Each node is represented
as a uint32, which
s/Nodes/nodes/

https://codereview.appspot.com/6999045/diff/3/publicsuffix/gen.go#newcode295
publicsuffix/gen.go:295: // Children is the list of nodes' children, and the
wildcard bit. If a node
s/Children/children/

https://codereview.appspot.com/6999045/diff/3/publicsuffix/gen.go#newcode308
publicsuffix/gen.go:308: for i, c := range childrenEncoding {
This range childrenEncoding bugged me several minutes:
childrenEncoding has just 2 elements when declared but
gets filled during printNode which isn't obvious from
the functions name.  Maybe filling childrenEncoding
in the style of line 267 like
  n.walk(w, constructChildrenEncoding)
and pulling the childrenEncoding stuff from printNode
to constructChildrenEncoding might be a bit clearer.

https://codereview.appspot.com/6999045/diff/3/publicsuffix/gen.go#newcode309
publicsuffix/gen.go:309: s, wildcardStr := "---------------", ' '
wildcardStr is actually a char. Maybe just s/Str//

https://codereview.appspot.com/6999045/diff/3/publicsuffix/gen.go#newcode400
publicsuffix/gen.go:400: if len(c.children) != 0 {
This blocks function (filling the global childrenEncoding)
doesn't belong into a function whose name suggests just
output. (See above.)

https://codereview.appspot.com/6999045/diff/3/publicsuffix/list_test.go
File publicsuffix/list_test.go (right):

https://codereview.appspot.com/6999045/diff/3/publicsuffix/list_test.go#newco...
publicsuffix/list_test.go:216: for _, tc := range publicSuffixTestCases {
Just a remark: publicSuffixTestCases contains lots of
"interesting" test cases, but it might not represent the
average use. It is good if looking up www.city.kobe.jp
is fast, but the more common case will be lookups for
.com or .org domains.  Maybe the benchmarks should contain
at least as many simple www.google.com and golang.org
test cases as it contains test for fancy rules. Otherwise
a degradation for common cases might be overlooked too
easy.

[nigeltao, 2012-12-22 01:01:02]

Submitting...

https://codereview.appspot.com/6999045/diff/3/publicsuffix/gen.go
File publicsuffix/gen.go (right):

https://codereview.appspot.com/6999045/diff/3/publicsuffix/gen.go#newcode271
publicsuffix/gen.go:271: // Nodes is the list of nodes. Each node is represented
as a uint32, which
On 2012/12/21 22:36:54, volker.dobler wrote:
> s/Nodes/nodes/

Done.

https://codereview.appspot.com/6999045/diff/3/publicsuffix/gen.go#newcode295
publicsuffix/gen.go:295: // Children is the list of nodes' children, and the
wildcard bit. If a node
On 2012/12/21 22:36:54, volker.dobler wrote:
> s/Children/children/

Done.

https://codereview.appspot.com/6999045/diff/3/publicsuffix/gen.go#newcode308
publicsuffix/gen.go:308: for i, c := range childrenEncoding {
On 2012/12/21 22:36:54, volker.dobler wrote:
> This range childrenEncoding bugged me several minutes:
> childrenEncoding has just 2 elements when declared but
> gets filled during printNode which isn't obvious from
> the functions name.  Maybe filling childrenEncoding
> in the style of line 267 like
>   n.walk(w, constructChildrenEncoding)
> and pulling the childrenEncoding stuff from printNode
> to constructChildrenEncoding might be a bit clearer.

childrenEncoding is now constructed during assignIndexes.

https://codereview.appspot.com/6999045/diff/3/publicsuffix/gen.go#newcode309
publicsuffix/gen.go:309: s, wildcardStr := "---------------", ' '
On 2012/12/21 22:36:54, volker.dobler wrote:
> wildcardStr is actually a char. Maybe just s/Str//

Pulled out a helper function.

https://codereview.appspot.com/6999045/diff/3/publicsuffix/gen.go#newcode400
publicsuffix/gen.go:400: if len(c.children) != 0 {
On 2012/12/21 22:36:54, volker.dobler wrote:
> This blocks function (filling the global childrenEncoding)
> doesn't belong into a function whose name suggests just
> output. (See above.)

Done.

https://codereview.appspot.com/6999045/diff/3/publicsuffix/list_test.go
File publicsuffix/list_test.go (right):

https://codereview.appspot.com/6999045/diff/3/publicsuffix/list_test.go#newco...
publicsuffix/list_test.go:216: for _, tc := range publicSuffixTestCases {
On 2012/12/21 22:36:54, volker.dobler wrote:
> Just a remark: publicSuffixTestCases contains lots of
> "interesting" test cases, but it might not represent the
> average use. It is good if looking up http://www.city.kobe.jp
> is fast, but the more common case will be lookups for
> .com or .org domains.  Maybe the benchmarks should contain
> at least as many simple http://www.google.com and http://golang.org
> test cases as it contains test for fancy rules. Otherwise
> a degradation for common cases might be overlooked too
> easy.

Yeah, a representative sample would be nice, but I don't have one. This is
really just for a sanity check; I don't imagine that this would be the
bottleneck of a network-intensive program.

[nigeltao, 2012-12-22 01:11:01]

*** Submitted as
https://code.google.com/p/go/source/detail?r=3d9483b02eb3&repo=net ***

go.net/publicsuffix: tighten the encoding from 8 bytes per node to 4.

On the full list (running gen.go with -subset=false):

Before, there were 6086 nodes (at 8 bytes per node) before. After,
there were 6086 nodes (at 4 bytes per node) plus 354 children entries
(at 4 bytes per node). The difference is 22928 bytes.

In comparison, the (crushed) text is 21082 bytes, and for the curious,
the longest label is 36 bytes: "xn--correios-e-telecomunicaes-ghc29a".

All 32 bits in the nodes table are used, but there's wiggle room to
accomodate future changes to effective_tld_names.dat:

The largest children index is 353 (in 9 bits, so max is 511).
The largest node type is 2 (in 2 bits, so max is 3).
The largest text offset is 21080 (in 15 bits, so max is 32767).
The largest text length is 36 (in 6 bits, so max is 63).

benchmark                old ns/op    new ns/op    delta
BenchmarkPublicSuffix        19948        19744   -1.02%

R=dr.volker.dobler
CC=golang-dev
https://codereview.appspot.com/6999045