Duff's device or loop unrolling in C with your own hands

Does the following code look like valid C ++ code? If so, what value will it output as a result of its operation?





#include <iostream>

int main() {
  int number = 11;     
  int count  = number / 4;
  int i = 0;
  
  switch (number % 4) {
    case 0: 
      do {
    	  ++i;
    case 3: ++i;
    case 2: ++i;
    case 1: ++i;
      } while (count-- > 0);
  }

  std::cout << i;
}
      
      



At first glance, this code may seem like some kind of mess, in which the switch statement and the do-while loop are simply superimposed on each other. However, from the point of view of the language standard, everything is perfectly legal here.





, , i number , , , 11. "" :





#include <iostream>

int main() {
  int number = 11;
  int i = 0;
  
  while (number-- > 0) {
    ++i;
  }

  std::cout << i;
}
      
      



do-while switch?





Duff's device ( )

1983 Tom Duff, , loop unrolling.



. , . , , number . loop unroling ( ), , , . i. , , — .





. , , . , ? — , . ,





#include <iostream>

int main() {   
  int number = 11;   
  int i = 0;   
  
  while (number-- > 0) {
    ++i;
  }   
  
  std::cout << i; 
}
      
      



, :





int main() {
  int number = 11; //    = 11.
  
  //      4    .
  int count  = number / 4; //    .
  int left   = number % 4; //  ,    " ".
  int i = 0;
  
  //  ""    
  //    .
  while (left-- > 0) {
    i++;
  }

  //     4   .
  while (count-- > 0) {
    i++;
    i++;
    i++;
    i++;
  }  
  
  std::cout << i;
}
      
      



11 , , number / 4 + number % 4 , 5, number 11.





Assembly : jump , . . , :





#include <iostream>

int main() {
  int number = 11; //       11.
  int count = number / 4; //    .
  int i = 0;

  //          
  //           
  //    .
  switch (number % 4) {
    case 0: 
      do {  
        ++i;
    case 3: ++i; // <-  .       
    case 2: ++i; //       ,  
    case 1: ++i; //      (11 % 4 ).
      } while (count-- > 0); 
  }
  
  std::cout << i;
}
      
      



number / 4 , , . , switch "" case break. , , case - , do-while . , case switch, , .





:





send(to, from, count)
// to -  /,   .   
//    .
// from -   ,      'to'
register short *to, *from;
register count;
{
    //       8   
    register n = (count + 7) / 8;
    switch (count % 8) {
    case 0: do { *to = *from++;
    case 7:      *to = *from++;
    case 6:      *to = *from++;
    case 5:      *to = *from++;
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
            } while (--n > 0);
    }
}
      
      



, . , , , , . ?





, . Compiler Explorer' gcc 11.1 x86-64 . , .





:





... 
;      while
; [rbp-4] -   number = 11  
; [rbp-8] -   i = 0  
        jmp     .L2 
.L3:
        add     DWORD PTR [rbp-8], 1    ;  i  
.L2:
        mov     eax, DWORD PTR [rbp-4]  ;    eax  number
        lea     edx, [rax-1]            ;   number 
        mov     DWORD PTR [rbp-4], edx  ;   number-1  
        test    eax, eax                ; ,  number    0
        jg      .L3                     ;   ,    
...
      
      



.L2, , , 11 . , .





...
;    switch
;  [rbp-4]  [rbp-8]    
; [rbp-12] -  count

        mov     eax, DWORD PTR [rbp-4] ;      .L8   
        cdq                            ;     
        shr     edx, 30                ;    
        add     eax, edx               ;     
        and     eax, 3                 ;      .
        sub     eax, edx               
        cmp     eax, 3                 ;       :
        je      .L2                    ;  
        cmp     eax, 3
        jg      .L3				
        cmp     eax, 2
        je      .L4                    ;  
        cmp     eax, 2
        jg      .L3
        test    eax, eax
        je      .L5                    ;  
        cmp     eax, 1
        je      .L6                    ;  
        jmp     .L3                    ; ,        
                                       ;   .
.L8:
        nop
.L5:                                   ;    " ":
        add     DWORD PTR [rbp-8], 1   ;  i++
.L2:
        add     DWORD PTR [rbp-8], 1   ;  i++
.L4:
        add     DWORD PTR [rbp-8], 1   ;  i++
.L6:
        add     DWORD PTR [rbp-8], 1   ;  i++
        mov     eax, DWORD PTR [rbp-4] ;     , 
        lea     edx, [rax-1]           ;    ,  
        mov     DWORD PTR [rbp-4], edx ;   
        test    eax, eax
        jg      .L8
.L3: 
        ;    
...
      
      



, , . , 11 2, .





, , . , . - , "", . , . , 1983 , , , , , .












All Articles