numpy · ewmoore · Jul 24, 2020 · May 22, 2020 · Jul 24, 2020 · Jul 31, 2020
diff --git a/benchmarks/benchmarks/bench_function_base.py b/benchmarks/benchmarks/bench_function_base.py
@@ -285,3 +285,27 @@ def time_2(self):
 
     def time_2_broadcast(self):
         np.where(self.cond, self.d, 0)
+
+class SearchSorted(Benchmark):
+    params = [[1, 10, 100, 1000, 10000, 100000],
+              [10, 1000, 10000, 100000, 1000000],
+              ['sorted', 'random'],
+              [('f8', 'f8'), ('i8', 'i8'), ('i4', 'i8'), ('i8', 'i4'),  ('i4', 'u4')],]
+
+    param_names = ['needlesize', 'haystacksize', 'needletype', 'dtype']
+
+    def setup(self, needlesize, haystacksize, needletype, dtype):
+        self.random = np.random.RandomState(3333).random_integers(0, haystacksize, needlesize).astype(dtype[1])
+        self.sorted = np.sort(self.random)
+        if needletype == 'sorted':
+            self.needle = self.sorted
+        else:
+            self.needle = self.random
+        self.haystack = np.arange(haystacksize, dtype=dtype[0])
+        self.sorter = np.arange(haystacksize, dtype=np.intp)
+
+    def time_searchsorted(self, *args):
+        self.haystack.searchsorted(self.needle)
+
+    def time_argsearchsorted(self, *args):
+        self.haystack.searchsorted(self.needle, sorter=self.sorter)
diff --git a/numpy/core/setup.py b/numpy/core/setup.py
@@ -686,26 +686,6 @@ def get_mathlib_info(*args):
     config.add_npy_pkg_config("mlib.ini.in", "lib/npy-pkg-config",
             subst_dict)
 
-    #######################################################################
-    #                         npysort library                             #
-    #######################################################################
-
-    # This library is created for the build but it is not installed
-    npysort_sources = [join('src', 'common', 'npy_sort.h.src'),
-                       join('src', 'npysort', 'quicksort.c.src'),
-                       join('src', 'npysort', 'mergesort.c.src'),
-                       join('src', 'npysort', 'timsort.c.src'),
-                       join('src', 'npysort', 'heapsort.c.src'),
-                       join('src', 'npysort', 'radixsort.c.src'),
-                       join('src', 'common', 'npy_partition.h.src'),
-                       join('src', 'npysort', 'selection.c.src'),
-                       join('src', 'common', 'npy_binsearch.h.src'),
-                       join('src', 'npysort', 'binsearch.c.src'),
-                       ]
-    config.add_library('npysort',
-                       sources=npysort_sources,
-                       include_dirs=[])
-
     #######################################################################
     #                     multiarray_tests module                         #
     #######################################################################
@@ -825,7 +805,7 @@ def get_mathlib_info(*args):
             join('include', 'numpy', 'npy_1_7_deprecated_api.h'),
             # add library sources as distuils does not consider libraries
             # dependencies
-            ] + npysort_sources + npymath_sources
+            ] + npymath_sources
 
     multiarray_src = [
             join('src', 'multiarray', 'abstractdtypes.c'),
@@ -877,6 +857,16 @@ def get_mathlib_info(*args):
             join('src', 'multiarray', 'typeinfo.c'),
             join('src', 'multiarray', 'usertypes.c'),
             join('src', 'multiarray', 'vdot.c'),
+            join('src', 'common', 'npy_sort.h.src'),
+            join('src', 'npysort', 'quicksort.c.src'),
+            join('src', 'npysort', 'mergesort.c.src'),
+            join('src', 'npysort', 'timsort.c.src'),
+            join('src', 'npysort', 'heapsort.c.src'),
+            join('src', 'npysort', 'radixsort.c.src'),
+            join('src', 'common', 'npy_partition.h.src'),
+            join('src', 'npysort', 'selection.c.src'),
+            join('src', 'common', 'npy_binsearch.h.src'),
+            join('src', 'npysort', 'binsearch.c.src'),
             ]
 
     #######################################################################
@@ -938,7 +928,7 @@ def generate_umath_c(ext, build_dir):
                                  ],
                          depends=deps + multiarray_deps + umath_deps +
                                 common_deps,
-                         libraries=['npymath', 'npysort'],
+                         libraries=['npymath'],
                          extra_info=extra_info)
 
     #######################################################################

diff --git a/numpy/core/src/common/array_assign.c b/numpy/core/src/common/array_assign.c
@@ -150,7 +150,46 @@ IsUintAligned(PyArrayObject *ap)
                                 npy_uint_alignment(PyArray_DESCR(ap)->elsize));
 }
 
+/*
+ * Check that array data is both uint-aligned and true-aligned for all array
+ * elements, as required by the copy/casting code in lowlevel_strided_loops.c
+ */
+NPY_NO_EXPORT int
+copycast_isaligned(int ndim, npy_intp const *shape,
+        PyArray_Descr *dtype, char *data, npy_intp const *strides)
+{
+    int aligned;
+    int big_aln, small_aln;
+
+    int uint_aln = npy_uint_alignment(dtype->elsize);
+    int true_aln = dtype->alignment;
+
+    /* uint alignment can be 0, meaning not uint alignable */
+    if (uint_aln == 0) {
+        return 0;
+    }
 
+    /*
+     * As an optimization, it is unnecessary to check the alignment to the
+     * smaller of (uint_aln, true_aln) if the data is aligned to the bigger of
+     * the two and the big is a multiple of the small aln. We check the bigger
+     * one first and only check the smaller if necessary.
+     */
+    if (true_aln >= uint_aln) {
+        big_aln = true_aln;
+        small_aln = uint_aln;
+    }
+    else {
+        big_aln = uint_aln;
+        small_aln = true_aln;
+    }
+
+    aligned = raw_array_is_aligned(ndim, shape, data, strides, big_aln);
+    if (aligned && big_aln % small_aln != 0) {
+        aligned = raw_array_is_aligned(ndim, shape, data, strides, small_aln);
+    }
+    return aligned;
+}
 
 /* Returns 1 if the arrays have overlapping data, 0 otherwise */
 NPY_NO_EXPORT int

diff --git a/numpy/core/src/common/array_assign.h b/numpy/core/src/common/array_assign.h
@@ -114,5 +114,12 @@ IsUintAligned(PyArrayObject *ap);
 NPY_NO_EXPORT int
 arrays_overlap(PyArrayObject *arr1, PyArrayObject *arr2);
 
+/*
+ * Check that array data is both uint-aligned and true-aligned for all array
+ * elements, as required by the copy/casting code in lowlevel_strided_loops.c
+ */
+NPY_NO_EXPORT int
+copycast_isaligned(int ndim, npy_intp const *shape,
+        PyArray_Descr *dtype, char *data, npy_intp const *strides);
 
 #endif
diff --git a/numpy/core/src/common/npy_binsearch.h.src b/numpy/core/src/common/npy_binsearch.h.src
@@ -1,7 +1,11 @@
 #ifndef __NPY_BINSEARCH_H__
 #define __NPY_BINSEARCH_H__
 
+#define NPY_NO_DEPRECATED_API NPY_API_VERSION
+#define _MULTIARRAYMODULE
+#include "lowlevel_strided_loops.h"
 #include "npy_sort.h"
+
 #include <numpy/npy_common.h>
 #include <numpy/ndarraytypes.h>
 
@@ -12,20 +16,35 @@ typedef void (PyArray_BinSearchFunc)(const char*, const char*, char*,
                                      npy_intp, npy_intp, npy_intp,
                                      PyArrayObject*);
 
+typedef void (PyArray_TransferBinSearchFunc)(char*, const char*, char*,
+                                     npy_intp, npy_intp,
+                                     npy_intp, npy_intp, npy_intp,
+                                     npy_intp, PyArray_StridedUnaryOp*, NpyAuxData*,
+                                     PyArrayObject*);
+
 typedef int (PyArray_ArgBinSearchFunc)(const char*, const char*,
                                        const char*, char*,
                                        npy_intp, npy_intp, npy_intp,
                                        npy_intp, npy_intp, npy_intp,
                                        PyArrayObject*);
 
+typedef int (PyArray_TransferArgBinSearchFunc)(char*, const char*,
+                                       const char*, char*,
+                                       npy_intp, npy_intp, npy_intp,
+                                       npy_intp, npy_intp, npy_intp,
+                                       npy_intp, PyArray_StridedUnaryOp*, NpyAuxData*,
+                                       PyArrayObject*);
+
 typedef struct {
     int typenum;
     PyArray_BinSearchFunc *binsearch[NPY_NSEARCHSIDES];
+    PyArray_TransferBinSearchFunc *transferbinsearch[NPY_NSEARCHSIDES];
 } binsearch_map;
 
 typedef struct {
     int typenum;
     PyArray_ArgBinSearchFunc *argbinsearch[NPY_NSEARCHSIDES];
+    PyArray_TransferArgBinSearchFunc *transferargbinsearch[NPY_NSEARCHSIDES];
 } argbinsearch_map;
 
 /**begin repeat
@@ -45,13 +64,27 @@ binsearch_@side@_@suff@(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 *unused);
+NPY_VISIBILITY_HIDDEN void
+transferbinsearch_@side@_@suff@(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,
+                        npy_intp arr_itemsize, PyArray_StridedUnaryOp *transfer,
+                        NpyAuxData *transfer_data, PyArrayObject *NOT_USED);
 NPY_VISIBILITY_HIDDEN int
 argbinsearch_@side@_@suff@(const char *arr, const char *key,
                            const char *sort, char *ret,
                            npy_intp arr_len, npy_intp key_len,
                            npy_intp arr_str, npy_intp key_str,
                            npy_intp sort_str, npy_intp ret_str,
                            PyArrayObject *unused);
+NPY_VISIBILITY_HIDDEN int
+transferargbinsearch_@side@_@suff@(char *arr, const char *key,
+                           const char *sort, char *ret,
+                           npy_intp arr_len, npy_intp key_len,
+                           npy_intp arr_str, npy_intp key_str,
+                           npy_intp sort_str, npy_intp ret_str,
+                           npy_intp arr_itemsize, PyArray_StridedUnaryOp *transfer,
+                           NpyAuxData *transfer_data, PyArrayObject *unused);
 /**end repeat1**/
 
 NPY_VISIBILITY_HIDDEN void
@@ -90,6 +123,10 @@ static @arg@binsearch_map _@arg@binsearch_map[] = {
             &@arg@binsearch_left_@suff@,
             &@arg@binsearch_right_@suff@,
         },
+        {
+            &transfer@arg@binsearch_left_@suff@,
+            &transfer@arg@binsearch_right_@suff@
+        }
     },
     /**end repeat1**/
 };
@@ -99,16 +136,20 @@ static PyArray_@Arg@BinSearchFunc *gen@arg@binsearch_map[] = {
     &npy_@arg@binsearch_right,
 };
 
-static NPY_INLINE PyArray_@Arg@BinSearchFunc*
-get_@arg@binsearch_func(PyArray_Descr *dtype, NPY_SEARCHSIDE side)
+static NPY_INLINE void
+get_@arg@binsearch_func(PyArray_Descr *dtype, NPY_SEARCHSIDE side,
+    PyArray_@Arg@BinSearchFunc **func,
+    PyArray_Transfer@Arg@BinSearchFunc **transferfunc)
 {
     npy_intp nfuncs = ARRAY_SIZE(_@arg@binsearch_map);
     npy_intp min_idx = 0;
     npy_intp max_idx = nfuncs;
     int type = dtype->type_num;
 
     if (side >= NPY_NSEARCHSIDES) {
-        return NULL;
+        (*func)= NULL;
+        (*transferfunc) = NULL;
+        return;
     }
 
     /*
@@ -128,14 +169,19 @@ get_@arg@binsearch_func(PyArray_Descr *dtype, NPY_SEARCHSIDE side)
 
     if (min_idx < nfuncs &&
             _@arg@binsearch_map[min_idx].typenum == type) {
-        return _@arg@binsearch_map[min_idx].@arg@binsearch[side];
+        (*func) = _@arg@binsearch_map[min_idx].@arg@binsearch[side];
+        (*transferfunc) = _@arg@binsearch_map[min_idx].transfer@arg@binsearch[side];
+        return;
     }
 
     if (dtype->f->compare) {
-        return gen@arg@binsearch_map[side];
+        (*func) = gen@arg@binsearch_map[side];
+        (*transferfunc) = NULL;
+        return;
     }
 
-    return NULL;
+    (*func) = NULL;
+    (*transferfunc) = NULL;
 }
 /**end repeat**/
 

diff --git a/numpy/core/src/multiarray/array_assign_array.c b/numpy/core/src/multiarray/array_assign_array.c
@@ -24,47 +24,6 @@
 
 #include "array_assign.h"
 
-/*
- * Check that array data is both uint-aligned and true-aligned for all array
- * elements, as required by the copy/casting code in lowlevel_strided_loops.c
- */
-NPY_NO_EXPORT int
-copycast_isaligned(int ndim, npy_intp const *shape,
-        PyArray_Descr *dtype, char *data, npy_intp const *strides)
-{
-    int aligned;
-    int big_aln, small_aln;
-
-    int uint_aln = npy_uint_alignment(dtype->elsize);
-    int true_aln = dtype->alignment;
-
-    /* uint alignment can be 0, meaning not uint alignable */
-    if (uint_aln == 0) {
-        return 0;
-    }
-
-    /*
-     * As an optimization, it is unnecessary to check the alignment to the
-     * smaller of (uint_aln, true_aln) if the data is aligned to the bigger of
-     * the two and the big is a multiple of the small aln. We check the bigger
-     * one first and only check the smaller if necessary.
-     */
-    if (true_aln >= uint_aln) {
-        big_aln = true_aln;
-        small_aln = uint_aln;
-    }
-    else {
-        big_aln = uint_aln;
-        small_aln = true_aln;
-    }
-
-    aligned = raw_array_is_aligned(ndim, shape, data, strides, big_aln);
-    if (aligned && big_aln % small_aln != 0) {
-        aligned = raw_array_is_aligned(ndim, shape, data, strides, small_aln);
-    }
-    return aligned;
-}
-
 /*
  * Assigns the array from 'src' to 'dst'. The strides must already have
  * been broadcast.