FizzBuzz Senior

- Guten Tag, ich bin in einem Interview für eine leitende Entwicklerposition.

- Hallo, fangen wir mit einem kleinen Test an, während ich mir Ihren Lebenslauf ansehe. Schreiben Sie ein Programm, das Zahlen von 1 bis beispielsweise einer Milliarde anzeigt. Wenn die Zahl ein Vielfaches von drei ist, wird Fizz anstelle der Zahl angezeigt, wenn es ein Vielfaches von fünf ist, dann Buzz und wenn ja ist ein Vielfaches von fünf, dann FizzBuzz.

Im Ernst, FizzBuzz ? Problem für die Grundschule, für eine leitende Position? Okay.

---

, :

#include <stdio.h>

#define LIMIT 1000000000

int main(void) {
    for (int i = 1; i <= LIMIT; i++) {
        if (0 == i % 3) {
            if (0 == i % 5) {
                printf("FizzBuzz\n");
            } else {
                printf("Fizz\n");
            }
        } else if (0 == i % 5) {
            printf("Buzz\n");
        } else {
            printf("%d\n", i);
        }
    }

    return 0;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

, , , 3 - , , , . , , , , , , 41.5 7.5 .

- , ? - .

- , I/O, 7.5 — , SSD.

- /dev/null



.

- .

:

- — 39.5 ? I/O 2 , — ?

- , . , printf



, printf



’. , , . ...

, , , . , , .

- .

- . , .

- , — 3*5, 15 . :

    for (i = 1; i < LIMIT - 15; i += 15) {
        printf( "%d\n"          // 1
                "%d\n"          // 2
                "Fizz\n"        // 3
                "%d\n"          // 4
                "Buzz\n"        // 5
                "Fizz\n"        // 6
                "%d\n"          // 7
                "%d\n"          // 8
                "Fizz\n"        // 9
                "Buzz\n"        // 10
                "%d\n"          // 11
                "Fizz\n"        // 12
                "%d\n"          // 13
                "%d\n"          // 14
                "FizzBuzz\n",   // 15
                i, i+1, i+3, i+6, i+7, i+10, i+12, i+13);
    }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- 15 15 if



’ , 45 , — branch prediction’, . printf



’ 15 . — , 999999990 ( , 15 ), , , 10 ( ).

.

- ?

- , 22.5 , /dev/null



– 20.2

, , - . … .

- , .

- ? ?

- printf



’ 15 , printf



’ . printf



, - — , , - . printf



, - , :

#define NUM cur += myitoa(num++, cur)
#define FIZZ do { memcpy(cur, "Fizz\n", 5); cur += 5; num++; } while (0)
#define BUZZ do { memcpy(cur, "Buzz\n", 5); cur += 5; num++; } while (0)
#define FIZZBUZZ do { memcpy(cur, "FizzBuzz\n", 9); cur += 9; } while (0)

void print(int num) {
    static char wrkbuf[CHUNK_SIZE];

    char *cur = wrkbuf;
    NUM;
    NUM;
    FIZZ;
    NUM;
    BUZZ;
    FIZZ;
    NUM;
    NUM;
    FIZZ;
    BUZZ;
    NUM;
    FIZZ;
    NUM;
    NUM;
    FIZZBUZZ;
    fwrite(wrkbuf, cur - wrkbuf, 1, stdout);
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- , , itoa



, , , , , - , . , , print(i)



printf



’.

.

:

- — - I/O, , I/O.

, .

- 4 .

. , , , . .

- , .

- ?

- . , . , , , , print(150000001)



print(150000016)



:

150000001\n150000002\nFizz\n150000004\nBuzz\nFizz\n150000007\n150000008\nFizz\nBuzz\n150000011\nFizz\n150000013\n150000014\nFizzBuzz\n
150000016\n150000017\nFizz\n150000019\nBuzz\nFizz\n150000022\n150000023\nFizz\nBuzz\n150000026\nFizz\n150000028\n150000029\nFizzBuzz\n
       ^^         ^^               ^^                     ^^         ^^                     ^^               ^^         ^^ 
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- 16 , . . , , , — , , . , , , , — — !

, , . , .

Intel’ 16- . 10-, 16, . , 16- — SSE , AVX-512 , 4- .

:

unsigned int diff = 0xFFFF & ~_mm_movemask_epi8(_mm_cmpeq_epi8(
                                  _mm_load_si128((__m128i const *)prev_first_number),
                                  _mm_load_si128((__m128i const *)last_number)));
unsigned int diff_pos = 16 - _tzcnt_u32(diff);   // number of changed digits
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

flags



/proc/cpuinfo



– SSE2 ( Pentium 4) BMI1 ( Haswell’) CPU , .

, , /dev/null



:

2 ! 9. , 10 .

- , . -.

.

- , , , - , . ! - !

, , - , - , , . , !

- , , , :

for (int j = 0; j < THREAD_COUNT; j++) {
        thread_pool[j].start_num = i;
        thread_pool[j].count = NUMS_PER_THREAD;
        thread_pool[j].buf = malloc(BUFFER_SIZE);
        pthread_create(&thread_pool[j].id, NULL, worker, (void *)&thread_pool[j]);
        i += NUMS_PER_THREAD;
    }
    int active_threads = THREAD_COUNT;
    int max = LIMIT / 15 * 15;
    for (int j = 0; active_threads; j = (j+1) % THREAD_COUNT) {
        pthread_join(thread_pool[j].id, NULL);
        fwrite(thread_pool[j].buf, thread_pool[j].buflen, 1, stdout);
        if (max - i > NUMS_PER_THREAD) {
            thread_pool[j].start_num = i;
            pthread_create(&thread_pool[j].id, NULL, worker, (void *)&thread_pool[j]);
            i += NUMS_PER_THREAD;
        } else if (max > i) {
            thread_pool[j].start_num = i;
            thread_pool[j].count = max - i + 1;
            pthread_create(&thread_pool[j].id, NULL, worker, (void *)&thread_pool[j]);
            i += max - i + 1;
        } else {
            free(thread_pool[j].buf);
            active_threads--;
        }
    } 
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- , , , , 4 . , , — , , , .

, 3 — , 15, .

.

, :

- , 22 . — , , . ?

, . , - , . , ? , .

. - .

---

Dell Latitude 7480 i7-7600U 2.8 Ghz, 16 Gb , SSD OpenSUSE Leap 15.1 kernel’ 4.12.14, 10 , . -O3 -march=native -pthread

Alle Codevarianten führen zum gleichen Ergebnis, wenn die Ausgabe an eine Datei gerichtet ist, dh sie funktionieren ordnungsgemäß. Der Code ist in diesem Repo verfügbar .