재미있는 놀이: C, Python, Erlang으로 50000! 해보기 #0

재미있는 놀이: C, Python, Erlang으로 50000! 해보기
#0. 동기, 그리고 삽질.

-프롤로그-
나는 1996년부터 C언어를 사용했고, 2001년부터 파이썬을 사용했다. 그리고 2011년 12월 17일부터 얼랭(Erlang) 책을 읽기 시작했고, 2011년 12월 20일에 얼랭으로 처음 코딩을 해 봤다.(얼랭이라는 언어를 안건 2009년 즈음이다.) 이 글을 쓰고 있는 현재 나는 얼랭이란 언어를 본격적으로 공부해야겠다라고 다짐한지 3일이 지났다.

정리해보면, 이 글을 쓰고 있는 현 시점 기준으로

* C언어: 15년
* Python: 10년
* Erlang: 3일

의 경력을 가지고 있다.

어떤 언어든지 그 언어를 처음 공부하는 사람이 읽는 책에는 그 언어에 대한 장점을 언급하면서 칭찬이 가득하다. C언어나 파이썬처럼 10년 정도 만지다 보면 책에 나온 장점 중 어떤 것이 뻥인지 진짜인지 자연스레 알게 된다. 하지만 얼랭은 이제 3일 공부했다. 그나마 코딩해 본것도 예제 수준의 코드일 뿐이다. 책에 나와 있는 수많은 장점들이 진짜인지 궁금했다. 순진했던 어린 시절이었다면 의심없이 받아 들였겠지만 지금은 많이 타락해 버렸는지 자꾸만 의심이 생긴다. 그래서 한번 비교해봤다.

뭐랑? 내가 제일 잘 다루는 언어 두 개랑. 바로 C와 파이썬이다.

얼랭 책에 보면 이런 저런 좋은 말들이 많다. 이 많은 내용들을 내가 적절히 요약하면 아래와 같다.

"얼랭은 병행성 지향 프로그래밍을 위해 설계된 함수형 언어이다. 그래서 분산 노드, 분산 프로세싱으로 설계되어야 하는 어플리케이션에 적합하며, 멀티 코어, 멀티 프로세서 컴퓨팅 환경의 하드웨어를 쉽게 효율적으로 사용할 수 있도록 언어 수준에서 지원해 준다. 따라서 대용량 분산 프로세싱이 필요한 네트워크 서버 등의 개발에 적합하다."

맞는 요약인지는 모르겠지만 얼랭이 가지는 분명한 장점이 맞다. 실제 얼랭이 에릭슨에서 상용으로 쓰였던 분야도 전화 교환기 내부의 프로그램을 작성하기 위해서 였다고 한다. 전화 교환기라는 것이 아주 많은 네트워크 요청을 받아서 처리해주는 동작을 하는 녀석이니 현대의 네트워크 서버와 큰 틀에서 비슷한 목적의 솔루션이라고 볼 수 있다.

또 하나 얼랭에서 미는 것 중 하나는 저렇게 언어 수준에서 분산 처리를 지원해 주면서도 성능이 괜찮게 나온다는 것이다. 여기서 나는 몇 가지 궁금한 점이 생겼다.

1. 정말 코딩이 쉬운가?
2. 정말 성능이 괜찮게 나오는가?

성능이 아주 좋더라도 그 목적을 달성하기 위해 매우 복잡하고 어려운 코드를 작성해야 한다면 이것은 성능과 난이도 사이에서 선택을 해야 한다. 마찬가지로 간결하고 쉬운 코드로 작성을 해서 기능 목적을 달성하였지만 성능이 너무 안나온다면 역시 문제가 있다. 적당히 용납할 수 있는 수준의 성능과 짧은 학습으로도 코드를 이해할 수 있다면 얼랭은 최적의 선택이 될 수도 있을 것이다.

-선택-
일단 C, 파이썬, 얼랭을 비교하기로 결정했다. 이 세 언어로 무엇을 만들어서 비교를 해야 할까? 아래 네 가지 조건을 만족하는 그 무엇을 찾아야 한다.

1. 얼랭이 주장하는 장점을 실질적으로 검증할 수 있어야 한다.
2. 기본 개념이나 이론 자체가 쉬워야 한다.
3. 점진적 확장이 가능해야 한다.
4. 측정 가능할 만큼 충분히 빡센 계산이어야 한다.

얼랭이 주장하는 장점을 실질적으로 검증할 수 있어야 한다는 말은 병행성 프로그래밍으로 구현할 수 있는 것이어야 한다는 말이다. 기본 개념이나 이론 자체가 쉬워야 한다는 말은 말 그대로 쉬운 그 무엇이어야 한다는 말이고 점진적 확장이 가능하다는 말은 순차적 프로그래밍 -> 리컬시브 프로그래밍 -> 디바이드앤 퀀커 프로그래밍 -> 병행 프로그래밍 순서로 점진적으로 키워갈 수 있어야 한다는 말이다. 마지막 네 번째 충분히 빡세야 한다는 말은 세 가지 언어로 작성하려는 프로그램이 너무 빨리 처리되어서 (요즘 컴퓨터는 성능이 너무 좋다!) 시간 측정이 소수점 이하에서 나온다면 뭔가 유의미한 비교가 힘들어지기 때문에 최소한 5초에서 10초 이상의 컴퓨팅 파워를 소모할 수 있는 무언가여야 한다는 말이다.

그래서 내가 선택한 주제는 팩토리얼 계산이다.

모두가 알다시피 5!은 1*2*3*4*5의 결과이다. 알고리즘이라고 말하기도 민망할 정도로 쉽다. 중학교 정도 수학적 소양만 있으면 이해할 수 있다. 위의 2번 조건을 만족한다.

마찬가지로 10!의 경우 (1*2*3*4)의 결과와 (5*6*7)의 결과와 (8*9*10)의 결과를 곱해서 계산해도 구할 수 있다. 10!을 세 조각으로 쪼개서 계산을 해도 마지막에 아주 쉽게 합쳐서 계산할 수 있다. 이것은 병행성 지향 프로그래밍이 가능하다는 말로 1번 조건을 만족한다.

또한, for문으로 순차적으로 계산해서 구할 수 있고, 숫자를 하나씩 줄여가며 곱하거나 늘려가며 곱하는 식으로 리컬시브로 계산할 수도 있고, 앞 절에서 설명한 병행성 요소는 디바이드앤 퀀커 프로그래밍이 가능하다. 3번 조건을 만족한다.

마지막으로 한 50000! 정도 계산하려면 현대의 컴퓨터도 힘들어할 것이다. 만약 그래도 빨리 끝난다면 100000! 정도 하면 될 것이다. 간단하게 계산시간을 늘릴 수 있다. 4번 조건을 만족한다.

결론적으로 팩토리얼을 선택했지만, 사실 기본적으로 디바이드 앤 퀀커 접근으로 풀 수 있는 알고리즘은 모두 가능하다. 다만 2번과 4번 조건에 의해 후보에 있던 알고리즘들이 탈락하고 팩토리얼이 남았다.

먼저 퀵소트 알고리즘이었다. 소스 코드 자체는 아주 쉽지만 사실 개념 이해가 그렇게 직관적으로 와 닿지 않는다. (팩토리얼보다 더 직관적이지 않다!) 게다가 4번 조건을 만족하기 위해 계산 량을 늘리려면 입력으로 들어가는 정렬되지 않은 소스를 아주 크게 만들어야 하는데, 그것 자체가 상당히 부하가 큰 일이다. 그래서 탈락했다.

두 번째로 바이너리 서치 알고리즘이었다. 바이너리 서치는 퀵소트보다 먼저 탈락했다. 이유는 일단 소스코드가 어렵다. 팩토리얼은 말할 것도 없고 퀵소트보다 어려웠다. 그리고 마찬가지로 계산량을 늘리기 위해서는 커다란 입력 소스가 필요했다. 적당한 것으로는 인터넷에 공개된 ARM 아키텍처 메뉴얼등을 생각해 봤다. 하지만 이를 읽고 처리하기위한 파일 입출력 코드와 정규화 작업이 너무 귀찮았다.

세 번째 고려해본 알고리즘은 피보나치 수열이었다. 역시 코드는 지극히 단순하고 팩토리얼만큼이나 기본 개념이 쉬운 알고리즘이다. 계산량을 늘리는 것도 간단했다. Fib(50000) 정도 계산은 몇 초 이상 걸릴 것이 뻔했기 때문이다. 하지만 결정적으로 디바이드 앤 퀀커로 접근하는 방법이 직관적이지 않았다. 아니 아예 디바이드 앤 퀀커로는 피보나치 계산을 할 수 없던가...-_-;

아무튼, 이런 전차로 팩토리얼을 선택했다.

-삽질-
앞서도 말했듯 나는 15년 정도 C언어를 다루었다. 당연히 C언어에서는 정수 자료형에 데이터 사이즈가 정해져 있고, 그 이상의 정수를 처리하려면 오버플로우가 발생한다는 사실을 알고 있었다.

"그래도 64bit 정도면 충분할 거라 생각했다..."

하지만 큰 오산이었다. 난 팩토리얼이 숫자가 커질 수록 결과값이 어마어마하게 증가한다는 사실을 관과하고 있었다....

처음 C언어로 작성한 코드는 다음과 같았다.

#include <stdio.h>
 
unsigned long long factorial(unsigned int N)
{
	unsigned int i = 1;
	unsigned long long fac = 1;
	for (i = 1; i <= N; i++){
		fac *= i;
	}
	return fac;
}
 
int main(int argc, char* argv[])
{
	unsigned long long facN = 0;
	unsigned int N = 5;
 
	facN = factorial(N);
 
	printf("fac %u is %llu \n", N, facN);
 
	return 0;
 
}

초등학생 컴퓨터 수업시간 수준의 코드이다. 코딩하는데 한 30초 걸렸다. 이때만해도 한 두세시간 안에 모든 목적을 달성할 수 있을 줄 알았다. 파이썬 코딩은 더 빨리할 수 있을 테고, 얼랭은 조금 삽질해도 간단하니까 금방 할테니.

시험삼아 5!을 계산했다. 결과는 120으로 잘 나왔다.

$ ./c_fac
fac 5 is 120

그리고 바로 목적하는 50000!을 시험했다. 위 소스코드에서 main() 함수의 N을 50000으로 바꾸면 된다. 나는 뭔가 큰 수가 쭉 나오는걸 기대했다. 하지만 결과는 0이었다.

$ ./c_fac
fac 50000 is 0

당연히 결과를 보자마자 오버플로우된 것이라고 생각했다. 그러면서도 50000!이 얼마나 크길래 64비트로도 표현을 못하는 건지 감을 잡지 못했다. 그래서 간단하게 100!을 계산해 보았다. 100! 정도는 오버플로우되지 않을 것이라 생각했기 때문이다. 하지만 역시 결과는 0이었다.

$ ./c_fac
fac 100 is 0

어라.. 100!도 이렇게 큰 숫자인건가? 그래서 64비트의 최대값이 얼마인지를 뽑아 봤다.

踀17> 16#FFFFFFFFFFFFFFFF.
18446744073709551615

얼랭 인터프리터 쉘에서 16#FFFFFFFFFFFFFFFF을 하면 16진수의 최대값이 출력된다. 놀랍게도 결과는 18446744073709551615 밖에 안되었다. 20자리 밖에 안되질 않는가! 생각해보면 10!을 넘어가는 순간부터 팩토리얼 계산을 하나씩 올릴 때마다 10진수 자릿수가 하나씩 올라간다. 그리고 100!을 넘어가면 10진수로 두 자리씩 늘어난다. 당연히 20자리 정도의 표현으로는 텍도 없이 부족하다.

"내가 팩토리얼을 너무 쉽게 봤어..."

결국 64비트라는 크기를 너무 크게 생각한 나의 무지로 아까운 시간을 소비하고 빅 넘버(Big number) 표현이 가능한 라이브러리를 찾아보았다. libbign이라는 것이 있었고 GNU에서 배포하는 libgmp라는 것이 있었다. 당연히 보다 공신력(!)있어 보이는 GNU의 libgmp를 선택했다.

libgmp를 처음 사용해 보는지라 메뉴얼과 예제 소스를 보고 내 목적에 맞게 코딩하는 데에 거의 한 시간 이상이 걸렸다. 역시 C언어는 어려운 언어다. 나야 다른 어떤 언어보다 쉽고 편하게 쓰고 있지만 만약 C언어를 사용한지 몇 달 밖에 안되는 사람이 나와 같은 문제를 풀어야 한다면, 상당히 간단한 해결 방법임에도 꽤나 시간과 노력을 들여야 할 것이다.

얼랭을 테스트해 보려고 가벼운 마음으로 시작한 일인데 시작부터 C언어로 삽질하고 있는 나를 보면서 무언가 주객이 전도된 느낌을 지울수는 없지만 그래도 일단 시작한 일이니 끝까지 가겠다는 마음을 먹고 컴퓨터를 끄고 잠을 잤다.(응?)

이어지는 내용은 다음 시간에! ^^;

-다음 내용 예고-
본격적으로 순차 프로그램에 대한 성능 비교를 해 본다. 일단 C는 빅 넘버를 표현하기 위한 언어적 배려가 없으므로 libgmp로 작성한 for문 형태의 50000! 계산 코드를 작성해서 출력해보고 시간을 측정하기 위해 리눅스 명령어의 time 명령을 사용했다. 파이썬은 언어에서 빅 넘버가 그냥 되기 때문에 아주 가뿐하게 for문 형태의 팩토리얼 프로그램을 만들었다. 문제는 얼랭이다. 얼랭엔 for문이 없다!! 아.. 또 난관인가.. 난 그냥 가볍게 놀아보려고 시작한 건데.. 왜 자꾸 태클이 들어오지..-_-;

시간 측정도 뭔가 개운치 않다. 쉘 명령어인 time을 쓸려니 인터프리터를 먼저 로딩해야 하는 파이썬과 얼랭은 초기화 오버로드까지 시간을 먹어버린다. 그리고 stdout 출력 시간도 무시할 수 없다. 따라서 순수 계산에 들어간 시간을 알기 위해서 각 언어별로 있는 time관련 라이브러리를 사용해야 한다.

난... 이 짓을 왜 시작한 걸까...