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

Code before:

template <>
struct side_to_generic_cmp<left> {
    using type = std::less<int>;
};

template <>
struct side_to_generic_cmp<right> {
    using type = std::less_equal<int>;
};

/*
 *****************************************************************************
 **                            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 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.

Review comment (suggestion):
```suggestion
    // Let's handle this corner case first: if the array length is 0 we return all 0s
```

Code after:

template <>
struct side_to_generic_cmp<left> {
    using type = std::less<int>;
};

template <>
struct side_to_generic_cmp<right> {
    using type = std::less_equal<int>;
};

/*
 *****************************************************************************
 **                            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.