23년 11월 1일(수요일) - 23번째 TIL : String.repeat vs StringBuilder.append 속도 차이

 

문제

String.repeat 은 왜 빠르고 StringBuilder.append 는 왜 느린가

 

 

오늘 ㅈㅎ님에게 코드 리뷰를 부탁받아서 보던 중에 인텔리제이의 요상한 추천을 받게 된다. 

public String getBar(int len) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < len; i++) {
        sb.append("-");
    }
    return sb.toString();
}

 

String.repeat()으로 바꿀 수 있다고 추천하는거다. 바꾼 코드는 다음과 같다. 

public String getBar(int len) {
    return "-".repeat(len);
}

 

 

문득, 둘 사이의 성능차이가 어느정도 날지가 궁금해졌다. 그래서 다음과 같이 테스트를 구상해봤다. 

public class StringTest {

	static final int 십억 = 1_000_000_000;
	static final int 십오억 = 1_500_000_000;

	public static void main(String[] args) {
		checkTime("스트링빌더", 십억, getBarWithStringBuilder);
		checkTime("리핏", 십억, getBarWithRepeat);
	}

	static Function<Integer, String> getBarWithRepeat = (len) -> "-".repeat(len);

	static Function<Integer, String> getBarWithStringBuilder = (len) -> {
		StringBuilder sb = new StringBuilder(); // 이후 십오억으로 사이즈를 늘려서 재실험함
		for (int i = 0; i < len; i++) {
			sb.append("-");
		}
		return sb.toString();
	};

	static void checkTime(String title, int count, Function<Integer, String> func) {
		long start = System.currentTimeMillis();
		func.apply(count);
		long end = System.currentTimeMillis();
		System.out.println(title + " : " + (end - start));
	}
}

 

checkTime 함수는 테스트명, 반복  연산할 횟수, 연산할 함수를 받아 걸린 시간을 측정한다. 

 

getBarWithRepeat은 repeat 이용하는 문자열 연산 함수, getBarWithStringBuilder는 StringBuilder를 이용하는 문자연 연산 함수다. 

 

10억번 동안 문자열을 더하는 테스트를 5번 해보니 결과는 다음과 같았다. 

스트링빌더 : 2564
리핏 : 61

스트링빌더 : 2847
리핏 : 63

스트링빌더 : 2240
리핏 : 61

스트링빌더 : 2334
리핏 : 72

스트링빌더 : 2392
리핏 : 65

둘 사이가 약 40배 정도 차이가 났다. 

 

 

StringBuilder의 기본 사이즈를 15억으로 충분히 넓혀주기 위해 다음과 같이 코드를 고치고, 

static Function<Integer, String> getBarWithStringBuilder = (len) -> {
    StringBuilder sb = new StringBuilder(십오억);
    for (int i = 0; i < len; i++) {
        sb.append("-");
    }
    return sb.toString();
};

 

다시 테스트를 해보면 다음과 같다. 

스트링빌더 : 1151
리핏 : 153

스트링빌더 : 1362
리핏 : 139

스트링빌더 : 1224
리핏 : 158

스트링빌더 : 1074
리핏 : 183

스트링빌더 : 903
리핏 : 279

 StringBuilder 의 사이즈를 늘리니 걸린 시간이 1/2~1/3까지도 줄긴 했지만 여전히 repeat과 4~12배는 차이가 난다. 

그리고 repeat은 왜 갑자기 오래 걸리지.. 이건 모르겠다. 

 

---

가설

 

일단 가설을 세워봤는데, 

1. 얼마나 반복될 지 알고 있어서 그만큼의 배열을 마련해두고, 배열을 돌며 문자열을 삽입하는거랑 (repeat)
2. 반복만큼 append를 호출하는 시간 + 삽입해도 내부 배열이 안 넘치는지 체크 + 문자열 삽입 (append)

 

정도의 차이인데 이정도로 시간 차이가 큰건 원래 이런건지, 아니면 다른 이유가 있는지 궁금해서 내부를 봐밨다. 

 

String.reapeat

먼저 repeat 함수의 전체 코드다. 다 볼 필요는 없고 밑밑 코드만 따로 떼어뒀으니 그거 보면 된다. 

public String repeat(int count) {
    if (count < 0) {
        throw new IllegalArgumentException("count is negative: " + count);
    }
    if (count == 1) {
        return this;
    }
    final int len = value.length;
    if (len == 0 || count == 0) {
        return "";
    }
    if (Integer.MAX_VALUE / count < len) {
        throw new OutOfMemoryError("Required length exceeds implementation limit");
    }
    if (len == 1) {
        final byte[] single = new byte[count];
        Arrays.fill(single, value[0]);
        return new String(single, coder);
    }
    final int limit = len * count;
    final byte[] multiple = new byte[limit];
    System.arraycopy(value, 0, multiple, 0, len);
    int copied = len;
    for (; copied < limit - copied; copied <<= 1) {
        System.arraycopy(multiple, 0, multiple, copied, copied);
    }
    System.arraycopy(multiple, 0, multiple, copied, limit - copied);
    return new String(multiple, coder);
}

우리는 "-" 문자열을 10억번 반복하니까 len == 1 이고, count 는 10억이어서 중간의 if (len == 1) {...} 부분만 다시 보자면, 

if (len == 1) {
    final byte[] single = new byte[count];
    Arrays.fill(single, value[0]);
    return new String(single, coder);
}

다음과 같다. 즉, 10억 길이의 배열을 만든 후, "-" 를 쭉 채워준 후, 다시 문자열로 만들어서 리턴하는 간단한 로직이다. 당연히 빠를 거라고 생각했고, 실제로도 빨랐다. 

 

---

StringBuilder.append

 

다음은 StringBuilder 부분이다. 

일단 생성자에 정수를 넣으면 정수의 2배( StringUTF16의 마지막 줄의 쉬프트 연산 << 1 는 이진수의 자릿수를 하나 올리므로 2배가 된다) 만큼의 배열이 생성된다.  엥 근데 왜 StringUTF16.newBytesFor 에서 MAX_LENGTH 가 약 10.7억인데 15억을 넣어도 예외가 발생 안 하지...??

 

 

String의 내부 저장 방식

 

String 내부에서는 char(2byte크기)이 아닌 byte(1byte크기) 배열로 저장이 되고, 1byte 로 저장될 수 있는지(LATIN1)과 2byte로 저장해야하는지(UTF16)를 coder 에 0과 1로 저장해둔다. 그래서 "-" 는 아스키코드로 1바이트로 표현할 수 있으므로 위에선 StringUTF16까지 갈  필요가 없었던 것. 

@Native static final byte LATIN1 = 0;
@Native static final byte UTF16  = 1;

실제로 영어 "abcde" 의 경우 byte[5]와 coder 0 이며, 

한글인 "한글" 의 경우 byte[4] 로 글자당 2byte를 차지하고 coder 는 1이다. 

영어와 한글이 섞인 경우는 (하나라도 1byte로 표시 못 하는 경우) 전부 2byte를 차지하여 byte[8], coder = 1 인걸 볼 수 있다. 

 

 

---

다시 돌아와서 append 메서드를 봐보면, 

public AbstractStringBuilder append(String str) {
    if (str == null) {
        return appendNull();
    }
    int len = str.length();
    ensureCapacityInternal(count + len);
    putStringAt(count, str);
    count += len;
    return this;
}

 

일단 if문은 null은 아니니 패스하고, len 도 "-" 이니 1이 될거고, ensureCapacityInternal 과 putStringAt 메서드를 중점적으로 보자면, 

private void ensureCapacityInternal(int minimumCapacity) {
    // overflow-conscious code
    int oldCapacity = value.length >> coder;
    if (minimumCapacity - oldCapacity > 0) {
        value = Arrays.copyOf(value,
                newCapacity(minimumCapacity) << coder);
    }
}

 

먼저 ensureCapacityInternal 의 매개변수는 count + len 인데, count는 현재까지 채워진 문자열 수 이다. 

 

즉 len 은 1이니까 반복문을 돌릴 때마다 1, 2, 3, ...., 10억 을 매개변수로 호출이 되게 된다. 

하지만 oldCapacity 15억이므로(위에서 LATIN1은 0이었고, coder = LATIN1 이므로 >> 0 은 값변화가 없다), if문의 조건을 만족하지 못해 바로 리턴된다. 

 

다음으로 putStringAt 메서드를 보면, 

private void putStringAt(int index, String str) {
    putStringAt(index, str, 0, str.length());
}

private void putStringAt(int index, String str, int off, int end) {
    if (getCoder() != str.coder()) {
        inflate();
    }
    str.getBytes(value, off, index, coder, end - off);
}

첫 번째 putStringAt이 실행되고, 매개변수로 index 는 count인 현재까지 채워진 문자열 수, str은 "-" 이다.

 

두 번째 putStringAt 메서드 내부에서 getCoder()는 StringBuilder의 요소의 coder를 가져오는 함수로, "-" 만 저장해왔으므로 getCoder()는 0 (LATIN1), str.coder()는 append로 넣는 문자열의 coder 를 가져오는 메서드로, 역시 새로 "-"를 저장하니 coder 는 0으로 같아서, str.getBytes 메서드를 실행하게 된다. 

void getBytes(byte[] dst, int srcPos, int dstBegin, byte coder, int length) {
    if (coder() == coder) {
        System.arraycopy(value, srcPos << coder, dst, dstBegin << coder, length << coder);
    } else {    // this.coder == LATIN && coder == UTF16
        StringLatin1.inflate(value, srcPos, dst, dstBegin, length);
    }
}

 

매개변수로 오는 값들을 보자면 

dst 는 지금껏 저장해온 "-" 배열,  srcPos = 0, dstBegin 은 현재까지 채워진 문자열 수(= 새로 "-"가 추가될 인덱스) , coder는 LATIN1 이니 0, length는 "-"의 길이인 1이다. 

 

if 문의 조건을 만족하므로, System.arraycopy 부분이 실행되는데, 이 메서드는 배열은 원본배열의 srcPos 번째 요소부터 length 개만큼 dest 배열에 붙여넣는 메서드다. 밑의 예시를 보면 감이 잡힌다. 

int[] src = {1, 2, 3, 4, 5};
int[] dst = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
System.arraycopy(src, 2, dst, 5, 3); // src의 2 인덱스 요소부터 3개 요소를 dst의 5 인덱스 부터 붙여넣음 
System.out.println("dst = " + Arrays.toString(dst));
// dst = [0, 0, 0, 0, 0, 3, 4, 5, 0, 0]

 

즉, StringBuilder가 가진 배열의 다음 저장할 위치에 "-"를 저장한다는 소리다. 

 

혹시 System.arraycopy 내부에서 배열을 임시로 복사해서 쓰는지, 아니면 dest 배열에 붙여넣는지 궁금해서 보려고 했는데, 

@IntrinsicCandidate
public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos, int length);

코드는 구현부가 보이지 않았다..  다만 찾아보니 native 코드를 호출해서 빠르다고 한다.

 

---

 

static final int 일억 = 10_0000_000;
static final int 일점오억 = 15_0000_000;

public static void main(String[] args) {
    List<Long> appendTime = new ArrayList<>();
    List<Long> repeatTime = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        appendTime.add(checkTime("스트링빌더", 일억, getBarWithStringBuilder));
        repeatTime.add(checkTime("리핏", 일억, getBarWithRepeat));
    }

    double appendAvg = appendTime.stream().mapToDouble(Long::doubleValue).average().getAsDouble();
    double repeatAvg = repeatTime.stream().mapToDouble(Long::doubleValue).average().getAsDouble();

    System.out.println("appendAvg = " + appendAvg);
    System.out.println("repeatAvg = " + repeatAvg);
}

// appendAvg = 118.08
// repeatAvg = 5.82

음, 혹시 몰라서 1억번 반복하는 코드를 100번 반복해서 평균을 내봤는데 24배 정도 차이가 난다.

 

그래서 10억번 반복하는 코드를 100번 반복해서 평균내 봤는데 다음과 같다. 

appendAvg = 1283.88
repeatAvg = 61.8

20배 정도 차이가 나는데, 음 그냥 원래 느린갑다 하고 받아들이기로 했다,, 

---

정리 

1. repeat은 반복할 횟수를 알고 있으므로, 그만큼 배열을 만들어서 삽입하면 되니 빠르다. 
2. StringBuilder의 append는 반복마다 넣을 수 있는 크기가 충분한지 체크하고, 넣을 수 있다면 기존 StringBuilder의 배열에 새로 추가할 배열부분을 System.arraycopy로 붙여넣는다. 
   1. 크기 체크하다 사이즈가 부족하면 늘어날 크기의 + 2로 늘린다. 그래서 처음 StringBuilder를 생성할 때 적절한 사이즈를 설정해주어야 한다. 
   2. 크기 체크가 충분하다면 if 문에서 걸러지므로 큰 시간을 잡아먹지는 않는다. 
   3. 가장 시간을 잡아먹는 부분은 새로 문자열을 추가하면서 호출되는 System.arraycopy 부분인 것 같다. 
   4. 실행환경에 따라 다르지만, 평균 약 20배 정도 더 느리다.
3. 따라서, 동일한 문자열을 몇 번 반복해서 추가할지 알고있다면 String.repeat 을 쓰자,, 가 결론인 것 같다.