Fast memmove для x86 и +1 сдвиг (для Move-на-перед преобразованием)

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 (преобразование Burrows-Wheeler)

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

Answer 1

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

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

Answer 2

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

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

Для обратного преобразования, то получается, что массивы так быстро, как связанные списки.