gimmesilver's blog

Agbird.egloos.com

포토로그



벤치마크 테스트와 알고리즘 프로그래밍

 http://shootout.alioth.debian.org/ 라는 사이트가 있습니다. 다양한 프로그래밍 언어를 대상으로 여러 가지 측면에서 실행 시간과 메모리 사용량 등을 측정한 결과 및 언어 간 비교값을 제공합니다. 성능 측정을 위한 문제가 다양하고 여러 플랫폼에서 테스트를 했기 때문에 비교적 객관적인 수치를 알 수 있을뿐더러 각 문제에 대한 언어 별 구현 소스도 볼 수 있어 괜찮은 사이트입니다.

 위 사이트의 성능 측정 항목 중에 스레드 성능을 측정하는 항목이 있습니다. 스레드를 503개 생성해서 10,000,000번 차례로 순환하면서 동기화된 데이터에 접근하는데 걸리는 시간을 측정하는 문제인데 스레드 생성, 전환, 데이터 동기화 성능을 측정하는 것이 주된 목적입니다. 결과 순위를 보시면 아시겠지만 하스켈과 얼랭의 성능이 앞도적입니다. 커널 스레드를 사용하는 C 보다 8배나 빠르며 자바나 스크립트 언어들에 비해서는 수십 배 이상 빠릅니다. 그리고 그 이유는 하스켈과 얼랭 둘다 자체 언어 시스템에서 제공하는 경량 스레드를 사용하는데 둘다 커널 스레드보다 생성,전환에 필요한 오버헤드가 무척 적기 때문입니다.

 그런데 지난 주에 우연히 사이트에 들어가봤는데 JAVA6 가 전체 순위에서 몇 단계 상승되어 있었습니다. 살펴보니 스레드 성능이 비약적으로 높게 측정되어 있더군요. 무려 하스켈이나 얼랭보다 스레드 성능이 수십 배나 빠르다고 나와 있었습니다. 놀라서 구현 소스를 봤더니 상당히 tricky한 구현을 했더군요. 정확히 기억나진 않습니다만 대략 다음과 같은 방법이었습니다.

class ThreadTest {
  class Scheduler extends Thread {
    private int token;
    private ArrayList<CooperativeThread> threads = new ArrayList<CooperativeThread>();

    public Scheduler(int token) { this.token = token; }
    public void add(CooperativeThread t) { threads.add(t); }
    public void run() {
        int i = 0;
        while (true) {
            token = threads.get(i++).run(token);
            it (i >= threads.length)
                i = 0;
        }
    }
  }

  class CooperativeThread {
    public int run(int token) {
        if (--token == 0)
            System.exit(0);
        return token;
    }
  }

  public static void main(String[] args) {
      final int THREAD_CNT = 503;
      Scheduler scheduler = new Scheduler(10000000);
      for (int i = 0; i < THREAD_CNT; ++i) {
          scheduler.add(new CooperativeThread());
      }
      scheduler.start();
  }
}

 눈치채신 분도 계시겠지만 실제 CooperativeThread 는 스레드가 아니고 Scheduler 객체만 스레드로 실행되면서 차례대로 CooperativeThread 에 등록된 작업을 수행하도록 되어 있습니다. 위 Scheduler 방식대로라면 스레드간의 전환이나 동기화에 걸리는 오버헤드가 전혀 없기 때문에 대단히 빠른 속도로 CooperativeThread.run()를 실행시켜서 결과값을 얻어낼 수 있습니다.
 더 재미있는 것은 해당 사이트의 스레드 성능 결과 페이지 하단에는 다음과 같은 코멘트가 있습니다.

Programs may use kernel threads, lightweight threads… cooperative threads… and other programs with custom schedulers will be listed as interesting alternative implementations. Briefly say what concurrency technique is used in the program header comment.

 한마디로 하스켈이나 얼랭도 어차피 커널 스레드 사용안하고 자체 경량 스레드를 썼으니 나도 자체 구현 스레드를 사용하겠다는 것이죠...뭐 맞는 말이긴 하지만 실제 저 자바 구현물은 스레드 전환이나 데이터 동기화에 필요한 기능이 전혀 구비되어 있지 않으므로 일반적인 스레드라 할 수 없기 때문에 억지입니다. 아마도 그래서인지 지금은 해당 소스가 지워졌고 순위도 원래대로 재조정되었습니다.

 잠깐의 헤프닝이었지만 여기서 얻을 수 있는 교훈 두가지...
 1. 테스트는 맘먹고 속이려 들면 얼마든지 속일 수 있다. - 반대로 이야기하자면 한 가지 테스트에 의존하면 잘못된 결과를 얻을 수 있다.
 2. 때에 따라선 일반화에 대한 집착에서 벗어나 해당 문제 해결에만 집중할 경우 비약적인 성능 향상을 얻을 수 있다. - 위 소스는 성능 측정이라는 원래 취지로 놓고 볼 때는 잘못된 구현이지만 결과값을 얻는데 목적이 있었다고 한다면 훌륭한 최적화입니다. 때에 따라서는 저런 식으로 해당 상황에 적합한 구현이 필요하겠죠...(이것에 대한 비슷한 좋은 예가 '생각하는 프로그래밍'에 나옵니다)

덧글

댓글 입력 영역