roly: less overhead

[Keith Goodman]

Here's how we initialize the data (in cython) used for the linked list
moving median:

cdef mm_list mm = mm_new(window)
for i in range(window):
mm_insert_init(cython.address(mm), a[i])
y[i] = np.nan

Notice that the loop grabs an element from the array a and then
assigns a value to y. If a and y are large then that is not an
efficient use of cache. It is faster to replace the loop above with
two loops when a and y are large. So I'll commit the change.

fill1 uses one loop; fill2 uses two loops:

>> n = 100
>> a = np.random.rand(n)
>> timeit fill1(a, n)
100000 loops, best of 3: 16.7 us per loop
>> timeit fill2(a, n)
100000 loops, best of 3: 16.8 us per loop

>> n = 1000
>> a = np.random.rand(n)
>> timeit fill1(a, n)
1000 loops, best of 3: 808 us per loop
>> timeit fill2(a, n)
1000 loops, best of 3: 722 us per loop
>> timeit fill1(a, 10)
100000 loops, best of 3: 2.81 us per loop
>> timeit fill2(a, 10)
100000 loops, best of 3: 2.74 us per loop

>> n = 10000
>> timeit fill1(a, 100)
10000 loops, best of 3: 20.5 us per loop
>> timeit fill2(a, 100)
100000 loops, best of 3: 20 us per loop
>> timeit fill1(a, 1000)
1000 loops, best of 3: 810 us per loop
>> timeit fill2(a, 1000)
1000 loops, best of 3: 776 us per loop

Here's the code:

@cython.boundscheck(False)
@cython.wraparound(False)
def fill1(np.ndarray[np.float64_t, ndim=1] a, int window):
cdef np.npy_intp *dims
dims = PyArray_DIMS(a)
cdef int i, n = dims[0]
if window > n:
raise ValueError("`window` must be less than a.size.")
if window < 2:
raise ValueError("I get a segfault when `window` is 1.")
cdef np.ndarray[np.float64_t, ndim=1] y = PyArray_EMPTY(1, dims,
NPY_FLOAT64, 0)
cdef mm_list mm = mm_new(window)
for i in range(window):
mm_insert_init(cython.address(mm), a[i])
y[i] = np.nan
mm_free(cython.address(mm))
return y

@cython.boundscheck(False)
@cython.wraparound(False)
def fill2(np.ndarray[np.float64_t, ndim=1] a, int window):
cdef np.npy_intp *dims
dims = PyArray_DIMS(a)
cdef int i, n = dims[0]
if window > n:
raise ValueError("`window` must be less than a.size.")
if window < 2:
raise ValueError("I get a segfault when `window` is 1.")
cdef np.ndarray[np.float64_t, ndim=1] y = PyArray_EMPTY(1, dims,
NPY_FLOAT64, 0)
cdef mm_list mm = mm_new(window)
for i in range(window):
mm_insert_init(cython.address(mm), a[i])
for i in range(window):
y[i] = np.nan
mm_free(cython.address(mm))
return y