Fast memmove for x86 and +1 shift (for Move-to-front transform)

Question

Hi

For fast MTF ( http://en.wikipedia.org/wiki/Move-to-front_transform ) i need faster version of moving a char from inside the array into the front of it:

char mtfSymbol[256], front;
char i;

for(;;) { \\ a very big loop 
    ... 
    i=get_i(); \\ i is in 0..256 but more likely to be smaller.

    front=mtfSymbol[i];
    memmove(mtfSymbol+1, mtfSymbol, i);
    mtfSymbol[0]=front;
}

cachegrind shows, that for memmove there are lot of branch mispredictions here.

For the other version of code (not a memmove in the first example, but this one)

do
{
   mtfSymbol[i] = mtfSymbol[i-1];
} while ( --i );

there are lot of byte reads/writes, conditional branches and branch mispredictions

i is not very big, as it is MTF used for "good" input - a text file after a BWT ( Burrows–Wheeler transform )

Compiler is GCC.

Answer 1

If you pre-allocate your buffer bigger than you're going to need it, and put your initial array somewhere in the middle (or at the end, if you're never going to have to extend it that way) then you can append items (up to a limit) by changing the address of the start of the array rather than by moving all the elements.

You'll obviously need to keep track of how far back you've moved, so you can re-allocate if you do fall off the start of your existing allocation, but this should still be quicker than moving all of your array entries around.