14 ms·
Wouldn't something like float temp_out = 0.0f; for (j = 0;j<5;j++) temp_out += filter[j] * in[i+j]; out[i] = temp_out; solve the performa
by maweaver 16y ago
Wouldn't something like
float temp_out = 0.0f;
for (j = 0;j<5;j++)
temp_out += filter[j] * in[i+j];
out[i] = temp_out;
solve the performance issue, and allow for out = in? (which I would think would be desirable, in cases where you don't need the original input).
Also, this is way outside my area of expertise, but when I hear convolution I think FFT. I would be curious if anyone knows whether there is an algorithmic improvement to be made here.
- cameldrv 16y agoI think that your solution is better in that it's simpler, but I'm not sure what the compiler will do in this case. Theoretically, in[i+j] could point to temp_out, but it could only be through very tricky means, since temp_out is on the stack, and the caller presumably doesn't know where it will be allocated. An FFT wouldn't be faster in this case since the filter only has five taps. Generally there has to be a decent sized kernel for the FFT to be worth it -- the FFT is O(N log N), and this algorithm is only 5*N operations.
- JoachimSchipper 16y agoThe compiler is free to optimize in this case, because there's no requirement that in[i + j] point to temp_out, even if you manage to make the stars align.
- lbrandy 16y agoIf you look at the code I put on github, you will see I tested this exact bit of code. It does produce good assembly but I left it out because the post was already long, and it obfuscates -why- this improvement improves performance. Your second comment (about out == in), is a bit trickier. This is obviously a contrived example. In a normal gaussian filter, you'd want the filter centered so that the effective indexes of the filter are -2 .. 2, not 0 .. 5. This makes (out == in) a trickier problem to solve. I didn't really want to get into those details in the post.