Skip to content

Navigation Menu

Sign in

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 1c088d8

Browse filesBrowse files
habermancopybara-github
haberman
authored and
copybara-github
committed
Removed upb_Decoder's stateful, bespoke logic for field lookup.
upb_Decoder used to have its own logic for finding a MiniTable field by number. Instead of using the standard `upb_MiniTable_FindFieldByNumber()` function, it used a custom linear search that cached the most recently seen field index. The theory behind this design was that field numbers are usually serialized in increasing order, so by linear searching from the last seen index, we would have a small expected number of elements to inspect before finding the matching one. In practice, it appears that we can use the generic searching logic with no loss in performance -- in fact, performance increases by as much as 6% (see attached benchmark results). Removing the stateful search has several benefits: 1. This simplifies the decoder since we no longer have to preserve this extra state (`last_field_index`). Note that it was not even possible to put this variable into `upb_Decoder` because it is preserved per parsed message, so we previously needed a *stack* of `last_field_index` values. This CL lets us get rid of that completely. 2. This makes parsing performance less sensitive to whether field numbers are serialized in order. 3. This simplification will help as we refine the dispatch logic that switches between the standard and fasttable decoders. PiperOrigin-RevId: 758304268
1 parent 80f2550 commit 1c088d8
Copy full SHA for 1c088d8

File tree

4 files changed

+53
-83
lines changed
Filter options

4 files changed

+53
-83
lines changed

‎upb/mini_table/internal/message.h

Copy file name to clipboardExpand all lines: upb/mini_table/internal/message.h
+44
Original file line numberDiff line numberDiff line change
@@ -101,6 +101,50 @@ UPB_API_INLINE bool upb_MiniTable_IsMessageSet(const struct upb_MiniTable* m) {
101101
return m->UPB_PRIVATE(ext) == kUpb_ExtMode_IsMessageSet;
102102
}
103103

104+
UPB_API_INLINE
105+
const struct upb_MiniTableField* upb_MiniTable_FindFieldByNumber(
106+
const struct upb_MiniTable* m, uint32_t number) {
107+
const size_t i = ((size_t)number) - 1; // 0 wraps to SIZE_MAX
108+
109+
// Ideal case: index into dense fields
110+
if (i < m->UPB_PRIVATE(dense_below)) {
111+
UPB_ASSERT(m->UPB_ONLYBITS(fields)[i].UPB_ONLYBITS(number) == number);
112+
return &m->UPB_ONLYBITS(fields)[i];
113+
}
114+
115+
// Early exit if the field number is out of range.
116+
int32_t hi = m->UPB_ONLYBITS(field_count) - 1;
117+
if (hi < 0 || number > m->UPB_ONLYBITS(fields)[hi].UPB_ONLYBITS(number)) {
118+
return NULL;
119+
}
120+
121+
// Slow case: binary search
122+
uint32_t lo = m->UPB_PRIVATE(dense_below);
123+
const struct upb_MiniTableField* base = m->UPB_ONLYBITS(fields);
124+
while (hi >= (int32_t)lo) {
125+
uint32_t mid = (hi + lo) / 2;
126+
uint32_t num = base[mid].UPB_ONLYBITS(number);
127+
// These comparison operations allow, on ARM machines, to fuse all these
128+
// branches into one comparison followed by two CSELs to set the lo/hi
129+
// values, followed by a BNE to continue or terminate the loop. Since binary
130+
// search branches are generally unpredictable (50/50 in each direction),
131+
// this is a good deal. We use signed for the high, as this decrement may
132+
// underflow if mid is 0.
133+
int32_t hi_mid = mid - 1;
134+
uint32_t lo_mid = mid + 1;
135+
if (num == number) {
136+
return &base[mid];
137+
}
138+
if (UPB_UNPREDICTABLE(num < number)) {
139+
lo = lo_mid;
140+
} else {
141+
hi = hi_mid;
142+
}
143+
}
144+
145+
return NULL;
146+
}
147+
104148
UPB_INLINE bool UPB_PRIVATE(_upb_MiniTable_IsEmpty)(
105149
const struct upb_MiniTable* m) {
106150
extern const struct upb_MiniTable UPB_PRIVATE(_kUpb_MiniTable_Empty);

‎upb/mini_table/message.c

Copy file name to clipboardExpand all lines: upb/mini_table/message.c
-38
Original file line numberDiff line numberDiff line change
@@ -15,44 +15,6 @@
1515
// Must be last.
1616
#include "upb/port/def.inc"
1717

18-
const upb_MiniTableField* upb_MiniTable_FindFieldByNumber(
19-
const upb_MiniTable* m, uint32_t number) {
20-
const size_t i = ((size_t)number) - 1; // 0 wraps to SIZE_MAX
21-
22-
// Ideal case: index into dense fields
23-
if (i < m->UPB_PRIVATE(dense_below)) {
24-
UPB_ASSERT(m->UPB_PRIVATE(fields)[i].UPB_PRIVATE(number) == number);
25-
return &m->UPB_PRIVATE(fields)[i];
26-
}
27-
28-
// Slow case: binary search
29-
uint32_t lo = m->UPB_PRIVATE(dense_below);
30-
int32_t hi = m->UPB_PRIVATE(field_count) - 1;
31-
const upb_MiniTableField* base = m->UPB_PRIVATE(fields);
32-
while (hi >= (int32_t)lo) {
33-
uint32_t mid = (hi + lo) / 2;
34-
uint32_t num = base[mid].UPB_ONLYBITS(number);
35-
// These comparison operations allow, on ARM machines, to fuse all these
36-
// branches into one comparison followed by two CSELs to set the lo/hi
37-
// values, followed by a BNE to continue or terminate the loop. Since binary
38-
// search branches are generally unpredictable (50/50 in each direction),
39-
// this is a good deal. We use signed for the high, as this decrement may
40-
// underflow if mid is 0.
41-
int32_t hi_mid = mid - 1;
42-
uint32_t lo_mid = mid + 1;
43-
if (num == number) {
44-
return &base[mid];
45-
}
46-
if (UPB_UNPREDICTABLE(num < number)) {
47-
lo = lo_mid;
48-
} else {
49-
hi = hi_mid;
50-
}
51-
}
52-
53-
return NULL;
54-
}
55-
5618
const upb_MiniTableField* upb_MiniTable_GetOneof(const upb_MiniTable* m,
5719
const upb_MiniTableField* f) {
5820
if (UPB_UNLIKELY(!upb_MiniTableField_IsInOneof(f))) {

‎upb/mini_table/message.h

Copy file name to clipboardExpand all lines: upb/mini_table/message.h
+1-1
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,7 @@ typedef struct upb_MiniTable upb_MiniTable;
2323
extern "C" {
2424
#endif
2525

26-
UPB_API const upb_MiniTableField* upb_MiniTable_FindFieldByNumber(
26+
UPB_API_INLINE const upb_MiniTableField* upb_MiniTable_FindFieldByNumber(
2727
const upb_MiniTable* m, uint32_t number);
2828

2929
UPB_API_INLINE const upb_MiniTableField* upb_MiniTable_GetFieldByIndex(

‎upb/wire/decode.c

Copy file name to clipboardExpand all lines: upb/wire/decode.c
+8-44
Original file line numberDiff line numberDiff line change
@@ -965,55 +965,22 @@ UPB_NOINLINE const upb_MiniTableField* _upb_Decoder_FindExtensionField(
965965
return &upb_Decoder_FieldNotFoundField;
966966
}
967967

968-
static const upb_MiniTableField* _upb_Decoder_FindField(
969-
upb_Decoder* d, const upb_MiniTable* t, uint32_t field_number,
970-
uint32_t* last_field_index, int wire_type) {
968+
static const upb_MiniTableField* _upb_Decoder_FindField(upb_Decoder* d,
969+
const upb_MiniTable* t,
970+
uint32_t field_number,
971+
int wire_type) {
971972
if (t == NULL) return &upb_Decoder_FieldNotFoundField;
972973

973-
uint32_t idx = ((uint32_t)field_number) - 1; // 0 wraps to UINT32_MAX
974-
if (idx < t->UPB_PRIVATE(dense_below)) {
975-
// Fastest case: index into dense fields, and don't update last_field_index.
976-
return &t->UPB_PRIVATE(fields)[idx];
977-
}
978-
979-
uint32_t field_count = t->UPB_PRIVATE(field_count);
980-
if (t->UPB_PRIVATE(dense_below) < field_count) {
981-
// Linear search non-dense fields. Resume scanning from last_field_index
982-
// since fields are usually in order.
983-
idx = *last_field_index;
984-
uint32_t candidate;
985-
do {
986-
candidate = t->UPB_PRIVATE(fields)[idx].UPB_PRIVATE(number);
987-
if (candidate == field_number) {
988-
goto found;
989-
}
990-
} while (++idx < field_count);
991-
992-
if (UPB_LIKELY(field_number > candidate)) {
993-
// The field number we encountered is larger than any of our known fields,
994-
// so it's likely that subsequent ones will be too.
995-
*last_field_index = idx - 1;
996-
} else {
997-
// Fields not in tag order - scan from beginning
998-
for (idx = t->UPB_PRIVATE(dense_below); idx < *last_field_index; idx++) {
999-
if (t->UPB_PRIVATE(fields)[idx].UPB_PRIVATE(number) == field_number) {
1000-
goto found;
1001-
}
1002-
}
1003-
}
1004-
}
974+
const upb_MiniTableField* field =
975+
upb_MiniTable_FindFieldByNumber(t, field_number);
976+
if (field) return field;
1005977

1006978
if (d->extreg && t->UPB_PRIVATE(ext)) {
1007979
return _upb_Decoder_FindExtensionField(d, t, field_number,
1008980
t->UPB_PRIVATE(ext), wire_type);
1009981
}
1010982

1011983
return &upb_Decoder_FieldNotFoundField; // Unknown field.
1012-
1013-
found:
1014-
UPB_ASSERT(t->UPB_PRIVATE(fields)[idx].UPB_PRIVATE(number) == field_number);
1015-
*last_field_index = idx;
1016-
return &t->UPB_PRIVATE(fields)[idx];
1017984
}
1018985

1019986
static int _upb_Decoder_GetVarintOp(const upb_MiniTableField* field) {
@@ -1318,8 +1285,6 @@ UPB_NOINLINE
13181285
const char* _upb_Decoder_DecodeMessage(upb_Decoder* d, const char* ptr,
13191286
upb_Message* msg,
13201287
const upb_MiniTable* layout) {
1321-
uint32_t last_field_index = 0;
1322-
13231288
#if UPB_FASTTABLE
13241289
// The first time we want to skip fast dispatch, because we may have just been
13251290
// invoked by the fast parser to handle a case that it bailed on.
@@ -1358,8 +1323,7 @@ const char* _upb_Decoder_DecodeMessage(upb_Decoder* d, const char* ptr,
13581323
return ptr;
13591324
}
13601325

1361-
field = _upb_Decoder_FindField(d, layout, field_number, &last_field_index,
1362-
wire_type);
1326+
field = _upb_Decoder_FindField(d, layout, field_number, wire_type);
13631327
ptr = _upb_Decoder_DecodeWireValue(d, ptr, layout, field, wire_type, &val,
13641328
&op);
13651329

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.