You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@thrift.apache.org by "slachiewicz (via GitHub)" <gi...@apache.org> on 2026/09/06 18:01:30 UTC
[PR] THRIFT-6195: Compare Go set and entry-slice map fields without regard to order [thrift]
slachiewicz opened a new pull request, #3806:
URL: https://github.com/apache/thrift/pull/3806
Fixes THRIFT-6195.
Thrift defines `set` and `map` as unordered. The Go binding represents a `set`, and a `map` whose key type cannot be a Go map key, as a slice, and the generated `Equals` compared those slices position by position. Two values holding the same members in a different order therefore compared unequal.
This affects three constructs, because they share one code path in `generate_go_equals_container`:
| Thrift type | Go type | Since |
|---|---|---|
| `set<T>` | `[]T` | long-standing |
| `map<container, V>` | `[]thrift.MapEntry[K, V]` | THRIFT-2063 |
| `map<struct, V>` with `go:struct_key_entries` | `[]thrift.MapEntry[*K, V]` | THRIFT-6175, #3788 |
Java compares these with `HashSet` and `HashMap` equality and Python with `set` and `dict`, so both are order-insensitive without extra work. Go cannot use a native map or set here, because a slice, a map, or a struct holding either is not a valid Go map key. The slice representation is forced by the language; the positional comparison is not.
### What changed
Sets and entry slices now go through a new `thrift.UnorderedEqual`. Lists keep the positional comparison, because a list is ordered, so the list and set arm is split.
The helper compares position by position first and only then falls back to matching each element against an unmatched element of the other side. Values that agree on order, which includes anything that has just been deserialized, cost one pass and allocate nothing.
Matching consumes an element of the other side at most once. Without that a set holding `{a, a}` compares equal to one holding `{a, b}`, since both copies of `a` match the same element. `TestUnorderedEqual` pins that case and the symmetric one.
### Cost
The fallback is quadratic. A hashed index would make it linear for element types that can be Go map keys, but it needs a type predicate, a separate nil path, and per-type projections, and it is roughly twelve times slower than the positional pass on the common path when applied unconditionally. Trying positional first avoids paying that, and the hashed tier can be added later if a profile asks for it.
`TestUnorderedEqualOrderedPathDoesNotAllocate` pins the zero-allocation property of the fast path.
### Compatibility
This changes observable behaviour. Code whose tests depend on positional comparison of a set or an entry-slice map field will start seeing values compare equal that previously did not. Nothing semantically correct should break, since the change only makes `Equals` agree with what the Thrift type system already says these collections mean.
### Notes for the reviewer
- Opened as a draft until CI is green.
- Supersedes #3805, which GitHub closed when its branch was renamed to match the ticket.
- Overlaps in spirit with #3788, but the two are independent and touch different functions. Once both land, struct-keyed maps generated with `go:struct_key_entries` pick this up automatically.
- The `-remote` packages for `includestest` fail to build on master already, with `undefined: includestest.Numberz`. That is unrelated and not part of the `check` target.
*This change was created with AI assistance.*
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@thrift.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] THRIFT-6195: Compare Go set and entry-slice map fields without regard to order [thrift]
Posted by "slachiewicz (via GitHub)" <gi...@apache.org>.
slachiewicz commented on PR #3806:
URL: https://github.com/apache/thrift/pull/3806#issuecomment-5561175554
Rebased onto master now that #3788 has landed, which is what the two `lib-go` failures were about.
THRIFT-6175 added `TestStructKeyEqualsDetectsKeyDifference/entry_order_only`, asserting that reordering entries changes equality, plus a README paragraph saying the same. Both describe exactly the behaviour this change removes. The assertion is now its opposite, as `TestStructKeyEqualsIgnoresEntryOrder`, and the entry-slice section of the README says a map is compared as a collection.
I missed it locally because the branch was cut before #3788 merged, so neither the test nor the paragraph existed in my tree.
*This comment was created with AI assistance.*
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@thrift.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] THRIFT-6195: Compare Go set and entry-slice map fields without regard to order [thrift]
Posted by "fishy (via GitHub)" <gi...@apache.org>.
fishy merged PR #3806:
URL: https://github.com/apache/thrift/pull/3806
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@thrift.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] THRIFT-6195: Compare Go set and entry-slice map fields without regard to order [thrift]
Posted by "slachiewicz (via GitHub)" <gi...@apache.org>.
slachiewicz commented on code in PR #3806:
URL: https://github.com/apache/thrift/pull/3806#discussion_r3947752931
##########
lib/go/thrift/unordered_equal.go:
##########
@@ -0,0 +1,71 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package thrift
+
+// UnorderedEqual reports whether a and b hold the same elements, in any order,
+// comparing them with eq.
+//
+// Generated code calls this for the fields that stand in for an unordered
+// Thrift collection: a set, and a map whose key type forces the entry-slice
+// representation. Lists are ordered and are compared position by position
+// instead.
+//
+// The elements are compared position by position first, so two values that
+// agree on order, which includes any value that has just been deserialized,
+// cost one pass and allocate nothing. Only when that fails does each element
+// of a get matched against an unmatched element of b, which is quadratic.
+//
+// Matching consumes an element of b at most once, so a and b compare equal
+// only if they hold the same elements with the same multiplicities. That
+// matters for a value assembled in memory: the wire format rejects a set or
+// map that repeats an element, but nothing stops a caller from building one.
+func UnorderedEqual[T any](a, b []T, eq func(x, y T) bool) bool {
+ if len(a) != len(b) {
+ return false
+ }
+
+ ordered := true
+ for i := range a {
+ if !eq(a[i], b[i]) {
+ ordered = false
+ break
+ }
+ }
+ if ordered {
+ return true
+ }
Review Comment:
Kept, but restructured so it costs nothing: the first loop stops at the first differing pair and the pairwise phase starts from that index, so the n-2 leading matches you describe are consumed rather than repeated.
Removing it outright would make the common case quadratic and allocating — for values that agree on order, the inner loop still walks the matched prefix before `matched[j]` short-circuits it. `BenchmarkUnorderedEqualSameOrder`, 1000 elements: 3646 ns/op, 0 allocs.
Consuming the prefix is safe because `eq` is an equality: a pair it accepted can belong to any matching of the whole.
*This comment was created with AI assistance.*
##########
lib/go/thrift/unordered_equal_test.go:
##########
@@ -0,0 +1,122 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package thrift
+
+import "testing"
+
+func intEq(x, y int) bool { return x == y }
+
+func TestUnorderedEqual(t *testing.T) {
+ for name, c := range map[string]struct {
+ a, b []int
+ want bool
+ }{
+ "both nil": {nil, nil, true},
+ "nil and empty": {nil, []int{}, true},
+ "same order": {[]int{1, 2, 3}, []int{1, 2, 3}, true},
+ "reversed": {[]int{1, 2, 3}, []int{3, 2, 1}, true},
+ "rotated": {[]int{1, 2, 3}, []int{2, 3, 1}, true},
+ "single element": {[]int{1}, []int{1}, true},
+ "different element": {[]int{1, 2}, []int{1, 3}, false},
+ "shorter": {[]int{1, 2}, []int{1}, false},
+ "longer": {[]int{1}, []int{1, 2}, false},
+ "disjoint": {[]int{1, 2}, []int{3, 4}, false},
+ "same multiset": {[]int{1, 1, 2}, []int{2, 1, 1}, true},
+ "different multiplic.": {[]int{1, 1, 2}, []int{1, 2, 2}, false},
+ "all duplicates": {[]int{7, 7, 7}, []int{7, 7, 7}, true},
+ } {
+ t.Run(name, func(t *testing.T) {
+ if got := UnorderedEqual(c.a, c.b, intEq); got != c.want {
+ t.Errorf("UnorderedEqual(%v, %v) = %v, want %v", c.a, c.b, got, c.want)
+ }
+ // The relation must not depend on which side is which.
+ if got := UnorderedEqual(c.b, c.a, intEq); got != c.want {
+ t.Errorf("UnorderedEqual(%v, %v) = %v, want %v (not symmetric)", c.b, c.a, got, c.want)
+ }
+ })
+ }
+}
+
+// Elements that cannot be Go map keys take the same path as any other.
+func TestUnorderedEqualNonComparable(t *testing.T) {
+ eq := func(x, y []string) bool {
+ if len(x) != len(y) {
+ return false
+ }
+ for i := range x {
+ if x[i] != y[i] {
+ return false
+ }
+ }
+ return true
+ }
+ a := [][]string{{"a"}, {"b", "c"}}
+ b := [][]string{{"b", "c"}, {"a"}}
+ if !UnorderedEqual(a, b, eq) {
+ t.Error("reordered slice elements should compare equal")
+ }
+ if UnorderedEqual(a, [][]string{{"a"}, {"b"}}, eq) {
+ t.Error("differing slice elements should compare unequal")
+ }
+}
+
+// Comparing values that agree on order must not allocate.
+func TestUnorderedEqualOrderedPathDoesNotAllocate(t *testing.T) {
+ a := []int{1, 2, 3, 4, 5, 6, 7, 8}
+ b := []int{1, 2, 3, 4, 5, 6, 7, 8}
+ if n := testing.AllocsPerRun(100, func() {
+ if !UnorderedEqual(a, b, intEq) {
+ t.Fatal("expected equal")
+ }
+ }); n != 0 {
+ t.Errorf("ordered comparison allocated %v times per run, want 0", n)
+ }
+}
+
+func BenchmarkUnorderedEqualSameOrder(b *testing.B) {
+ x := make([]int, 1000)
+ y := make([]int, 1000)
+ for i := range x {
+ x[i], y[i] = i, i
+ }
+ b.ReportAllocs()
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ if !UnorderedEqual(x, y, intEq) {
+ b.Fatal("expected equal")
+ }
+ }
+}
+
+func BenchmarkUnorderedEqualReordered(b *testing.B) {
+ x := make([]int, 1000)
+ y := make([]int, 1000)
+ for i := range x {
+ x[i] = i
+ y[len(y)-1-i] = i
+ }
+ b.ReportAllocs()
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
Review Comment:
Done — `for b.Loop()`, `ResetTimer` dropped.
*This comment was created with AI assistance.*
##########
lib/go/thrift/unordered_equal_test.go:
##########
@@ -0,0 +1,122 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package thrift
+
+import "testing"
+
+func intEq(x, y int) bool { return x == y }
+
+func TestUnorderedEqual(t *testing.T) {
+ for name, c := range map[string]struct {
+ a, b []int
+ want bool
+ }{
+ "both nil": {nil, nil, true},
+ "nil and empty": {nil, []int{}, true},
+ "same order": {[]int{1, 2, 3}, []int{1, 2, 3}, true},
+ "reversed": {[]int{1, 2, 3}, []int{3, 2, 1}, true},
+ "rotated": {[]int{1, 2, 3}, []int{2, 3, 1}, true},
+ "single element": {[]int{1}, []int{1}, true},
+ "different element": {[]int{1, 2}, []int{1, 3}, false},
+ "shorter": {[]int{1, 2}, []int{1}, false},
+ "longer": {[]int{1}, []int{1, 2}, false},
+ "disjoint": {[]int{1, 2}, []int{3, 4}, false},
+ "same multiset": {[]int{1, 1, 2}, []int{2, 1, 1}, true},
+ "different multiplic.": {[]int{1, 1, 2}, []int{1, 2, 2}, false},
+ "all duplicates": {[]int{7, 7, 7}, []int{7, 7, 7}, true},
+ } {
+ t.Run(name, func(t *testing.T) {
+ if got := UnorderedEqual(c.a, c.b, intEq); got != c.want {
+ t.Errorf("UnorderedEqual(%v, %v) = %v, want %v", c.a, c.b, got, c.want)
+ }
+ // The relation must not depend on which side is which.
+ if got := UnorderedEqual(c.b, c.a, intEq); got != c.want {
+ t.Errorf("UnorderedEqual(%v, %v) = %v, want %v (not symmetric)", c.b, c.a, got, c.want)
+ }
+ })
+ }
+}
+
+// Elements that cannot be Go map keys take the same path as any other.
+func TestUnorderedEqualNonComparable(t *testing.T) {
+ eq := func(x, y []string) bool {
+ if len(x) != len(y) {
+ return false
+ }
+ for i := range x {
+ if x[i] != y[i] {
+ return false
+ }
+ }
+ return true
+ }
+ a := [][]string{{"a"}, {"b", "c"}}
+ b := [][]string{{"b", "c"}, {"a"}}
+ if !UnorderedEqual(a, b, eq) {
+ t.Error("reordered slice elements should compare equal")
+ }
+ if UnorderedEqual(a, [][]string{{"a"}, {"b"}}, eq) {
+ t.Error("differing slice elements should compare unequal")
+ }
+}
+
+// Comparing values that agree on order must not allocate.
+func TestUnorderedEqualOrderedPathDoesNotAllocate(t *testing.T) {
+ a := []int{1, 2, 3, 4, 5, 6, 7, 8}
+ b := []int{1, 2, 3, 4, 5, 6, 7, 8}
+ if n := testing.AllocsPerRun(100, func() {
+ if !UnorderedEqual(a, b, intEq) {
+ t.Fatal("expected equal")
+ }
+ }); n != 0 {
+ t.Errorf("ordered comparison allocated %v times per run, want 0", n)
+ }
+}
+
+func BenchmarkUnorderedEqualSameOrder(b *testing.B) {
+ x := make([]int, 1000)
+ y := make([]int, 1000)
+ for i := range x {
+ x[i], y[i] = i, i
+ }
+ b.ReportAllocs()
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
Review Comment:
Same here.
*This comment was created with AI assistance.*
##########
compiler/cpp/src/thrift/generate/t_go_generator.cc:
##########
@@ -4278,6 +4278,19 @@ void t_go_generator::generate_go_equals_struct(ostream& out,
/**
* Compares any container type
*/
Review Comment:
Moved back above `generate_go_equals_container`.
*This comment was created with AI assistance.*
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@thrift.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] THRIFT-6195: Compare Go set and entry-slice map fields without regard to order [thrift]
Posted by "fishy (via GitHub)" <gi...@apache.org>.
fishy commented on code in PR #3806:
URL: https://github.com/apache/thrift/pull/3806#discussion_r3945065624
##########
lib/go/thrift/unordered_equal_test.go:
##########
@@ -0,0 +1,122 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package thrift
+
+import "testing"
+
+func intEq(x, y int) bool { return x == y }
+
+func TestUnorderedEqual(t *testing.T) {
+ for name, c := range map[string]struct {
+ a, b []int
+ want bool
+ }{
+ "both nil": {nil, nil, true},
+ "nil and empty": {nil, []int{}, true},
+ "same order": {[]int{1, 2, 3}, []int{1, 2, 3}, true},
+ "reversed": {[]int{1, 2, 3}, []int{3, 2, 1}, true},
+ "rotated": {[]int{1, 2, 3}, []int{2, 3, 1}, true},
+ "single element": {[]int{1}, []int{1}, true},
+ "different element": {[]int{1, 2}, []int{1, 3}, false},
+ "shorter": {[]int{1, 2}, []int{1}, false},
+ "longer": {[]int{1}, []int{1, 2}, false},
+ "disjoint": {[]int{1, 2}, []int{3, 4}, false},
+ "same multiset": {[]int{1, 1, 2}, []int{2, 1, 1}, true},
+ "different multiplic.": {[]int{1, 1, 2}, []int{1, 2, 2}, false},
+ "all duplicates": {[]int{7, 7, 7}, []int{7, 7, 7}, true},
+ } {
+ t.Run(name, func(t *testing.T) {
+ if got := UnorderedEqual(c.a, c.b, intEq); got != c.want {
+ t.Errorf("UnorderedEqual(%v, %v) = %v, want %v", c.a, c.b, got, c.want)
+ }
+ // The relation must not depend on which side is which.
+ if got := UnorderedEqual(c.b, c.a, intEq); got != c.want {
+ t.Errorf("UnorderedEqual(%v, %v) = %v, want %v (not symmetric)", c.b, c.a, got, c.want)
+ }
+ })
+ }
+}
+
+// Elements that cannot be Go map keys take the same path as any other.
+func TestUnorderedEqualNonComparable(t *testing.T) {
+ eq := func(x, y []string) bool {
+ if len(x) != len(y) {
+ return false
+ }
+ for i := range x {
+ if x[i] != y[i] {
+ return false
+ }
+ }
+ return true
+ }
+ a := [][]string{{"a"}, {"b", "c"}}
+ b := [][]string{{"b", "c"}, {"a"}}
+ if !UnorderedEqual(a, b, eq) {
+ t.Error("reordered slice elements should compare equal")
+ }
+ if UnorderedEqual(a, [][]string{{"a"}, {"b"}}, eq) {
+ t.Error("differing slice elements should compare unequal")
+ }
+}
+
+// Comparing values that agree on order must not allocate.
+func TestUnorderedEqualOrderedPathDoesNotAllocate(t *testing.T) {
+ a := []int{1, 2, 3, 4, 5, 6, 7, 8}
+ b := []int{1, 2, 3, 4, 5, 6, 7, 8}
+ if n := testing.AllocsPerRun(100, func() {
+ if !UnorderedEqual(a, b, intEq) {
+ t.Fatal("expected equal")
+ }
+ }); n != 0 {
+ t.Errorf("ordered comparison allocated %v times per run, want 0", n)
+ }
+}
+
+func BenchmarkUnorderedEqualSameOrder(b *testing.B) {
+ x := make([]int, 1000)
+ y := make([]int, 1000)
+ for i := range x {
+ x[i], y[i] = i, i
+ }
+ b.ReportAllocs()
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ if !UnorderedEqual(x, y, intEq) {
+ b.Fatal("expected equal")
+ }
+ }
+}
+
+func BenchmarkUnorderedEqualReordered(b *testing.B) {
+ x := make([]int, 1000)
+ y := make([]int, 1000)
+ for i := range x {
+ x[i] = i
+ y[len(y)-1-i] = i
+ }
+ b.ReportAllocs()
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
Review Comment:
use `b.Loop()` instead: https://go.dev/doc/go1.26#testingpkgtesting
and we no longer need to call `b.ResetTimer` here.
##########
lib/go/thrift/unordered_equal_test.go:
##########
@@ -0,0 +1,122 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package thrift
+
+import "testing"
+
+func intEq(x, y int) bool { return x == y }
+
+func TestUnorderedEqual(t *testing.T) {
+ for name, c := range map[string]struct {
+ a, b []int
+ want bool
+ }{
+ "both nil": {nil, nil, true},
+ "nil and empty": {nil, []int{}, true},
+ "same order": {[]int{1, 2, 3}, []int{1, 2, 3}, true},
+ "reversed": {[]int{1, 2, 3}, []int{3, 2, 1}, true},
+ "rotated": {[]int{1, 2, 3}, []int{2, 3, 1}, true},
+ "single element": {[]int{1}, []int{1}, true},
+ "different element": {[]int{1, 2}, []int{1, 3}, false},
+ "shorter": {[]int{1, 2}, []int{1}, false},
+ "longer": {[]int{1}, []int{1, 2}, false},
+ "disjoint": {[]int{1, 2}, []int{3, 4}, false},
+ "same multiset": {[]int{1, 1, 2}, []int{2, 1, 1}, true},
+ "different multiplic.": {[]int{1, 1, 2}, []int{1, 2, 2}, false},
+ "all duplicates": {[]int{7, 7, 7}, []int{7, 7, 7}, true},
+ } {
+ t.Run(name, func(t *testing.T) {
+ if got := UnorderedEqual(c.a, c.b, intEq); got != c.want {
+ t.Errorf("UnorderedEqual(%v, %v) = %v, want %v", c.a, c.b, got, c.want)
+ }
+ // The relation must not depend on which side is which.
+ if got := UnorderedEqual(c.b, c.a, intEq); got != c.want {
+ t.Errorf("UnorderedEqual(%v, %v) = %v, want %v (not symmetric)", c.b, c.a, got, c.want)
+ }
+ })
+ }
+}
+
+// Elements that cannot be Go map keys take the same path as any other.
+func TestUnorderedEqualNonComparable(t *testing.T) {
+ eq := func(x, y []string) bool {
+ if len(x) != len(y) {
+ return false
+ }
+ for i := range x {
+ if x[i] != y[i] {
+ return false
+ }
+ }
+ return true
+ }
+ a := [][]string{{"a"}, {"b", "c"}}
+ b := [][]string{{"b", "c"}, {"a"}}
+ if !UnorderedEqual(a, b, eq) {
+ t.Error("reordered slice elements should compare equal")
+ }
+ if UnorderedEqual(a, [][]string{{"a"}, {"b"}}, eq) {
+ t.Error("differing slice elements should compare unequal")
+ }
+}
+
+// Comparing values that agree on order must not allocate.
+func TestUnorderedEqualOrderedPathDoesNotAllocate(t *testing.T) {
+ a := []int{1, 2, 3, 4, 5, 6, 7, 8}
+ b := []int{1, 2, 3, 4, 5, 6, 7, 8}
+ if n := testing.AllocsPerRun(100, func() {
+ if !UnorderedEqual(a, b, intEq) {
+ t.Fatal("expected equal")
+ }
+ }); n != 0 {
+ t.Errorf("ordered comparison allocated %v times per run, want 0", n)
+ }
+}
+
+func BenchmarkUnorderedEqualSameOrder(b *testing.B) {
+ x := make([]int, 1000)
+ y := make([]int, 1000)
+ for i := range x {
+ x[i], y[i] = i, i
+ }
+ b.ReportAllocs()
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
Review Comment:
same here
##########
compiler/cpp/src/thrift/generate/t_go_generator.cc:
##########
@@ -4278,6 +4278,19 @@ void t_go_generator::generate_go_equals_struct(ostream& out,
/**
* Compares any container type
*/
Review Comment:
this comment should be right above `generate_go_equals_container`
##########
lib/go/thrift/unordered_equal.go:
##########
@@ -0,0 +1,71 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package thrift
+
+// UnorderedEqual reports whether a and b hold the same elements, in any order,
+// comparing them with eq.
+//
+// Generated code calls this for the fields that stand in for an unordered
+// Thrift collection: a set, and a map whose key type forces the entry-slice
+// representation. Lists are ordered and are compared position by position
+// instead.
+//
+// The elements are compared position by position first, so two values that
+// agree on order, which includes any value that has just been deserialized,
+// cost one pass and allocate nothing. Only when that fails does each element
+// of a get matched against an unmatched element of b, which is quadratic.
+//
+// Matching consumes an element of b at most once, so a and b compare equal
+// only if they hold the same elements with the same multiplicities. That
+// matters for a value assembled in memory: the wire format rejects a set or
+// map that repeats an element, but nothing stops a caller from building one.
+func UnorderedEqual[T any](a, b []T, eq func(x, y T) bool) bool {
+ if len(a) != len(b) {
+ return false
+ }
+
+ ordered := true
+ for i := range a {
+ if !eq(a[i], b[i]) {
+ ordered = false
+ break
+ }
+ }
+ if ordered {
+ return true
+ }
Review Comment:
do we even need this part? we don't care if they are matching in order in this function do we?
in worst case scenario, a and b has elements 0 to n-3 matching in order, only the last 2 elements are swapped, this part would waste n-2 iterations.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@thrift.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org