How to implement spline16/bicubic, etc, quickly

[wonkey_monkey]

Hi all (apologies in advance if this is a bit vague),

I'm writing a myriad of filters, most of which involve warping images in all kinds of ways, so I've written a function to do spline16 interpolation for coorindates in an AVS frame. It seems to be running a bit slow to me, though, and I'm not sure if I'm missing something obvious or if I'm just expecting too much from my CPU.

For instance (and it's not the best comparison admittedly) Guth's Deshaker (VirtualDub filter) seems capable of nearly 25fps bicubic resampling of HD video on a single core, whereas I'm barely reaching 10fps on all 8 cores (all of which are only running at about 45%, perhaps[?] because they're all trying to access the same areas of memory at the same time - if anyone also has some tips on multithreading Avisynth filters, they will also be gratefully received!).

Can anyone recommend some implementations of bicubic or similar resampling that I might get some hints from? The kind of filtering I'm doing involves more than translations and rotations, so I don't know of any two-pass or three-shear type approaches that will work.

Thanks,

David

[IanB]

A bit (lot) to vague, post your code or at least the algorithm.

Internally threading a filter usually means segmenting the frame in some access pattern sensible manner and giving a chunk to each core. Vertical strips, horizontal strips, rectangles, interleaves are some choices. Which you end up using depends on the individual algorithm. Generally at the deepest level you want unique sets of cache lines processed by individual cores. Coordinating access to common data by multiple cores can be a pita and very slow when done badly.

[wonkey_monkey]

This is the main loop of my pixel interpolating function:


af=0; rf=0; gf=0; bf=0;
for (iy=sy; iy<ey; iy++) {
x_offset_=x_offset;
wy=interleavedweights[y_offset++];
for (ix=sx; ix<ex; ix++) {
w=interleavedweights[x_offset_++]*wy;
bf+=input->rows[iy][ix*4]*w;
gf+=input->rows[iy][ix*4+1]*w;
rf+=input->rows[iy][ix*4+2]*w;
af+=input->rows[iy][ix*4+3]*w;
}
}


(double*)interleavedweights is a lookup table of precalculated weights (in this case spline16, but could be bicubic, etc), the starting offsets of which are calculated per pixel, based on the non-integer part of the x,y position. input is my own class for manipulating images - in this case RGBA, so input->rows is a unsigned char** (pointing to the rows of the GetReadPtr() bitmap). af/rf/gf/bf are all doubles which are round back to ints afterward and returned as a 32-bit unsigned int to be inserted into the output image (GetWritePtr()).

I borrowed the multithreading code from Efenstor's multithreaded version of Defish (http://forum.doom9.org/showthread.php?p=1496351#post1496351). It splits the image into horizontal strips, one per core, passing the input/output images and start/end rows, but each thread will be reading some of the same memory, such as the interleavedweights table, and of course the images - could this be why the cores aren't being fully utilised?

David

[IanB]

A keyhole of the view of what you think you want to show does not inspire people to want to help you. :devil:

The type of variables and the range of values they are likely to experience is important information when assessing how to improve the performance of code.

You do confess (double*)interleavedweights. Probably float will have sufficient precision and be ~2 times faster, if so then scaled integer arithmetic may avoid the convert to and from floating point extra cost.

This part of the code wy=interleavedweights[y_offset++];
for (ix=sx; ix<ex; ix++) {
w=interleavedweights[x_offset_++]*wy;implies that algorithm is probably separable. If it is not then why not dodge the extra multiply and pre-calculate all the coefficients.

Separable algorithms have the property that a [M x N] result can be achieved with only a [M] + [N] complexity. i.e. 2x2=4, 2+2=4 but 3x3=9, 3+3=6 and 3x4=12, 3+4=7 and 4x4=16, 4+4=8.

Also do not be lazy and trust the optimiser to recognise common code, when it is obvious do it yourself. Quite often you will see a further improvement the compiler can never be allowed to utilise. i.e. Pixel[Y*pitch+X] versus Row=Pixel[0], Row[X], Row+=pitch

[wonkey_monkey]

Thanks Ian, that's given me some good pointers - I'm embarrassed to say it never occurred to me to pre-calculate all the coefficients. Using floats improved things only very slightly, and it seems my multithreading is okay because it works at 100% when called from plain C++ - I guess I'm missing something in what should be my minimal filter overheads. Hopefully with your suggestions I will get it to a usable speed and have something useful to share soon.

David