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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
