- Good afternoon, I'm in an interview for a senior developer position.
- Hello, let's start with a little test while I'm looking at your CV. Write a program that would display numbers from 1 to, say, a billion, moreover, if the number is a multiple of three, then Fizz is displayed instead of the number, if it is a multiple of five, then Buzz, and if it is a multiple of five, then FizzBuzz.
Seriously, FizzBuzz ? Problem for elementary school, for a senior 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
’.
:
|
|
|
|
||||
() |
|
|
() |
|
|
|
|
|
41.429 |
1x |
- |
39.650 |
1x |
- |
|
22.546 |
1.83x |
1.83x |
20.151 |
1.97x |
1.97x |
|
12.563 |
3.30x |
1.80x |
8.771 |
4.52x |
2.30x |
- — - 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 , .
|
|
() |
|
|
|
|
39.650 |
1x |
- |
|
20.151 |
1.97x |
1.97x |
|
8.771 |
4.52x |
2.30x |
|
4.490 |
8.83x |
1.95x |
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, .
, :
|
|
() |
|
|
|
|
39.650 |
1x |
- |
|
20.151 |
1.97x |
1.97x |
|
8.771 |
4.52x |
2.30x |
|
4.490 |
8.83x |
1.95x |
|
|
1.748 |
22.68x |
2.57x |
- , 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
All code variants produce the same result when the output is directed to a file, that is, they work correctly. The code is available in this repo .