code review 6821094: reflect: fix FieldByNameFunc

reflect: fix FieldByNameFunc

The existing algorithm did not properly propagate the type
count from one level to the next, and as a consequence it
missed collisions.

Properly propagate multiplicity (count) information to the
next level.

benchmark                old ns/op    new ns/op    delta
BenchmarkFieldByName1          182          180   -1.10%
BenchmarkFieldByName2         6273         6183   -1.43%
BenchmarkFieldByName3        49267        46784   -5.04%

Fixes issue 4355.

[gri, 2012-11-07 19:41:16]

Hello golang-dev@googlegroups.com,

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

[gri, 2012-11-07 20:31:40]

hold your horses - I think there's a faster way
- gri

On Wed, Nov 7, 2012 at 11:41 AM,  <gri@golang.org> wrote:
> Reviewers: golang-dev_googlegroups.com,
>
> Message:
> Hello golang-dev@googlegroups.com,
>
> I'd like you to review this change to
> https://code.google.com/p/go
>
>
> Description:
> reflect: fix FieldByNameFunc
>
> The existing algorithm eliminated types occuring multiple
> times on the same level early, under the assumption that
> if they contain matches, they would cancel each other out.
> However, by eliminating them early, we miss potential
> collisions with other types, reaching the same match on
> a different path, and as a result we return false matches.
>
> It seems that there's no easy way around and we must
> search all unvisited types. As a result, the worst-case
> scenario becomes massively slower.
>
> benchmark                old ns/op    new ns/op    delta
> BenchmarkFieldByName1          190          196   +3.16%
> BenchmarkFieldByName2         6266         6245   -0.34%
> BenchmarkFieldByName3        49903      3697419  +7309.21%
>
> Fixes issue 4355.
>
> Please review this at http://codereview.appspot.com/6821094/
>
> Affected files:
>   M src/pkg/reflect/all_test.go
>   M src/pkg/reflect/type.go
>
>
> Index: src/pkg/reflect/all_test.go
> ===================================================================
> --- a/src/pkg/reflect/all_test.go
> +++ b/src/pkg/reflect/all_test.go
> @@ -1694,6 +1694,20 @@
>         S8
>  }
>
> +// The X in S15.S11.S1 and S16.S11.S1 annihilate.
> +type S14 struct {
> +       S15
> +       S16
> +}
> +
> +type S15 struct {
> +       S11
> +}
> +
> +type S16 struct {
> +       S11
> +}
> +
>  var fieldTests = []FTest{
>         {struct{}{}, "", nil, 0},
>         {struct{}{}, "Foo", nil, 0},
> @@ -1719,6 +1733,7 @@
>         {S5{}, "Y", []int{2, 0, 1}, 0},
>         {S10{}, "X", nil, 0},
>         {S10{}, "Y", []int{2, 0, 0, 1}, 0},
> +       {S14{}, "X", nil, 0},
>  }
>
>  func TestFieldByIndex(t *testing.T) {
> Index: src/pkg/reflect/type.go
> ===================================================================
> --- a/src/pkg/reflect/type.go
> +++ b/src/pkg/reflect/type.go
> @@ -856,18 +856,10 @@
>         // The algorithm is breadth first search, one depth level at a time.
>
>         // The current and next slices are work queues:
> -       // current lists the fields to visit on this depth level,
> -       // and next lists the fields on the next lower level.
> -       current := []fieldScan{}
> -       next := []fieldScan{{typ: t}}
> -
> -       // nextCount records the number of times an embedded type has been
> -       // encountered and considered for queueing in the 'next' slice.
> -       // We only queue the first one, but we increment the count on each.
> -       // If a struct type T can be reached more than once at a given depth
> level,
> -       // then it annihilates itself and need not be considered at all when
> we
> -       // process that next depth level.
> -       var nextCount map[*structType]int
> +       // current lists the types to visit on this depth level,
> +       // and next lists the types on the next lower level.
> +       current := []fieldScan{{typ: t}}
> +       next := []fieldScan{}
>
>         // visited records the structs that have been considered already.
>         // Embedded pointer fields can create cycles in the graph of
> @@ -876,23 +868,15 @@
>         // embedded type T at level 2, we won't find it in one at level 4
> either.
>         visited := map[*structType]bool{}
>
> -       for len(next) > 0 {
> -               current, next = next, current[:0]
> -               count := nextCount
> -               nextCount = nil
> +       for len(current) > 0 {
> +               // Start with empty next list
> +               next = next[:0] // don't waste underlying array
>
> -               // Process all the fields at this depth, now listed in
> 'current'.
> -               // The loop queues embedded fields found in 'next', for
> processing during the next
> -               // iteration. The multiplicity of the 'current' field counts
> is recorded
> -               // in 'count'; the multiplicity of the 'next' field counts
> is recorded in 'nextCount'.
> +               // Process all the types at this depth, listed in 'current'.
> +               // The loop queues embedded fields found in 'next', for
> +               // processing during the next iteration.
>                 for _, scan := range current {
>                         t := scan.typ
> -                       if visited[t] {
> -                               // We've looked through this type before, at
> a higher level.
> -                               // That higher level would shadow the lower
> level we're now at,
> -                               // so this one can't be useful to us. Ignore
> it.
> -                               continue
> -                       }
>                         visited[t] = true
>                         for i := range t.fields {
>                                 f := &t.fields[i]
> @@ -914,9 +898,10 @@
>                                 // Does it match?
>                                 if match(fname) {
>                                         // Potential match
> -                                       if count[t] > 1 || ok {
> +                                       if ok {
>                                                 // Name appeared multiple
> times at this level: annihilate.
> -                                               return StructField{}, false
> +                                               ok = false
> +                                               return
>                                         }
>                                         result = t.Field(i)
>                                         result.Index = nil
> @@ -927,29 +912,35 @@
>                                 }
>
>                                 // Queue embedded struct fields for
> processing with next level,
> -                               // but only if we haven't seen a match yet
> at this level and only
> -                               // if the embedded types haven't alredy been
> queued.
> -                               if ok || ntyp == nil || ntyp.Kind() !=
> Struct {
> -                                       continue
> +                               // but only if we haven't seen a match yet
> at this level and
> +                               // the kind is Struct.
> +                               if !ok && ntyp != nil && ntyp.Kind() ==
> Struct {
> +                                       styp :=
> (*structType)(unsafe.Pointer(ntyp))
> +                                       var index []int
> +                                       index = append(index, scan.index...)
> +                                       index = append(index, i)
> +                                       next = append(next, fieldScan{styp,
> index})
>                                 }
> -                               styp := (*structType)(unsafe.Pointer(ntyp))
> -                               if nextCount[styp] > 0 {
> -                                       nextCount[styp]++
> -                                       continue
> -                               }
> -                               if nextCount == nil {
> -                                       nextCount = map[*structType]int{}
> -                               }
> -                               nextCount[styp] = 1
> -                               var index []int
> -                               index = append(index, scan.index...)
> -                               index = append(index, i)
> -                               next = append(next, fieldScan{styp, index})
>                         }
>                 }
>                 if ok {
> -                       break
> +                       // Found a match at this level.
> +                       return
>                 }
> +
> +               // No match so far; compute the list to search for the next
> level.
> +               current = current[:0] // don't waste underlying array
> +               for _, fs := range next {
> +                       // We can ignore types visited already, but we
> cannot ignore
> +                       // types appearing multiple times on the next level:
> If they
> +                       // contain a match they would cancel each other out,
> but if
> +                       // we eliminate them now, we miss potential
> collisions with
> +                       // other types also containing a match.
> +                       if !visited[fs.typ] {
> +                               current = append(current, fs)
> +                       }
> +               }
> +
>         }
>         return
>  }
>
>

[gri, 2012-11-07 23:24:18]

Hello rsc@golang.org (cc: golang-dev@googlegroups.com),

Please take another look.

[rsc, 2012-11-12 20:31:43]

The test looks good. I don't think FieldByName needs to be changed
quite so much, though. The bug in the current code is that it always
sets nextCount[styp] = 1, instead of setting nextCount[styp] =
count[t]. This is a bug left because in the first draft the loop body
was bypassed for count[t] != 1. There is a slight subtlety because
count is initialized lazily so count[t] may be 0 but mean 1:

diff -r 9ef24096faf2 src/pkg/reflect/type.go
--- a/src/pkg/reflect/type.go Mon Nov 12 15:31:23 2012 +0000
+++ b/src/pkg/reflect/type.go Mon Nov 12 15:30:48 2012 -0500
@@ -934,13 +934,16 @@
  }
  styp := (*structType)(unsafe.Pointer(ntyp))
  if nextCount[styp] > 0 {
- nextCount[styp]++
+ nextCount[styp] = 2
  continue
  }
  if nextCount == nil {
  nextCount = map[*structType]int{}
  }
  nextCount[styp] = 1
+ if count[t] > 1 {
+ nextCount[styp] = count[t]
+ }
  var index []int
  index = append(index, scan.index...)
  index = append(index, i)

This patch passes the test in this CL.

Russ

[gri, 2012-11-13 18:41:32]

Hello rsc@golang.org (cc: golang-dev@googlegroups.com),

Please take another look.

[rsc, 2012-11-13 18:44:48]

LGTM

[gri, 2012-11-13 18:45:35]

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

reflect: fix FieldByNameFunc

The existing algorithm did not properly propagate the type
count from one level to the next, and as a consequence it
missed collisions.

Properly propagate multiplicity (count) information to the
next level.

benchmark                old ns/op    new ns/op    delta
BenchmarkFieldByName1          182          180   -1.10%
BenchmarkFieldByName2         6273         6183   -1.43%
BenchmarkFieldByName3        49267        46784   -5.04%

Fixes issue 4355.

R=rsc
CC=golang-dev
http://codereview.appspot.com/6821094