Skip to content

Commit 8f47d36

Browse files
arjan-balarjan-bal
authored
attributes: Replace internal map with linked list (#8933)
Fixes: #8921 This PR replaces the underlying `map[any]any` implementation in the `Attributes` struct with a singly linked list. Because `Attributes` are immutable, the previous implementation required a complete allocation and map copy every time `WithValue` was called. Since this data structure is primarily used in the control plane and typically holds a small number of values (10-20 at most), optimizing for memory is significantly more valuable than optimizing for lookup speed. By switching to a persistent linked-list , appending a new value becomes a highly efficient operation. `WithValue` now simply prepends a new node that points to the previous state, entirely eliminating the need to copy existing elements. Shadowing is handled naturally by returning the first match found during traversal. This approach is very similar to the implementation of [context.WithValue](https://cs.opensource.google/go/go/+/refs/tags/go1.26.0:src/context/context.go;l=727;drc=1a53ce9734c0b2a3e2a9814e75949ea77a978143). ### Complexity Comparison The following table breaks down the time and memory complexity of the `Attributes` operations, where $N$ is the number of keys. | Operation | Previous Time | Previous Space | New Time | New Space | Notes on New Implementation | | :--- | :--- | :--- | :--- | :--- | :--- | | **`New`** | $O(1)$ | $O(1)$ | $O(1)$ | $O(1)$ | Allocates a single head node. | | **`WithValue`** | $O(N)$ | $O(N)$ | $O(1)$ | $O(1)$ | **Highly Optimized:** Merely prepends a new node to the existing list instead of copying a full map. | | **`Value`** (Lookup) | $O(1)$ | $O(1)$ | $O(N)$ | $O(1)$ | Requires a linear scan. For $N \le 20$, this overhead is negligible. | | **`Equal`** | $O(N)$ | $O(1)$ | $O(N)$ | $O(N)$ | Allocates temporary maps to track shadowed keys and compare list contents. | ### Benchmark The benchmark added compares the memory usage for storing 10 attributes in 50 endpoints. It shows a 86% reduction is memory utilization. ```sh goos: linux goarch: amd64 pkg: google.golang.org/grpc/attributes cpu: Intel(R) Xeon(R) CPU @ 2.60GHz │ old.txt │ new.txt │ │ sec/op │ sec/op vs base │ WithValue-48 168.26µ ± 0% 15.53µ ± 1% -90.77% (p=0.000 n=10) │ old.txt │ new.txt │ │ B/op │ B/op vs base │ WithValue-48 200.00Ki ± 0% 23.44Ki ± 0% -88.28% (p=0.000 n=10) │ old.txt │ new.txt │ │ allocs/op │ allocs/op vs base │ WithValue-48 1700.0 ± 0% 500.0 ± 0% -70.59% (p=0.000 n=10) ``` RELEASE NOTES: * attributes: Optimize memory utilization from $O(n)$ to $O(1)$.
1 parent 22e1ee8 commit 8f47d36

2 files changed

Lines changed: 137 additions & 43 deletions

File tree

‎attributes/attributes.go‎

Lines changed: 55 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,8 @@ package attributes
2727

2828
import (
2929
"fmt"
30+
"iter"
31+
"maps"
3032
"strings"
3133
)
3234

@@ -37,37 +39,46 @@ import (
3739
// any) bool', it will be called by (*Attributes).Equal to determine whether
3840
// two values with the same key should be considered equal.
3941
type Attributes struct {
40-
m map[any]any
42+
parent *Attributes
43+
key, value any
4144
}
4245

4346
// New returns a new Attributes containing the key/value pair.
4447
func New(key, value any) *Attributes {
45-
return &Attributes{m: map[any]any{key: value}}
48+
return &Attributes{
49+
key: key,
50+
value: value,
51+
}
4652
}
4753

4854
// WithValue returns a new Attributes containing the previous keys and values
4955
// and the new key/value pair. If the same key appears multiple times, the
50-
// last value overwrites all previous values for that key. To remove an
51-
// existing key, use a nil value. value should not be modified later.
56+
// last value overwrites all previous values for that key. value should not be
57+
// modified later.
58+
//
59+
// Note that Attributes do not support deletion. Avoid using untyped nil values.
60+
// Since the Value method returns an untyped nil when a key is absent, it is
61+
// impossible to distinguish between a missing key and a key explicitly set to
62+
// an untyped nil. If you need to represent a value being unset, consider
63+
// storing a specific sentinel type or a wrapper struct with a boolean field
64+
// indicating presence.
5265
func (a *Attributes) WithValue(key, value any) *Attributes {
53-
if a == nil {
54-
return New(key, value)
66+
return &Attributes{
67+
parent: a,
68+
key: key,
69+
value: value,
5570
}
56-
n := &Attributes{m: make(map[any]any, len(a.m)+1)}
57-
for k, v := range a.m {
58-
n.m[k] = v
59-
}
60-
n.m[key] = value
61-
return n
6271
}
6372

6473
// Value returns the value associated with these attributes for key, or nil if
6574
// no value is associated with key. The returned value should not be modified.
6675
func (a *Attributes) Value(key any) any {
67-
if a == nil {
68-
return nil
76+
for cur := a; cur != nil; cur = cur.parent {
77+
if cur.key == key {
78+
return cur.value
79+
}
6980
}
70-
return a.m[key]
81+
return nil
7182
}
7283

7384
// Equal returns whether a and o are equivalent. If 'Equal(o any) bool' is
@@ -83,11 +94,15 @@ func (a *Attributes) Equal(o *Attributes) bool {
8394
if a == nil || o == nil {
8495
return false
8596
}
86-
if len(a.m) != len(o.m) {
87-
return false
97+
if a == o {
98+
return true
8899
}
89-
for k, v := range a.m {
90-
ov, ok := o.m[k]
100+
m := maps.Collect(o.all())
101+
lenA := 0
102+
103+
for k, v := range a.all() {
104+
lenA++
105+
ov, ok := m[k]
91106
if !ok {
92107
// o missing element of a
93108
return false
@@ -101,7 +116,7 @@ func (a *Attributes) Equal(o *Attributes) bool {
101116
return false
102117
}
103118
}
104-
return true
119+
return lenA == len(m)
105120
}
106121

107122
// String prints the attribute map. If any key or values throughout the map
@@ -110,11 +125,11 @@ func (a *Attributes) String() string {
110125
var sb strings.Builder
111126
sb.WriteString("{")
112127
first := true
113-
for k, v := range a.m {
128+
for k, v := range a.all() {
114129
if !first {
115130
sb.WriteString(", ")
116131
}
117-
sb.WriteString(fmt.Sprintf("%q: %q ", str(k), str(v)))
132+
fmt.Fprintf(&sb, "%q: %q ", str(k), str(v))
118133
first = false
119134
}
120135
sb.WriteString("}")
@@ -139,3 +154,21 @@ func str(x any) (s string) {
139154
func (a *Attributes) MarshalJSON() ([]byte, error) {
140155
return []byte(a.String()), nil
141156
}
157+
158+
// all returns an iterator that yields all key-value pairs in the Attributes
159+
// chain. If a key appears multiple times, only the most recently added value
160+
// is yielded.
161+
func (a *Attributes) all() iter.Seq2[any, any] {
162+
return func(yield func(any, any) bool) {
163+
seen := map[any]bool{}
164+
for cur := a; cur != nil; cur = cur.parent {
165+
if seen[cur.key] {
166+
continue
167+
}
168+
if !yield(cur.key, cur.value) {
169+
return
170+
}
171+
seen[cur.key] = true
172+
}
173+
}
174+
}

‎attributes/attributes_test.go‎

Lines changed: 82 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -95,34 +95,95 @@ func ExampleAttributes_String() {
9595
// a8: {"<%!p(int=1)>": "<%!p(bool=true)>" }
9696
}
9797

98-
// Test that two attributes with the same content are Equal.
98+
// Test that two attributes with different content are not Equal.
9999
func TestEqual(t *testing.T) {
100100
type keyOne struct{}
101101
type keyTwo struct{}
102-
a1 := attributes.New(keyOne{}, 1).WithValue(keyTwo{}, stringVal{s: "two"})
103-
a2 := attributes.New(keyOne{}, 1).WithValue(keyTwo{}, stringVal{s: "two"})
104-
if !a1.Equal(a2) {
105-
t.Fatalf("%+v.Equals(%+v) = false; want true", a1, a2)
102+
tests := []struct {
103+
name string
104+
a *attributes.Attributes
105+
b *attributes.Attributes
106+
want bool
107+
}{
108+
{
109+
name: "different_first_value",
110+
a: attributes.New(keyOne{}, 1).WithValue(keyTwo{}, stringVal{s: "two"}),
111+
b: attributes.New(keyOne{}, 2).WithValue(keyTwo{}, stringVal{s: "two"}),
112+
want: false,
113+
},
114+
{
115+
name: "different_second_value",
116+
a: attributes.New(keyOne{}, 1).WithValue(keyTwo{}, stringVal{s: "one"}),
117+
b: attributes.New(keyOne{}, 1).WithValue(keyTwo{}, stringVal{s: "two"}),
118+
want: false,
119+
},
120+
{
121+
name: "same",
122+
a: attributes.New(keyOne{}, 1).WithValue(keyTwo{}, stringVal{s: "two"}),
123+
b: attributes.New(keyOne{}, 1).WithValue(keyTwo{}, stringVal{s: "two"}),
124+
want: true,
125+
},
126+
{
127+
name: "subset",
128+
a: attributes.New(keyOne{}, 1),
129+
b: attributes.New(keyOne{}, 1).WithValue(keyTwo{}, stringVal{s: "two"}),
130+
want: false,
131+
},
132+
{
133+
name: "superset",
134+
a: attributes.New(keyOne{}, 1).WithValue(keyTwo{}, stringVal{s: "two"}),
135+
b: attributes.New(keyTwo{}, stringVal{s: "two"}),
136+
want: false,
137+
},
138+
{
139+
name: "a_nil",
140+
a: nil,
141+
b: attributes.New(keyOne{}, 1),
142+
want: false,
143+
},
144+
{
145+
name: "b_nil",
146+
a: attributes.New(keyOne{}, 1),
147+
b: nil,
148+
want: false,
149+
},
150+
{
151+
name: "both_nil",
152+
a: nil,
153+
b: nil,
154+
want: true,
155+
},
106156
}
107-
if !a2.Equal(a1) {
108-
t.Fatalf("%+v.Equals(%+v) = false; want true", a2, a1)
157+
158+
for _, tt := range tests {
159+
t.Run(tt.name, func(t *testing.T) {
160+
if got := tt.a.Equal(tt.b); got != tt.want {
161+
t.Errorf("%+v.Equal(%+v) = %v; want %v", tt.a, tt.b, got, tt.want)
162+
}
163+
// The Equal function should be symmetric, i.e. a.Equals(b) ==
164+
// b.Equals(a).
165+
if got := tt.b.Equal(tt.a); got != tt.want {
166+
t.Errorf("%+v.Equal(%+v) = %v; want %v", tt.b, tt.a, got, tt.want)
167+
}
168+
})
109169
}
110170
}
111171

112-
// Test that two attributes with different content are not Equal.
113-
func TestNotEqual(t *testing.T) {
114-
type keyOne struct{}
115-
type keyTwo struct{}
116-
a1 := attributes.New(keyOne{}, 1).WithValue(keyTwo{}, stringVal{s: "two"})
117-
a2 := attributes.New(keyOne{}, 2).WithValue(keyTwo{}, stringVal{s: "two"})
118-
a3 := attributes.New(keyOne{}, 1).WithValue(keyTwo{}, stringVal{s: "one"})
119-
if a1.Equal(a2) {
120-
t.Fatalf("%+v.Equals(%+v) = true; want false", a1, a2)
121-
}
122-
if a2.Equal(a1) {
123-
t.Fatalf("%+v.Equals(%+v) = true; want false", a2, a1)
172+
func BenchmarkWithValue(b *testing.B) {
173+
keys := make([]any, 10)
174+
for i := range 10 {
175+
keys[i] = i
124176
}
125-
if a3.Equal(a1) {
126-
t.Fatalf("%+v.Equals(%+v) = true; want false", a3, a1)
177+
b.ReportAllocs()
178+
179+
for b.Loop() {
180+
// 50 endpoints
181+
for range 50 {
182+
a := attributes.New(keys[0], keys[0])
183+
// 10 attributes each.
184+
for j := 1; j < 10; j++ {
185+
a = a.WithValue(keys[j], keys[j])
186+
}
187+
}
127188
}
128189
}

0 commit comments

Comments
 (0)