BUG: cKDTree GIL handling is incorrect

[sturlamolden]

I believe #9915 has introduced errors in cKDTree GIL handling.

Declaring a C++ function nogil in Cython does not ensure that the GIL is automatically released and reaquired. It only declares that it is allowed to call the function in a nogil context.

Releasing the GIL in Cython is accomplished with a with nogil: statement. There is no such statement in ckdtree.pyx. Therefore, cKDTree does not release the GIL and all multithreading code is now defective.

We must either revert #9915 to keep GIL release and exception translation in C++ or fix ckdtree.pyx to actually release the gil.

[sturlamolden]

ping @rainwoodman @rgommers

[sturlamolden]

Fortunately, fixing ckdtree.pyx is easy. I will take care of it.

[sturlamolden]

This is now fixed in #10516

[rainwoodman]

Ah. Yes there needs to be an explicit release! Totally forgot about that. cython claims memoryviews do not need gil. Are you sure you need to introduce new named variables in those cdefs in and around the thread handler function?

…

On Wed, Jul 24, 2019, 9:13 PM Sturla Molden ***@***.***> wrote: This is now fixed in #10516 <#10516> — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#10514?email_source=notifications&email_token=AABBWTG5M6R4CEKOKKNLFX3QBER75A5CNFSM4IGWCZM2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD2YJESY#issuecomment-514888267>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AABBWTFOK5VVSTYW2YUZ3GTQBER75ANCNFSM4IGWCZMQ> .

[sturlamolden]

I am not sure. We do no use @boundscheck(False) so those indexing can raise exceptions. Maybe Cython will translate them? I do not get errors when those new pointers are not used, but I do get warnings about performence when memoryviews are indexed in the nogil context. Those warnings are silencenced by the new pointer variables, and that is good too, perhaps.

[sturlamolden]

I also took liberty to put the STL std::sort calls into nogil. But here I am wondering about performance and #10216. We use quicksort. Is there any chance that we can get O(Nˆ2) here? Maybe we should use heapsort instead, i.e. std::make_heap and std::sort_heap??

And following this line of thought, do we really a custom C++ heap in query.cxx? Maybe we can just use STL?

[sturlamolden]

But that is for another PR :)

[peterbell10]

We use quicksort. Is there any chance that we can get O(Nˆ2) here? Maybe we should use heapsort instead, i.e. std::make_heap and std::sort_heap??

You shouldn't be worried, std::sort is mandated by the standard to have O(N logN) complexity. Implementations will use some hybrid algorithm such as introsort that handles the degenerate cases gracefully and never falls back to O(N^2).

[sturlamolden]

Good to know, one thing less to worry about :)