Is it simple to implement a simple python function in C?

Question

I am working on the problem posed by this post: Fast way to remove a few items from a list/queue

Basically all I want to do is implement a for loop in C. The for loop needs to access a generator and be able to delete elements of an array (and increment an integer). Something in me tells me this would be painfully difficult, but another part says it could be handled in minutes.

I have no experience writing high level C (I've written code for microcontrollers though), and the tutorials for ctypes and other c-> python seem like they are addressing more difficult problems.

def forfilt():
   marked = (i for i, x in enumerate(b) if tokeep(x))
   shift = 0
   for n in marked:
      del b[n - shift]
      shift += 1

I'm asking two questions:

• IS this difficult?

• Do you have any pointers/want to write the code yourself? :D

This seems like a rather important problem to me actually. I don't know of any way to quickly do what the original question was asking. I suppose if you know the answer to that, then the question is void.

Answer 1

If all you need is to remove for-loop overhead then it is sufficient to define type of a for loop variable in Cython (pip install cython). Here's a modified remove_inplace_senderle2() in Cython delitems.pyx:

#cython: boundscheck=False, wraparound=False
import cython

@cython.locals(end=cython.Py_ssize_t, i=cython.Py_ssize_t)
def remove_inplace_senderle2(L, keep):
    end = 0
    for i in range(len(L)):
        x = L[end] = L[i]
        if keep(x):
           end += 1

    del L[end:]

for i in range(len(L)) translates to a classic C-loop: for (i=0; i < L_length; ++i) and its overhead is dwarfed by a keep()'s function call overhead.

Note: the above function can be slower in pure Python than L = filter(keep, L) (or listcomp).

See gcd() function for even simpler example how Cython can be compiled and used.

Answer 2

It depends how simple is simple. Yes, this particular function can be written as in-place memory movement, as long as the input is an array.

size_t for_filt( my_struct *b, size_t n ) {
    my_struct *src_pen, *dst_pen;

    for ( src_pen = dst_pen = b;
          src_pen != b + n;
          ++ src_pen ) {
        if ( tokeep( src_pen ) ) {
            memmove( dst_pen ++, src_pen, sizeof (my_struct) );
        }
    }

    return dst_pen - b; /* return number of elements in resulting array */
}

The C++ Standard Library reduces the above function to a one-liner:

n = std::remove_if( b, b+n, std::not1( tokeep ) ) - b;

The function will work with structures besides arrays, but the n = … - b; is array-specific.

Answer 3

Writing C code against the CPython C-API is considerably more pleasant than writing C code without the support of such an API. However, it is primarily the building and linking process and getting all that set up which can be rather tedious. Once you have a C extension in place, adding to it isn't too difficult (although there is still some fiddling around to do getting things properly exposed at the Python level and making sure all your reference counts are correct).

Other static compilation tools like Cython similar suffer from relatively high setup costs to get the compiled extension working in the first place, but are much easier to use once that is already in place.

In relation to your specific question, by comparing the list comprehension approach to the filter builtin (or its Py3k equivalent, functools.filter) the poster of the question you linked has already demonstrated the effect of dropping the looping code down into C - native looping is one of the major benefits of the builtin iteration and reduction functions like sum, any, all, map and filter.

The removal of the Python level loop overhead is likely responsible for most of the measured ~10% difference in the performance of the two approaches (list comprehension vs filter call).