3장 Vectors and Hashtables - Java Performance and Scalability

원문 : http://www.mobilejava.co.kr/bbs/temp/lecture/j2me/perf3.html

※이 문서는 『Java Performance and Scalability Volume1』(by Dov Bulka)라는 책의

3장:Vectors and Hashtables 를 읽고 나름대로 정리한 것입니다.

 

1. Vector Add and Remove

 

Vector 클래스에 엘리먼트를 추가하는 방법에는 여러가지가 있다(Java2의 경우).

 ◇ insertElementAt(e, index)

 ◇ add(index, e)

 ◇ addElement(e)

 ◇ add(e)

이러한 메소드들은 서로 같지 않고, 각각의 성능 특성에는 많은 차이가 있다.

add(e)와 addElement(e)는 Vector의 끝 부분에만 엘리먼트를 삽입하고, 나머지 두 메소드는중간의 어느 부분에라도 엘리먼트를 삽입할 수 있다. 엘리먼트들은 메모리에 인접해서 존재하기 때문에 중간에 엘리먼트를 삽입하기 위해서는 삽입 부분부터 끝부분까지를 밀어내고 삽입을 위한 새로운공간을 만들어 주어야 한다(Vector의 엘리먼트는 내부적으로 배열에 들어있다). 

그러므로 성능면에서 본다면 엘리먼트를 삽입하기 위한 가장 좋은 장소는 Vector의 끝 부분이고 가장 나쁜 장소는 앞부분이다. 당신이 Vector의 끝 부분보다 중간 부분에 엘리먼트를 삽입하는 일이 자주 있다면 당신은잘못된 자료 구조를 사용하고 있는 것이다.

 실제로 비교를 해보자. 예제1은 1000개의 엘리먼트를 끝 부분에 추가한다.

(예제1) 수행시간 : 750 ms

public void add1000(Vector v, String s){

for(int i = 0 ; i<1000 ; i++){

      v.addElement(s);

}

}

일단 여기서는 add(e)보다 addElement(e)를 사용하였다. 전자는 boolean 값을 리턴해야 하지만후자는 리턴값이 없으므로 후자가 아주 약간 더 빠르기 때문이다.

예제2는 1000개의 엘리먼트를 맨 앞 부분에 추가한다.

(예제2) 수행시간 : 5,400 ms

public void add1000AtFront(Vector v, String s){

for(int i = 0 ; i<1000 ; i++){

      v.insertElementAt(s,0);

}

}

결과를 보면 수행시간에 많은 차이가 있음을 알 수 있다.

Vector에서 엘리먼트를 삭제할때도 마찬가지이다. 끝에서 엘리먼트를 삭제하는 것이 가장 싼 작업이고, 중간부분에서 삭제하는 것은 앞 부분으로 갈수록 점점 비싼 작업이 된다. 당신이 종종Vector의 끝 부분이 아닌 중간 부분에서 엘리먼트를 삭제한다면 당신은 잘못된 자료 구조를 사용하고 있는 것이다.

 

2. Vector Capacity

  

벡터의 엘리먼트는 내부적으로 배열에 저장되어 있다. 기본적으로 객체가 생성되면 배열의 크기는10이 된다. 만약에 엘리먼트가 늘어나서 엘리먼트의 갯수가 10을 넘어가면 디폴트로 2배의 크기가되는 배열을 새로 생성하고 이전의 값들을 새로운 배열에 복사한 후 새로운 배열을 사용한다. 이전의배열은 가비지 컬렉터의 대상이 되면서 버려진다. 이렇듯, 벡터 크기를 확장 시키는 것은 매우 비싼작업이다.

일단 생성자들을 살펴보자.

       Vector v = new Vector();

 이렇게 생성을 한다면 초기 용량은 10 이 되고 확장이 일어나면 매번 두배씩 용량이 늘어난다.

       Vector v = new Vector(1000);

 이 경우 초기 용량은 1000 이 되고 확장시 디폴트로 2배씩 확장된다. 또 다른 방법으로 초기용량(initial capacity)과 용량 증가분(capacity increment)을 지정할 수 있다.

       Vector v = new Vector(100,25);

초기 용량은 100 이 되고 매 확장시 25개씩 용량이 늘어난다.

 

  성능 관점에서 본다면 가장 중요한 것은 초기용량과 증가분이다.

초기 용량을 정하는데 있어서 목표는 Vector가 ‘확장’되는 것을 최소화 시키는 것이다. 아마도초기용량을 충분히 지정해서 확장이 일어나지 않도록 하는 것이 가장 이상적일 것이다. 그러므로 디폴트 생성자를 그대로 사용하는 건 좀 문제가 있다. 대부분 크기를 예측할 수 있으므로 객체 생성시그 값을 사용하는 것이 좋다.

 증가분에 대해서 생각해보자. Vector 생성시 과연 이 값을 지정해 주어야 할까? 답은 ‘NO’이다.지정하지 않고 그대로 놔둔다면 디폴트로 2배씩 기하급수적으로 늘어난다. 단순히 산술적인 값을 지정하는 것보다 당연히 더 빠를 것이다. 테스트를 해보자.

       Vector v1 = new Vector();        (1)

       Vector v2 = new Vector(10,10);   (2)

       Vector v3 = new Vector(1000);    (3)

(1),(2),(3)을 가지고 앞절의 add1000() 메소드를 1,000번씩 호출해 보았다.

       (1)의 수행시간 : 870 ms

       (2)의 수행시간 : 4,400 ms

       (3)의 수행시간 : 750 ms

 예상대로 확장할 필요가 없는 (3)이 가장 좋은 성능을 보였다. 나머지를 살펴보자. (1)의 경우 초기용량이 10이고 확장시 두배씩 증가하므로 1000개 이상 확장하기 위해서는 7번만 확장하면 된다.그러나 (3)의 경우 10개씩 확장되므로 1000개까지 확장하기 위해서는 무려 100번의 확장이 필요하게 된다.

 결과적으로 전체 용량을 예측할 수 있으면 Vector 객체 생성시 예상되는 크기값을 지정해주고, 증가분은 그냥 디폴트로 놔두는 것이 좋다는 것을 알 수 있다.

 

 

3. Vector Enumeration

  

Vector의 엘리먼트를 가지고 반복문을 실행하는 방법에도 여러 가지가 있다. 두가지 방법을 살펴보자.

(1)  int size = v.size();

for (int i= 0 ; i<size; i++){

        s = (String)v.elementAt(i);

        //do something

}

(2) for (Enumeration enum = v.elements() ; enum.hasMoreElements(); ){

        s = (String)enum.nextElement(i);

        //do something

     }

실행 루틴을 분석해보자.

	(1)	(2)
초기화	i = 0	Enumeration enum = v.elements()
종결조건	i < size	enum.hasMoreElements()
객체추출	v.elementAt(i); i++;	enum.nextElement(i)

 

Vector.java 의 소스 코드를 살펴보면 초기화 부분은 굳이 측정해보지 않더라도 (1)이 (2)보다빠르다는 것을 알 수 있다. elements() 메소드는 새로운 Enumeration 객체를 생성하여 넘겨준다. 그리고 Enumeration 객체는 반드시 초기화되어야 하는 count(int)라는 private 멤버도 가지고 있다. 당연히 (1)이 더 빠를 것이다.

종결조건에 있어서 두가지 다 Vector의 엘리먼트 수를 가지고 비교하지만 (2)처럼 메소드를 호출하는 것보다는 바로 비교하는(1)이 더 빠르다.

마지막으로 다음 객체를 추출하는데도 (1)이 (2)보다 빠르다. nextElement() 메소드는 현재 위치의 객체를 가져오고 count를 하나 증가시켜야 하므로 좀 더 느리다.

결과적으로 Enumeration을 이용하여 반복문을 실행하는 (2)가 단순 인덱스를 사용하는 (1)보다는 느리다. 그렇지만 (2)를 조금은 향상 시킬 수 있다.

(3) try{

for (Enumeration enum = v.elements() ; ; ){

          s = (String)enum.nextElement(i);

         //do something

       }

}catch(NoSuchElementException e){}

위와 같이 실행한다면 종결조건이 생략되므로 (2)보다는 조금 빨라진다.

(1),(2),(3)에 대해서 1000개의 String 엘리먼트를 가지고 있는 Vector를 가지고 각각 1000번씩 루프를 돌려보면 수행시간은 (1)이 570ms, (2)가 620ms, (3)이 570ms 가 된다.

 예상대로 (1)이 (2)보다는 빠르지만 주어진 소스는 루프내에서 간단한 작업만 하므로 3가지가 그다지 차이가 많이 나지는 않는다. 루프내에서 복잡한 작업을 수행하도록 한다면 성능차이가 많이 난다는 것을 알 수 있을 것이다.

 

4. Efficient Vector Class

 

Vector.java 에서 성능만을 고려했다면 아마 elementAt()이라는 메소드는 다음과 같았을 것이다.

   public Object elementAt(int index){

     return elementData[index];

   }

 그러나 실제로 Vector 클래스는 인덱스 값이 Vector의 크기보다 작은 값인지 체크도 하고 동기화까지도 구현한다.

 만약에 호출자가 Vector의 size를 알고 있다면 elementAt()에서의 범위체크는 불필요한 것이다.게다가 Vector가 멀티 쓰레드 환경에서 쓰이지 않는다면 동기화는 CPU 싸이클의 또다른 낭비가 된다.

 Java2 에서는 Vector에서 동기화가 빠진 ArrayList라는 클래스를 제공한다. 그래서 만약에 단일쓰레드 환경이라면 우리는 Vector 대신 ArrayList를 사용해야 한다. Vector는 멀티 쓰레드 환경에서만 유리하다. 그러나 ArrayList에도 범위 체크라는 오버헤드는 여전히 남아있다.

 

 Vector 클래스가 가지고 있는 또다른 문제점은 다음의 몇가지 메소드를 수행하기 위해서 엘리먼트를 처음부터 끝까지 다 훑어야 한다는 점이다.

 ◇ contains()

 ◇ indexOf()

 ◇ lastIndexOf()

 ◇ removeElement()

 ◇ remove()

 ◇ removeAllElements()

 ◇ clear()

이러한 것들은 다 비싼 작업이며, 그 비용은 Vector의 size에 비례할 것이다.

(책에서는 이러한 문제점들을 바탕으로 좀 더 효율적인 Vector 클래스를 작성하였지만 여기에서는생략하였다.)

 

5. Hashtable Parameters

 

Hashtable은 일련의 bucket들로 이루어져 있다. 각각의 버킷은 key-value 쌍으로 이루어진 링크드 리스트를 담고 있다. 키-값 쌍이 Hashtable에 삽입되면 이 쌍은 key객체의 hashCode()라는메소드가 리턴하는 값에 따라 특정 버킷을 부여받고 그 버킷의 링크드 리스트에 추가된다. 

비슷한 방법으로 키를 가지고 값을 찾아내고자 할 때는 먼저 버킷의 위치를 알기 위해 키 객체의 hashCode()가 계산되고 이 값으로 버킷을 찾아간다. 그런 다음 키값이 일치하는 것을 찾기 위해 버킷에 있는 링크드 리스트를 선형 검색한다. 

주어진 키와 링크드 리스트에 있는 키값을 비교하기 위해서는 키 객체의 equals() 메소드가 사용된다. 일치하는 것을 찾게되면 해당 값을 리턴한다. 

(주: 간단한 빌라를생각해보면 쉽다. 층(버킷)마다 한 가구씩 산다. 때로는 한 층에 여러 가구가 살 수도 있다(링크드리스트). 누군가가 새로 입주를 한다면 층수(키)를 지정해 줄 것이다. 방문객이 찾아와서 누구누구를찾아달라고 한다면 일일히 찾아볼 필요없이 그 사람의 층수(hashCode이용)를 찾아보고 층수만 가르쳐 주면 된다. 만약에 한 층에 여러 가구가 산다면 들어가서 일일히 물어봐야 한다(선형 검색).)

 이해가 됬다면 이제는 Hashtable의 성능에 영향을 주는 요인들을 찾아낼 수 있다.

 

◇ 선형 검색 : 버킷에 들어있는 링크드 리스트는 가능하면 짮을 수록 좋을 것이다.

◇ hashCode() : put() 또는 get() 하기 위해서는 언제나 키 객체의 hashCode()가 계산되어야한다. 그러므로 키 객체의 hashCode()의 성능은 매우 중요하다.

◇ equals() : 선형검색시 매번 호출된다. 효율적이어야 한다.

 

(1) 버킷의 링크드 리스트의 길이는 가능한 짧을수록 좋다. 그러기 위해서는 객체가 삽입될때 동일한버킷으로 삽입되는 일은 가능하면 없어야 한다. 이는 곧 키의 hashCode() 값이 가능하면 넓게 분포되는 것이 좋다는 말이다. 

만약에 String의 hashCode()가 처음 네개의 문자만을 계산한다면 어떻게 될까? 그렇다면 첫 4자가 같은 키는 항상 같은 버킷에 존재할 것이다. 그런 이유로String.hashCode()는 String의 모든 문자를 가지고 계산한다.

 

(2) 링크드 리스트의 길이는 결정하는 또하나의 요인은 초기 용량(capacity)과  부하율(load factor)이다. Hashtable의 초기 용량은 곧 버킷의 수이다. 부하율은 현재의 버킷이 얼마만큼 찼을때 버킷의 수를 두배로 늘릴것인가(rehashing)하는 것이다. 예로 디폴트 생성자를 사용했다면

   Hashtable ht = new Hashtable();

초기 용량은 101이고 부하율은 0.75이다. 그러므로 리해쉬가 되는 경계선은

  threshold = 101*0.75 ; //initial_capacity * load_factor

가 된다. 버킷에 들어있는 엘리먼트의 수가 이 값을 넘어서면 버킷을 두배로 늘리고 키들을 재분배하는 rehash 작업이 이루어진다. 일반적으로 부하율은 1.0을 넘을 수 없으므로 버킷보다 많은 엘리먼트를 넣을 수는 없다. 엘리먼트의 수가 버킷의 수를 넘는다면 몇몇 링크드 리스트들은 한개 이상의엘리먼트를 가지고 있을 것이다. 디폴트 값인 0.75는 합리적인 값이며 수정할 필요는 없다고 본다.

 

(3) 링크드 리스트를 선형 검색할 때 우리는 리스트에 있는 각각의 키의 equals() 메소드를 호출한다. 만약에 equals()메소드가 굉장히 느리다면 리스트의 갯수가 하나만 있더라고 성능에 치명적인영향을 줄 수 있다.

 

(4) 앞에서도 살펴봤듯이 rehash 는 굉장히 비싼 작업이다. 가능하면 초기 용량을 충분히 주어서rehash()가 일어나지 않도록 하는 것이 제일 중요하다.

       Hashtable ht = new Hashtable(initial_capacity);

 위와 같이 hashtable을 생성한다면 부하율은 0.75 이므로 초기용량의 75%가 차게 되면 rehash가 일어난다. 그러므로 우리가 들어가야할 엘리먼트의 수를 예상할 수 있다면 초기 용량을 예상 엘리먼트 수의 1.33배(1/0.75)이상으로 지정해 주면 절대로 rehash가 일어나지 않는다. 예상되는 갯수가 9개 라면 “9×(4/3)=12” 이상으로 초기값을 잡는 것이 좋을 것이다.