Быстрое замещение для x86 и +1 shift (для преобразования Move-to-front)

Question

Для быстрого MTF (http://en.wikipedia.org/wiki/Move-to-front_transform) мне нужна более быстрая версия перемещения символа из массива в его переднюю часть:

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 показывает, что для memmove существует множество неправильных прогнозов ветвей.

Для другой версии кода (не memmove в первом примере, а этот)

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

Есть много байтов для чтения / записи, условных ветвлений и неправильных прогнозов ветвей

я не очень большой, так как это MTF, используемый для «хорошего» ввода - текстовый файл после BWT (преобразование Берроуза – Уилера)

Компилятор GCC.

Answer 1

Вы также можете использовать выделенную структуру данных, а не массив для ускорения прямого преобразования. Быстрая реализация может быть построена со списком связанных списков, чтобы избежать перемещения элементов массива.

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

Оказывается, что для обратного преобразования массивы работают так же быстро, как связанные списки.

Answer 2

Если вы предварительно выделите свой буфер больше, чем вам понадобится, и поместите исходный массив где-то посередине (или в конце, если вам никогда не придется расширять его таким образом), тогдаВы можете добавлять элементы (до предела), изменяя адрес начала массива, а не перемещая все элементы.

Вам, очевидно, нужно будет отслеживать, насколько далеко вы переместились, так что вы можете перераспределить, если вы упали с начала существующего выделения, но это все равно должно быть быстрее, чем перемещать все записи массива.