How can I tell which functions are safe to use inplace?

[ThomasHabets]

This doesn't seem like the right place to ask, but:

1. libvolk.org "documentation" gives 403
2. chat.gnuradio.org does not connect with IRC
3. even after resetting my password, the web version of the chat rejects my login
4. libvolk.org mailing list link gives 404

So I'm running out of places to ask these kinds of questions.

Anyway, to my question:

I started a Rust wrapper for volk, and would like to provide safe wrapper functions that allow in-place calls.

E.g. in addition to volk_32fc_x2_multiply_32fc I would like to have this inplace version.

But is that safe? Which, if any, volk functions guarantee correctness if input overlaps with output, and if so, what kind of overlap?

[jdemel]

This is a really cool project =D

The gnuradio mailing list should be another place to ask questions. For VOLK specific questions a [VOLK] prefix in the subject would be helpful. The correct link probably needs to be updated on the website. Thanks for reporting this issue.

Since VOLK is written in C, it can't give the same compile-time guarantees that Rust offers.

I assume your question relates to a situation like this:

volk::vector<std::complex<float>> input(100);
auto in = std::span{input};
auto out = std::span{input}.subspan(10);

volk_32fc_x2_multiply_32fc(out.data(), in.data(), out.data(), out.size());

The example is written in C++, but it should convey the problem.

There are no tests that ensure that the result of this operation would be correct for partially overlapping input. So far, this case has been neglected. I could imagine that a specific test with our new-ish googletest framework to cover this situation would help to ensure it doesn't break in the future. While I don't expect a reason that this kernel would break, it could happen for another kernel.
In essence: there are currently no guarantees.

[ThomasHabets]

I intend to export (and do, for the couple of functions I've implemented) both safe and unsafe versions into Rust. So I believe I can provide a Rust level of safety, with minimal overhead.

Yeah, that illustrates it. Well, your version goes even more extreme by setting a, b (in0, in1), and out all to the same buffer, but I was thinking more out *= b, by setting either a or b equal to out.

If there are no guarantees, then the multiply block has a bug. Also a couple of other blocks make this assumption, as can be seen by just running grep -r volk_32fc_x2_multiply_32fc .

[jdemel]

If there are no guarantees, then the multiply block has a bug. Also a couple of other blocks make this assumption, as can be seen by just running grep -r volk_32fc_x2_multiply_32fc .

yeah. So we rely on the fact that this works in GR, however, we don't validate this assumption. This is something we should certainly do.

[ThomasHabets]

Yeah both specify and validate.

I'm guessing most are probably fine, and would only need to document as such, and get a test.

Likely the test would need to carefully check that it works both aligned and unaligned.

[marcusmueller]

If there are no guarantees, then the multiply block has a bug.

so, no, it doesn't have a bug (mostly by design luck), because the function signature is

static inline void f(t* out, const t* in_a, const t* in_b, unsigned int);

and aliasing rules say that the compiler mustn't assume out and in_a or in_b point to different objects, because t* and const t* are "compatible types" in terms of both C and C++'s strict aliasing rules. And the logic we do in multiply_* doesn't try to read any input values from "earlier" addresses assuming they weren't changed in the meantime.

Now.

Of course that means that all our non-in-place kernels leave compiler optimization on the table.

But that, at least, isn't bugprone.

I think in C, we have basically no help from the language to mark the out-of- or in-placeness of a kernel, and must document it manually. We can add restrict to out parameters where we explicitly do not allow in-place operation to signal that. But that's only useful when from the absence of restrict on a parameter it follows that it's OK to pass the same array for multiple inputs or one output and one input parameter.

And that would require a very thorough study of the implementations of all kernels. Uff.

[ThomasHabets]

@marcusmueller I think with the function signature you're addressing a bit of a different issue. Yes, the lack of restrict (a good thing) means that the compiler can't turn:

*out = *in_a * *in_b;

into:

*out = *in_a;
*out *= in_b;

(If out==in_b, this produces wrong output)

But if in fact the _generic implementation is or in the future becomes the latter, then any caller using in-place would have a bug.

GNU Radio is relying on the implementation, not the documentation/specification (Hyrum's law). I guess you can say that GNU Radio does not have a bug because you've peaked into one of the actual kernel implementations? I guess it depends on what the meaning of "bug" is, but fair enough.

Of course that means that all our non-in-place kernels leave compiler optimization on the table.

This is assuming that, in fact, none of those kernels (some of which are written in pure assembly) do some sketchy things that would break in-place. Maybe some do. Probably not(?), but best would probably be to actually add that to the tests, and then document that it's safe to rely on in-place being safe.

I don't think volk needs or should have memmove() levels of guarantees, where any and all levels of overlap works. That would compromise basically all kernels, as we'd need to check for all edge cases. But maybe that's just because I personally have never needed to do that.

I think the way forward may be to do these things:

1. Decide/document that it's the intention that kernels having an output of the same type as one or more of the inputs will do the right thing if the output pointer is the same as one or more of those inputs. Explicitly do not support partial overlap.
2. Add tests to make sure that this is true.

On the topic of restrict, last I checked that's C-only, not C++, technically and amusingly.