Оптимизированное вращение матрицы - произвольный угол относительно центра матрицы

Вы можете оптимизировать довольно много вещей, если сначала выполните простой приблизительный поворот (90/190/270) градусов, а затем окончательный поворот между 0-90 градусами. Например. тогда вы могли бы оптимизировать тест if( srcX >= 0 && srcX < colSpan && srcY >= 0 && srcY < rowSpan ), и это было бы более удобно для кэширования. Могу поспорить, что ваше профилирование показывает, что поворот на 91 градус намного медленнее, чем поворот на 1 градус.

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

Единственное, что осталось, это цикл, разворачивающий ваш внутренний цикл for... ~4x (для 32-битной системы) или 8x (для 64-битной системы). Это, вероятно, принесет вам улучшение примерно на 10-20%. Из-за характера проблемы (принудительное произвольное чтение из srcData) у вас всегда будет разница во времени.

буду дальше думать...

Ваш внутренний цикл for... является сильной мишенью для векторизации. Рассмотрим статические векторы:

// SSE instructions MOVDDUP (move and duplicate) MULPD (multiply packed double)
double[] vcosa = [cosa, cosa, cosa, cosa] * [1.0, 2.0, 3.0, 4.0]
double[] vsina = [sina, sina, sina, sina] * [1.0, 2.0, 3.0, 4.0]

vxOffset = [xOffset, xOffset, xOffset, xOffset]
vyOffset = [yOffset, yOffset, yOffset, yOffset]

// SSE instructions ADDPD (add packed double) and CVTPD2DQ (convert packed double to signed integer)
vsrcX = vcosa + vxOffset
vsrcY = vsina + vyOffset

Инструкции SSE x86 идеально подходят для обработки данных такого типа. Даже преобразование из двойных чисел в целые. Инструкции AVX, позволяющие использовать 256-битные векторы (4 двойных), подходят еще лучше.

Принимая во внимание предложенные предложения, я пришел к этому решению. Кроме того, я исправил ошибку в моей исходной реализации, из-за которой возникали проблемы с прямоугольными изображениями.

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

Использование тайлов 16x16:

class DoRotate
{
const double sina;
const double cosa;

const double xHelper;
const double yHelper;

const int rowSpan;
const int colSpan;

mutable fcomplex *destData;
const fcomplex *srcData;

const float *offsetsX;
const float *offsetsY;

__m128 dupOffsetsX;
__m128 dupOffsetsY;

public:
void operator() ( const tbb::blocked_range2d<size_t, size_t> r ) const
{
    float xOffset;
    float yOffset;
    int lineOffset;

    __m128i srcXints;
    __m128i srcYints;

    __m128 dupXOffset;
    __m128 dupYOffset;

    for ( size_t row = r.rows().begin(); row != r.rows().end(); ++row )
    {
        const size_t colBegin = r.cols().begin();
        xOffset = -(row * sina) + xHelper + (cosa * colBegin);
        yOffset =  (row * cosa) + yHelper + (sina * colBegin);
        lineOffset = ( row * colSpan );  //- all col values are offsets of this row

        for( size_t col = colBegin; col != r.cols().end(); col+=4, xOffset += (4 * cosa), yOffset += (4 * sina) )
        {
            dupXOffset = _mm_load1_ps(&xOffset); //- duplicate the x offset 4 times into a 4 float field
            dupYOffset = _mm_load1_ps(&yOffset); //- duplicate the y offset 4 times into a 4 float field

            srcXints = _mm_cvttps_epi32( _mm_add_ps( dupOffsetsX, dupXOffset ) );
            srcYints = _mm_cvttps_epi32( _mm_add_ps( dupOffsetsY, dupYOffset ) );

            if( srcXints.m128i_i32[0] >= 0 && srcXints.m128i_i32[0] < colSpan && srcYints.m128i_i32[0] >= 0 && srcYints.m128i_i32[0] < rowSpan ) 
            {
                destData[col + lineOffset] = srcData[srcXints.m128i_i32[0] + ( srcYints.m128i_i32[0] * colSpan )]; 
            }

            if( srcXints.m128i_i32[1] >= 0 && srcXints.m128i_i32[1] < colSpan && srcYints.m128i_i32[1] >= 0 && srcYints.m128i_i32[1] < rowSpan ) 
            {
                destData[col + 1 + lineOffset] = srcData[srcXints.m128i_i32[1] + ( srcYints.m128i_i32[1] * colSpan )]; 
            }

            if( srcXints.m128i_i32[2] >= 0 && srcXints.m128i_i32[2] < colSpan && srcYints.m128i_i32[2] >= 0 && srcYints.m128i_i32[2] < rowSpan ) 
            {
                destData[col + 2 + lineOffset] = srcData[srcXints.m128i_i32[2] + ( srcYints.m128i_i32[2] * colSpan )]; 
            }

            if( srcXints.m128i_i32[3] >= 0 && srcXints.m128i_i32[3] < colSpan && srcYints.m128i_i32[3] >= 0 && srcYints.m128i_i32[3] < rowSpan ) 
            {
                destData[col + 3 + lineOffset] = srcData[srcXints.m128i_i32[3] + ( srcYints.m128i_i32[3] * colSpan )]; 
            }
        }
    }
}

DoRotate( const double pass_sina, const double pass_cosa, const double pass_xHelper, const double pass_yHelper, 
             const int pass_rowSpan, const int pass_colSpan, const float *pass_offsetsX, const float *pass_offsetsY, 
             fcomplex *pass_destData, const fcomplex *pass_srcData ) : 
    sina(pass_sina), cosa(pass_cosa), xHelper(pass_xHelper), yHelper(pass_yHelper), 
    rowSpan(pass_rowSpan), colSpan(pass_colSpan),
    destData(pass_destData), srcData(pass_srcData)
{
    dupOffsetsX = _mm_load_ps(pass_offsetsX); //- load the offset X array into one aligned 4 float field
    dupOffsetsY = _mm_load_ps(pass_offsetsY); //- load the offset X array into one aligned 4 float field
}
};

а затем вызвать код:

double sina = sin(radians);
double cosa = cos(radians);

double centerX = (colSpan) / 2;
double centerY = (rowSpan) / 2;

//- Adding .5 for rounding to avoid periodicity
const double xHelper = centerX - (centerX * cosa) + (centerY * sina) + .5;
const double yHelper = centerY - (centerX * sina) - (centerY * cosa) + .5;

float *offsetsX = (float *)_aligned_malloc( sizeof(float) * 4, 16 );
offsetsX[0] = 0.0f;
offsetsX[1] = cosa;
offsetsX[2] = cosa * 2.0;
offsetsX[3] = cosa * 3.0;
float *offsetsY = (float *)_aligned_malloc( sizeof(float) * 4, 16 );
offsetsY[0] = 0.0f;
offsetsY[1] = sina;
offsetsY[2] = sina * 2.0;
offsetsY[3] = sina * 3.0;

//- tiled approach. Works better, but not by much.  A little more stays in cache
tbb::parallel_for( tbb::blocked_range2d<size_t, size_t>( 0, rowSpan, 16,  0, colSpan, 16 ), DoRotate( sina, cosa, xHelper, yHelper, rowSpan, colSpan, offsetsX, offsetsY, (fcomplex *)pDestData, (fcomplex *)pSrcData ) );

_aligned_free( offsetsX );
_aligned_free( offsetsY );

Я никоим образом не на 100% уверен, что это лучший ответ. Но это лучшее, что я мог предложить. Итак, я решил передать свое решение сообществу.