문자열을 붙이는 문제가 있었는데, 그것을 풀다가 시간 초과가 났었다.
시간 초과가 난 이유는 바로 String을 썼기 때문이었다.
문자열을 붙이거나 수정할 때는 String 보다는 StringBuilder를 써야 메모리와 시간을 지킬 수 있다.
이 이유를 String과 StringBuilder 비교, 내부 동작 과정을 설명해 풀어가겠다.
문자열을 붙이는 것만으로도 차이가 확연히 난다.
간단하게 코드로 작성하고, 시간을 비교해봤다.
import java.util.*;
import java.io.*;
public class Main {
static int N=10;
public static void main(String[] args) throws IOException {
long start = System.currentTimeMillis(); // 시작 시간
string();
// stringBuilder();
long end = System.currentTimeMillis(); // 종료 시간
System.out.println("실행 시간: " + (end - start) + "ms");
}
public static void string() {
String s="";
for (int i = 0; i < N; i++) {
s+="a";
}
System.out.println(s);
}
public static void stringBuilder() {
StringBuilder sb=new StringBuilder();
for (int i = 0; i < N; i++) {
sb.append("a");
}
System.out.println(sb);
}
}
10개를 붙일 때를 보자
string 함수는 호출마다 시간 차이가 있었는데, 약 5~10ms로 나왔다.
StringBuilder을 사용했을 때랑 비교해보면 5~10배 정도 차이난다고 보면 된다.
숫자가 더 커졌을 때 더 많은 차이가 난다.
이때도 약 8~10배정도 차이가 난다.
100,000일 때, 확실하게 많은 차이가 나는 걸 볼 수 있다. 대략 100배 정도 차이가 난다.
왜 이렇게 차이가 날까?
이유는 String이 불변 객체이기 때문이다. 이것을 알기 위해서 불변 객체가 무엇인지 알아보자
불변 객체는 말 그대로 변하지 않는다는 것이다. String은 불변 객체다.
따라서 한번 String 객체를 만들면, 바꾸고자 할 때 새로운 String 객체를 만들어줘야 한다.
/*
...
@implNote The implementation of the string concatenation operator is left to
* the discretion of a Java compiler, as long as the compiler ultimately conforms
* to <i>The Java Language Specification</i>. For example, the {@code javac} compiler
* may implement the operator with {@code StringBuffer}, {@code StringBuilder},
* or {@code java.lang.invoke.StringConcatFactory} depending on the JDK version. The
* implementation of string conversion is typically through the method {@code toString},
* defined by {@code Object} and inherited by all classes in Java.
...
*/
public final class String
implements java.io.Serializable, Comparable<String>, CharSequence,
Constable, ConstantDesc {
@Stable
private final byte[] value;
public String() {
this.value = "".value;
this.coder = "".coder;
}
/**
* Initializes a newly created {@code String} object so that it represents
* the same sequence of characters as the argument; in other words, the
* newly created string is a copy of the argument string. Unless an
* explicit copy of {@code original} is needed, use of this constructor is
* unnecessary since Strings are immutable.
*
* @param original
* A {@code String}
*/
@IntrinsicCandidate
public String(String original) {
this.value = original.value;
this.coder = original.coder;
this.hash = original.hash;
this.hashIsZero = original.hashIsZero;
}
}
String class 코드를 보면 String 객체를 생성할 때, value에 저장을 한다.
@Stable
private final byte[] value;
근데 value는 private final이 붙어 있다.
final이 붙으면 참조 자체를 바꿀 수 없다는 뜻이다.
즉, value=new byte[10]
이런 식으로 새로운 배열을 참조하도록 할 수 없다는 것이다.
value[0]=’c’ 이렇게 할 경우 배열 내용은 변경이 가능하지만 private라는 외부에서 접근 불가능한 제한자가 붙어 외부에서 변경을 할 수 없다.
String 클래스 또한 모든 변경 시, 새 String 객체를 생성하도록 코드가 만들어져 있기 때문에 불변이 될 수 있는 것이다.
@Stable
은 컴파일러에게 “이 필드 값은 한 번 초기화 후 변하지 않는다”라고 알려주는 표시다.
java는 c언어와 달리 연산자 오버로딩이 없다.
문자열 연결 연산자는 컴파일러에서 언어 규칙에 따라 특별히 처리한다.
JLS(java language specification)이라는 java 언어 처리 규칙을 써놓은 공식 문서가 있다. 컴파일러 제작자와 JVM 개발자들이 java를 어떻게 처리해야 하는지 기준을 제공해, 모두 동일한 방식으로 동작하는 걸 보장하도록 한다.
The result of string concatenation is a reference to a
String
object that is the concatenation of the two operand strings. The characters of the left-hand operand precede the characters of the right-hand operand in the newly created string.The
String
object is newly created (§12.5) unless the expression is a constant expression (§15.29).(번역) 두 String 피 연산자가 +로 이어져 있을 경우, 문자열 연결의 결과는 String 객체를 참조한다. 새로 생성된 문자열에서 왼쪽 피 연산자의 문자가 오른쪽 피연산자의 문자 앞에 있다. 상수가 아닐 경우, 새롭게 String 객체로 생성된다.
출처: JLS 3.10.5
이렇게 어떻게 자바 언어를 처리하면 되는지 규칙이 적혀있다.
그럼 컴파일러에서는 + 연산자를 어떻게 처리할까?
컴파일러가 어떻게 처리하는지 보려면 다음과 같은 명령어를 치면 된다.
javac Main.java // 컴파일
javap -c Main.class // 디스어셈블
Main.java는 아까 String과 StringBuilder를 비교할 때 쓴 코드가 저장되어 있는 파일이다.
Compiled from "Main.java"
public class find.Main {
static int N;
public find.Main();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]) throws java.io.IOException;
Code:
0: invokestatic #7 // Method java/lang/System.currentTimeMillis:()J
3: lstore_1
4: invokestatic #13 // Method string:()V
7: invokestatic #18 // Method stringBuilder:()V
10: invokestatic #7 // Method java/lang/System.currentTimeMillis:()J
13: lstore_3
14: getstatic #21 // Field java/lang/System.out:Ljava/io/PrintStream;
17: lload_3
18: lload_1
19: lsub
20: invokedynamic #25, 0 // InvokeDynamic #0:makeConcatWithConstants:(J)Ljava/lang/String;
25: invokevirtual #29 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
28: return
public static void string();
Code:
0: ldc #35 // String
2: astore_0
3: iconst_0
4: istore_1
5: iload_1
6: getstatic #37 // Field N:I
9: if_icmpge 25
12: aload_0
13: invokedynamic #41, 0 // InvokeDynamic #1:makeConcatWithConstants:(Ljava/lang/String;)Ljava/lang/String;
18: astore_0
19: iinc 1, 1
22: goto 5
25: getstatic #21 // Field java/lang/System.out:Ljava/io/PrintStream;
28: aload_0
29: invokevirtual #29 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
32: return
public static void stringBuilder();
Code:
0: new #44 // class java/lang/StringBuilder
3: dup
4: invokespecial #46 // Method java/lang/StringBuilder."<init>":()V
7: astore_0
8: iconst_0
9: istore_1
10: iload_1
11: getstatic #37 // Field N:I
14: if_icmpge 30
17: aload_0
18: ldc #47 // String a
20: invokevirtual #49 // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
23: pop
24: iinc 1, 1
27: goto 10
30: getstatic #21 // Field java/lang/System.out:Ljava/io/PrintStream;
33: aload_0
34: invokevirtual #53 // Method java/io/PrintStream.println:(Ljava/lang/Object;)V
37: return
static {};
Code:
0: sipush 30000
3: putstatic #37 // Field N:I
6: return
}
이렇게 컴파일러를 거친 바이트 코드를 사람이 읽을 수 있는 어셈블리어 형태로 바꿔서 보여지게 된다.
여기서 잘 보면, string 함수에서 invokedynamic을 호출한다.
13: invokedynamic #41, 0 // InvokeDynamic #1:makeConcatWithConstants:(Ljava/lang/String;)Ljava/lang/String;
InvokeDynamic이 뭘까?
openJDK에서 기록한 JEP를 보면 알 수 있다.
We will use the power of
invokedynamic
: It offers the facilities for a lazy linkage, by providing the means to bootstrap the call target once, during the initial invocation.The idea is to replace the entire
StringBuilder
append dance with a simpleinvokedynamic
call tojava.lang.invoke.StringConcatFactory
, that will accept the values in the need of concatenation. For example,String m(String a, int b) { return a + "(" + b + ")"; }
is currently compiled to:
java.lang.String m(java.lang.String, int); 0: new #2 // class java/lang/StringBuilder 3: dup 4: invokespecial #3 // Method java/lang/StringBuilder."<init>":()V 7: aload_1 8: invokevirtual #4 // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder; 11: ldc #5 // String ( 13: invokevirtual #4 // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder; 16: iload_2 17: invokevirtual #6 // Method java/lang/StringBuilder.append:(I)Ljava/lang/StringBuilder; 20: ldc #7 // String ) 22: invokevirtual #4 // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder; 25: invokevirtual #8 // Method java/lang/StringBuilder.toString:()Ljava/lang/String; 28: areturn
But even with the naive indy translation, available in the proposed implementation via
-XDstringConcat=indy
, it can be significantly simpler:java.lang.String m(java.lang.String, int); 0: aload_1 1: ldc #2 // String ( 3: iload_2 4: ldc #3 // String ) 6: invokedynamic #4, 0 // InvokeDynamic #0:makeConcat:(Ljava/lang/String;Ljava/lang/String;ILjava/lang/String;)Ljava/lang/String; 11: areturn BootstrapMethods: 0: #19 invokestatic java/lang/invoke/StringConcatFactory.makeConcat:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/String;[Ljava/lang/Object;)Ljava/lang/invoke/CallSite;
이 내용은 invokedynamic로의 변경 내용을 담고 있다.
자바 8까지는 무조건 + 연산자가 있으면 StringBuilder.append를 호출했다.
String m(String a, int b) {
return a + "(" + b + ")";
}
이 코드가 java 8 버전에서는 컴파일 된다면 다음과 같이 컴파일이 된다.
java.lang.String m(java.lang.String, int);
0: new #2 // class java/lang/StringBuilder
3: dup
4: invokespecial #3 // Method java/lang/StringBuilder."<init>":()V
7: aload_1
8: invokevirtual #4 // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
11: ldc #5 // String (
13: invokevirtual #4 // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
16: iload_2
17: invokevirtual #6 // Method java/lang/StringBuilder.append:(I)Ljava/lang/StringBuilder;
20: ldc #7 // String )
22: invokevirtual #4 // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
25: invokevirtual #8 // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
28: areturn
연쇄적인 StringBuilder 객체 생성 후, 연쇄적인 append 후, toString 호출을 하는걸 볼 수 있다.
근데 java 9부터는 최적화를 더 해, invokedynamic이라는 명령어로 바꿔서 컴파일한다. 이 invokedynamic은 실행시 부트스트랩 메소드(StringConcatFactory)를 호출해 실제 연결 방식을 정해준다.
java.lang.String m(java.lang.String, int);
0: aload_1
1: ldc #2 // String (
3: iload_2
4: ldc #3 // String )
6: invokedynamic #4, 0 // InvokeDynamic #0:makeConcat:(Ljava/lang/String;Ljava/lang/String;ILjava/lang/String;)Ljava/lang/String;
11: areturn
>
BootstrapMethods:
0: #19 invokestatic java/lang/invoke/StringConcatFactory.makeConcat:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/String;[Ljava/lang/Object;)Ljava/lang/invoke/CallSite;
아까 Main class를 연결된 링크들도 볼 수 있게 하는 명령어는 다음과 같다.
javap -v Main.class
public static void main(java.lang.String[]) throws java.io.IOException;
descriptor: ([Ljava/lang/String;)V
flags: (0x0009) ACC_PUBLIC, ACC_STATIC
Code:
stack=5, locals=5, args_size=1
0: invokestatic #7 // Method java/lang/System.currentTimeMillis:()J
3: lstore_1
4: invokestatic #13 // Method string:()V
7: invokestatic #18 // Method stringBuilder:()V
10: invokestatic #7 // Method java/lang/System.currentTimeMillis:()J
13: lstore_3
14: getstatic #21 // Field java/lang/System.out:Ljava/io/PrintStream;
17: lload_3
18: lload_1
19: lsub
20: invokedynamic #25, 0 // InvokeDynamic #0:makeConcatWithConstants:(J)Ljava/lang/String;
25: invokevirtual #29 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
28: return
LineNumberTable:
line 12: 0
line 14: 4
line 15: 7
line 17: 10
line 18: 14
line 19: 28
Exceptions:
throws java.io.IOException
public static void string();
descriptor: ()V
flags: (0x0009) ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=2, args_size=0
0: ldc #35 // String
2: astore_0
3: iconst_0
4: istore_1
5: iload_1
6: getstatic #37 // Field N:I
9: if_icmpge 25
12: aload_0
13: invokedynamic #41, 0 // InvokeDynamic #1:makeConcatWithConstants:(Ljava/lang/String;)Ljava/lang/String;
18: astore_0
19: iinc 1, 1
22: goto 5
25: getstatic #21 // Field java/lang/System.out:Ljava/io/PrintStream;
28: aload_0
29: invokevirtual #29 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
32: return
LineNumberTable:
line 22: 0
line 23: 3
line 24: 12
line 23: 19
line 26: 25
line 27: 32
StackMapTable: number_of_entries = 2
frame_type = 253 /* append */
offset_delta = 5
locals = [ class java/lang/String, int ]
frame_type = 250 /* chop */
offset_delta = 19
public static void stringBuilder();
descriptor: ()V
flags: (0x0009) ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=2, args_size=0
0: new #44 // class java/lang/StringBuilder
3: dup
4: invokespecial #46 // Method java/lang/StringBuilder."<init>":()V
7: astore_0
8: iconst_0
9: istore_1
10: iload_1
11: getstatic #37 // Field N:I
14: if_icmpge 30
17: aload_0
18: ldc #47 // String a
20: invokevirtual #49 // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
23: pop
24: iinc 1, 1
27: goto 10
30: getstatic #21 // Field java/lang/System.out:Ljava/io/PrintStream;
33: aload_0
34: invokevirtual #53 // Method java/io/PrintStream.println:(Ljava/lang/Object;)V
37: return
LineNumberTable:
line 30: 0
line 31: 8
line 32: 17
line 31: 24
line 34: 30
line 35: 37
StackMapTable: number_of_entries = 2
frame_type = 253 /* append */
offset_delta = 10
locals = [ class java/lang/StringBuilder, int ]
frame_type = 250 /* chop */
offset_delta = 19
static {};
descriptor: ()V
flags: (0x0008) ACC_STATIC
Code:
stack=1, locals=0, args_size=0
0: sipush 30000
3: putstatic #37 // Field N:I
6: return
LineNumberTable:
line 9: 0
}
SourceFile: "Main.java"
BootstrapMethods:
0: #74 REF_invokeStatic java/lang/invoke/StringConcatFactory.makeConcatWithConstants:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/String;[Ljava/lang/Object;)Ljava/lang/invoke/CallSite;
Method arguments:
#70 실행 시간: \u0001ms
1: #74 REF_invokeStatic java/lang/invoke/StringConcatFactory.makeConcatWithConstants:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/String;[Ljava/lang/Object;)Ljava/lang/invoke/CallSite;
Method arguments:
#72 \u0001a
InnerClasses:
public static final #85= #81 of #83; // Lookup=class java/lang/invoke/MethodHandles$Lookup of class java/lang/invoke/MethodHandles
BootstrapMethods인 StringConcatFacotry의 makeConcatWithConstants를 호출한다.
public static CallSite makeConcatWithConstants(MethodHandles.Lookup lookup,
String name,
MethodType concatType,
String recipe,
Object... constants)
throws StringConcatException {
Objects.requireNonNull(lookup, "Lookup is null");
Objects.requireNonNull(name, "Name is null");
Objects.requireNonNull(recipe, "Recipe is null");
Objects.requireNonNull(concatType, "Concat type is null");
Objects.requireNonNull(constants, "Constants are null");
for (Object o : constants) {
Objects.requireNonNull(o, "Cannot accept null constants");
}
if ((lookup.lookupModes() & MethodHandles.Lookup.PRIVATE) == 0) {
throw new StringConcatException("Invalid caller: " +
lookup.lookupClass().getName());
}
String[] constantStrings = parseRecipe(concatType, recipe, constants);
if (!concatType.returnType().isAssignableFrom(String.class)) {
throw new StringConcatException(
"The return type should be compatible with String, but it is " +
concatType.returnType());
}
if (concatType.parameterSlotCount() > MAX_INDY_CONCAT_ARG_SLOTS) {
throw new StringConcatException("Too many concat argument slots: " +
concatType.parameterSlotCount() +
", can only accept " +
MAX_INDY_CONCAT_ARG_SLOTS);
}
try {
if (concatType.parameterCount() <= HIGH_ARITY_THRESHOLD) {
return new ConstantCallSite(
generateMHInlineCopy(concatType, constantStrings)
.viewAsType(concatType, true));
} else {
return new ConstantCallSite(
SimpleStringBuilderStrategy.generate(
lookup, concatType, constantStrings));
}
} catch (Error e) {
// Pass through any error
throw e;
} catch (Throwable t) {
throw new StringConcatException("Generator failed", t);
}
}
런타임에 invokedynamic이 실행될 때, 이 메소드가 호출되게 된다.
try {
if (concatType.parameterCount() <= HIGH_ARITY_THRESHOLD) {
return new ConstantCallSite(
generateMHInlineCopy(concatType, constantStrings)
.viewAsType(concatType, true));
} else {
return new ConstantCallSite(
SimpleStringBuilderStrategy.generate(lookup, concatType, constantStrings));
}
}
이 부분을 보면,
HIGH_ARITY_THRESHOLD: 기준이 되는 숫자 (기본값 20)
인자 개수가 20개 이하면, MethodHandle 기반 최적화로, 20개 이상이면 StringBuilder 기반 전략을 선택한다.
(참고)
Eclipse에서 generateMHInlineCopy 메소드 설명과 SimpleStringBuilderStrategy 설명이다.MethodHandle java.lang.invoke.StringConcatFactory.generateMHInlineCopy ( MethodType mt, String[] constants ) This strategy replicates what StringBuilders are doing: it builds the byte[] array on its own and passes that byte[] array to String constructor. This strategy requires access to some private APIs in JDK, most notably, the private String constructor that accepts byte[] arrays without copying. Parameters: mt constants
java.lang.invoke.StringConcatFactory.SimpleStringBuilderStrategy Bytecode StringBuilder strategy. This strategy emits StringBuilder chains as similar as possible to what javac would. No exact sizing of parameters or estimates.
항목 MethodHandle 전략 SimpleStringBuilder 전략 인자 수 ≤ 20 (작은 경우) > 20 (큰 경우) 내부 구현 byte[] + private String constructor StringBuilder append 체인 성능 빠름, JIT 최적화 가능 안정적, 메모리/시간 효율 사용 시점 invokedynamic 부트스트랩 시점 invokedynamic 부트스트랩 시점
즉, + 연산의 인자 개수에 따라 컴파일 전략이 다르다.
인자 개수에 따라 + 연산자를 사용해 더하는 것과 StringBuilder를 비교해보겠다.
public class Main {
static int N=20000;
public static void main(String[] args) throws IOException {
long start = System.currentTimeMillis(); // 시작 시간
// string();
// stringBuilder();
// ten();
// twelve();
// twelveOne();
eman();
long end = System.currentTimeMillis(); // 종료 시간
System.out.println("실행 시간: " + (end - start) + "ms");
}
public static void string() {
String s="";
for (int i = 0; i < N; i++) {
s+="a";
}
System.out.println(s);
}
public static void stringBuilder() {
StringBuilder sb=new StringBuilder();
for (int i = 0; i < N; i++) {
sb.append("a");
}
System.out.println(sb);
}
public static void ten() {
String s="";
s="a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a";
System.out.println(s);
}
public static void twelve() {
String s="";
s="a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a";
System.out.println(s);
}
public static void twelveOne() {
String s="";
s="a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a"+"a";
System.out.println(s);
}
public static void eman() {
String s="";
s="a"+"a"+...."a"; // 20000번 더하는 연산자 작성
System.out.println(s);
}
}
확실히 for문 반복으로 + 연산자를 할 때와 차이가 있다. 이전엔 5~10ms 정도 나왔다.
java 8까지는 + 연산자는 무조건 StringBuilder.append 체인으로 컴파일되었다.
java 9부터는 invokeDynamic+StringConcatFacotry로 처리되는걸로 바꼈다.
한 줄에 + 하는 인자 개수에 따라 MethodHandle 또는 SimpleStringBuilder 전략을 실행하고, 이들 각각의 전략은 StringBuilder의 성능과 크게 차이가 나지 않는다. 오히려 더 빠를 수도 있다.
결국 java 8 이하던, java 9 이상이던 for문으로 인자를 더했을 때 StringBuilder와 차이가 나게 된다.
왜냐하면 불필요한 오버헤드가 누적되기 때문이다.
java 8 이하의 경우, 매번 new StringBuilder() → append() → toString() 과정이 반복되면서 불필요한 객체 생성 + 복사 오버헤드 때문에 느리다.
java 9 이상의 경우, 반복문에서 계속 invokedynamic + concat 전략을 실행하면서 오버헤드가 쌓인다.
알고리즘이나 실생활에서 인자들을 전부 다 한 줄에 써놓을 일이 없다.
보통 for문을 통해 반복을 하기 때문에, StringBuilder를 써서 append를 해 오버헤드를 줄이는게 성능상 좋다
참고했던 문서들이 어떤 문서들일지 궁금할 것 같아서 적어놓겠다.
+
연산을 invokedynamic
으로 처리
정말 좋은 내용입니다. 감사합니다