code review 8730044: reflect: use visit structure for map key in DeepEqual

reflect: use visit structure for map key in DeepEqual

[rh, 2013-04-13 00:05:14]

Hello golang-dev@googlegroups.com,

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

[bradfitz, 2013-04-13 00:11:29]

Nice.

Likely too late for go 1.1 but good find. Leaving for r.
 On Apr 12, 2013 5:05 PM, <robert.hencke@gmail.com> wrote:

> Reviewers: golang-dev1,
>
> Message:
> Hello golang-dev@googlegroups.com,
>
> I'd like you to review this change to
> https://code.google.com/p/go
>
>
> Description:
> reflect: use visit structure for map key in DeepEqual
>
> Please review this at
https://codereview.appspot.**com/8730044/<https://codereview.appspot.com/8730...
>
> Affected files:
>   M src/pkg/reflect/deepequal.go
>
>
> Index: src/pkg/reflect/deepequal.go
> ==============================**==============================**=======
> --- a/src/pkg/reflect/deepequal.go
> +++ b/src/pkg/reflect/deepequal.go
> @@ -9,18 +9,17 @@
>  // During deepValueEqual, must keep track of checks that are
>  // in progress.  The comparison algorithm assumes that all
>  // checks in progress are true when it reencounters them.
> -// Visited are stored in a map indexed by 17 * a1 + a2;
> +// Visited comparisons are stored in a map indexed by visit.
>  type visit struct {
> -       a1   uintptr
> -       a2   uintptr
> -       typ  Type
> -       next *visit
> +       a1  uintptr
> +       a2  uintptr
> +       typ Type
>  }
>
>  // Tests for deep equality using reflected types. The map argument tracks
>  // comparisons that have already been seen, which allows short circuiting
> on
>  // recursive types.
> -func deepValueEqual(v1, v2 Value, visited map[uintptr]*visit, depth int)
> (b bool) {
> +func deepValueEqual(v1, v2 Value, visited map[visit]bool, depth int) bool
> {
>         if !v1.IsValid() || !v2.IsValid() {
>                 return v1.IsValid() == v2.IsValid()
>         }
> @@ -44,17 +43,14 @@
>                 }
>
>                 // ... or already seen
> -               h := 17*addr1 + addr2
> -               seen := visited[h]
>                 typ := v1.Type()
> -               for p := seen; p != nil; p = p.next {
> -                       if p.a1 == addr1 && p.a2 == addr2 && p.typ == typ {
> -                               return true
> -                       }
> +               v := visit{addr1, addr2, typ}
> +               if visited[v] {
> +                       return true
>                 }
>
>                 // Remember for later.
> -               visited[h] = &visit{addr1, addr2, typ, seen}
> +               visited[v] = true
>         }
>
>         switch v1.Kind() {
> @@ -135,5 +131,5 @@
>         if v1.Type() != v2.Type() {
>                 return false
>         }
> -       return deepValueEqual(v1, v2, make(map[uintptr]*visit), 0)
> +       return deepValueEqual(v1, v2, make(map[visit]bool), 0)
>  }
>
>
> --
>
> ---You received this message because you are subscribed to the Google
> Groups "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to
golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou...
> .
> For more options, visit
https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o...
> .
>
>
>

[rh, 2013-04-13 01:11:49]

Thank you for the kind words, Brad.  I wish you folks all the best on the Go 1.1
release.

On 2013/04/13 00:11:29, bradfitz wrote:
> Nice.
> 
> Likely too late for go 1.1 but good find. Leaving for r.
>  On Apr 12, 2013 5:05 PM, <mailto:robert.hencke@gmail.com> wrote:
> 
> > Reviewers: golang-dev1,
> >
> > Message:
> > Hello mailto:golang-dev@googlegroups.com,
> >
> > I'd like you to review this change to
> > https://code.google.com/p/go
> >
> >
> > Description:
> > reflect: use visit structure for map key in DeepEqual
> >
> > Please review this at
>
https://codereview.appspot.**com/8730044/%3Chttps://codereview.appspot.com/87...>
> >
> > Affected files:
> >   M src/pkg/reflect/deepequal.go
> >
> >
> > Index: src/pkg/reflect/deepequal.go
> > ==============================**==============================**=======
> > --- a/src/pkg/reflect/deepequal.go
> > +++ b/src/pkg/reflect/deepequal.go
> > @@ -9,18 +9,17 @@
> >  // During deepValueEqual, must keep track of checks that are
> >  // in progress.  The comparison algorithm assumes that all
> >  // checks in progress are true when it reencounters them.
> > -// Visited are stored in a map indexed by 17 * a1 + a2;
> > +// Visited comparisons are stored in a map indexed by visit.
> >  type visit struct {
> > -       a1   uintptr
> > -       a2   uintptr
> > -       typ  Type
> > -       next *visit
> > +       a1  uintptr
> > +       a2  uintptr
> > +       typ Type
> >  }
> >
> >  // Tests for deep equality using reflected types. The map argument tracks
> >  // comparisons that have already been seen, which allows short circuiting
> > on
> >  // recursive types.
> > -func deepValueEqual(v1, v2 Value, visited map[uintptr]*visit, depth int)
> > (b bool) {
> > +func deepValueEqual(v1, v2 Value, visited map[visit]bool, depth int) bool
> > {
> >         if !v1.IsValid() || !v2.IsValid() {
> >                 return v1.IsValid() == v2.IsValid()
> >         }
> > @@ -44,17 +43,14 @@
> >                 }
> >
> >                 // ... or already seen
> > -               h := 17*addr1 + addr2
> > -               seen := visited[h]
> >                 typ := v1.Type()
> > -               for p := seen; p != nil; p = p.next {
> > -                       if p.a1 == addr1 && p.a2 == addr2 && p.typ == typ {
> > -                               return true
> > -                       }
> > +               v := visit{addr1, addr2, typ}
> > +               if visited[v] {
> > +                       return true
> >                 }
> >
> >                 // Remember for later.
> > -               visited[h] = &visit{addr1, addr2, typ, seen}
> > +               visited[v] = true
> >         }
> >
> >         switch v1.Kind() {
> > @@ -135,5 +131,5 @@
> >         if v1.Type() != v2.Type() {
> >                 return false
> >         }
> > -       return deepValueEqual(v1, v2, make(map[uintptr]*visit), 0)
> > +       return deepValueEqual(v1, v2, make(map[visit]bool), 0)
> >  }
> >
> >
> > --
> >
> > ---You received this message because you are subscribed to the Google
> > Groups "golang-dev" group.
> > To unsubscribe from this group and stop receiving emails from it, send an
> > email to
>
mailto:golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegroups.com>
> > .
> > For more options, visit
>
https://groups.google.com/**groups/opt_out%3Chttps://groups.google.com/groups...>
> > .
> >
> >
> >

[titanous, 2013-04-13 15:36:31]

https://codereview.appspot.com/8730044/diff/4001/src/pkg/reflect/deepequal.go
File src/pkg/reflect/deepequal.go (right):

https://codereview.appspot.com/8730044/diff/4001/src/pkg/reflect/deepequal.go...
src/pkg/reflect/deepequal.go:22: func deepValueEqual(v1, v2 Value, visited
map[visit]bool, depth int) bool {
I think you can save a bit of memory by using map[visit]struct{}, as struct{}
takes up zero bytes.

[r, 2013-04-14 17:13:25]

This can wait until after Go 1.1.

It might be worth writing a benchmark.

[r, 2013-05-15 21:37:18]

unresolved comments. want to address them?

i am fine with this as is, however. bool is fine, and i don't feel a pressing
need for a benchmark.

[bradfitz, 2013-05-15 21:40:38]

LGTM too.

I think bool is actually better than struct{} for readability.



On Wed, May 15, 2013 at 2:37 PM, <r@golang.org> wrote:

> unresolved comments. want to address them?
>
> i am fine with this as is, however. bool is fine, and i don't feel a
> pressing need for a benchmark.
>
>
>
https://codereview.appspot.**com/8730044/<https://codereview.appspot.com/8730...
>

[r, 2013-05-15 21:45:34]

LGTM

[r, 2013-05-15 21:45:41]

I'll check it in. A benchmark can come later if someone is eager (I'm not).

-rob

[r, 2013-05-15 21:51:01]

*** Submitted as https://code.google.com/p/go/source/detail?r=9f146b985681 ***

reflect: use visit structure for map key in DeepEqual

R=golang-dev, bradfitz, jonathan, r
CC=golang-dev
https://codereview.appspot.com/8730044

Committer: Rob Pike <r@golang.org>