welcome :)

0%

Rust print 매크로 병목현상

작성일 In ,

러스트 print 매크로 사용하는 경우의 성능에 대해서 정리합니다.

문제 발생 시점

러스트로 백준의 하노이 탑 문제를 풀고 있었다. 이미 해당 문제는 파이썬으로 풀었기에 로직 변화 없이 러스트 코드로 컨버팅했다. 하지만 계속 채점률 40%에서 시간 초과 오류가 발생했다. 시간 초과가 발생하는 코드는 아래와 같다.

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
use std::io;

fn main() {
    let mut num = String::new();
    io::stdin().read_line(&mut num).unwrap();
    let n:u32 = num.trim().parse().expect("숫자가 아닙니다.");
    let start:u32 = 1;
    let dest:u32 = 3;

    if 0 < n && n <= 20 {
        count_move(n);
        hanoi(n, start, dest);
    }
    else{
        count_move(n);
    }
}

fn count_move(n: u32) {
    let count = i128::pow(2,n);
    print!("{}\n",count-1);
}

fn hanoi(n: u32, start: u32, dest: u32) {
    if n == 1 {
        print!("{} {}\n",start, dest);
    }
    else {
        hanoi(n-1, start, 6-start-dest);
        print!("{} {}\n",start, dest);
        hanoi(n-1, 6-start-dest, dest);
    }
}

위 코드의 로직이 궁금한 사람은 이 글에서 확인할 수 있다.

원인 분석

처음에는 로직에 문제가 있었나 했지만 파이썬 코드로는 채점 통과하는 것을 확인하니 이 부분은 문제가 아닐 것 같아 배제하고 다른 원인을 찾아보았다.
그러다가 아래와 같은 글을 발견하였다.

아 출력 병목이었습니다.
rust 쓰시는 분들 조심하세요.
println!이나 print! 호출이 100000단위가 넘어가면 무조건 병목 생깁니다.
병목 해결 소스도 같이 올려요~
https://www.acmicpc.net/board/view/43948

위 코드는 원판이 20개 이하라면 이동 과정을 모두 출력하는데, 원판 20개일 때 출력해야 하는 개수는 $2^{20}-1$의 결과인 1048575개이다. 그래서 채점 중간에 시간초과로 결과가 나오는 것 같았다. 그렇다면 러스트는 왜 println!, print!를 일정 이상 사용하면 병목현상이 발생하는 것인가?
이에 대해 reddit에서 관련 내용들을 찾아보았다.

I would guess the explanation is output buffering. By default, Python will buffer multiple lines before writing them to stdout, which Rust does not. Try running the Python script with a -u flag and see what happens.
https://www.reddit.com/r/rust/comments/qiyqlo/fizzbuzz_in_rust_is_slower_than_python/

사실인지는 확실하지 않지만 이를 통해 파이썬에서는 작동이 되고 러스트에서는 안되는 이유를 유추해볼 수 있을 것 같다. 파이썬은 여러 줄을 버퍼링해서 출력하지만 러스트는 매크로가 작동될 때마다 출력한다는 것이다. 당연히 출력이 여러 번 발생하면 rust가 모니터로 출력할 데이터를 전송해야 하기에 더 많은 시간이 소요될 수밖에 없다. 따라서 위와 같은 로직을 구현할 때는 버퍼를 사용하여 출력해야 할 자료들을 메모리에 올려놨다가 한번에 출력하는게 훨씬 빠를 수 있다는 것이다.

코드 분석

아래의 코드는 채점을 통과한 코드이다.

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
use std::io;

fn main() {
    let mut num = String::new();
    io::stdin().read_line(&mut num).unwrap();
    let n:u32 = num.trim().parse().expect("숫자가 아닙니다.");
    count_move(n);

    if n < 21 {
        let mut list = String::new();
        hanoi(n, 1, 3, &mut list);
        print!("{}", list);
    }
}

fn count_move(n: u32) {
    let count = i128::pow(2,n);
    print!("{}\n",count-1);
}

fn hanoi(n: u32, start: u32, dest: u32, list: &mut String) {
    if n == 1 {
        list.push_str(&format!("{} {}\n",start, dest));
        return;
    }
    else {
        hanoi(n-1, start, 6-start-dest, list);
        list.push_str(&format!("{} {}\n",start, dest));
        hanoi(n-1, 6-start-dest, dest, list);
    }
}

에러가 발생한 코드와의 차이점은 재귀함수에 println!, print! 명령어를 없앴다는 것이다.
코드를 자세히 뜯어보면 main()에서 list라는 빈 문자열을 만들고 출력해야 할 문자열을 list에 저장하였다. 그리고 재귀가 끝나면 한번에 출력하였다.

Python과 성능 비교

이제 러스트의 성능을 확인해보기 위해서 동일한 로직으로 작성한 파이썬 코드와 비교해보자.
먼저 위 코드를 백준에서 채점하면 아래와 같다.

rust

다음으로는 파이썬 코드를 채점해보자.
아래 코드는 비교를 위해 사용한 파이썬 코드이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def hanoi_func(n, _from, _to):
    if n == 0: return 0
    if n == 1:
        path.append([_from,_to])
    else:
        hanoi_func(n-1,_from,6-(_from+_to))
        path.append([_from,_to])
        hanoi_func(n-1,6-(_from+_to),_to)
        
def hanoi_num_func(n):
    if n == 0: return 0
    return 2**n -1

n = int(input())

if n < 21:
    print(hanoi_num_func(n))
    path = []
    hanoi_func(n,1,3)
    for a,b in path:
        print(a, end=" ")
        print(b)
else:
    print(hanoi_num_func(n))

백준에서 파이썬 코드로 채점한 결과는 아래와 같다.

python

확실히 똑같은 로직이라도 러스트가 리소스를 덜 사용하는 것을 알 수 있다.

언어 메모리 소요시간
python 122052 KB 1812 ms
rust 20340 KB 120 ms