Как работают Bitshifting и UInt64?

Question

При чтении сообщения в StackOverflow (http://stackoverflow.com/questions/1502081/im-trying-to-optimize-this-c-code-using-4-way-loop-unrolling), который теперь отмечен как и закрыто, я наткнулся на ответ (на самом деле), в котором говорилось следующее: «Две внутренние петли могли бы получить ускорение скорости, используя UInt64 и смещение бит»

Вот код, который был int he post :

char rotate8_descr[] = "rotate8: rotate with 8x8 blocking"; 

    void rotate8(int dim, pixel *src, pixel *dst) 
    { 

    int i, j, ii, jj; 

    for(ii = 0; ii < dim; ii += 8) 
      for(jj = 0; jj < dim; jj += 8) 
        for (i = ii; i < ii + 8; i++) 
         for (j = jj; j < jj + 8; j++) 
          dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)]; 
    } 

Не могли бы вы объяснить, как это будет применяться здесь? Мне интересно знать, как применять битрейт на этом коде или аналогичный код, и почему это поможет в производительности. Кроме того, как оптимизировать этот код для использования кеша? Какие-либо предложения?

Предположим, что этот код был двойным черепицей/заблокирован (большая плитка = 32, а внутри него - плитка 16), а также было применено Loop Invariant Code Motion .. было бы еще полезно использовать bithifting и UInt64?

Если нет, то какие другие предложения будут работать?

Спасибо!

Answer 1

Если пиксели были меньше, вы могли бы использовать 8 регистров Uint64 (они большие и их много), чтобы получить результат для повернутой матрицы.

Пример для sizeof(pixel) == 1 и Little Endian машины:

for (int y = 0; y < 8; ++y){ 
// for every line, we get 8 pixels from row y into src0. 
// they should go in the last colomn of the result 
// so after 8 iterations they'll get exactly in the 8ht byte 
    Uint64 src0 = *(Uint64*)(src + dim * y); 
    dst0 = (dst0 << 8) | (src0 & 0xff); // this was pixel src[y][0] 
    dst1 = (dst1 << 8) | ((src0 >> 8) & 0xff); // and pixel src[y][1] 
    etc... 
}; 
// now the 8 dst0..dst7 registers contain rows 0..7 of the result. 
// putting them there 
*(Uint64*)(dst) = dst0; 
*(Uint64*)(dst + dim) = dst1; 
etc.. 

Значительная часть является то, что легче раскатать и изменять порядок, и есть меньше доступа к памяти.