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

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 l开发者_高级运维ot 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.

---

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.

---

You can also use a dedicated data structure rather than an array to speed up the forward transform. A fast implementation can be built with a list of linked lists to avoid the array element moves altogether.

See http://code.google.com/p/kanzi/source/browse/java/src/kanzi/transform/MTFT.java

For inverse transform, it turns out that arrays are as fast as linked lists.