Found usecase where reults vary from one run to another

The attached code gives different results in one run and another in my computer. Only merge function is tested. Versions: sortednp 0.2.0 numpy 1.16.2 python 3.6.7

I could not replicate the problem with arrays created directly from lists. It might be caused by the slice but sadly I found my level too low to follow the sortednp source code to narrow down the scope of the issue myself.

test_sortednp.py

assigned to @frank

added reported bug label

@Mantxurreta Thanks for opening this issue. I will look into this and might come back to you if I need more information.

tl;dr The issue is caused by incorrect reference count handling in connection with non-c-contiguous (array.flags) arrays. As a quick fix, warp the array with a = numpy.array(a). I will work on a proper fix today.

---

long version

I could reproduce the underlying issue with a minimal script:

import numpy as np
import sortednp as snp

a = np.array([[1, 2], [3, 4]]) 
nonzero_row, nonzero_col = np.nonzero(a)

x = nonzero_col[0:2]
y = nonzero_col[0:2]

print(snp.merge(x, y))

When executed, this script prints [0 1 0 1] which is not sorted. Looking deeper into the issue reveals that the values from the second array are garbage. It turns out the issue is buried in these two lines.

  a = PyArray_FROM_OF(a, NPY_ARRAY_CARRAY_RO);
  Py_XDECREF(a);

My initial understanding of the reference count of PyArray_FROM_OF was not complete. I assumed that the method simply increments the reference count to the initial array. Since there is always the reference from the caller, I assumed that I can decrement the reference count right away and be safe to exit on error.

However, with non-c-contiguous or not aligned arrays, PyArray_FROM_OF returns a new object with a single reference to it. Deceasing the reference in that case deletes the object. The actual merge algorithm was then reading random values from a memory location that was already freed.

The solution is to decrease the reference count only once the merge/intersect is done or an error occurred.

created merge request !18 (merged) to address this issue

mentioned in merge request !18 (merged)

added confirmed label

mentioned in commit 740489d5

I guess that the origin of the issue is the same, but just to point it out, I find problems with "intersect" function as well. a = numpy.array(a) works to fix the issues with merge and intersect.

Yes, the issue is also present in intersect when the array is not c-contiguous.

Can you have a look at the new release candidate?

pip install sortednp==0.2.1rc1

The new version should fix the issue.

With sortednp==0.2.1rc1 I find it working fine. In my particular case I find it about 5% faster than the suggested quickfix a = numpy.array(a).

This sounds great! I will release this as version 0.2.1.

Thanks for spotting this problem, opening this issue and thus contributing to the project.

Thank you for maintaining the project!

closed