System.out.print

알고리즘 문제를 풀이하면서 시간초과가 발생하는 경우가 있다. 그런 경우에는 풀이를 위한 알고리즘 선택이 잘못된 경우도 있지만 출력에서 시간이 오래걸리는 경우도 있다.

백준 1406번 에디터 문제를 풀면서 생겼던 문제점과 이를 해결하는 과정을 기록해보았다.

문제의 내용은 링크를 통해 확인하고 내용에 대해서는 깊이 있게 작성하지 않겠다.
문제 : https://www.acmicpc.net/problem/1406

이 문제에서 시간초과가 발생하는 이유는 최대 출력이 100,000 글자인데 이를 하나 하나 출력을 하다보니 최대 100,000번 출력을 해야하므로 시간초과가 발생하였다.

System.out.print 성능

그렇다면 근본적인 이유로 System.out.print가 느린이유는 무엇인지 궁금하여 학습을 해보았다. 먼저 System.out.print에 대해서 깊이 있게 탐구를 하였다.

System 클래스의 구조는 다음과 같다. 이 외에 아주 많은 코드가 있지만 오늘 주제에 맞춰 구조를 가져왔다. 간단히 살펴보면 System 클래스에 out이라는 PrintStream타입의 static 필드가 있는 구조 였다.

package java.lang;

public final class System {

	public static final PrintStream out = null;
    ...
}

이 구조로만 보았을 때에는 성능에 대해 파악할 수 없다. 그래서 PrintStream 내부에 print 메소드를 확인해보기로 하였다.

package java.io;

public class PrintStream extends FilterOutputStream implements Appendable, Closeable {

	public void print(boolean b) {
        write(String.valueOf(b));
    }
    
    public void print(char c) {
        write(String.valueOf(c));
    }
    ...
    
    private void write(String s) {
        try {
            synchronized (this) {
                ensureOpen();
                textOut.write(s);
                textOut.flushBuffer();
                charOut.flushBuffer();
                if (autoFlush && (s.indexOf('\n') >= 0))
                    out.flush();
            }
        }
        catch (InterruptedIOException x) {
            Thread.currentThread().interrupt();
        }
        catch (IOException x) {
            trouble = true;
        }
    }
}

print 함수를 확인하니 이유를 알게되었다. print 함수에 들어가는 파라미터를 전부 String 타입으로 변환하는 과정이 있었고, 이를 write 함수에 매개변수로 넘겨주게 된다. 그리고 write에 synchronized 키워드를 통해 멀티스레드 환경에서 안전성을 보장하고 있다.

타입을 변환하는 과정에 매번 출력물을 String으로 생성하는 과정에서 성능이 떨어진거 같다.

그렇다면 이를 해결하기 위해서 출력 성능을 높일 수 있는 것이 무엇이 있을까 찾아보게되었다.

BufferedWriter

package java.io;

public abstract class Writer implements Appendable, Closeable, Flushable {
	private char[] writeBuffer;
    private static final int WRITE_BUFFER_SIZE = 1024;
    
    public void write(String str) throws IOException {
        write(str, 0, str.length());
    }
    
    public void write(String str, int off, int len) throws IOException {
        synchronized (lock) {
            char cbuf[];
            if (len <= WRITE_BUFFER_SIZE) {
                if (writeBuffer == null) {
                    writeBuffer = new char[WRITE_BUFFER_SIZE];
                }
                cbuf = writeBuffer;
            } else {    
                cbuf = new char[len];
            }
            str.getChars(off, (off + len), cbuf, 0);
            write(cbuf, 0, len);
        }
    }
    ...
}

System.out.print() 보다 성능이 좋은 BufferedWriter에 대해 탐색해보았다. BufferedWriter경우에는 String과 달리 final이 붙지 않은 char 타입의 배열을 통해 String을 관리하고 출력하는 형태를 보이고 있다. 그리고 이 또한 synchronized 키워드를 통해 멀티스레드 환경에서 안전성을 보장하고 있다.

System.out.print()와 달리 문자열을 새로 생성하거나 하지 않기 때문에 속도면에서 더 성능이 좋은 것 같다.

Stringbuilder

package java.lang;

public final class StringBuilder
    extends AbstractStringBuilder
    implements java.io.Serializable, Comparable<StringBuilder>, CharSequence
{
	//상속 클래스 AbstractStringBuilder 변수
	byte[] value;

	public StringBuilder append(String str) {
        super.append(str);
        return this;
    }
    
    //상속 클래스 AbstractStringBuilder 함수
    AbstractStringBuilder append(AbstractStringBuilder asb) {
        if (asb == null) {
            return appendNull();
        }
        int len = asb.length();
        ensureCapacityInternal(count + len);
        if (getCoder() != asb.getCoder()) {
            inflate();
        }
        asb.getBytes(value, count, coder);
        count += len;
        return this;
    }
    ...
}

Stringbuilder도 얼핏보기엔 append를 통해 계속 새로운 String을 생성하니 System.out.print랑 차이가 없지 않은가? 라고 생각했다. 하지만 상속 받은 AbstractStringBuilder 클래스에 들어가보니 BufferedWriter와 같이 final이 붙지 않은 byte 타입의 배열을 통해 데이터를 관리하고 있었다. 그러므로 System.out.print 보다 더 성능이 좋은 것이다.

다만 멀티스레드 환경에서 안전성을 보장해주지는 않는다는 점이 BufferedWriter와 다르다.