2016-01-28 19 views
6

Opracowuję algorytmy przetwarzania obrazu (używając GCC, kierując ARMv7 (Raspberry Pi 2B)).Szybkie wyszukiwanie/zamiana pasujących pojedynczych bajtów w tablicy 8-bitowej, na ARM

W szczególności używam prostego algorytmu, który zmienia się indeks w masce:

void ChangeIndex(uint8_t * mask, size_t size, uint8_t oldIndex, uint8_t newIndex) 
{ 
    for(size_t i = 0; i < size; ++i) 
    { 
     if(mask[i] == oldIndex) 
      mask[i] = newIndex; 
    } 
} 

Niestety to ma słabą wydajność platformy docelowej.

Czy istnieje sposób na jej optymalizację?

+1

Nie od razu oczywiste, jak sprawić, że szybciej - nie może być sztuczek, jeśli wiesz więcej o danych - na przykład, można mieć listę komórek zawierających wartość 'X' - ale jest to bardzo przydatne, jeśli liczba" trafień "jest dość niska - jeśli trafisz na większość wpisów w" masce "pasujących do" oldIndex ", to raczej nie przyspieszysz. Jaka jest wartość "size" i ile procent tabeli ma przeciętnie wartość "oldIndex"? –

+0

Jakie opcje kompilatora są używane? Upewnij się, że instruujesz go, aby używał instrukcji NEON ("-mfpu = neon-vfpv4", w przeciwnym razie może generować kod zgodny ze starszymi procesorami, które nie mają NEON. – Gilles

+0

Powinieneś również uzyskać pewne przyspieszenie za pomocą potrójnego operatora: 'mask [i] = (mask [i] == oldIndex)? newIndex: mask [i]; ' – Miki

Odpowiedz

13

Platforma ARMv7 obsługuje instrukcje SIMD o nazwie NEON. Dzięki wykorzystaniu nich można sprawić, że kod szybciej:

#include <arm_neon.h> 

void ChangeIndex(uint8_t * mask, size_t size, uint8_t oldIndex, uint8_t newIndex) 
{ 
    size_t alignedSize = size/16*16, i = 0; 

    uint8x16_t _oldIndex = vdupq_n_u8(oldIndex); 
    uint8x16_t _newIndex = vdupq_n_u8(newIndex); 

    for(; i < alignedSize; i += 16) 
    { 
     uint8x16_t oldMask = vld1q_u8(mask + i); // loading of 128-bit vector 
     uint8x16_t condition = vceqq_u8(oldMask, _oldIndex); // compare two 128-bit vectors 
     uint8x16_t newMask = vbslq_u8(condition, _newIndex, oldMask); // selective copying of 128-bit vector 
     vst1q_u8(mask + i, newMask); // saving of 128-bit vector 
    } 

    for(; i < size; ++i) 
    { 
     if(mask[i] == oldIndex) 
      mask[i] = newIndex; 
    } 
} 
+0

Sprawdziłem twoją wersję algorytmu. Działa w 5 razy szybciej niż wersja oryginalna. Wspaniale! –

+0

Możesz osiągnąć dalsze, niewielkie zwiększenie prędkości, pracując bezpośrednio ze wskaźnikiem 'mask', zamiast' mask + i'. Najpierw oblicz obliczenie punktu końcowego 'uint8_t * maskEnd = mask + i;' następnie zmień pętle for, aby działały bezpośrednio ze wskaźnikiem, np. 'for (; mask

+0

Prawdopodobnie możesz zrobić to jeszcze szybciej, pisząc bezpośrednio zespół Neon. Implanty Neon GCC w Neon nie są zbyt szybkie, ponieważ przenoszą materiał między Neonem a głównymi rejestrami, co zatrzymuje rurociąg. (Może naprawili to od czasu ich ostatniego użycia.) –

Powiązane problemy