[소현수] perf 성능분석보고서

[SoHyunsu]

[SoHyunsu]

1. 5가지의 서로다른 sudoku 소스를 각각 실행해본다.

1.1 fax

• 컴파일

gcc -O3 -std=c99 -o sudoku sudoku.c

• 실행

time ./sudoku 115 123 157 216 241 259 265 329 338 386 418 456 493 514 548 563 591 617 652 696 726 772 788 844 851 869 895 958 987 999

• 실행 결과

+---------+---------+---------+
| 5  3  4 | 6  7  8 | 9  1  2 |
| 6  7  2 | 1  9  5 | 3  4  8 |
| 1  9  8 | 3  4  2 | 5  6  7 |
+---------+---------+---------+
| 8  5  9 | 7  6  1 | 4  2  3 |
| 4  2  6 | 8  5  3 | 7  9  1 |
| 7  1  3 | 9  2  4 | 8  5  6 |
+---------+---------+---------+
| 9  6  1 | 5  3  7 | 2  8  4 |
| 2  8  7 | 4  1  9 | 6  3  5 |
| 3  4  5 | 2  8  6 | 1  7  9 |
+---------+---------+---------+

real    0m0.003s
user    0m0.001s
sys     0m0.002s

• 실행

time ./sudoku 118 233 246 327 359 372 425 467 554 565 577 641 683 731 786 798 838 845 881 929 974

• 실행 결과

+---------+---------+---------+
| 8  1  2 | 7  5  3 | 6  4  9 |
| 9  4  3 | 6  8  2 | 1  7  5 |
| 6  7  5 | 4  9  1 | 2  8  3 |
+---------+---------+---------+
| 1  5  4 | 2  3  7 | 8  9  6 |
| 3  6  9 | 8  4  5 | 7  2  1 |
| 2  8  7 | 1  6  9 | 5  3  4 |
+---------+---------+---------+
| 5  2  1 | 9  7  4 | 3  6  8 |
| 4  3  8 | 5  2  6 | 9  1  7 |
| 7  9  6 | 3  1  8 | 4  5  2 |
+---------+---------+---------+

real    0m0.006s
user    0m0.004s
sys     0m0.001s

• 내용

1. 실행파일은 스도쿠 문제를 3자리 씩 27개를 입력받는다.
2. 구현된 알고르짐으로, 0으로 입력받는 곳의 숫자를 찾는다.
3. time command를 활용해서 real user sys 확인한다.

[SoHyunsu]

1. 5가지의 서로다른 sudoku 소스를 각각 실행해본다.

1.2 imphasing

• 컴파일

make

• 실행

cat sample_easy | ./solver

• 입력

530070000600195000098000060800060003400803001700020006060000280000419005000080079

• 실행 결과

534678912672195348198342567859761423426853791713924856961537284287419635345286179

• 실행

cat sample_worst | ./solver

• 입력

000000000000003085001020000000507000004000100090000000500000073002010000000040009

• 실행 결과

987654321246173985351928746128537694634892157795461832519286473472319568863745219

• 내용

1. 실행파일은 simple_easy와 simple_worst에 있는 문제를 실행한다.
2. 구현된 알고르짐으로, 0으로 입력받는 곳의 숫자를 찾는다.
3. 두 input값 실행한 결과, '0'이 많은 sample_worst의 시간이 오래 걸리는 것을 확인할 수 있다.

[SoHyunsu]

1. 5가지의 서로다른 sudoku 소스를 각각 실행해본다.

1.3 hmgle

• 컴파일

make

• 실행

./sudoku_solver -v hardest_sudoku.txt

• 실행 결과

input sudoku:
+-------+-------+-------+
| 8 0 0 | 0 0 0 | 0 0 0 |
| 0 0 3 | 6 0 0 | 0 0 0 |
| 0 7 0 | 0 9 0 | 2 0 0 |
+-------+-------+-------+
| 0 5 0 | 0 0 7 | 0 0 0 |
| 0 0 0 | 0 4 5 | 7 0 0 |
| 0 0 0 | 1 0 0 | 0 3 0 |
+-------+-------+-------+
| 0 0 1 | 0 0 0 | 0 6 8 |
| 0 0 8 | 5 0 0 | 0 1 0 |
| 0 9 0 | 0 0 0 | 4 0 0 |
+-------+-------+-------+
dlx_search return 60:
+-------+-------+-------+
| 8 1 2 | 7 5 3 | 6 4 9 |
| 9 4 3 | 6 8 2 | 1 7 5 |
| 6 7 5 | 4 9 1 | 2 8 3 |
+-------+-------+-------+
| 1 5 4 | 2 3 7 | 8 9 6 |
| 3 6 9 | 8 4 5 | 7 2 1 |
| 2 8 7 | 1 6 9 | 5 3 4 |
+-------+-------+-------+
| 5 2 1 | 9 7 4 | 3 6 8 |
| 4 3 8 | 5 2 6 | 9 1 7 |
| 7 9 6 | 3 1 8 | 4 5 2 |
+-------+-------+-------+

• 실행

echo "800000000003600000070090200050007000000045700000100030001000068008500010090000400"|./sudoku_solver -v

• 실행 결과

input sudoku:
+-------+-------+-------+
| 8 0 0 | 0 0 0 | 0 0 0 |
| 0 0 3 | 6 0 0 | 0 0 0 |
| 0 7 0 | 0 9 0 | 2 0 0 |
+-------+-------+-------+
| 0 5 0 | 0 0 7 | 0 0 0 |
| 0 0 0 | 0 4 5 | 7 0 0 |
| 0 0 0 | 1 0 0 | 0 3 0 |
+-------+-------+-------+
| 0 0 1 | 0 0 0 | 0 6 8 |
| 0 0 8 | 5 0 0 | 0 1 0 |
| 0 9 0 | 0 0 0 | 4 0 0 |
+-------+-------+-------+
dlx_search return 60:
+-------+-------+-------+
| 8 1 2 | 7 5 3 | 6 4 9 |
| 9 4 3 | 6 8 2 | 1 7 5 |
| 6 7 5 | 4 9 1 | 2 8 3 |
+-------+-------+-------+
| 1 5 4 | 2 3 7 | 8 9 6 |
| 3 6 9 | 8 4 5 | 7 2 1 |
| 2 8 7 | 1 6 9 | 5 3 4 |
+-------+-------+-------+
| 5 2 1 | 9 7 4 | 3 6 8 |
| 4 3 8 | 5 2 6 | 9 1 7 |
| 7 9 6 | 3 1 8 | 4 5 2 |
+-------+-------+-------+

• 내용

1. 실행파일은 *.txt와 echo로 문제를 받아서 실행한다.
2. 구현된 알고르짐으로, 0으로 입력받는 곳의 숫자를 찾는다.

[SoHyunsu]

1. 5가지의 서로다른 sudoku 소스를 각각 실행해본다.

1.4 rg3

• 컴파일

sudo gcc -o sudoku sudoku.c 

• 실행

./sudoku quiz

• 입력

5 3 . . 7 . . . .
6 . . 1 9 5 . . .
. 9 8 . . . . 6 .
8 . . . 6 . . . 3
4 . . 8 . 3 . . 1
7 . . . 2 . . . 6
. 6 . . . . 2 8 .
. . . 4 1 9 . . 5
. . . . 8 . . 7 9

• 실행 결과

5 3 4 6 7 8 9 1 2
 6 7 2 1 9 5 3 4 8
 1 9 8 3 4 2 5 6 7
 8 5 9 7 6 1 4 2 3
 4 2 6 8 5 3 7 9 1
 7 1 3 9 2 4 8 5 6
 9 6 1 5 3 7 2 8 4
 2 8 7 4 1 9 6 3 5
 3 4 5 2 8 6 1 7 9

• 내용

1. 실행파일은 input값이 있는 파일을 받아서 실행한다.
2. 구현된 알고르짐으로, '.'으로 입력받는 곳의 숫자를 찾는다.

[SoHyunsu]

1. 5가지의 서로다른 sudoku 소스를 각각 실행해본다.

1.5 geeksforgeeks

• 컴파일

sudo g++ -o sudoku sudoku.c

• 실행

./sudoku

• 입력

 grid[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0},
                          {5, 2, 0, 0, 0, 0, 0, 0, 0},
                          {0, 8, 7, 0, 0, 0, 0, 3, 1},
                          {0, 0, 3, 0, 1, 0, 0, 8, 0},
                          {9, 0, 0, 8, 6, 3, 0, 0, 5},
                          {0, 5, 0, 0, 9, 0, 6, 0, 0},
                          {1, 3, 0, 0, 0, 0, 2, 5, 0},
                          {0, 0, 0, 0, 0, 0, 0, 7, 4},
                          {0, 0, 5, 2, 0, 6, 3, 0, 0}};

• 실행 결과

 3 1 6 5 7 8 4 9 2
 5 2 9 1 3 4 7 6 8
 4 8 7 6 2 9 5 3 1
 2 6 3 4 1 5 9 8 7
 9 7 4 8 6 3 1 2 5
 8 5 1 7 9 2 6 4 3
 1 3 8 9 4 7 2 5 6
 6 9 2 3 5 1 8 7 4
 7 4 5 2 8 6 3 1 9

• 내용

1. 실행파일 내부에 값을 초기화하고 실행한다.
2. 구현된 알고르짐으로, '0'으로 입력받는 곳의 숫자를 찾는다.

[SoHyunsu]

2. perf record, stat를 사용하여 아래 event 뿐만아니라 여러 event로 초점을 바꿔가며 성능분석한다.

1.1 fax

• 실행

time ./sudoku 800 000 000 003 600 000 070 090 200 050 007 000 000 045 700 000 100 030 001 000 068 008 500 010 090 000 400

• 결과

+---------+---------+---------+
| 9  8  7 | 6  5  4 | 3  2  1 |
| 2  4  6 | 1  7  3 | 9  8  5 |
| 3  5  1 | 9  2  8 | 7  4  6 |
+---------+---------+---------+
| 1  2  8 | 5  3  7 | 6  9  4 |
| 6  3  4 | 8  9  2 | 1  5  7 |
| 7  9  5 | 4  6  1 | 8  3  2 |
+---------+---------+---------+
| 5  1  9 | 2  8  6 | 4  7  3 |
| 4  7  2 | 3  1  9 | 5  6  8 |
| 8  6  3 | 7  4  5 | 2  1  9 |
+---------+---------+---------+

real    0m28.665s
user    0m28.620s
sys     0m0.010s

• 실행

 sudo perf stat -e cycles,instructions,branch-instructions,cache-references,cache-misses,branch-misses -a ./sudoku 263 288 295 331 352 445 467 534 571 629 715 787 793 832 851 954 999

• 실행

sudo perf record -g -e cycles,instructions,branch-instructions,cache-references,cache-misses,branch-misses -a ./sudoku 263 288 295 331 352 445 467 534 571 629 715 787 793 832 851 954 999

• 분석

1.1 cycles

1.2 instructions

1.3 branch-instructions

1.4 cache-references

1.5 cache-messes

1.6 branch-misses

[SoHyunsu]

2. perf record, stat를 사용하여 아래 event 뿐만아니라 여러 event로 초점을 바꿔가며 성능분석한다.

1.2 imphasing

• 입력

800 000 000
003 600 000
070 090 200
050 007 000
000 045 700
000 100 030
001 000 068
008 500 010
090 000 400

• 실행

time cat test| ./solver

• 결과

812 753 649
943 682 175
675 491 283
154 237 896 
369 845 721
287 169 534
521 974 368
438 526 917
796 318 452

real    0m0.601s
user    0m0.580s
sys     0m0.010s

• 실행

sudo perf stat -e cycles,instructions,branch-instructions,cache-references,cache-misses,branch-misses -a cat test | ./solver

• 실행

sudo perf record -g -e cycles,instructions,branch-instructions,cache-references,cache-misses,branch-misses -a ./sudoku 263 288 295 331 352 445 467 534 571 629 715 787 793 832 851 954 999

• 분석

1.1 cycles

1.2 instructions

1.3 branch-instructions

1.4 cache-references

1.5 cache-messes

1.6 branch-misses