java replaceAll 메서드 : 그냥 쓰면 어떤 오버헤드가 걸릴까요?

 String 클래스의 replaceAll 메서드는 상당히 많이 쓰는 메서드 중 하나입니다. 이것의 성능 문제에 대해서는, 이미 다른 곳에서도 많이 언급이 되기도 했습니다. 만.. 한 번 더 짚고 넘어가셔도 좋을 듯 싶습니다. 사실 제대로 분석하시려면 컴파일러나 프로그래밍 언어론을 보시는 게 도움이 많이 될 겁니다.

 

 replaceAll 메소드는 크게 어려운 게 없습니다. 단지, regex 패턴을 찾으면, 그것을 replacement로 대체합니다. 예를 들자면, 숫자를 없애기 위해서는 regex에 "[0-9]"를, replacement에 ""을 넣으면 됩니다.

 

---

 내부를 보겠습니다.

 

 보면, Parrern.compile(regex).matcher(this).replaceAll(replacement); 이 문장이 다입니다. 그러면 이들이 무엇을 하는지를 알아야 겠습니다.

 

 먼저, compile을 한 결과물을 보겠습니다. 뭔가 이상한데, next, next라는 구조가 계속 보입니다. List나 Tree로 이루어진 무언가라는 이야기입니다. 중간 중간 보시면, cmax가 1이고, cmin이 0인 것은 {0,1}을 의미합니다. 그리고, cmax가 2147483647인 것은 그 다음 부분인 [\d]+를 의미합니다.

 

 그리고 46이 보이는데요. ascii 코드로 46번은 '.'입니다. 다음에, cmax가 2147483647인 것은 [\d]+을 의미합니다. 여기서 대략적으로 정리를 해 보면, regex 표현을 가지고, 그에 맞게 List나 Tree 등을 생성하는 역할을 한다고 볼 수 있습니다. 어떻게 생성하는지는 언젠가 볼 기회는 있겠습니다만, 지금은 꽤 덩치가 있는 덩어리 정도를 새로 만든다고 생각하시면 좋겠습니다.

 

 

 일단, Pattern의 compile 메서드를 호출하면 새로운 Pattern 객체를 만들게 됩니다.

 

 

 이 메서드 안으로 들어가면, compile이라는 메서드를 호출하게 되는데요. 이 메서드를 간단하게 보겠습니다. 이 포스팅을 쓰기 위해 중요한 부분인 것만 간단하게 보겠습니다.

 

 

  new int가 보입니다. patternLength + 2가 눈에 보이는군요.

 

 

 다음에 buffer랑 groupNodes가 또 눈에 보입니다. GroupHead도 보이는데요. 이들이 모두 새로 추가되는 객체들입니다.

 

 

 이것으로 끝이면 좋을 텐데, 그렇지도 않습니다. newSlice에, 파싱하는 데 이용하는 재귀 함수인 expr. 사실 이 부분만 보더라도 컴파일 메서드를 수행하는 데 상당한 연산이 들어감을 알 수 있습니다. validation 체크만 한다고 쳐도. 어마어마한 연산입니다. 이 연산을 replaceAll을 부르면 컴파일이 이미 되었던 되지 않았던 항상 수행합니다. 이것이 그대로 오버헤드로 들어가는 셈입니다.

 

---

 미리 컴파일된 Pattern을 저장하고 있으면 어떨까요?

 

 이 경우, 이미 컴파일이 되어 있다면, 바로 새로운 Matcher를 생성합니다. Matcher를 생성하는 비용 역시 많이 들어갈 듯 합니다만, 최소한 어마어마한 객체를 생성하고, 재귀적으로 expr 등을 부르는 compile 메서드를 수행하지 않아도 됩니다. 이는 target 문자열의 길이에 비해서, 패턴이 상대적으로 복잡한 경우에 더 잘 나타납니다. 미리 패턴을 전처리 해 놓는 것과 replaceAll을 수행하는 경우의 성능차가 극단적으로 나타나는 셈입니다. 사실 당연할 수 밖에 없습니다.

 

 컴파일 하는 데 C만큼이 걸리고, Matcher로 매칭하는데 M만큼 걸리고, 나머지 연산을 하는 데 R만큼 걸린다고 해 봅시다. replaceAll을 호출하는 경우 C+M+R만큼 걸리던 것이, 미리 컴파일된 패턴을 가지고 있으면 M+R만큼 걸립니다. R, M에 비해서 C를 하는 비용이 매우 크다면 극단적으로 다가오는 것은 당연한 이치일 겁니다. 이제 실험 프로그램을 보겠습니다.

 

 

 4가지 패턴을 가지고 실험을 해 보았습니다. 이 중 (4)번째 패턴은 부호가 붙은 소수점을 나타내는 것입니다. +2.3, -5.77 이런 것들을 패턴으로 가지는 것들입니다. 디버그를 돌리다 보면, 아래와 같은 문장에서도 멈춘다는 것을 볼 수 있는데요.

 

 

 new BitClass()가 눈에 들어옵니다.

 

 

 이것은 Pattern.compile을 불렀을 때 내부적으로 호출이 되는 것입니다. 그리고 이 안을 들여다 보시면 다음과 같은 것이 또 있음을 알 수 있습니다.

 

 

 256개 짜리의 boolean 배열이 눈에 보입니다.

 

 

 이것이 작동된 것으로 보아서는, 256개짜리 bit가 컴파일이 될 때 마다 하나 이상은 만들어 지겠네요. [+-] 부분이 말입니다. \\d는 따로 type을 두어서 관리하기 때문에 boolean으로 관리하지는 않습니다.

 

 

 atom 내부에 있는 bits를 보세요. boolean[256]@39. 다음 루프를 돌았을 때는 어떨까요?

 

 

 boolean[256]@63. 다른 무언가임을 알 수 있습니다. 한 번 컴파일 될 때 마다, 저 패턴을 쓰면 256개의 boolean 배열도 계속 생성이 됨을 알 수 있습니다. 그러면, 매번 컴파일을 할 때 효율이 극단적으로 떨어지게 하는 케이스를 만들려면 어떻게 하면 좋을까요? 타겟 문자열의 길이를 작게 하면 됩니다. 아래는 Main 클래스입니다.

 

 

 이제, 어떻게 실행하는 지 보이실 듯 싶습니다. 테스트 케이스 1천만개, 문자열 길이는 10. 이렇게 setting을 해 놓았습니다. 이제 2개를 비교해 보도록 하겠습니다.

 

 

---

 

 먼저, 단순히 replaceAll을 썼을 때입니다.

 

 

 

 미리 처리된 것을 Common에다 넣어두고 패턴을 컴파일 하는 과정을 생략했을 때입니다. 둘을 비교해 보았을 때, 꽤나 유의미한 차이가 나타남을 알 수 있는데요. 이는, 패턴에 비해서 테스트 케이스의 문자열 길이가 크지 않고, 컴파일 메서드가 호출되었을 때, 내부적으로 새로운 객체들이 많이 생성되기 때문입니다. 아래 그림에서 (1)번부터 (3)번 패턴에 대해서는, 성능 차이가 유의미 하긴 하지만, 그렇게 심하게 많이 나지 않았다는 것도 보실 필요가 있습니다.