개발자라면 피할 수 없는 성능 고민#
개발을 할때 가끔 성능에 대해 고민할때가 가끔 있습니다.
예를 들면 미묘한 차이지만 for~in 을 쓸지, index를 이용하여 loop를 할지.. 가끔 이런 고민에 빠집니다.
아니면 LinkedHashSet을 쓰는게 좋을지, HashSet을 쓰는게 좋을지도 있겠네요.
결과적으로는 제공하는 메서드들은 비슷할텐데 말이죠.?
오늘은 다트에서 제공하는 성능 프로파일러를 사용해서 각 유사 반복문들을 비교하며 성능측정을 해보려고 해요.
또한 어떤 컬렉션이 좀더 성능에 기여할 수 있는 컬렉션인지 찾아보려고 해요.
IDA를 이용하여 직접 실시간으로 셈블리어로 확인하여 좀더 좋은 지표가 될 수 있도록 하려 했지만.. 컨버터정도로 사용해서 지표를 확인해보려고 해요.
IDA를 사용해서 어셈블리어로 확인하다가 머리에 쥐가 나버렸습니다..
일단, 시간복잡도#
개발 하시면서 시간 복잡도는 많이 접해보셧을겁니다. 아래와 같은 그래프도 말이죠.
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)
- 위의 수식의 나열은 오른쪽으로 갈수록 시간복잡도가 큰 알고리즘입니다.
- N값이 작을때는 알고리즘 사이에 큰 차이가 없지만 n값이 커지면 커질수록 복잡한 알고리즘은 수행시간이 급격히 길어집니다.
- X축은 데이터의 양을 나타내며, Y축은 연산되는 단계의 개수 즉 소요시간 이라고 보면됩니다.
위의 그래프에 따라서 O(1)는 데이터의 개수가 많아도 연산되는 개수가 일정하게 처리가 되는 반면, O(n!)은 데이터의 개수가 많아지면 많아질수록 연산단계가 급수적으로 늘어나는 그래프를 볼 수 있습니다.
그래서, 어떤 Collection 이 시간복잡도면에서 빠를까?#
우리가 Dart 언어에서 제공하는 Collection들은 다음과 같습니다.
각 참조하는 방법에 따라서 좀 시간 복잡도가 다르게 측정이 됬습니다. 여기서 최고 느린 복잡성을 가진 구조는 SplayTreeMap으로 O(log N)을 가지고 있습니다.
조금 특이한 부분은 List의 Lookup부분이 조금 특이해 보이네요. List에 접근하는 방법에 따라서 복잡도가 달라지는 형태를 나타내고 있습니다. 위의 표에 따르면 value보단 Index로 접근하는것이 빠르겠습니다.
생각보다 각 컬렉션의 방법에따라서 크게 차이가 나지 않기때문에, 생각보다 금방 끝나버렸네요.
개발할때 크게 상관하며 개발하지 않아도 될거 같은 지표로 보여집니다.
배열의 순회 성능#
배열의 순회하는 방법에는 다양한 반복문을 사용하여 순회를 할 수 있습니다.
index를 사용하여 for문을 사용하는방법, for~in 을 사용하는 방법등. 여러 방법이 있습니다.
우리는 각 순회방법을 가지고 어떤 반복문이 좀더 빠르게 도는지 성능 측정을 해보려합니다.
측정 공통조건#
- 0 ~ 999,999가 담긴 list의 배열을 1,000,000번 접근하여 모두 값을 더하는 성능 측정 방식
- 리스트와 변수의 할당은 측정전 모두 메모리에 로딩된 상태에서 진행되며 각 측정은 반복문의 형태만 바뀌며 격리수준으로 측정된 타임라인의 Duration의 값을 3번 측정하여 평균치를 환산합니다.
- 모든 측정값은 ms단위입니다.
while ~#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| import 'dart:developer';
void main() {
print("Begin start");
List<int> filledList = List<int>.generate(1000000, (index) => index);
int sumResult = 0;
int index = 0;
Timeline.startSync('interesting function');
while (index < 1000000) {
sumResult += filledList[index];
index++;
}
Timeline.finishSync();
print("Finish ::::::: $sumResult");
}
|
1차. 13.381ms
2차. 14.147ms
3차. 14.499ms
(13.381 + 14.147 + 14.499) / 3 = 14.009ms
Index For loop#
1
2
3
4
5
6
7
8
9
10
11
12
13
| import 'dart:developer';
void main() {
print("Begin start");
List<int> filledList = List<int>.generate(1000000, (index) => index);
int sumResult = 0;
Timeline.startSync('interesting function');
for (int i = 0; i < 1000000; i++) {
sumResult += filledList[i];
}
Timeline.finishSync();
print("Finish ::::::: $sumResult");
}
|
1차. 14.836ms
2차. 14.309ms
3차. 14.719ms
(14.836 + 14.309 + 14.719) / 3 = 14.621ms
For ~ in#
1
2
3
4
5
6
7
8
9
10
11
12
13
| import 'dart:developer';
void main() {
print("Begin start");
List<int> filledList = List<int>.generate(1000000, (index) => index);
int sumResult = 0;
Timeline.startSync('interesting function');
for (int i in filledList) {
sumResult += i;
}
Timeline.finishSync();
print("Finish ::::::: $sumResult");
}
|
1차. 18.851ms
2차. 17.700ms
3차. 17.967ms
(18.851 + 17.700 + 17.967) / 3 = 18.173ms
Loop 평균 결과#
- while 문: 14.009ms
- for 문 (인덱스 사용): 14.621ms
- for-in 문: 18.173ms
1
2
3
4
5
6
7
| 반복문 성능 비교 (ms)
for-in |████████████████████ 18.173
for |███████████████ 14.621
while |██████████████ 14.009
0 5 10 15 20
|
이 그래프를 통해 다음과 같은 점을 쉽게 확인할 수 있습니다:
- while 문이 가장 빠른 성능을 보입니다.
- for 문은 while 문보다 약간 느리지만, 큰 차이는 없습니다.
- for~in 문은 다른 두 방식에 비해 눈에 띄게 느린 성능을 보입니다.
이러한 측정을 통하여 반복문 선택 시 성능 차이를 고려할 수 있습니다. 하지만 실제 코드에서는 가독성과 유지보수성도 중요한 요소이므로, 상황에 따라 적절한 반복문을 선택하는 것이 좋을것으로 보여집니다.
아마 for-in 이 좀더 느린 이유는 위의 시간복잡도에서 언급했던 부분과 같이 List를 Value로 접근해서 좀더 느린 결과를 도출해내지 않을까라는 생각이듭니다.
if문 vs switch문#
switch ~ case 문
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
import 'dart:developer';
void main() {
print("Begin start");
int sumResult = 0;
int index = 0;
Timeline.startSync('interesting function');
while (index < 1000000) {
switch (index) {
case 5:
sumResult += index;
break;
case 1003:
sumResult += index;
break;
default:
sumResult -= index;
break;
}
index++;
}
Timeline.finishSync();
print("Finish ::::::: $sumResult");
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| section .data
start_msg db "Begin start", 0
finish_msg db "Finish ::::::: ", 0
sumResult dq 0
index dq 0
timeline_start db "interesting function", 0
section .text
global _start
_start:
; Print start message
mov rax, 1 ; syscall: write
mov rdi, 1 ; file descriptor: stdout
mov rsi, start_msg ; message to write
mov rdx, 12 ; message length
syscall
; Start timeline
call Timeline_startSync
; Initialize variables
mov rbx, 0 ; index = 0
mov rdi, 0 ; sumResult = 0
.loop:
cmp rbx, 1000000 ; while (index < 1000000)
jge .end_loop ; if index >= 1000000, exit loop
; Switch case logic
cmp rbx, 5
je .case_5
cmp rbx, 1003
je .case_1003
.default_case:
sub rdi, rbx ; sumResult -= index
jmp .next_index
.case_5:
add rdi, rbx ; sumResult += index
jmp .next_index
.case_1003:
add rdi, rbx ; sumResult += index
jmp .next_index
.next_index:
inc rbx ; index++
jmp .loop ; repeat loop
.end_loop:
; Finish timeline
call Timeline_finishSync
; Print finish message
mov rax, 1 ; syscall: write
mov rdi, 1 ; file descriptor: stdout
mov rsi, finish_msg ; message to write
mov rdx, 20 ; message length
syscall
; Print sumResult
; (Assuming a function to convert integer to string and print it exists)
; Exit program
mov rax, 60 ; syscall: exit
xor rdi, rdi ; exit code 0
syscall
|
if ~ else if ~ else
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| import 'dart:developer';
void main() {
print("Begin start");
int sumResult = 0;
int index = 0;
Timeline.startSync('interesting function');
while (index < 1000000) {
if (index == 5) {
sumResult += index;
} else if (index == 1003) {
sumResult += index;
} else {
sumResult -= index;
}
index++;
}
Timeline.finishSync();
print("Finish ::::::: $sumResult");
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| section .data
start_msg db "Begin start", 0
finish_msg db "Finish ::::::: ", 0
sumResult dq 0
index dq 0
timeline_start db "interesting function", 0
section .text
global _start
_start:
; Print start message
mov rax, 1 ; syscall: write
mov rdi, 1 ; file descriptor: stdout
mov rsi, start_msg ; message to write
mov rdx, 12 ; message length
syscall
; Initialize variables
mov rbx, 0 ; sumResult = 0
mov rcx, 0 ; index = 0
; Start timeline
call Timeline_startSync
.loop:
cmp rcx, 1000000 ; while (index < 1000000)
jge .end_loop
cmp rcx, 5 ; if (index == 5)
je .add_five
cmp rcx, 1003 ; else if (index == 1003)
je .add_one_thousand_three
; else
sub rbx, rcx ; sumResult -= index
jmp .continue
.add_five:
add rbx, rcx ; sumResult += index
jmp .continue
.add_one_thousand_three:
add rbx, rcx ; sumResult += index
.continue:
inc rcx ; index++
jmp .loop
.end_loop:
; Finish timeline
; (Assuming a function to finish timeline exists)
call Timeline_finishSync
; Print finish message
mov rax, 1 ; syscall: write
mov rdi, 1 ; file descriptor: stdout
mov rsi, finish_msg ; message to write
mov rdx, 18 ; message length
syscall
; Print sumResult
; (Assuming a function to convert and print integer exists)
mov rdi, rbx ; pass sumResult to print function
call print_integer
; Exit program
mov rax, 60 ; syscall: exit
xor rdi, rdi ; status: 0
syscall
|
위의 어셈블리 코드를 살펴보면 각 case가 테이블화가 되어있는정도로 차이가 났습니다.
다른 컴파일러에서는 Switch가 미세하게 성능의 이점이 있다고 이야기하나, Dart에서는 크게 차이가 없는것으로 보여집니다.
따라서 2 - 3 줄정도 되는 구문인경우 if문보다는 switch를 이용하여 풀면 좀더 가독성 있는 코드가 될것으로 보여집니다.
Reference & Tools
Dart Decompiler Obstacles and the Impact on Flutter | Guardsquare
https://github.com/Guardsquare/flutter-re-demo
Flutter Hackers: Uncovering the Dev’s Myopia (Part 2)
Debug Flutter apps from code
Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell