JUnit로 검색한 결과 :: 시소커뮤니티[SSISO Community]
 
SSISO 카페 SSISO Source SSISO 구직 SSISO 쇼핑몰 SSISO 맛집
추천검색어 : JUnit   Log4j   ajax   spring   struts   struts-config.xml   Synchronized   책정보   Ajax 마스터하기   우측부분

회원가입 I 비밀번호 찾기


SSISO Community검색
SSISO Community메뉴
[카페목록보기]
[블로그등록하기]  
[블로그리스트]  
SSISO Community카페
블로그 카테고리
정치 경제
문화 칼럼
비디오게임 스포츠
핫이슈 TV
포토 온라인게임
PC게임 에뮬게임
라이프 사람들
유머 만화애니
방송 1
1 1
1 1
1 1
1 1
1

JUnit로 검색한 결과
등록일:2008-04-15 10:44:18
작성자:
제목:Ropes: 이론과 실제 (한글)


문자열 조작 때 Ropes for Java를 사용해야 하는 경우와 그 이유

developerWorks
문서 옵션

JavaScript가 필요한 문서 옵션은 디스플레이되지 않습니다.

수평출력으로 설정

이 페이지 출력

이 페이지를 이메일로 보내기

이 페이지를 이메일로 보내기

영어원문

영어원문


제안 및 의견
피드백

난이도 : 중급

Amin Ahmad, 독립 컨설턴트, Department13

2008 년 4 월 08 일

자바(Java™)의 StringStringBuilder 클래스는 많은 문자열 데이터를 처리해야 하는 시스템에는 그다지 적합하지 않습니다. 이 경우 로프(rope) 자료 구조가 더 나은 대안이 될 수 있습니다. 이 글에서는 자바 플랫폼을 위한 로프 구현인 Ropes for Java를 소개하고, 성능 관련 이슈를 살펴 봅니다. 또, 해당 라이브러리를 효과적으로 사용하기 위한 지침을 제시합니다.

자바 String처럼 로프 자료 구조는 내용을 바꿀 수 없는 문자열을 표현한다. 하지만 로프는 효율적으로 변형될 수 있어 String 또는 내용을 바꿀 수 있는 StringBuffer, StringBuilder와 달리 문자열 조작이 많은 애플리케이션에 이상적이다. 특히 멀티스레드 환경에서 더욱 빛을 발한다.

이 글에서는 먼저 로프 자료 구조에 대해 간단히 요약한 후, 자바 플랫폼을 위한 로프 구현인 Ropes for Java를 소개한다. 다음으로 자바 플랫폼에서 String, StringBuffer, Ropes for Java의 성능을 벤치마크해 보고, 성능에 관련된 몇 가지 특별한 이슈를 살펴본다. 그 후 로프를 사용해야 할 때와 말아야 할 때를 살펴보는 것으로 글을 맺겠다.

로프: 간단한 소개

로프는 내용을 바꿀 수 없는 문자열을 나타내며, 그 길이는 문자열 내 문자 개수다. 보통 문자열을 나타내는 자료 구조는 대부분 모든 문자를 메모리 상에서 연속되게 배치한다. 로프의 고유한 특징은 이러한 제약을 없애고, 로프 내 부분부분이 불연속으로 저장할 수 있도록 하고 연결 노드(concatenation node)로 결합하게 한 점이다. 이 때문에 두 문자열을 하나로 결합할 때 로프가 자바 String보다 점근적으로 더 빠르다(역주: 원문은 asymptotically faster이며 여기서는 구현과 무관하게 얼마 길이 이상의 문자열에 대해서는 항상 로프가 빠르게 됨을 의미한다). 자바 String을 이어 붙일 때는 각 문자열을 새 위치에 복사해야 한다. 이 때 해당 작업의 복잡도는 O(n)이다. 반면 로프에서는 새 연결 노드를 만들면 끝이고, 이 작업의 복잡도는 O(1)이다(Big-O 표기에 익숙하지 않으면 이해하는 데 도움이 될 만한 자료가 참고자료에 나와 있으니 참고한다).

그림 1에 두 가지 문자열 표현 방식을 나타냈다. 좌측 표현 방식에선 문자들이 연속된 메모리 공간에 배치되어 있다. 자바 문자열이 이런 방식을 사용한다. 우측에서는 분리된 문자열이 연결 노드로 연결되어 있다.


그림 1. 두 가지 문자열 표현 방식
두 가지 문자열 표현 방식

또, 로프 구현은 종종 부분 문자열 노드(substring node)를 사용해 큰 부분 문자열을 당장 뽑아내지 않고 뒤로 미룬다(역주: 부분을 별도로 복사해 추출하지 않고 원본의 일부라는 표시만 한다는 뜻이다). 부분 문자열 노드를 쓰면 길이가 n인 부분 문자열을 뽑아내는 데 걸리는 시간을 O(n)에서 O(log n)으로 줄일 수 있고, O(1)으로 줄어드는 경우도 많다. 여기서 중요한 것은 내용이 안 바뀌는 자바 String도 고정 시간(constant-time)에 부분 문자열을 구할 수 있다는 점이다. 하지만 StringBuilder의 경우는 그렇지 못할 때가 많다.

연결 노드나 부분 문자열 노드가 없는 평평한 로프(flat rope)깊이가 1이다. 연결 노드와 부분 문자열 노드의 깊이는 해당 노드가 참조하는 가장 깊은 노드보다 깊이가 1 깊다.

문 자를 연속으로 표현하는 문자열 표현 방식에 비해 로프에는 다음 두 가지 추가 부담이 있다. 첫째, 특정 문자를 참조하려면 부분 문자열 노드와 연결 노드라는 상위 구조를 따라가야 한다. 게다가 따라가는 시간을 최소로 하려면 가능한 트리 형태 상위 구조 양쪽이 균형을 유지해야 한다. 이는 읽기 성능을 좋게 유지하려면 종종 다시 균형을 맞춰 줘야 한다는 뜻이다. 설사 로프가 균형이 잘 맞더라도, 특정 위치의 문자를 읽는 것은 로프를 구성하는 연결 노드와 부분 문자열 노드 수를 n이라고 할 때 O(log n) 작업이다(로프에서는 그 길이가 부분 문자열과 연결 노드 수보다 항상 크기 때문에 편의상 로프의 길이를 n으로 해도 무방하다).

다 행히 로프 구조를 다시 균형을 맞추는 작업은 빨리 수행할 수 있다. 또 로프 길이와 깊이를 비교하는 식으로, 언제 균형을 맞춰야 하는지도 쉽게 판단할 수 있다. 일반적인 데이터 처리 루틴에서는 로프의 문자를 순차적으로 읽어야 하는 경우가 대부분인데, 로프 반복자(iterator)를 쓰면 부가 부담을 상각해 사실상 O(1)에 각 문자를 읽을 수 있다.

표 1은 로프와 자바 String을 각기 사용할 때 일반적인 문자열 작업 수행 시간을 비교한 것이다.


표 1. 일반적인 문자열 작업의 예상 소요 시간
작업루프자바 String
스트링 연결O(1)O(n)
부분 문자열 추출O(1)O(1)
문자 읽기O(log n)O(1)
모든 문자를 순서대로 읽을 때(한 문자당 소요 시간)O(1)O(1)



위로


Ropes for Java에 대한 소개

메모리 이슈

자바에서 고정 시간 부분 문자열 구현은 메모리 문제를 일으킬 수 있다. 부분 문자열이 원본 문자열을 참조하고 있으면 원본 문자열을 가비지 컬렉션할 수 없기 때문이다. RopeString 모두 같은 문제를 안고 있다.

Ropes for Java는 자바 플랫폼을 위한 고품질 로프 자료 구조 구현이다(참고자료를 살펴 보라). 성능 전반과 메모리 사용성을 높이기 위해 광범위한 최적화를 했다. 이 절에서는 로프를 어떻게 자바 애플리케이션에 통합하는가를 살펴보고, 로프의 성능을 StringStringBuffer를 사용할 때와 비교해 보겠다.

Ropes for Java는 프로그래머에게 Rope 클래스 하나만 열어준다. Rope 객체는 Rope.BUILDER 팩토리 빌더를 사용해 임의의 CharSequence에서 생성한다.

Listing 1은 로프 객체를 생성하는 예다.


Listing 1. 로프 생성
                
Rope r = Rope.BUILDER.build("Hello World");

Rope를 조작하기 위해 다음을 포함한 표준 메서드 한 벌을 제공한다.

  • 문자열을 맨 뒤에 추가하는 메서드
  • 일부분을 삭제하는 메서드
  • 다른 문자열을 로프에 삽입하는 메서드

여기서 각 메서드는 String과 마찬가지로 각 변형 시 새로운 로프 객체를 돌려준다는 점을 유념하자. 원본은 변하지 않는다. Listing 2에 이런 작업의 예를 보였다.


Listing 2. 로프 변형
                
Rope r = Rope.BUILDER.build("Hello World");
r = r.append("!"); // r is now "Hello World!"
r = r.delete(0,6); // r is now "World!"

효율적인 로프 내 문자 순서대로 읽어내기

로프 내 문자를 순서대로 읽을 때는 주의할 점이 있다. Listing 3의 두 코드 블록을 보고 어느 쪽 성능이 나을지 판단해 보라.


Listing 3. 로프에서 순서대로 문자를 읽는 두 가지 기법
                
//Technique 1
final Rope r=some initialization code;
for (int j=0; j<r.length(); ++j)
result+=r.charAt(j);

//Technique 2
final Rope r=some initialization code;
for (final char c: r)
result+=c;

로프에서 임의 위치의 문자를 읽어 내는 작업은 복잡도가 O(log n)이었다는 점을 상기하자. 첫 번째 코드 블록은 매번 charAt을 사용하므로 O(log n)짜리 검색을 n번 수행한다. 반면에 Iterator를 사용하는 두 번째 코드 블록은 첫 번째보다 더 빨라야 한다. 표 2는 길이가 10,690,488인 로프 내 문자를 순서대로 읽는 경우 성능을 요약한 것이다. 비교를 위해 StringStringBuffer를 사용하는 경우도 같이 나타냈다.


표 2. 복잡한 rope에서 문자 순서대로 읽을 때 성능
기법시간(ns)
String 69,809,420
StringBuffer 251,652,393
Rope.charAt 79,441,772,895
Rope.iterator 1,910,836,551

표 2의 결과는 예상대로인데 여기에 사용한 로프는 원본 문자열에 복잡한 변형을 가해 생성하였다. 하지만 해당 로프를 변형 없이 문자열에서 곧바로 생성하면 성능 측정치가 완전히 달라진다. 표 3은 프로젝트 구텐베르크(역주. 무료 전자책을 공급하기 위한 프로젝트: http://www.gutenberg.org) 판 찰스 디킨즈의 'A Christmas Carol'을 담은 문자 배열에서 바로 생성한 길이 182,029짜리 로프를 순서대로 읽었을 때 성능을 비교한 것이다.


표 3. 로프에서 문자를 순서대로 읽을 때 성능
기법시간(ns)
String 602,162
StringBuffer 2,259,917
Rope.charAt 462,904
Rope.iterator 3,466,047

앞서 언급한 이론적인 예측과 반대인 성능 측정치는 대체 어떻게 된 것일까? 로프 생성에 그 답이 있다. CharacterSequence나 문자 배열에서 직접 로프를 생성하면, 그 로프는 하나의 평평한 로프로 구성된 단순한 구조를 갖는다. 연결 노드나 부분 문자열 노드를 갖지 않으므로 특정 위치에서 문자를 읽으면, 하부 문자열이 CharacterSequence인 경우 charAt 메서드를 직접 호출하고, 문자 배열인 경우 배열에서 곧바로 문자를 읽는다. 평평한 로프의 Rope.charAt 성능은 하부 표현 방식의 성능과 같고, 보통 복잡도가 O(1)인 작업이다. 결국 이러한 성능 차이가 생긴다.

눈치 빠른 사람이라면 똑같이 O(1) 시간이 걸리는 작업인데도 왜 charAt이 반복자보다 일곱 배나 빠른지 의아할 것이다. 이는 자바에서 Iterator객체를 돌려줘야 하기 때문이다. charAt은 기본 타입인 char를 직접 돌려주는 반면, 반복자는 char 타입을 Character 객체로 바꿔야 한다. auto-boxing 기능이 기본 타입을 객체로 바꾸는 코드를 일일이 작성해야 하는 번거로움을 덜어 주기는 하지만 성능이 떨어지는 것까지 막아주지는 못한다.

끝으로 Rope.charAtString.charAt보다 성능이 낫다는 점이 눈에 띈다. 이는 Rope가 부분 문자열 표현을 위해 별도 클래스를 사용해 일반 로프의 charAt 구현을 단순하게 둔 것에 반해, 자바 SE의 String 구현은 일반 문자열과 부분 문자열을 표현할 때 똑 같은 클래스를 사용한다. 이 때문에 charAt의 로직이 다소 복잡해지며, 일반적인 문자열에서 문자를 순서대로 읽을 때 약간의 성능 저하가 생긴다.

로프 내 문자를 순서대로 읽는 문제에 대해서는 로프상 정규식 검색 검색의 성능을 최적화하는 이슈에 대해 다룰 때 다시 언급하겠다.

Rope.write로 출력 최적화하기

로프 객체는 대부분 어딘가로 출력해야 한다. 보통은 스트림으로 내보낸다. 공교롭게도 임의의 객체를 스트림에 출력하면 해당 객체의 toString 메서드가 호출되는데, 문자 하나라도 출력되려면 미리 객체 전체를 메모리 상에서 문자열로 바꿔야 한다. 객체가 큰 경우 이는 상당한 성능 저하 요인이 된다. Ropes for Java는 큰 문자열 객체를 염두에 두고 설계되었기 때문에 더 나은 해법을 제공한다.

성능 향상을 위해 Rope 클래스에는 Writer와 범위 명세를 받아 로프 내 명시된 범위를 주어진 Writer에 출력하는 write 메서드를 제공한다. write 메서드를 사용하면 로프에서 문자열을 만드는 시간과 메모리 낭비를 없앨 수 있는데 큰 로프의 경우 효과가 매우 크다. Listing 4에 로프를 출력하는 표준 방법과 향상된 방법을 함께 나타냈다.


Listing 4. Rope를 출력하기 위한 두 가지 방법
                
out.write(rope);
rope.write(out);

표 4는 길이 10,690,488, 깊이 65에 내부에 메모리 버퍼를 사용하는 로프를 스트림에 출력한 벤치마크 결과다. 여기선 시간상 절약된 부분만 보였지만 임시로 할당되는 힙 공간을 줄인 효과는 더욱 크다.


표 4. 로프의 출력 성능
기법시간(ns)
out.write 75,136,884
rope.write 13,591,023



위로


문자열 변형 성능 벤치마킹

이 론적으로 로프를 변형하는 것이 문자를 연속으로 저장한 문자열 표현을 변형하는 것보다 훨씬 빠르다. 반면 앞서 살펴본 것처럼 로프 내 문자를 순서대로 읽는 경우는 그 때문에 더 느릴 수 있다. 이번에는 Ropes for Java의 변형 성능을 StringStringBuffer 경우와 비교해 보겠다.

모든 테스트는 프로젝트 구텐베르크의 전자책, A Christmas Carol(12만 8029바이트)로 초기화한 뒤 이어 일련의 변형을 가했다. 로프 자료 구조가 변형 횟수 변화에 얼마나 잘 대응하는지를 보기 위해 대부분의 경우 변형 횟수를 20에서 480회까지 변경했다(그림 2, 3, 4에 plan length가 이 횟수를 가리킨다). 각 테스트는 일곱 번 수행했고 그 평균값을 구해 기록하였다.

문자열 삽입 벤치마크

문자열 삽입 벤치마크에서는 이전 테스트 결과에서 무작위로 부분 문자열을 추출한 뒤 해당 문자열의 임의 위치에 삽입했다. 그림 2에 벤치마크 결과를 보였다.


그림 2. 문자열 삽입 벤치마크 결과
문자열 삽입 벤치마크 결과

StringStringBuffer 모두 벤치마크를 끝내는 데 걸리는 시간이 기하급수적으로 증가한다. 반면 로프는 뛰어난 결과를 보여준다.

문자열 추가 벤치마크

문자열 추가 벤치마크에는 주어진 문자열의 임의 부분을 바로 그 문자열 뒤에 추가한다. 이 테스트 결과는 StringBuffer가 문자열 추가를 빨리 할 수 있도록 최적화되어 있기 때문에 흥미롭다. 그림 3이 벤치마크 결과다.


그림 3. 문자열 추가 벤치마크 결과
문자열 추가 벤치마크 결과

그림 3의 그래프에서는 String이 형편없는 성능 때문에 Rope와 StringBuffer 간의 차이가 명확히 보이지 않지만, 예상한 대로 StringBuffer의 성능이 매우 높다.

그림 4는 동일한 테스트에서 String을 빼고 RopeStringBuffer 간의 더 명확한 비교를 위해 차트의 배율을 재조정하였다.


그림 4. String을 배제한 문자열 추가 벤치마크 결과
문자열 추가 벤치마크 결과
로프의 불변성(不變性, immutability)이 지니는 함정

Rope 클래스는 내용을 바꿀 수 없도록 설계되어 있다. 이는 변형 함수가 원본 Rope 객체를 수정하지 않고 수정된 복사본을 돌려준다는 뜻이다. 불변성에는 여러 이점이 있는데, 가장 큰 이점은 멀티스레드 환경에서 별 주의하지 않고도 Rope 객체를 공유할 수 있고 그 때문에 프로그램 논리가 아주 단순해진다는 점이다.

Ropes for Java는 주어진 CharSequence에 서 로프를 생성한다. CharSequence가 인터페이스이므로 상당한 유연성이 있다. 즉 디스크 상의 파일, 메모리 버퍼, 원격 서버에 저장된 문서 등 이질적인 소스에서 로프를 생성할 수 있다. 하지만 수정되지 않는 것이 보장되는 String과 달리 CharSequence는 구현에 그런 제약을 두지 않는다. 로프 생성에 사용한 문자열이 해당 로프가 사용되는 동안은 사실상 변경되지 않는다는 것을 보장하는 것은 프로그래머 몫이다.

그림 4에서는 그림 3에서 명확하지 않았던 RopeStringBuffer 간의 두드러진 차이를 볼 수 있다. Rope가 겨우 x축 위로 올라가는 데 비해, StringBuffer는 완만하게 증가하는 대신 급격히 증가한 뒤 상승세가 둔화된다(연습 삼아 다음 단락을 읽기 전에 왜 그런지를 생각해 보자).

그 이유는 StringBuffer가 메모리 영역을 할당하는 방식과 연관이 있다. StringBuffer는 효율적으로 문자열을 추가하기 위해 내부 배열 끝에 여분의 공간을 할당한다. 하지만 이 여분을 소진하면 새로운 배열을 할당하고 모든 데이터를 새 배열로 복사해야 한다. 이 때 새 배열은 보통 현재 길이의 두 배로 할당한다. 결국 문자열 추가 횟수가 늘어나면서 StringBuffer의 길이도 따라서 증가하고, 내부 버퍼 한계치에 이르면 내부 버퍼를 키우고 데이터를 복사하면서 소요 시간이 급격히 증가한다. 그 후 몇 차례는 문자열을 추가하더라도 시간 증가세가 둔화된다. 즉 소요 시간이 서서히 증가한다. 각 추가 시 총 문자열 길이는 대략 같은 분량만큼 증가하므로 연이은 증가세 둔화 구간 사이의 비율로 내부 배열 크기를 키워야 하는 비율을 결정할 수 있다. 위 결과를 바탕으로 할 때 테스트에 사용된 StringBuffer 구현의 경우 대략 1.5다.

결과 요약

지금까지 그래프를 이용해 Rope, String, StringBuffer 간 성능 차이를 살펴 봤다. 표 5는 모든 벤치마크에 대해 480번 반복했을 때 수행 시간을 정리한 것이다.


표 5. 일회 테스트당 480회 반복할 경우의 변형 작업 소요 시간 평균치, 삭제 작업 결과 포함
변형 작업/자료 구조소요 시간(ns)
Insert  
String 18,447,562,195
StringBuffer 6,540,357,890
Rope 31,571,989
Prepend  
String 22,730,410,698
StringBuffer 6,251,045,63
Rope 57,748,641
Append  
String 23,984,100,264
StringBuffer 169,927,944
Rope 1,532,799
Delete (원본 텍스트에서 임의 범위를 230회 삭제)  
String 162,563,010
StringBuffer 10,422,938
Rope 865,154

참고자료에 벤치마크 프로그램을 링크해 뒀다. 각자 플랫폼에서 직접 돌려보고 여기 보인 결과를 직접 확인해 볼 것을 권장한다.




위로


정규식 성능 최적화

JDK 1.4에서 소개된 정규식은 많은 애플리케이션에서 널리 사용되는 기능이다. 따라서 정규식이 로프에 사용될 때 잘 동작하는 게 매우 중요하다. 자바에서 정규식은 Pattern 객체로 나타낸다. 임의의 CharSequencePattern을 매치하려면 해당 Pattern 객체를 이용하여 해당 Matcher를 인자로 줘서 Matcher 객체를 생성해야 한다.

CharSequence를 입력으로 받는다는 사실은 자바 정규식 라이브러리에 상당한 융통성을 주지만, 반대로 심각한 결점이 되기도 한다. CharSequence는 문자를 읽기 위해 charAt 메서드를 하나만 제공한다. 개요 부분에서 언급했듯이 내부 노드가 많은 로프 내 임의의 문자를 읽는 데는 대략 O(log n) 시간이 필요하다. 그래서 전체를 훑는 데 O(n log n) 시간이 소요된다. 이에 따른 문제점을 나타내기 위해 길이가 10,690,488인 문자열에서 "Crachit*"이라는 패턴에 맞는 모든 부분을 찾는 데 걸리는 시간을 벤치마크했다. 테스트에 사용한 로프는 문자열 삽입 벤치마크와 같은 변형을 해 만들었고 깊이가 65다. 표 6이 그 결과다.


표 6. 정규식을 이용한 검색 소요 시간
기법시간 (ns)
String 75,286,078
StringBuffer 86,083,830
Rope 12,507,367,218
Rebalanced Rope 2,628,889,679

명백히 Rope이 매칭 성능은 나쁘다(정확히는 내부 노드가 많은 Rope의 경우 그렇다. 평평한 로프의 경우 성능은 하부 문자 표현 방식과 거의 같다). 심지어 내부 구조의 균형을 맞춰 놓은 Rope의 경우 매칭이 3.5배 빠르기는 해도 여전히 String이나 StringBuffer에 비할 바가 아니다.

상황을 개선하려면 Matcher에서 Rope 반복자가 제공하는 훨씬 빠른 O(1) 접근 시간을 활용해야 한다. 어떻게 그럴 수 있는지를 이해하려면 먼저 MatcherCharSequence를 사용하는 방식을 알아야 한다.

정 규식을 매칭하는 데 있어 가장 흔한 시나리오는 문자열 특정 위치에서 시작해서 일치하는 모든 부분을 발견하고 문자열이 끝날 때까지 계속 전진하는 것이다. 이 시나리오에서 Matcher는 때론 한 문자 이상씩 주로 문자열 끝을 향해 움직인다. 하지만 종종 뒤로 거슬러 가기도 해야 한다.

Rope 반복자를 한 번에 한 문자 이상 건너 뛸 수 있도록 수정하기는 쉽다. 하지만 반복자가 내부적으로 깊이 우선(depth-first), 전순위(preorder)로 Rope를 훑어가면서 각 최종단 노드(leaf node)를 짚어가기 때문에 반대로 움직이는 것이 더 복잡하다. 노드를 훑기 위한 스택은 이전 최종단 노드로 돌아가기에 충분한 정보를 담고 있지 않다. 하지만 뒤로 움직여서 반복자가 현재 처리 중인 최종단 노드를 벗어나지 않으면 뒤로 돌아가는 데 문제가 없다. 예를 들어 설명하면 그림 5는 뒤로 하나나 둘, 셋, 넷만큼만 움직일 수 있는 가상적인 반복자의 상태를 나타낸 것이다. 더 이상 뒤로 가면 이전에 처리한 최종단 노드를 읽어야 하므로 그 이상 뒤로 움직일 수는 없다.


그림 5. 예제 iterator 상태
예제 iterator 상태

이 새 기능을 지원하기 위해 RopecharAt 메서드를 다음과 같이 수정할 수 있다. 처음 호출됐을 때 지정한 위치에 반복자를 생성하고, 그 뒤부터는 반복자를 필요한 만큼 앞 뒤로 움직인다. 만약 반복자가 지정한 만큼 뒤로 못 움직이면 문자를 읽기 위해 원래 charAt 루틴을 실행한다. 당연하지만 이 상황이 거의 안 일어나길 기대한다.

이 최적화는 정규식 외에 일반적인 경우 적용할 수 없고 새 멤버 변수가 있어야 해서 Rope 클래스에 직접 추가하지는 않는 것이 좋다. 대신 로프를 필요한 경우만 이 최적화를 추가하면 된다. 이 때문에 Ropes for Java의 Rope 클래스에는 명시한 패턴에 최적화된 Matcher를 돌려주는 메서드가 있다. Listing 5에 예를 보였다.


Listing 5. 최적화된 정규식 매칭
                
Pattern p = ...
Matcher m = rope.matcher(p);

정규식 매칭을 최적화하기 위해 Listing 5 두 번째 줄의 메서드 호출에서 주어진 Rope에 최적화를 추가한 것이다.

표 7은 이 방식을 사용할 때 벤치마크 결과를 나타낸 것으로 명확한 비교를 위해 표 6에 나타낸 이전 결과와 함께 표시한 것이다.


표 7. rope.matcher()를 사용하여 정규식을 검색한 결과
기법시간(ns)
String 75,286,078
StringBuffer 86,083,830
Rope 12,507,367,218
Rebalanced Rope 2,628,889,679
Rope.matcher 246,633,828

최적화 결과 균형을 맞춰둔 로프에서 10.6배라는 주목할 만한 개선을 이뤄 String보다 3.2배 이하 시간에 처리하는 수준을 달성했다.




위로


적용 범위

부적절한 로프 사용

엔터프라이즈 자바 애플리케이션에서는 종종 다음과 비슷한 코드가 발견된다.

String x = "<input type='text' name='name' value='" 
+ escapePcData(bean.getName()) + "'>";

x 는 HTML 페이지의 일부분으로 클라이언트 브라우저로 전송된다. x 를 계산하기 위해 컴파일러가 기본으로 생성하는 StringBuilder 대신 로프를 사용하는 게 낫지 않을까?

여러 이유로 정답은 "아니오"다. 우선 연결되는 데이터 양이 작고, 그래서 로프를 사용하는 경우 비록 신뢰도와 부하 증가에 대한 적응성이 좋아질 수는 있어도 성능 향상을 볼 가능성이 낮다(getName이 예상 밖에 50MB 문자열을 돌려준다면 양쪽 각각의 경우 어떤 결과를 낳을까 생각해 보라).

논지를 이어가기 위해 더 많은 데이터 조각을 연결한다고 생각해 보자. 문자열을 추가하는 데 있어 보통 RopeStringBuffer보 다 나으니 로프를 쓰는 편이 나을까? 이번에도 "아니오"다. 입력 데이터가 결합돼 포맷된 출력을 낼 때마다 가장 깔끔하고 효과적인 방법은 StringTemplate이나 FreeMaker 같은 템플릿 엔진을 사용하는 것이다. 표현을 위한 마크업을 코드와 깨끗하게 분리할 뿐 아니라 템플릿은 한번 컴파일되면(대체로 JVM 바이트코드로) 재사용할 수 있어 높은 성능을 얻을 수 있다.

템플릿을 사용해 얻는 두 번째 이득은 로프를 사용하는 경우를 포함해 위 예제처럼 출력을 만드는 루틴에 일반적인 근본적인 결점을 알게 해 준다는 점이다. 템플릿은 점진적으로 처리될 수 있고 출력은 불필요하게 먼저 메모리에 쌓을 필요 없이 생성되는 족족 Writer에 출력될 수 있다. Writer가 클라이언트 브라우저로의 버퍼링된 연결인 자바 EE 애플리케이션에서 이 방식은 고정된 분량의 메모리, 즉 O(1) 메모리를 사용한다. 반면 다른 경우 O(n) 메모리를 사용한다. 작은 입력이나 로드가 낮을 때는 명확하지 않아도 이는 애플리케이션이 처리 규모에 적응하는 정도와 신뢰도에 매우 큰 향상을 준다(참고자료에 이 방법을 상세히 설명하고 정량화한, 스트리밍 구조에 대한 글 두 개의 링크가 있으니 참고한다).

이제 로프의 성능 특성에 대해 잘 이해하게 됐을 것이다. 이제 로프를 사용한 전통적인 용례를 살펴보고 아울러 자바 EE 애플리케이션에서 로프에 잘 맞을 것 같으면서도 통상 부적절한 경우를 함께 살펴보겠다.

로 프는 범용 문자열 표현으로 연속된 메모리를 사용하는 문자열 형식을 대체할 수 있지만 큰 문자열을 대규모로 처리하는 애플리케이션에서나 눈에 띄는 성능 개선을 볼 수 있다. 이쯤 되면 초기에 로프를 적용한 예 중에 텍스트 편집기에서 문서를 표현하기 위해 사용한 예가 있다는 것이 그다지 놀랍지 않을 것이다. 거의 고정 시간에 방대한 문서에 대한 텍스트를 삽입, 삭제할 수 있을 뿐더러 내용이 변경되지 않는 로프의 특성으로 작업 취소 스택(undo stack) 구현이 간단하다. 즉 변경할 때마다 이전 로프에 대한 참조를 저장하기만 하면 된다.

또 다른 더 독특한 적용 예는 가상 기계 상태를 표현하는 데 사용한 것이다. 예를 들어 ICFP 2007 프로그래밍 경진대회에서는 상태를 사이클마다 변경하고 어떤 입력에 대해 수백만 사이클 동안 동작하는 가상 기계를 구현해야 했다(참고자료를 참조하라). 자바 구현 하나는 상태 표현을 수정한 StringBuffer 구현을 사용하는 대신 Rope를 사용해 가상 기계 속도를 초당 50 사이클 이하에서 초당 5만 사이클 이상으로 1000배 가량 향상시켰다.

향후 연구 방향

Ropes for Java가 새로운 라이브러리이기는 하나 개념 자체는 오래된 것이고, 로프 자체가 보장하는 성능을 제공하기 위해 만들어졌다. 하지만 추후 버전에서 다음 작업을 통해 라이브러리의 일부 측면을 향상시키려고 계획하고 있다.

  • 다른 보편적인 문자열 작업의 고성능 구현을 제공

  • 로프를 Scala(참고자료를 보라)나 자바 플랫폼 상의 다른 발전된 언어에 말끔하게 통합하기 위한 어댑터를 작성

  • 추가적인 자동화된 테스트로 품질을 향상. Rope for Java는 수작업으로 작성된 자동화된 JUnit 테스트와 JUnit Factory를 이용해 자동으로 생성된 테스트로 테스트된다. ESC/Java2(참고자료를 보라)로 체크되는 자바 모델링 언어(JML) 애노테이션(annotation)은 품질을 더욱 향상시킬 수 있을 것이다.


참고자료

교육
  • Ropes for Java: 프로젝트 웹 사이트

  • "Ropes: an Alternative to Strings" (Hans-J. Boehm, Russ Atkinson, and Michael Plass, Software Practice & Experience, 1995년 12월): 로프 자료 구조에 대한 소개의 결정판

  • Big-O notation: 계산의 복잡도 이론에서는 입력 데이터 크기가 알고리즘의 계산 자원 사용에 미치는 영향을 나타내기 위해 big-O 표기법을 쓴다.

  • The 10th ICFP Programming Contest: 이 경진대회에서 저자가 속한 팀이 Ropes for Java의 생산성을 시연했다.

  • "Streaming Architecture"와 "Streaming Presidents" (Amin Ahmad, Ahmadsoft.org): 스트리밍 아키텍쳐에 대한 상세한 설명과 정량화

  • Scala 프로그래밍 언어: JVM에서 동작하는 함수형 프로그램 언어

  • JUnitJUnitFactory: Ropes for Java는 JUnitJUnitFactory를 써서 테스트한다.

  • JMLESC/Java2: ESC/Java2는 JML 애노테이션을 단 자바 프로그램에서 일반적인 실행 시간 오류를 찾아 주는 프로그래밍 도구다.

  • 이 주제 또는 다른 기술적인 주제를 다루는 책을 서점에서 찾아 보라.

  • 한국 developerWorks의 자바 코너: 자바 프로그래밍의 여러 관점에 대한 수백 가지의 자료를 찾아 보라.


제품 및 기술 얻기
  • Ropes for Java: 최신 배포판을 다운로드할 수 있다.

  • PerformanceTest.java: 본 문서에서 변형 작업의 성능을 테스트하기 위해 사용한 성능 벤치마크 코드다. 본 코드를 다운로드해 실행하면 각자의 플랫폼에서 각자의 결과를 얻을 수 있다.

  • IBM 제품의 평가판을 다운로드하여 DB2®, Lotus®, Rational®, Tivoli®, WebSphere®에서부터 애플리케이션 개발툴과 미들웨어 제품을 사용해 보라.

토론


필자소개


Amin Ahmad는 독립 컨설턴트이자 Ahmadsoft, LLC의 대표로 재직 중이다. 고성능 엔터프라이즈 자바 시스템을 고객에 제공하는 데 초점을 맞춰 7년 이상의 자바 컨설팅을 수행한 경험이 있다.