Самый быстрый способ побитового И между двумя массивами на iPhone? - PullRequest
Новая
       17

Самый быстрый способ побитового И между двумя массивами на iPhone?

11 голосов
/ 14 июня 2011

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

int compare(unsigned char *a, int a_pitch, 
            unsigned char *b, int b_pitch, int a_lenx, int a_leny) 
{
    int overlap =0 ;

    for(int y=0; y<a_leny; y++) 
        for(int x=0; x<a_lenx; x++) 
        {
            if(a[x + y * a_pitch] & b[x+y*b_pitch]) 
                overlap++ ;
        }
    return overlap ;
}

На самом деле, мне приходится выполнять эту работу около 220 000 раз, поэтому на устройствах iphone она работает очень медленно.

Как я могу ускорить эту работу на iPhone?

Я слышал, что NEON может быть полезен, но я не очень знаком с ним.Кроме того, кажется, что у NEON нет побитового И ...

Ответы [ 3 ]

2 голосов
/ 14 июня 2011

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

int compare(unsigned char *a, int a_pitch, 
            unsigned char *b, int b_pitch, int a_lenx, int a_leny) 
{
    int overlap = 0;
    uint32_t* a_int = (uint32_t*)a;
    uint32_t* b_int = (uint32_t*)b;

    a_leny = a_leny / 4;
    a_lenx = a_lenx / 4;
    a_pitch = a_pitch / 4;
    b_pitch = b_pitch / 4;

    for(int y=0; y<a_leny_int; y++) 
        for(int x=0; x<a_lenx_int; x++) 
        {
            uint32_t aVal = a_int[x + y * a_pitch_int];
            uint32_t bVal = b_int[x+y*b_pitch_int];
            if (aVal & 0xFF) & (bVal & 0xFF)
                overlap++;
            if ((aVal >> 8) & 0xFF) & ((bVal >> 8) & 0xFF)
                overlap++;
            if ((aVal >> 16) & 0xFF) & ((bVal >> 16) & 0xFF)
                overlap++;
            if ((aVal >> 24) & 0xFF) & ((bVal >> 24) & 0xFF)
                overlap++;
        }
    return overlap ;
}

Вариант 2. Использование эвристики для получения приблизительного результата с использованием меньшего количества вычислений (хороший подход, если абсолютная разница между 101 и 100 перекрытиями не важна для вашего приложения): 

int compare(unsigned char *a, int a_pitch, 
            unsigned char *b, int b_pitch, int a_lenx, int a_leny) 
{
    int overlap =0 ;

    for(int y=0; y<a_leny; y+= 10) 
        for(int x=0; x<a_lenx; x+= 10) 
        {
            //we compare 1% of all the pixels, and use that as the result
            if(a[x + y * a_pitch] & b[x+y*b_pitch]) 
                overlap++ ;
        }
    return overlap * 100;
}

Вариант 3 - переписать вашу функцию в коде встроенной сборки.Ты один для этого.

1 голос
/ 01 ноября 2011

Ваш код - Rambo для процессора - его худший кошмар:

  • байт доступа.Как и упоминалось выше, ARM ОЧЕНЬ медленно читает байты из памяти
  • произвольного доступа.Две абсолютно ненужные операции умножения / сложения в дополнение к и без того крутому снижению производительности по своей природе.

Проще говоря, все неправильно, что может быть неправильно.

Не звоните мнегруб.Позвольте мне вместо этого быть вашим ангелом.

Сначала я предоставлю вам рабочую НЕОН-версию.Затем оптимизированная версия C, показывающая, что именно вы сделали не так.

Просто дайте мне немного времени.Я должен идти спать прямо сейчас, и завтра у меня важная встреча.

Почему бы вам не научиться сборке ARM?Это намного проще и полезнее, чем сборка x86.Это также значительно улучшит ваши возможности программирования на C.Настоятельно рекомендуется

cya

==================================================================================

ОКВот оптимизированная версия, написанная на C с учетом сборки ARM.

Обратите внимание, что оба шага и a_lenx должны быть кратны 4. В противном случае, это не будет работать должным образом.

В этой версии не так много места для оптимизации сборки ARM.(NEON - это другая история, которая скоро появится)

Внимательно рассмотрите, как обрабатывать объявления переменных, цикл, доступ к памяти и операции AND.

И убедитесь, что эта функция выполняется вРежим ARM, а не Thumb для лучших результатов. 

unsigned int compare(unsigned int *a, unsigned int a_pitch, 
            unsigned int *b, unsigned int b_pitch, unsigned int a_lenx, unsigned int a_leny) 
{
    unsigned int overlap =0;
    unsigned int a_gap = (a_pitch - a_lenx)>>2;
    unsigned int b_gap = (b_pitch - a_lenx)>>2;
    unsigned int aval, bval, xcount;

    do
    {
        xcount = (a_lenx>>2);
        do
        {
            aval = *a++;
            // ldr      aval, [a], #4
            bval = *b++;
            // ldr      bavl, [b], #4
            aval &= bval;
            // and      aval, aval, bval

            if (aval & 0x000000ff) overlap += 1;
            // tst      aval, #0x000000ff
            // addne    overlap, overlap, #1
            if (aval & 0x0000ff00) overlap += 1;
            // tst      aval, #0x0000ff00
            // addne    overlap, overlap, #1
            if (aval & 0x00ff0000) overlap += 1;
            // tst      aval, #0x00ff0000
            // addne    overlap, overlap, #1
            if (aval & 0xff000000) overlap += 1;
            // tst      aval, #0xff000000
            // addne    overlap, overlap, #1
        } while (--xcount);

        a += a_gap;
        b += b_gap;
    } while (--a_leny);

    return overlap;
}
0 голосов
/ 14 июня 2011

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

Кроме того, вам не нужно вычислять шаг x + y * для каждого отдельного пикселя;просто увеличить два указателя на один.Увеличение на единицу намного быстрее, чем шаг x + y *.

Почему именно вам нужно выполнить эту операцию?Я хотел бы убедиться в отсутствии высокоуровневых оптимизаций / изменений, прежде чем рассматривать низкоуровневое решение, такое как NEON.

...