FAQ
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/

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.
For more options, visit https://groups.google.com/groups/opt_out.

Search Discussions

  • Brad Fitzpatrick at Apr 13, 2013 at 12:11 am
    Nice.

    Likely too late for go 1.1 but good find. Leaving for r.
    On Apr 12, 2013 5:05 PM, 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/8730044/>

    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@googlegroups.com>
    .
    For more options, visit https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/opt_out>
    .

    --

    ---
    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.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Robert Hencke at Apr 13, 2013 at 1:11 am
    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, 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/8730044/>
    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/opt_out>
    .



    https://codereview.appspot.com/8730044/

    --

    ---
    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.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Jonathan at Apr 13, 2013 at 3:36 pm
    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#newcode22
    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.

    https://codereview.appspot.com/8730044/

    --

    ---
    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.
    For more options, visit https://groups.google.com/groups/opt_out.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-dev @
categoriesgo
postedApr 13, '13 at 12:10a
activeApr 13, '13 at 3:36p
posts4
users3
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase