Using cdef extern to get std::algorithm c++ functionality into Cython

[Adam Li]

Hi

Per this GH issue, I want to get std::swap functionality into my Cython code. How would I go about doing this? I currently have the following code, but it errors out when I try to build.

```
# XXX: replace with from libcpp.algorithm cimport swap
# when Cython 3.0 is released
cdef extern from "<algorithm>" namespace "std" nogil:
    void swap[T](T& a, T& b) except +  # array overload also works

...
cdef func(...) nogil:
        # construct an array to sample from mTry x n_features set of indices
        cdef vector[SIZE_t] indices_to_sample = vector[SIZE_t](max_features * n_non_zeros)
        cdef SIZE_t n = indices_to_sample.size()
        for i in range(0, n):
            indices_to_sample.push_back(i)

        # shuffle indices over the 2D grid to sample using Fisher-Yates
        cdef SIZE_t j
        cdef int* T1
        cdef int* T2  
        for i in range(0, n):
            j = rand_int(0, n - i, random_state)
            swap(&indices_to_sample[i], &indices_to_sample[j])
```

produces an error still when trying to build:

```
     ^
    sklearn/tree/_oblique_splitter.cpp:5457:7: error: no matching function for call to 'swap'
```

Is there something extra one must do to copy over the swap functionality?        

Thanks!

--

Best Regards,

Adam Li (he/him), PhD in Biomedical Engineering 

Postdoctoral Researcher at Columbia University

Causal AI Lab

LinkedIn | Personal Website | al...@jhu.edu

[da-woods]

The following compiles correctly on my PC (both Cython 0.29.x and master)

```

# distutils: language=c++

from libcpp.vector cimport vector

# XXX: replace with from libcpp.algorithm cimport swap
# when Cython 3.0 is released
cdef extern from "<algorithm>" namespace "std" nogil:
    void swap[T](T& a, T& b) except +  # array overload also works

ctypedef size_t SIZE_t

...
cdef void func(int max_features, int n_non_zeros) nogil:

        # construct an array to sample from mTry x n_features set of indices
        cdef vector[SIZE_t] indices_to_sample = vector[SIZE_t](max_features * n_non_zeros)
        cdef SIZE_t n = indices_to_sample.size()
        for i in range(0, n):
            indices_to_sample.push_back(i)

        # shuffle indices over the 2D grid to sample using Fisher-Yates
        cdef SIZE_t j
        cdef int* T1
        cdef int* T2
        for i in range(0, n):

            j = j+1
            #j = rand_int(0, n - i, random_state)

            swap(&indices_to_sample[i], &indices_to_sample[j])

```

Changes I had to make were:

* cimport vector

* defined SIZE_t by ctypedef

* replace "rand_int" by a placeholder expression (just because I don't have a definition for it)

* add some dummy function args and a return type

* add `distutils: language=c++` (this may well be in setup.py or similar)

I imagine a good chunk of these were in the code that you omitted from your example. But your example basically works and it's some minor detail that you probably don't show that's tripping it up.

David**

--

---
You received this message because you are subscribed to the Google Groups "cython-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cython-users...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cython-users/CAJ1JY4qM-tp3Zybms-SXqn4xRpX4UB5zdT2KhDzPZoO63Z-XWw%40mail.gmail.com.

[da-woods]

On 14/05/2022 18:03, da-woods wrote:
> The following compiles correctly on my PC (both Cython 0.29.x and master)

On GCC 11.2.1 on Linux...

[Adam Li]

Hi David,

I get the following error:

```

sklearn/tree/_oblique_splitter.cpp:5458:7: error: no matching function for call to 'swap'
          std::swap<size_t *>((&(__pyx_v_indices_to_sample[__pyx_v_i])), (&(__pyx_v_indices_to_sample[__pyx_v_j])));
          ^~~~~~~~~~~~~~~~~~~
    /Users/adam2392/miniforge3/envs/sklearn-dev/bin/../include/c++/v1/type_traits:3948:1: note: candidate function template not viable: expects an lvalue for 1st argument
    swap(_Tp& __x, _Tp& __y) _NOEXCEPT_(is_nothrow_move_constructible<_Tp>::value &&

    /Users/adam2392/miniforge3/envs/sklearn-dev/bin/../include/c++/v1/memory:3545:1: note: candidate function template not viable: no known conversion from 'std::__vector_base<unsigned long, std::allocator<unsigned long>>::value_type *' (aka 'unsigned long *') to 'shared_ptr<unsigned long *> &' for 1st argument

```

with a setup.py and pyx file as attached. Any chance you can see something I'm immediately doing wrong here? If not, then no problem... I suspect there's some I guess weird c++ syntax I'm not doing correctly perhaps... Thanks!

--

---
You received this message because you are subscribed to the Google Groups "cython-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cython-users...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/cython-users/d9cfffa7-7e28-8b89-9026-4b167d07132f%40d-woods.co.uk.

[da-woods]

That seems very odd to me - this feels like a bug in the C++ standard library implementation to me. But I could be wrong...

I think your example file depends on enough of sklearn that it's difficult for me to test independently. So I'll offer a few of untested options to try:

1. `swap(indices_to_sample.data()+i, indices_to_sample.data()+j)`

2. Try defining swap as `void swap(...)` - this tells Cython that it's a C varargs function (so Cython can't know the argument types). It stops Cython trying to second-guess the templates and lets C++ sort it out.

3. You could just skip swap and write it yourself: `indices_to_sample[j], indices_to_sample[i] = indicies_to_sample[i], indices_to_sample[j]`. The real value of swap is for expensive-to-copy types (and with move constructors that applies less than it did). For integers it'll just be the same as doing the assignment.

To view this discussion on the web visit https://groups.google.com/d/msgid/cython-users/CAJ1JY4r64Z7BoRtJvdHfFb-KJtsDeDzAKVEC2dvYj36UP7vVew%40mail.gmail.com.

[Adam Li]

Hmm... It doesn't work, but I suspect it might be because swap is not thread safe(?) According to SO: https://stackoverflow.com/questions/29541387/is-shared-ptr-swap-thread-safe.

However, I saw that atomic_exchange is? Do you know if the exchange function here is the same as in std? https://github.com/cython/cython/blob/master/Cython/Includes/libcpp/atomic.pxd

My question is:

- Do you know how one would use the "atomic_exchange" function in Cython to exchange values in a vector container of integers that is thread safe (parallelizable)? I am trying to achieve a Fisher-Yates shuffling since there is no shuffle function in Cython. 

Thanks so much for your help!

To view this discussion on the web visit https://groups.google.com/d/msgid/cython-users/4c3b2339-0dd5-3b15-5161-f36cd010fd38%40d-woods.co.uk.