volk_32fc_index_max_16u returns wrong values

[willcode]

Issue reported by Gilad Beeri. This originally looked like a memory corruption problem, but it seems like there might be something wrong with the kernel. The result is that the first index out of the group of 4 containing the max value is returned.

On Tue, Jan 23, 2018 at 8:12 AM, Gilad Beeri (ApolloShield) gilad@apolloshield.com wrote:

First,
"~/p/s/p/test_data (master)> cat ~/.volk/volk_config | grep volk_32fc_index_max_16u
volk_32fc_index_max_16u a_sse3 generic"

I did "vector[996] = gr_complex(1,1);" and it resulted in argmax 996 (correct result).
Same results when setting any single sample between 996 to 999.
But - when I set 995 to (1,1), argmax returns 992 (?!)
When I set 992 to (1,1), argmax returns 992.
When I set 991, argmax returns 888.
When I set sample #2, argmax returns 0.

So the pattern seems to be:
Return the first index of the quartet that contains the biggest sample.



On Tue, Jan 23, 2018 at 1:52 PM Jeff Long <willcode4@gmail.com> wrote:

    The generic VOLK implementation (probably not the one being called) can't do this, but the vectorized version (which is probably being called) does things in groups of 4. Can you try making 996 the highest and see if it wrongly reports 999?

[giladbeeri]

Link to original GNU Radio thread: https://lists.gnu.org/archive/html/discuss-gnuradio/2018-01/msg00169.html

[awalls-cx18]

I'm not saying this is the cause of the bug, but the reassignment of xmm8 here looks like an error:

https://github.com/gnuradio/volk/blob/master/kernels/volk/volk_32fc_index_max_16u.h#L117

[n-west]

It does look like the xmm8 should not be reassigned. Removing that seems to fix the issue for me. Fix incoming.

Test program follows:

#include <volk/volk.h>
#include <stdint.h>
#include <stdio.h>


int test_the_kernel(int val) {
    lv_32fc_t test_array[1000] = {0};
    test_array[val] = 1.0;
    unsigned int length = 1000;
    uint16_t result;
    volk_32fc_index_max_16u_manual(&result, test_array, length, "a_sse3");
    return result;
}

int main() {
    for (int ii = 990; ii < 1000; ++ii) {
        int res = test_the_kernel(ii);
        printf("output result is %u, expected %i\n", res, ii);
    }
}

[n-west]

The fix is on maint and master, which should have releases very soon. A holler to confirm the issue is resolved for you would be appreciated :-)

[giladbeeri]

Update:
I applied the patch on top of v1.3 and installed a prefix using pybombs with the new patched version, so I have 2 GR environments and the only difference should be the patch, in addition to a 3rd env that uses the numpy-based Python block.

I ran the new version with the specific vector used for the above debugging (that resulted in argmax 996 when it should have been 999) and it now returns 996, so there's some progress.

I also ran several big input files with the 3 environments and compared the results.
It is clear that the old VOLK env shows significantly different results than the new VOLK env, when comparing to the numpy env, but there are still some differences between numpy and the patched VOLK (for about 10% of the input).

I'm investigating the other input data that reproduces wrong values and will update here.

[n-west]

I think numpy as not doing what you expect it to. Looking in to this I learned something new as well :-)

I added the index_max to my personal python wrapper around volk, which I suppose I can share but it's pretty minimal right now and prone to crashiness if you don't treat it carefully, then compare numpy and volk index_max results.

import pyvolk as volk
import numpy as np
test_v = np.complex64(np.random.randn(5000) + np.random.randn(5000)*1.j)
np_argmax = np.argmax(test_v)
volk_argmax= volk.argmax_16u(test_v)

print "numpy argmax: %i is (%1.4f, %1.4f) has mag %1.4f" % (np_argmax, test_v[np_argmax].real, test_v[np_argmax].imag, np.abs(test_v[np_argmax]))
print "volk  argmax: %i is (%1.4f, %1.4f) has mag %1.4f" % (volk_argmax, test_v[volk_argmax].real, test_v[volk_argmax].imag, np.abs(test_v[volk_argmax]))


print np.argmax(np.abs(test_v))

root@a119255b03b9:/projects/pyvolk/build-docker# python2 test_them.py
numpy argmax: 4810 is (3.6940, -0.1589) has mag 3.6974
volk  argmax: 489 is (2.9188, 3.1652) has mag 4.3056
489

So from this I deduce that numpy is probably casting the complex value to a float, which discards imaginary, before doing a comparison. If you do numpy.argmax(np.abs(vec)) you'lll probably get results that match volk. This might be an interesting bug to file with numpy, since it's certainly not the behavior I would have expected.

[giladbeeri]

Without digging into numpy, I can confirm the issue for now seems to be in numpy, not VOLK, as I have 2 vectors that differ in their argmax between numpy and VOLK, but when printing the abs value, it is clear that VOLK is right. I can also confirm that with numpy.argmax(numpy.abs(vec)), the argmax is as with VOLK, in the 2 vectors I'm testing now.

I don't really use numpy.argmax (was only used for the sake of debugging, I actually calculate argmax manually in the Python block) so I still need to explain the 10% difference between the Python block and the C++ block.

It might be rounding differences, as the differences are pretty small (with the VOLK argmax bug, the differences were huge).

I'll update.

[n-west]

OK. Seems like the remaining bug is likely in your custom argmax. I'll close the issue now.

[giladbeeri]

For future reference, the numpy.argmax() behavior is due to the behavior of argmax.sort() (sort complex items first by real, then by imaginary): numpy/numpy#10469 (comment)