Repository: numpy/numpy
File: numpy/_core/src/npysort/binsearch.cpp (C++)

Code before:
};

/*
 *****************************************************************************
 **                            NUMERIC SEARCHES                             **
 *****************************************************************************
 */
template <class Tag, side_t side>
static void
binsearch(const char *arr, const char *key, char *ret, npy_intp arr_len,
          npy_intp key_len, npy_intp arr_str, npy_intp key_str,
          npy_intp ret_str, PyArrayObject *)
{
    using T = typename Tag::type;
    auto cmp = side_to_cmp<Tag, side>::value;

    // Let's handle this corner case first: if length is 0 we return all 0s
    if (arr_len <= 0) {
        for (npy_intp i = 0; i < key_len; ++i) {
            *(npy_intp *)(ret + i * ret_str) = 0;
        }
        return;
    }

    /*
    In this binary search, the candidates are in the range [base, base+length]
    and on each iteration we pick a pivot at the mid-point of the range to
    compare against the key being search. Depending on the comparison result,
    we adjust the base index and halve the length of the interval..

    To batch multiple queries, we do one pivot pass for each different length
    for all keys, storing intermediate values of base for every key. To avoid
    consuming extra memory, we use the ret array to store intermediate values
    of each base until they become the final result in the last step.

    There are two benefits of this approach:

    1. Cache locallity of pivots. In early iterations each key is compared
    against the same set of pivots. For example, in the first iteration all
    keys are compared against the median. In the second iteration, all keys
    end up being compared against 1st and 3rd quartiles.

    2. Independent calculations for out-of-order execution. In the single-key
    version, step i+1 depends on computation of step i. Meaning that step i+1
    must wait for step i to complete before proceeding. When batching multiple
    keys, we compute each step for all keys before continuing on the next step.
    All the computations at a given step are independent across different keys.
    Meaning that the CPU can execute multiple keys out-of-order in parallel.

    Invariant:
    - cmp(arr[i], key_val) == true  for all i < base

Review comment (suggestion):
```suggestion
    In this binary search, the candidate insertion indices for the jth key are in the range [base_j, base_j+length]
```
(or something similar to make clear each key has its own interval)

Code after:
};

/*
 *****************************************************************************
 **                            NUMERIC SEARCHES                             **
 *****************************************************************************
 */
template <class Tag, side_t side>
static void
binsearch(const char *arr, const char *key, char *ret, npy_intp arr_len,
          npy_intp key_len, npy_intp arr_str, npy_intp key_str,
          npy_intp ret_str, PyArrayObject *)
{
    using T = typename Tag::type;
    auto cmp = side_to_cmp<Tag, side>::value;

    // If the array length is 0 we return all 0s
    if (arr_len <= 0) {
        for (npy_intp i = 0; i < key_len; ++i) {
            *(npy_intp *)(ret + i * ret_str) = 0;
        }
        return;
    }

    /*
    In this binary search implementation, the candidate insertion indices for
    the jth key are in the range [base_j, base_j+length] and on each iteration
    we pick a pivot at the mid-point of the range to compare against the jth
    key. Depending on the comparison result, we adjust the base_j and halve
    the length of the interval.

    To batch multiple queries, we do one pivot pass for each different length
    for all keys, storing intermediate values of base_j for every key_j. To
    avoid consuming extra memory, we use the ret array to store intermediate
    values of each base until they become the final result in the last step.

    There are two benefits of this approach:

    1. Cache locallity of pivots. In early iterations each key is compared
    against the same set of pivots. For example, in the first iteration all
    keys are compared against the median. In the second iteration, all keys
    end up being compared against 1st and 3rd quartiles.

    2. Independent calculations for out-of-order execution. In the single-key
    version, step i+1 depends on computation of step i. Meaning that step i+1
    must wait for step i to complete before proceeding. When batching multiple
    keys, we compute each step for all keys before continuing on the next
    step. All the computations at a given step are independent across
    different keys. Meaning that the CPU can execute multiple keys
    out-of-order in parallel.