Loop unroll (с побитови операции)

Пиша драйвер за ядрото на Linux (за ARM) и в irq манипулатор трябва да проверя битовете за прекъсване.

bit
 0/16  End point 0 In/Out interrupt
       (very likely, while In is more likely)
 1/17  End point 1 In/Out interrupt
 ...
15/31  End point 15 In/Out interrupt

Имайте предвид, че повече от малко могат да бъдат зададени наведнъж.

Така че това е кодът:

int i;
u32 intr = read_interrupt_register();

/* ep0 IN */
if(likely(intr & (1 << 0))){
    handle_ep0_in();
}

/* ep0 OUT */
if(likely(intr & (1 << 16))){
    handle_ep0_out();
}

for(i=1;i<16;++i){
    if(unlikely(intr & (1 << i))){
        handle_ep_in(i);
    }
    if(unlikely(intr & (1 << (i + 16)))){
        handle_ep_out(i);
    }
}

(1 << 0) и (1 << 16) ще бъдат изчислени по време на компилиране, но (1 << i) и (1 << (i + 16)) не. Също така ще има интегрално сравнение и добавяне в цикъла.

Тъй като това е irq манипулатор, работата трябва да се извърши в най-кратки срокове. Това ме кара да мисля дали трябва да го оптимизирам малко.

Възможни начини?

1. Разделете цикъла, изглежда няма значение...

/* ep0 IN */
if(likely(intr & (1 << 0))){
    handle_ep0_in();
}

/* ep0 OUT */
if(likely(intr & (1 << 16))){
    handle_ep0_out();
}

for(i=1;i<16;++i){
    if(unlikely(intr & (1 << i))){
        handle_ep_in(i);
    }
}
for(i=17;i<32;++i){
    if(unlikely(intr & (1 << i))){
        handle_ep_out(i - 16);
    }
}

2. Преместване на intr вместо стойността, с която да се сравнява?

/* ep0 IN */
if(likely(intr & (1 << 0))){
    handle_ep0_in();
}

/* ep0 OUT */
if(likely(intr & (1 << 16))){
    handle_ep0_out();
}

for(i=1;i<16;++i){
    intr >>= 1;
    if(unlikely(intr & 1)){
        handle_ep_in(i);
    }
}
intr >>= 1;
for(i=1;i<16;++i){
    intr >>= 1;
    if(unlikely(intr & 1)){
        handle_ep_out(i);
    }
}

3. Развийте напълно примката (не е показана). Това би направило кода малко объркан.

4. Има ли други по-добри начини?

5. Или компилаторът всъщност ще генерира най-оптимизирания начин?


Редактиране: Търсих начин да кажа на gcc компилатора да развие този конкретен цикъл, но изглежда, че не е възможно според моето търсене...


person Alvin Wong    schedule 13.09.2012    source източник
comment
Имате само 17 елемента, с които да се справите. Ръчно разгънат не е по-объркан от кода в първия ви пример   -  person fork0    schedule 13.09.2012


Отговори (2)


Ако можем да предположим, че броят на зададените битове в intr е малък (както обикновено се случва в маските за прекъсване), можем да оптимизираме малко и да напишем цикъл, който се изпълнява за всеки бит само веднъж:

void handle (int intr)
{
  while (intr)
  {
    // find index of lowest bit set in intr:
    int bit_id = __builtin_ffs(intr)-1;

    // call handler:
    if (bit_id > 16)
      handle_ep_out (bit_id-16);
    else
      handle_ep_in (bit_id);

    // clear that bit
    // (I think there was a bit-hack out there to simplify this step even further)
    intr -= (1<<bit_id);
  }
}

На повечето ARM архитектури __builtin_ffs ще компилира до CLZ инструкция и малко аритметика около нея. Трябва да го прави за всичко друго освен ARM7 и по-стари ядра.

Също така: Когато пишете манипулатори на прекъсвания на вградени устройства, размерът на функцията има значение и за производителността, тъй като инструкциите трябва да бъдат заредени в кодовия кеш. Lean кодът обикновено се изпълнява по-бързо. Малко претоварване е добре, ако запазвате достъп до паметта в памет, която е малко вероятно да бъде в кеша.

person Nils Pipenbrinck    schedule 13.09.2012
comment
Пропуснахте специалните случаи за функциите без аргументи handle_ep0_in и handle_ep0_out, но +1 за ffs - person fork0; 13.09.2012
comment
Също така не знам дали __builtin_ffs е разрешено в ядрото, но те много вероятно имат някакъв заместител за него, ако не е разрешен. - person Nils Pipenbrinck; 13.09.2012
comment
Защо да не е позволено. Ако случайно не е, можете да използвате clz чрез inline asm директно. - person dbrank0; 13.09.2012
comment
@nils-pipenbrinck: Да, ffs, със специфични за arch версии, ако са налични в __ffs. - person fork0; 13.09.2012
comment
@dbrank0: често причината за такива ограничения е библиотеката за поддръжка на компилатора, която не се използва в ядрото. Търсете udivdi3 тук. - person fork0; 13.09.2012
comment
Току-що проверих кода, компилиран с -O3 за cortex-a8.. Изглежда добре. 10 инструкции в тялото на цикъла, включително контрола на цикъла и разклоненията към функциите handle_op_in/out. - person Nils Pipenbrinck; 13.09.2012
comment
Мисля, че моята програма за обработка на прекъсвания не може да бъде наистина малка. Има само един irq за това устройство и има повече от 50 прекъсвания за обработка вътре в него. Показаният по-горе код е само част от тях. - person Alvin Wong; 13.09.2012
comment
Току-що намерено ffs в LXR. Но каква е разликата между ffs(x) и __ffs(x)? #define __ffs(x) (ffs(x) - 1) - person Alvin Wong; 13.09.2012
comment
Оказва се, че е същото, но поради логиката бих избрал intr ^= (1<<bit_id). - person Jens Gustedt; 13.09.2012

Вероятно бих избрал вариант 5. Кодирайте за четливост и оставете безумното ниво на оптимизация -O3 на gcc да направи каквото може.

Виждал съм код, генериран на това ниво, което дори не мога да разбера.

Всяка ръчно изработена оптимизация в C (освен евентуално разгръщане и използване на константи, а не битови смени по време на изпълнение, a la опция 3) е малко вероятно да надмине това, което самият компилатор може да направи.

Мисля, че ще откриете, че разгръщането може да не е толкова объркано, колкото си мислите:

if (  likely(intr & 0x00000001)) handle_ep0_in();
if (  likely(intr & 0x00010000)) handle_ep0_out();

if (unlikely(intr & 0x00000002)) handle_ep_in(1);
if (unlikely(intr & 0x00020000)) handle_ep_out(1);

:

if (unlikely(intr & 0x00008000)) handle_ep_in(15);
if (unlikely(intr & 0x80000000)) handle_ep_out(15);

Всъщност можете да го направите много по-малко по-объркано с макроси (непроверено, но трябва да разберете общата идея):

// Since mask is a constant, "mask << 32" should be too.

# define chkintr (mask, num) \
    if (unlikely(intr & (mask      ))) handle_ep_in  (num); \
    if (unlikely(intr & (mask << 32))) handle_ep_out (num);

// Special case for high probability bit.

if (likely(intr & 0x00000001UL)) handle_ep0_in();
if (likely(intr & 0x00010000UL)) handle_ep0_out();

chkintr (0x0002UL,  1);  chkintr (0x0004UL,  2);  chkintr (0x0008UL,  3);
chkintr (0x0010UL,  4);  chkintr (0x0020UL,  5);  chkintr (0x0040UL,  6);
chkintr (0x0080UL,  7);  chkintr (0x0100UL,  8);  chkintr (0x0200UL,  9);
chkintr (0x0400UL, 10);  chkintr (0x0800UL, 11);  chkintr (0x1000UL, 12);
chkintr (0x2000UL, 13);  chkintr (0x4000UL, 14);  chkintr (0x8000UL, 15);

Единствената стъпка нагоре оттук нататък е асемблерният език за ръчно кодиране и все още има добра възможност gcc да успее да ви надмине :-)

person paxdiablo    schedule 13.09.2012
comment
Е, може и да съм прекалено притеснен, защото наистина няма да отнеме твърде много време, но все пак не искам да лъжа себе си :P. Също така мисля, че ядрото на Linux по подразбиране се изгражда с ниво на оптимизация 2. - person Alvin Wong; 13.09.2012
comment
Ниво 2 може да е достатъчно. Разбира се, в ядрото вече има неща с доста строги изисквания за времето, така че може би -O2 е достатъчно. -O3 вероятно ще направи отстраняването на грешки в ядрото истински кошмар. Краен съвет, не се тревожете за това, докато не разберете, че е проблем. Както примката, така и разгънатата форма вероятно ще бъдат повече от достатъчно бързи. - person paxdiablo; 13.09.2012
comment
добре, да видим дали ще има още отговори. - person Alvin Wong; 13.09.2012