Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

You can beat the binary search

lemire.me

Post reply on HN
Print view View original

111–120 of 175 posts

Re: You can beat the binary search

#111

Post by ssivark »

hinkley wrote: post #81
ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

I swear I read an article about treaps but instead of being used to balance the tree, they used the weights to Huffman encode the search depth to reduce the average access time for heterogenous fetch frequencies. I did not bookmark it and about twice a year I go searching for it again. Some say he’s still searching to this day.

Huffman coding assumes your corpus is a string of discrete elements (symbol strings) without any continuous structure (eg. topology/geometry). With that fairly mild assumption, it gives a recipe to reorganize (transform/encode) your data as a prefix-tree, to minimize the bits of information needed to communicate the contents of your corpus i.e. reducing (on average) the bits of information you need to identify a specific item. Eg. To go back to the analogy from my previous comment above... if the function you are inverting via search has long plateaus then you could simply front-load those as guesses; that's roughly the spirit of Huffman coding, except it eschews monotonicity.

Re: You can beat the binary search

#112

Post by aidenn0 »

nly wrote: post #97
drkrab wrote: post #91

Since the cpu always accesses a full cache line (64 bytes) at a time, you might as well search the entire cache line (it’s practically free once the data is on-cpu). So I’d like to try a ‘binary’ search that tests all the values in the ‘middle cache line’ and then chooses to go left or right if none match. You can do the cache line search as a single 512bit simd instruction. A cache line is 64 bytes (or 32 16-bit int…

Searching the upper cache lines in your binary search tree (sorted vector) for your target is unlikely to yield results. Instead you want to use the extra data in the line to shorten the search, which leads you to a B-Tree or B+tree. For 4 byte keys and 4 byte child pointers (or indexes in to an array) your inner nodes would have 7 keys, 8 child pointers and 1 next pointer, completely filling a 64 byte cache-line and…

Binary searching a sorted array is isomorphic to a sorted binary tree with implicit child pointers.

It seems to me like there should be a sort order that stores the items as a fully-dense left-shifted binary tree from top-to-bottom (e.g. like the implicit heap in an in-place heap sort, but a binary search tree instead of a hea). Is there a name for this? Does it show any performance wins in practice?

Re: You can beat the binary search

#113

Post by ssivark »

rixed wrote: post #84
ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

> it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic Also if you do not learn anything about the data while performing the binary search, no? Like, if you are constantly below the estimate, you could gess that the distribution is biases toward large values and adjust your guess based on thi…

> Also [IFF] you do not learn anything about the data while performing the binary search, no?

Yes, absolutely!

I forgot to share this general perspective above, and it's too late to edit, so I'll add it here...

Since binary search assumes only monotonicity; splitting your interval into two equal parts extracts one bit of information per step, and any other choice would extract less information on average. One bit of information per step is how you end up needing log(n) steps to find the answer.

To accelerate your search, you basically need to extract those log(n) bits as fast as you can. You can think of that as leveraging both the prior, and everything you learn along the way -- to adaptively design each step to be the optimal experiment to extract maximum amount of information. And adaptive local models of your search space (gradient / hessian / etc) allow you to extract many more bits of information from each query / experiment, provided the function you are inverting has some local structure.

PS: That is why we leverage these ideas to "search" for the optimum, among a space of solutions.

Re: You can beat the binary search

#114

Post by echelon »

charleslmunger wrote: post #107
ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

I've spent some brainpower on binary search and have not been able to beat this: 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…

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 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;
    }

Re: You can beat the binary search

#115

Post by [deleted] »

ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

[deleted]

Re: You can beat the binary search

#116

Post by teo_zero »

TL;DR the author developed an algorithm to solve this specific problem:

> The popular Roaring Bitmap format uses arrays of 16-bit integers of size ranging from 1 to 4096. We sometimes have to check whether a value is present.

There's no claim that this algorithm is universal and performs equally well for other problems.

In fact, note how the compare operation on the data types involved (16-bit integers) is quite cheap for modern CPUs. A similar problem with strings instead of integers would get no benefits from the author's ideas and would actually fare worse, due to useless comparisons per cycle.

Re: You can beat the binary search

#117

Post by ahartmetz »

echelon wrote: post #114
charleslmunger wrote: post #107

Earlier quoted context omitted.

I've spent some brainpower on binary search and have not been able to beat this: 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…

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_…

I think this needs way more "upb" and "UPB" to make it clear that it is, in fact, dealing with UPBs. Whatever these are.

Re: You can beat the binary search

#118

Post by charleslmunger »

echelon wrote: post #114
charleslmunger wrote: post #107

Earlier quoted context omitted.

I've spent some brainpower on binary search and have not been able to beat this: 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…

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_…

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.

Re: You can beat the binary search

#119

Post by teo_zero »

echelon wrote: post #114
charleslmunger wrote: post #107

Earlier quoted context omitted.

I've spent some brainpower on binary search and have not been able to beat this: 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…

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_…

> 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
Post reply on HN