Most efficient way to build a 1-d array/list/vector of unknown length using Cython? Or should this never be done?

Question

I have a time-critical model that I wrote in Cython. The main function of my Cython extension has one loop, and according to the Cython profiler (where it shows the amount of Python calls in shades of yellow) the only 'yellow' part is currently where I'm appending to a Python list. (I have to output a Python object as I'm calling my Cython function in a Python script). This is the basic idea of my function (the rest is superfluous, I've tested every part of this function and the append operation is the bottleneck):

from libc.math cimport log
def main(some args):
    cdef (some vars)

    cdef list OutputList = []

    # NB: all vars have declared types
    for x in range(t):
        (do some Cythonic stuff, some of which uses my cimport-ed log)
        if condition is True:
            OutputList.append(x) # this is the only 'yellow' line in my main loop.
    return OutputList # return Python object to Python script that calls main()

Unfortunately, I don't know the length of my output array/list/vector (whatever I end up using). However, I could set it to 52560, which is what I end up resizing it to down the line in some other Python code. I'd like to get a major speed boost without setting the output array's length, but I will gladly toss that hope if it's holding me back.

I've also tried going with C++ in Cython to use C++ data structures (vector, queue, etc.) but doing so removes my ability to nicely cimport log. I see on the Cython documentation/wiki that you can write a 'shim' module to use pure-C functions in C++ Cython, but I have no idea how to do this and I can't find anything about how to go about that.

Anyway, I welcome all suggestions that adhere to my question:

What is the best way to build a list/array/vector of unknown size in Cython? Or is there a clear alternative (such as settling with a known-length iterable object) that makes moot my unknown-length problem?

Update

The C++ containers did show a speed increase over item assignment, and item assignment did show a speed increase over appending to lists and numpy arrays. The best method would be to use C++ containers while also being able to cimport pure-C functions...this would prevent the slow-down from having to look beyond libc.math for a quick log function.

Answer 1

build1darray.pyx:

• specifies types for index variables
• turns off safety checks
• can uses multiple cpus (it is useful for large t and v.size())

#cython: boundscheck=False, wraparound=False
from libc.math cimport log

from cython.parallel cimport prange

import numpy as pynp
cimport numpy as np

# copy declarations from libcpp.vector to allow nogil
cdef extern from "<vector>" namespace "std":
    cdef cppclass vector[T]:
        void push_back(T&) nogil
        size_t size()
        T& operator[](size_t)

def makearray(int t):
    cdef vector[np.float_t] v
    cdef int i
    with nogil: 
        for i in range(t):
            if i % 10 == 0:
                v.push_back(log(i+1))

    cdef np.ndarray[np.float_t] a = pynp.empty(v.size(), dtype=pynp.float)
    for i in prange(a.shape[0], nogil=True):
        a[i] = v[i]
    return a

The 2nd part is ~1% of the first loop therefore it doesn't make sense to optimize it for speed in this case.

<math.h> has extern "C" { ... } on my system so libc.math.log works.

PyArray_SimpleNewFromData() could be used to avoid copying data for the cost of managing memory for the array yourself.