5 ms·

I've spent some brainpower on binary search and have not been able to beat this: https://github.com/protocolbuffers/protobuf/blob/44025909eb7064a008decaa60c305

I've spent some brainpower on binary search and have not been able to beat this: https://github.com/protocolbuffers/protobuf/blob/44025909eb7064a008decaa60c305bddc8757b3a/upb/mini_table/internal/message.h#L235 https://github.com/protocolbuffers/protobuf/blob/44025909eb7... 1. Check for dense list O(1) 2. Check upper bound 3. Constant trip count binary search The constant trip count is great for the branch predictor, and the core loop is pretty tightly optimized for the target hardware, avoiding multiplies. Every attempt to get more clever made the loop worse and did not pay for itself. It's hard because it's an array-of-structs format with a size of 12, and mostly pretty small N.

echelon 5mo ago
I know protobuf code is extremely high quality, but I really can't stand the c-style naming conventions. I know people train themselves into grokking this and reading and emitting this way, but it sounds like writing "bork bork bork bork" runes to me. I'm glad Rust feels more like Ruby and Python and that method and field names are legible. My eyes just glaze over: UPB_API_INLINE const struct upb_MiniTableField* upb_MiniTable_FindFieldByNumber( const struct upb_MiniTable* m, uint32_t number) { const uint32_t i = number - 1; // 0 wraps to UINT32_MAX // Ideal case: index into dense fields if (i < m->UPB_PRIVATE(dense_below)) { UPB_ASSERT(m->UPB_ONLYBITS(fields)[i].UPB_ONLYBITS(number) == number); return &m->UPB_ONLYBITS(fields)[i]; } // Early exit if the field number is out of range. uint32_t hi = m->UPB_ONLYBITS(field_count); uint32_t lo = m->UPB_PRIVATE(dense_below); UPB_ASSERT(hi >= lo); uint32_t search_len = hi - lo; if (search_len == 0 || number > m->UPB_ONLYBITS(fields)[hi - 1].UPB_ONLYBITS(number)) { return NULL; } // Slow case: binary search const struct upb_MiniTableField* candidate; #ifndef NDEBUG candidate = UPB_PRIVATE(upb_MiniTable_ArmOptimizedLowerBound)( m, lo, search_len, number); UPB_ASSERT(candidate == UPB_PRIVATE(upb_MiniTable_LowerBound)(m, lo, search_len, number)); #elif UPB_ARM64_ASM candidate = UPB_PRIVATE(upb_MiniTable_ArmOptimizedLowerBound)( m, lo, search_len, number); #else candidate = UPB_PRIVATE(upb_MiniTable_LowerBound)(m, lo, search_len, number); #endif return candidate->UPB_ONLYBITS(number) == number ? candidate : NULL; }
- ahartmetz 5mo ago
  I think this needs way more "upb" and "UPB" to make it clear that it is, in fact, dealing with UPBs. Whatever these are.
  - jibal 5mo ago
    > μpb (often written 'upb') is a small protobuf implementation written in C.
- charleslmunger 5mo ago
  Yeah namespaces and public/private would be quite nice, but C doesn't have them, so they get hacked on via macros and prefixing. The syntax was not the hard part of working or analyzing this code, though.
- teo_zero 5mo ago
  > I really can't stand the c-style naming conventions. Honestly I don't see much difference between upb_MiniTable_FindFieldByNumber and upb::MiniTable::FindFieldByNumber
  - eximius 5mo ago
    Those are fairly indistinguishable. It's when they start removing letters from words to save... debug symbol bytes or something? That's when c-style naming annoys me.
    - adrianton3 5mo ago
      In their defence "hi" sounds very much like "high" in my mind's ear and "lo" like "low" :)
    - collabs 5mo ago
      This is also my pet peeve with a lot of code as well as commands like npm -g i package-name Like why would you teach people to do this? I understand people needed to save precious bytes in the sixties so we have cat and ls but saving 192 bytes or whatever with shorter variable names is not a worthwhile tradeoff anymore.
ben-schaaf 5mo ago
For a pretty small N I've found that less clever can be quite a bit faster. I'd try a linear search - possibly SIMD if you can change the data format to struct-of-arrays. An adaptive approach that uses linear search up to a certain N can also yield some benefit.
- ChadNauseam 5mo ago
  If you control the layout, eytzinger layout typically will give you the best of both worlds. As fast as a linear scan for small N, much faster than binary search over a sorted array for large N.
- charleslmunger 5mo ago
  The first implementation I encountered was a linear search, starting at the last-found field. Empirically it performed better to do a binary search with early exit and branchless bounds selection, I think due to branch predictor pressure. The data representation could be changed but it's tricky, as there are other traversals that want to go in sorted order, and there are lots of places that pass just one pointer for fields. But I agree any further improvement will probably have to come from that. SIMD is tricky even with SoA because there is significant latency going between the general registers and the vector units, plus arm little cores can be configured to share a vector unit with another core.
  - ben-schaaf 5mo ago
    > SIMD is tricky even with SoA because there is significant latency going between the general registers and the vector units My experience is mostly limited to AMD64, but libraries like glibc use SIMD in many places for faster linear search. Presumably they've done testing and found it worth while.
    - charleslmunger 5mo ago
      Yeah arm little cores are a very different story - they aren't superscalar out of order architectures, they can dispatch up to two operations per cycle. Big cores are more like that dispatching 8 or more operations per cycle, but they're also more expensive, larger, etc.
EMPTYCONTOUR 5mo ago
[dead]

echelon 5mo ago

I know protobuf code is extremely high quality, but I really can't stand the c-style naming conventions. I know people train themselves into grokking this and reading and emitting this way, but it sounds like writing "bork bork bork bork" runes to me. I'm glad Rust feels more like Ruby and Python and that method and field names are legible. My eyes just glaze over: UPB_API_INLINE const struct upb_MiniTableField* upb_MiniTable_FindFieldByNumber( const struct upb_MiniTable* m, uint32_t number) { const uint32_t i = number - 1; // 0 wraps to UINT32_MAX // Ideal case: index into dense fields if (i < m->UPB_PRIVATE(dense_below)) { UPB_ASSERT(m->UPB_ONLYBITS(fields)[i].UPB_ONLYBITS(number) == number); return &m->UPB_ONLYBITS(fields)[i]; } // Early exit if the field number is out of range. uint32_t hi = m->UPB_ONLYBITS(field_count); uint32_t lo = m->UPB_PRIVATE(dense_below); UPB_ASSERT(hi >= lo); uint32_t search_len = hi - lo; if (search_len == 0 || number > m->UPB_ONLYBITS(fields)[hi - 1].UPB_ONLYBITS(number)) { return NULL; } // Slow case: binary search const struct upb_MiniTableField* candidate; #ifndef NDEBUG candidate = UPB_PRIVATE(upb_MiniTable_ArmOptimizedLowerBound)( m, lo, search_len, number); UPB_ASSERT(candidate == UPB_PRIVATE(upb_MiniTable_LowerBound)(m, lo, search_len, number)); #elif UPB_ARM64_ASM candidate = UPB_PRIVATE(upb_MiniTable_ArmOptimizedLowerBound)( m, lo, search_len, number); #else candidate = UPB_PRIVATE(upb_MiniTable_LowerBound)(m, lo, search_len, number); #endif return candidate->UPB_ONLYBITS(number) == number ? candidate : NULL; }

ahartmetz 5mo ago
I think this needs way more "upb" and "UPB" to make it clear that it is, in fact, dealing with UPBs. Whatever these are.
- jibal 5mo ago
  > μpb (often written 'upb') is a small protobuf implementation written in C.
charleslmunger 5mo ago
Yeah namespaces and public/private would be quite nice, but C doesn't have them, so they get hacked on via macros and prefixing. The syntax was not the hard part of working or analyzing this code, though.
teo_zero 5mo ago
> I really can't stand the c-style naming conventions. Honestly I don't see much difference between upb_MiniTable_FindFieldByNumber and upb::MiniTable::FindFieldByNumber
- eximius 5mo ago
  Those are fairly indistinguishable. It's when they start removing letters from words to save... debug symbol bytes or something? That's when c-style naming annoys me.
  - adrianton3 5mo ago
    In their defence "hi" sounds very much like "high" in my mind's ear and "lo" like "low" :)
  - collabs 5mo ago
    This is also my pet peeve with a lot of code as well as commands like npm -g i package-name Like why would you teach people to do this? I understand people needed to save precious bytes in the sixties so we have cat and ls but saving 192 bytes or whatever with shorter variable names is not a worthwhile tradeoff anymore.

ben-schaaf 5mo ago

For a pretty small N I've found that less clever can be quite a bit faster. I'd try a linear search - possibly SIMD if you can change the data format to struct-of-arrays. An adaptive approach that uses linear search up to a certain N can also yield some benefit.

ChadNauseam 5mo ago
If you control the layout, eytzinger layout typically will give you the best of both worlds. As fast as a linear scan for small N, much faster than binary search over a sorted array for large N.
charleslmunger 5mo ago
The first implementation I encountered was a linear search, starting at the last-found field. Empirically it performed better to do a binary search with early exit and branchless bounds selection, I think due to branch predictor pressure. The data representation could be changed but it's tricky, as there are other traversals that want to go in sorted order, and there are lots of places that pass just one pointer for fields. But I agree any further improvement will probably have to come from that. SIMD is tricky even with SoA because there is significant latency going between the general registers and the vector units, plus arm little cores can be configured to share a vector unit with another core.
- ben-schaaf 5mo ago
  > SIMD is tricky even with SoA because there is significant latency going between the general registers and the vector units My experience is mostly limited to AMD64, but libraries like glibc use SIMD in many places for faster linear search. Presumably they've done testing and found it worth while.
  - charleslmunger 5mo ago
    Yeah arm little cores are a very different story - they aren't superscalar out of order architectures, they can dispatch up to two operations per cycle. Big cores are more like that dispatching 8 or more operations per cycle, but they're also more expensive, larger, etc.

EMPTYCONTOUR 5mo ago

[dead]