자료2014. 1. 2. 14:34

프로그래밍을 처음 배울 때부터 사용했던 C의 fread, C++의 ifstream, Java의 InputStream 등은 모두 IO 작업이 완료될 때까지 스레드가 멈추는 Blocking API이다. 디스크 IO, 네트워크 IO 등을 기다리느라 수 밀리세컨드 동안 아무 것도 하지 않는 것은 귀중한 CPU 자원의 낭비이며, 프로그램의 전체적인 성능 하락을 불러오게 된다.

이를 해결하기 위해 스레드가 멈추지 않는 방식으로 프로그램을 작성하는 것을 비동기 프로그래밍이라고 부른다. 일반적으로 비동기 프로그래밍에선 특정 동작이 완료되었을 때에 호출되는 콜백을 등록하는데, 이를 남용하면 프로그램의 복잡도가 크게 상승하여 콜백 지옥이라는 늪에 빠지게 된다.

Microsoft에서 개발한 Reactive Extensions(RX)와 Netflix에서 이를 JVM 기반으로 포팅한 RxJava 는 이러한 비동기 프로그래밍을 간결하게 할 수 있도록 도와주는 라이브러리다. 이 라이브러리를 사용하면 모든 비동기 동작은 Future<T>와 Iterable<T>의 특징을 모두 갖고 있는 Observable<T> 타입을 바탕으로 이루어진다. 

ZooKeeper와 같이 원격으로 관리되는 트리의 예를 들어보자. 동기 API 는 아래와 같은 형태일 것이다.


List<String> getChildren(String path); // 주어진 경로의 하위 노드들을 구함
void delete(String path);              // 자식 노드가 없는 노드를 삭제
void deleteAll(String path);           // 주어진 노드와 모든 자식 노드를 삭제


RxJava를 이용한 비동기 API는 여기서 리턴타입을 Observable로 감싼 형태가 된다.


Observable<List<String>> getChildren(String path); // 주어진 경로의 하위 노드들을 구함
Observable<Void> delete(String path);              // 자식 노드가 없는 노드를 삭제
Observable<Void> deleteAll(String path);           // 주어진 노드와 모든 자식 노드를 삭제


Observable클래스에는 Observable 을 처리하기 위한 다양한 메소드들이 포함되어 있으며, 이들을 이용하여 Observable 형태로 가져온 리턴값을  값을 변형하거나, 여러 Observable과 결합하거나, 필터링하여 새로운 Observable을 만드는 비동기 동작에 활용할 수 있고, 필요한 경우엔 BlockingObservable로 변환하여 원하는 결과가 주어질 때까지 기다릴 수 있다. 

예시로 든 deleteAll 함수는 아래와 같이 getChildren과 delete를 이용하여 만들 수 있다. getChildren 함수를 이용해 현재 노드의 모든 자식 노드를 가져와서 재귀적으로 삭제한 뒤 delete 함수로 해당 노드를 삭제하는 방식이다.


void deleteAll(String path) {
    List<String> children = getChildren(path);
    for (String child : children) {
        deleteAll(path + "/" + child);
    }
    delete(path);
}


getChildren과 delete의 비동기 버전, 즉 Observable 을 반환하는 버전을 이미 만들었다고 하면 이를 이용해서 어떻게 deleteAll의 비동기 버전을 만들 수 있을까? 약간의 고민 뒤에 내가 당도한 해결책은 다음과 같다.


Observable<Void> deleteAll(String path) {
    return getChildren(path).flatMap(children -> {
        List<Observable<Void>> requests = transform(children, child -> 
            deleteAll(path + "/" + child)
        );
        return merge(from(requests)).lastOrDefault(null);
    }).flatMap(done -> delete(path));
}

가독성을 위해 Observable.merge, Observable.from과 Guava의 Lists.transform 함수를 static import 했다. 

1행은 앞서 말한 것과 같이 void 였던 리턴 타입을 Observable<Void>로 바꾼 모습이다. 이 Observable에 subscribe하게 되면 onNext를 통해 값을 전달하지는 않고, 동작이 정상적으로 끝났을 때 onComplete를, 에러가 발생했을 때 onError가 호출된다.

2행에서는 getChildren 메소드를 호출하여 돌려받은 Observable<List<String>> 타입의 리턴값에 flatMap 메소드를 이어서 호출한다. 이렇게 해서 비동기적으로 자식 노드들의 리스트를 구해오고, 구해온 다음에 수행할 동작을 표현할 수 있다. 여기서 flatMap 메소드에 넘기는 인자는 List<String>을 받아서 Observable<Void>를 반환하는 함수이며, 역시 Java 8 lambda로 작성이 가능하다.

3행~5행에서는 children 각각에 대해 deleteAll 함수를 부른다. 자식 노드 각각에 대해 Observable을 부르기 때문에 여러 개의 Observable<Void>를 얻게 되고, Guava의 Lists.transform 을 이용해 List로 만들었다.

6행의 merge(from(request))는 List<Observable<Void>> 타입의 requests에 포함된 모든 Observable을 결합한 하나의 Observable을 만든다. 이 Observable<Void>는 모든 자식노드에 대한 처리가 성공한 경우에 onComplete로 끝나며, 하나라도 실패한 경우 onError를 발생시킨다. lastOrDefault 는 이 Observable이 끝날 때 null을 전달하도록 하기 위해 추가했으며, 아래쪽의 subscribe 부분을 간단히 작성할 수 있도록 하는 트릭이다.

7행에선 3행부터 시작한 flatMap 호출이 끝난다. 이 Observable이 완료된 시점에서는 하위 노드들이 모두 지워졌다고 가정할 수 있으므로, 한번 더 flatMap 메소드를 호출하여 path 경로에 있는 노드를 지우도록 한다.


세 번의 lambda를 사용했음에도 다섯 줄로 끝나는 동기 버전보다 현저히 가독성이 떨어지는 것이 사실이다. 자바 8에서조차 C#이나 Scala에 존재하는 async/await을 사용할 수 없고 7행에서처럼 비동기 연산의 결과를 다양한 방식으로 조작하는 것은 async/await이 있더라도 한계가 있는 부분이라, 비동기 어플리케이션을 구현하기 위한 아직은 어쩔 수 없는 trade-off라고 봐야 할 것 같다.

그래도 안도할 것은 Java 8 의 lambda 덕분에 가독성이 몇 배는 좋아졌다는 점이다. 위 구현에서 사용한 lambda 3개를 모두   anonymous class로 써야 했다면 누구라도 일찌감치 포기하고 말았을 것이다. Scala에서만 가능하다고 생각했던 Functional Reactive Programming 이 Java 8 에서야 비로소 현실적인 대안으로 자리잡은 듯하다. 과도한 패턴으로 악명이 높은 구시대적 자바의 관습이 Java 8을 계기로 보다 미래지향적으로 전환되길 하는 바람을 가져 본다.



Posted by jongwook
자료2013. 11. 6. 02:52

어쩌다 보니 온라인 게임서버 개발에 종사하게 되어서 종종 이름을 듣곤 하는 넷텐션은 고성능 네트워크 서버 엔진인 프라우드넷을 개발한 회사로 유명하다. 얼마 전 이 회사의 입사면접시험 문제가 인터넷 커뮤니티에 공개되었다. 바로 1부터 백만까지의 소수를 출력하는 프로그램을 만들라는 것. 사실 2번 문제가 핵심이고 출제자의 의도는 에라토스테네스의 체 보다도 단순한 방법(루트n까지 나눠보기)으로 소수를 판별하면서도 이것을 병렬화하는 테크닉을 보고자 한 것 같지만, Functional Programming in Scala 수업을 듣던 중 1번 문제를 풀 수 있는 아주 간결한 방법을 보고 충격을 받고 몇 달째 누르길 귀찮아 하고 있던 글쓰기 버튼을 눌렀다.

전통적인 방법이라면, 에라토스테네스의 체는 아래와 같이 순차적으로 계산할 것이다. (in C++)

#include <iostream>

using namespace std;

const int N = 1000;

int main() {
	bool nonprime[N + 1] = { true, true, false, };
	
	for (int n = 2; n <= N; n++) {
		if (!nonprime[n]) {
			for (int m = 2; n * m <= N; m++) {
				nonprime[n * m] = true;
			}
		}
	}

	for (int n = 2; n <= N; n++) {
		if (!nonprime[n]) {
			cout << n << endl;
		}
	}
}

2부터 시작해서 소수의 배수들을 하나씩 제외하는 정의에 충실한 코드이다. 그런데 Functional Programming in Scala 수업에서는 다음과 같이 위 C++ 프로그램과 같은 출력을 만드는 방법을 소개한다.

object Eratosthenes {
  def from(n: Int): Stream[Int] = n #:: from(n+1)

  def seive(s: Stream[Int]): Stream[Int] = {
    s.head #:: seive(s.tail filter (_ % s.head != 0))
  }

  val primes = seive(from(2))

  def main(args: Array[String]) {
    primes takeWhile(_ <= 1000) print
  }
}

순차적인 구현과 코드 분량은 크게 다르지 않지만, 접근 방법이 완전히 다르다. Stream[Int]는 수열을 의미하는데, lazy evaluation이 되기 때문에 무한히 긴 수열이 될 수도 있다. 실제로 from 은 n 이상의 모든 정수의 stream을 반환하고, seive는 주어진 stream의 첫 번째 숫자의 배수를 걸러내어 다시 seive를 적용한 stream을 반환한다. 종료 조건이 없는 재귀함수로 보이지만 이것 역시 lazy evaluation 덕분에 가능하다. 즉 2 이상의 모든 정수에 대해 seive를 하면, 모든 소수를 담고 있는 수열 primes를 얻게 된다. main 함수는 primes 에서 1000 이하의 소수를 뽑은 다음 출력한다. primes가 선언된 곳은 main 함수의 밖이었지만, lazy evaluation 덕분에 실제 에라토스테네스의 체 계산이 이루어지는 부분은 이곳이다.

저 풀이를 처음 보고선 무한히 긴 수열과 같은 추상적인 개념까지 간결하게 표현할 수 있는 함수형 프로그래밍의 매력에 awe moment를 느낄 수 밖에 없었다. 이어서 든 생각은, 정말 이건 Scala에서만 가능한걸까? 라는 것이었다. C++이나 Java와 같은 전통적인 언어는 태생적인 한계 덕분에 lazy evaluation같은 처리를 하려면 얼마나 손해를 보게 될까 라는 의문이 들어서 한번 해 보기로 했다. 두 언어 모두 lambda expression을 사용할 수 있게 되어서 수월하지 않을까 하는 낙관이 앞섰다...

먼저 Java 구현이다. 

import java.util.function.Predicate;
import java.util.function.Supplier;

class Lazy<T> {
	final Supplier<T> supplier;
	T value;

	public Lazy(Supplier<T> supplier) {
		this.supplier = supplier;
	}

	public T get() {
		if (value == null) {
			value = supplier.get();
		}
		return value;
	}
}

class Stream<T> {
	T head;
	Lazy<Stream<T>> tail;

	public Stream(T value) {
		this.head = value;
	}

	public Stream(T head, Supplier<Stream<T>> tail) {
		this.head = head;
		this.tail = new Lazy<>(tail);
	}

	public Stream<T> filter(Predicate<T> predicate) {
		return tail.get() == null ? null :
					predicate.test(head) ?
						new Stream<>(head, () -> tail.get().filter(predicate)) :
						tail.get().filter(predicate);
	}

	public Stream<T> takeUntil(Predicate<T> predicate) {
		return predicate.test(head) && tail.get() != null ?
				new Stream<>(head, () -> tail.get().takeUntil(predicate)) : null;
	}

	public void print() {
		System.out.println(head);

		if (tail.get() != null) {
			tail.get().print();
		}
	}
}

public class Sieve {
	static Stream<Integer> from(int n) {
		return new Stream<>(n, () -> from(n+1));
	}

	static Stream<Integer> sieve(Stream<Integer> stream) {
		return new Stream<>(stream.head, () -> sieve(stream.tail.get().filter(n -> n % stream.head != 0)));
	}

	static Stream<Integer> primes = sieve(from(2));

	public static void main(String ... args) {
		primes.takeUntil(n -> n < 1000).print();
	}
}

일일히 유틸리티 클래스를 만들어야 하는 것과 lazy value에 대한 문법적 지원이 없어서 매번 () -> 를 써 주어야 하는 것이 좀 고단하지만, 어쨌든 주요 구현부분 자체는 충분히 간결하게 가능하다는 것을 볼 수 있다! 다만 Java 8에서 추가된 lambda expression이 없으면 몇 배나 지저분해졌을 지 상상하기가 두렵다. 한편 Java 8에서는 Scala의 Stream과 매우 유사한 Stream 클래스를 제공한다. 이를 사용하면 꽤 깔끔하게 구현을 할 수 있을 것 같은데, Java 8의 Stream은 lazy value를 제대로 구현하지 않는 대신 재사용이 불가능하게 만들어 놓은 데다가 head와 tail을 떼어낼 적절한 방법이 없는 것 같아서 방법을 찾다가 포기해야 했고-_-; C++로도 해보다가 new 쓰기 싫어서 스택에서 최대한 해보다가 쥐쥐=_=.. 다음에 천천히 도전해야 할 것 같다.

Functional Programming in Scala 수업의 마지막 과제를 아직 하지 않았지만 그래도 60% 이상의 과제를 완료하여 수료증을 받는 것은 확실해졌다. 프로그래밍 숙제를 가이드를 따라 해결하고 제출하면 자동으로 채점해 주고 동작 결과는 물론 코딩 스타일과 같은 사소하지만 유익한 부분까지도 피드백을 제공하는 Coursera의 시스템 덕분에 더 적극적으로 수업에 참여하게 되었다. 그래서 그런지 이 수업은 Coursera 전체 강의 중 수료생 비율이 제일 높다고 한다. 이제 이어지는 Coursera 수업인 Principles of Reactive Programming을 수강신청하고 즐겁게 들으려고 한다. 클라우드 시대의 문턱에 서 있는 서버 프로그래머로서 배우고 따라해 볼 점이 아주 많을 것 같다.





Posted by jongwook
자료2012. 5. 26. 21:08

처음 프로그래밍을 배울 때, 특히 재귀함수를 다룰 때 팩토리얼 다음으로 자주 등장하는 예제는 피보나치 수열이다.


int fibonacci(int n) {
    if (n == 0 || n == 1) return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}


이렇게 하면 n이 커질 때 너무 오래 걸리기 때문에 배열을 사용해서 계산하는 법이 이어서 등장하기도 한다.


int fibonacci(int n) {
    int a[N];  // N = 관심 있는 n의 최대 크기+1
    a[0] = 1;
    a[1] = 1;
    for(int i=2; i<=n; i++) {
        a[i] = a[i-1] + a[i-2];
    }
    return a[n];
}


이런 방식을 다이나믹 프로그래밍이라고 하는데, 아래처럼 하면 메모리 사용량을 조금 아낄 수 있다.


int fibonacci(int n) {
    int a = 0, b = 1, c = 1;
    for(int i=0; i<n; i++) {
        c = a+b;
        a=b;
        b=c;
    }
    return c;
}


1, 1 대신에 다른 숫자 a, b로 시작하는 피보나치 수열을 구하는 좀 더 일반적인 함수는 다음과 같이 만들 수 있다.


int fibonacci(int a, int b, int N) {
	int c = b;
	for(int i=1; i<N; i++) {
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}


피보나치 수열은 꽤 빠르게 증가하는데 int 타입은 21억까지밖에 표현을 못한다. long이나 double을 쓰고 싶은 사용자가 있으면 쓸 수 있도록 템플릿으로 만들어 줄 수도 있다.


template <typename T>
T fibonacci(T a, T b, int N) {
	T c = b;
	for(int i=1; i<N; i++) {
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}


한편 템플릿 기능을 활용하면 다음처럼 색다른 방식으로 피보나치 수열을 구할 수 있다. 이런 방식을 템플릿 메타프로그래밍이라고 한다. 이 방식의 장점은 계산이 컴파일하면서 일어나기 때문에 실행할 땐 아무런 피보나치 계산도 일어나지 않는다는 점이다. 사실 이런 방식으로 컴퓨터의 모든 연산을 수행하는 것이 가능하다!


#include <iostream>
using namespace std;

template <int n>
struct Fibonacci { enum { value = Fibonacci<n-1>::value + Fibonacci<n-2>::value }; };

template <>
struct Fibonacci<0> { enum { value = 1 }; };

template <>
struct Fibonacci<1> { enum { value = 1 }; };

int main() {
    cout << Fibonacci<0>::value << endl;
    cout << Fibonacci<1>::value << endl;
    cout << Fibonacci<2>::value << endl;
    cout << Fibonacci<3>::value << endl;
    cout << Fibonacci<4>::value << endl;
    cout << Fibonacci<5>::value << endl;
    cout << Fibonacci<6>::value << endl;
    cout << Fibonacci<7>::value << endl;
    cout << Fibonacci<8>::value << endl;
    cout << Fibonacci<9>::value << endl;
    cout << Fibonacci<10>::value << endl;
    cout << Fibonacci<11>::value << endl;
}


CRTP라는 이상한 방식을 사용해서 조금 변태같은 방법으로 피보나치 수열을 구할 수도 있다. Expression, Integer, Sum 이라는 클래스가 각각 수식, 숫자, 덧셈의 역할을 수행한다. 이렇게 하면 각 연산이 일어날 때에 뭔가 부가적인 일(자동으로 미분을 시켜준다던가...)을 하는 것이 가능하다.


#include <iostream>
using namespace std;

template <typename T>
struct Expression {
	const T& cast() const { return static_cast<const T&>(*this); }
	int value() const { return cast().value(); }
};

struct Integer : Expression<Integer> {
	template<typename T>
	Integer& operator=(const Expression<T> &rhs) {
		N = rhs.value();
		return *this;
	}
	Integer(int N=0) : N(N) {}
	int value() const { return N; }
private:
	int N;
};

template <typename L, typename R>
struct Add : public Expression<Add<L,R> > {
	Add(const Expression<L> &lhs, const Expression<R> &rhs) : lhs(lhs.cast()), rhs(rhs.cast()) {}
	int value() const { return lhs.value() + rhs.value(); }
private:
	const L& lhs;
	const R& rhs;
};

template <typename L, typename R>
Add<L,R> operator+(const Expression<L>& lhs, const Expression<R>& rhs) {
	return Add<L,R>(lhs, rhs);
}

template <typename T>
T fibonacci(T a, T b, int N) {
	T c = b;
	for(int i=1; i<N; i++) {
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}

int main() {
	Integer a = 1, b = 1;
	for(int i=0; i<12; i++) {
		Integer f = fibonacci(a, b, i);
		cout << f.value() << "\t" << fibonacci(1, 1, i) << endl;
	}

	return 0;
}


Posted by jongwook
자료2012. 2. 21. 14:07
제대로 뉴스데스크는 현재 파업중인 MBC 기자들이 만드는 제대로된 뉴스입니다.

 





"뉴스타파"는 정권에 비판적인 기사를 내다 해직당한 기자들이 만든 뉴스입니다.










부정선거가 일어나고, 무수한 대학교의 교수진과 학생들이 시국선언을 해도 평화롭기만 한 주류언론.

밥줄을 건다는 것이 얼마나 힘든 선택인지 조금은 이해하기에 저들을 이해하고 응원합니다.

이렇게라도 제대로된 뉴스를 전할 수 있는 세상이라 다행이면서도

외국 동영상 서비스를 이용할 수 밖에 없는 현실이 안타깝습니다.

Posted by jongwook
자료2012. 1. 17. 00:40

윈도우 비스타와 윈도우 7에는 컴퓨터의 성능을 간단한 숫자들로 보여주는 윈도우 체험 지수(WEI; Windows Experience Index)라는 점수를 볼 수 있습니다. 투명한 창 테두리로 대표되는 윈도우 비스타와 윈도우 7의 에어로(Aero) 인터페이스도 이 윈도우 체험 지수가 있어야 활성화됩니다.

시작-컴퓨터-우클릭-속성으로 시스템 속성에 들어간 뒤 "Windows 체험 지수"를 클릭하면 자세한 항목을 볼 수 있다.

 

윈도우 체험 지수는 5개 항목으로 구성되어 있는데, 각각 CPU, 메모리, 그래픽, 게임 그래픽, 디스크 성능을 검사합니다. 윈도우 비스타에선 5.9점이, 윈도우 7에서는 7.9점이 최고 점수이고, 다음 윈도우 버전이 나오면 이 제한은 점점 올라갈 예정입니다.

보통 윈도우 체험 지수는 정확하지 않고 별로 신뢰할 필요가 없다고들 하는데요, 윈도우 체험 지수가 실제 성능과 어떤 관계가 있는지 알아보기 위해 몇몇 데이터를 모아 보았습니다.

우선 컴퓨터 매장을 돌아다니면서 전시된 데스크탑/노트북 컴퓨터들을 볼 때마다 각각의 CPU 이름과 윈도우 체험 지수를 기록했습니다. 그리고 이 CPU들에 대한 좀더 객관적인 성능 지표를 얻기 위해 PassMark Software에서 제공하는 CPU 성능 데이터도 함께 정리했습니다. 이 숫자는 PassMark에서 만든 벤치마킹 프로그램을 사용하여 사용자들이 측정한 데이터들의 평균값으로 아주 잘 통제된 환경에서 측정된 값은 아니지만, 상당히 많은 샘플들을 이용하였으므로 CPU 성능을 어느 정도는 잘 나타내는 숫자입니다.





PassMark CPU 점수와 윈도우 체험 지수를 좌표평면에 나타내 보면 조금은 중구난방하지만 두 점수 사이에 큰 상관관계가 있음이 보입니다. 또한 중요한 결론은 윈도우 체험 지수는 로그스케일인 것으로 보인다는 점입니다. 간단히 말해 컴퓨터의 성능이 두 배 좋아질 때마다 윈도우 체험 지수가 1.0 정도씩 커진다는 말인데, 이는 지진의 규모나 소리의 세기를 데시벨로 측정할 때와 비슷한 방식입니다.

엄밀하게는 이외에도 점수에 영향을 주는 변수들이 있지만, 대체로 로그스케일을 유지합니다. 로그스케일을 이용하는 것의 큰 장점은 기하급수적으로 발전하는 컴퓨터의 성능을 좀더 간단한 숫자로 표시할 수 있다는 점입니다. PassMark나 Futuremark사에서 제공하는벤치마크 도구들은 4~5자리수의 숫자로 컴퓨터의 성능을 정확히 측정합니다만, 소수의 매니아와 전문가들만이 이런 점수들을 꿰고 있죠. 모든 Windows 컴퓨터의 성능을 간단히 확인하는 도구로서 윈도우 체험 지수를 두 개의 유효숫자로 나타내어 보다 많은 소비자들이 접근할 수 있게 한 것은 마이크로소프트의 현명한 선택이라고 생각됩니다.



 
Posted by jongwook