Swift는 정말 파이썬보다 빠를까?

애플은 Swift가 파이썬보다 몇 십배 빠르다고 주장하고 있는데, 실질적으로는 파이썬이 더 빠른 것 같이 느껴지는 (심지어 pypy도 아니고) 경우가 너무나 많다. 물론 “어떤 언어가 더 빠르냐”는 질문만큼 바보같은 것도 없긴한데, 개인적으로는 애플이 말하는 것과 반대인 것 같은 체감이 많아서 한 번 확인해보았다.

결론부터 말하면 Swift는 그다지 Python에 비해서 아직까지는 빨리 처리되지 않는다. 이건 언어자체의 디자인보다는 실행기의 성능이나 표준 라이브러리 자체의 성능에도 좌우되고 있으므로 향후에는 애플의 공언이 사실이 될 수 있다.

긴 정수를 지원하는 Swift 타입 테스트를 하면서 300!의 값을 계산해보았는데, 명령줄을 통해서 실행해보려는데 시간이 꽤 많이 걸렸다. 파이썬과의 동등비교는 좀 어렵지만(파이썬은 자체적으로 큰 수를 지원하고, 이는 C라이브러리라 매우 빠르다.) 일단 파아썬에서의 결과를 보면…

$ time python -c "print reduce(lambda x,y: x*y, range(2,301), 1)"
306057512216440636035370461297268629388588804173576999416776741259476533176716867465515291422477573349939147888701726368864263907759003154226842927906974559841225476930271954604008012215776252176854255965356903506788725264321896264299365204576448830388909753943489625436053225980776521270822437639449120128678675368305712293681943649956460498166450227716500185176546469340112226034729724066333258583506870150169794168850353752137554910289126407157154830282284937952636580145235233156936482233436799254594095276820608062232812387383880817049600000000000000000000000000000000000000000000000000000000000000000000000000

굉장히 무지막지한 결과인데, 시간은 놀랍게도

real    0m0.059s
user    0m0.014s
sys 0m0.043s

거의 엔터치자마자 결과가 나온수준이다.

그럼, swift 버전은 어떨까? (곱하기 함수의 성능이 진짜 치명적이다;;)

real    0m17.115s
user    0m15.449s
sys 0m1.662s

거의 40배 차이난다. 곱셈의 횟수가 늘수록, 그리고 숫자가 커질수록 성능이 급속히 나빠진다. (1000!으로도 테스트해봤는데 거의 10분이 넘도록 끝나질 못하더라. 근데 파이썬의 경우에는 시간 차이가 거의 안났다.)

#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "BigInt.h"
#define UNITLENGTH (4)
#define UNITLIMIT (9999)
#define UNITSIZE (10000)
struct _BigInt {
unsigned int cellCount;
unsigned int numberCount;
int *data;
char *description;
bool _desc_created;
};
typedef struct _BigInt* BigInt;
static int convertShortStringIntoInteger(const char* str);
static void parseString(const char* str, int** array);
static BigIntRef BigIntShift(BigIntRef a, unsigned int s);
static BigIntRef BigIntMultiplyHelper(BigIntRef a, int s);
void BigIntRelease(BigIntRef r)
{
BigInt b = (BigInt)r;
if(b->_desc_created){
free(b->description);
}
free(b->data);
free(b);
}
BigIntRef BigIntCreateWithString(const char* str)
{
int len = strlen(str);
BigInt r = (BigInt)(malloc(sizeof(struct _BigInt)));
r->cellCount = (int)ceil((double)len / UNITLENGTH);
r->numberCount = len;
r->_desc_created = NO;
r->description = NULL;
parseString(str, &r->data);
return (void*)r;
}
BigIntRef BigIntCreate(int* data, int cellC, int numberC)
{
BigInt r = (BigInt)(malloc(sizeof(struct _BigInt)));
r->data = data;
r->numberCount = numberC;
r->cellCount = cellC;
r->_desc_created = NO;
r->description = NULL;
return (void*)r;
}
void BigIntTraverse(BigIntRef r)
{
BigInt b = (BigInt)r;
int i;
for(i=0;i<(int)b->cellCount;i++){
printf("%04d : %04d\n", i, b->data[i]);
}
}
const char* BigIntGetDescription(BigIntRef r)
{
BigInt b = (BigInt)r;
if(!b->_desc_created){
b->description = (char*)malloc(sizeof(char) * b->numberCount + 1);
b->description[b->numberCount] = 0;
int currentPosition = b->numberCount1;
int i, j, k;
for(i=0;i<(int)b->cellCount;i++){
k = b->data[i];
for(j=0;j<UNITLENGTH;j++){
b->description[currentPosition] = k % 10 + '0';
currentPosition–;
k = k / 10;
if(currentPosition < –1){
break;
}
}
}
}
return b->description;
}
BigIntRef BigIntAdd(BigIntRef a, BigIntRef b)
{
BigInt x = (BigInt)a;
BigInt y = (BigInt)b;
unsigned int maxCellCount = x->cellCount > y->cellCount ? x->cellCount : y->cellCount;
int* tempArray = (int*)malloc(sizeof(int) * (maxCellCount + 1));
int flag = 0;
int d = 0;
int i,j,k;
for(i=0;i<(int)maxCellCount;i++){
j = i >= (int)x->cellCount ? 0 : x->data[i];
k = i >= (int)y->cellCount ? 0 : y->data[i];
d = j + k + flag;
if(d > UNITLIMIT){
flag = 1;
d = d % UNITSIZE;
} else {
flag = 0;
}
tempArray[i] = d;
}
if(flag){
tempArray[i] = flag;
maxCellCount++;
}
unsigned int maxNumberCount = UNITLENGTH * (maxCellCount – 1) + (unsigned int)(floor(log10(tempArray[maxCellCount-1]))) + 1;
int* resultData = (int*)malloc(sizeof(int) * maxCellCount);
memcpy(resultData, tempArray, sizeof(int) * maxCellCount);
BigInt result = BigIntCreate(resultData, maxCellCount, maxNumberCount);
free(tempArray);
return (BigIntRef)result;
}
/** 문자열을 4자리씩 쪼갠후 int의 배열로 리턴해준다. **/
void parseString(const char* str, int** array)
{
int len = strlen(str);
int arraySize = ceil((double)len / UNITLENGTH);
char* ar = (char*)malloc(sizeof(char)*(UNITLENGTH + 1));
*array = (int*)malloc(sizeof(int)*arraySize);
int i, j;
int position;
for(i=0;i<arraySize;i++){
strcpy(ar, "0000"); // "0" * UNITLENGTH
for(j=0;j<UNITLENGTH;j++){
position = len – 1 – (UNITLENGTH * i) – j;
if(position >= 0){
ar[4-j-1] = str[position];
} else {
break;
}
}
(*array)[i] = convertShortStringIntoInteger(ar);
}
free(ar);
}
/** 4자리 미만의 문자열을 정수로 변경해주는 함수 **/
int convertShortStringIntoInteger(const char* str)
{
int len = strlen(str); // strlen은 마지막 널 종료문자는 세지 않는다.
int result = 0;
int i;
for(i=0;i<len;i++){
char c = str[i];
result = result * 10 + (int)(c – '0');
}
return result;
}
BigIntRef BigIntMultiply(BigIntRef a, BigIntRef b)
{
BigInt r = (BigInt)b;
int i;
int rightCellCount = (int)r->cellCount;
BigInt* tempResults = (BigInt*)malloc(sizeof(BigInt) * rightCellCount);
BigInt Result = BigIntCreateWithString("0");
BigIntRef temp;
for(i=0;i<rightCellCount;i++){
temp = BigIntMultiplyHelper(a, r->data[i]);
tempResults[i] = BigIntShift(temp, i);
BigIntRelease(temp);
}
for(i=0;i<rightCellCount;i++){
temp = BigIntAdd(Result, tempResults[i]);
BigIntRelease(Result);
Result = temp;
}
for(i=0;i<rightCellCount;i++){
BigIntRelease(tempResults[i]);
}
free(tempResults);
return Result;
}
static BigIntRef BigIntMultiplyHelper(BigIntRef a, int s)
{
int i;
int d=0, flag=0;
unsigned int newNumberCount;
int *newResultArray;
BigInt result;
BigInt b = (BigInt)a;
unsigned int newCellCount = b->cellCount;
int* tempArray = (int*)malloc(sizeof(int) * (b->cellCount + 1));
for(i=0;i<(int)b->cellCount;i++){
d = b->data[i] * s + flag;
if(d > UNITLIMIT){
flag = d / UNITSIZE;
d = d % UNITSIZE;
} else {
flag = 0;
}
tempArray[i] = d;
}
if(flag){
tempArray[i] = flag;
newCellCount += 1;
newNumberCount = UNITLENGTH * (i – 1) + (unsigned int)floor(log10(flag)) + 1;
} else {
newNumberCount = UNITLENGTH * (i – 2) + (unsigned int)floor(log10(flag)) + 1;
}
newResultArray = (int*)malloc(sizeof(int) * newCellCount);
memcpy(newResultArray, tempArray, sizeof(int) * newCellCount);
result = BigIntCreate(newResultArray, newCellCount, newNumberCount);
free(tempArray);
return (void*)result;
}
static BigIntRef BigIntShift(BigIntRef a, unsigned int s)
{
BigInt b = (BigInt)a;
int* tempArray = (int*)malloc(sizeof(int) * (b->cellCount + s));
int i, j;
for(j=0;j<(int)s;j++){
tempArray[j] = 0;
}
for(i=0;i<(int)b->cellCount;i++){
tempArray[i+s] = b->data[i];
}
BigInt result = BigIntCreate(tempArray, b->cellCount + s, b->numberCount + (UNITLENGTH * s));
return result;
}

view raw
BigInt.c
hosted with ❤ by GitHub

/*
* BigInt.h
* 2015. 05. 28 by sooop.
*
*
* 큰 정수 덧셈하기
* 큰 정수는 작은 조각으로 나누고
* 각 조각들과 올림처리된 플래그 값을 더한다.
* 최종적으로 올림처리된 플래그 값이 남아있으면 최상위 조각을 더해준다.
* 조각을 순서대로 연결해주면 끝
*
*
* BigInt 구조체는 큰 정수 계산을 쉽게 하기 위해서 사용하는 구조체
* 정수를 4자리 단위로 끊어서 리틀엔디언 방식으로 저장한다.
* 생성은 문자열을 기준으로 한다.
* –> 문자열을 뒤에서부터 4자리씩 끊는 함수가 필요하다.
* 그리고 출력은 역시 문자열로 해야 하므로 BigInt 타입의 값을
* 문자열로 표현해주는 함수가 필요하다.
*/
typedef unsigned short bool;
#define YES ((bool)(1))
#define NO ((bool)(0))
typedef void* BigIntRef;
BigIntRef BigIntCreateWithString(const char* str);
BigIntRef BigIntCreate(int* data, int cellC, int numberC);
BigIntRef BigIntAdd(BigIntRef a, BigIntRef b);
BigIntRef BigIntMultiply(BigIntRef a, BigIntRef b);
const char* BigIntGetDescription(BigIntRef r);
void BigIntTraverse(BigIntRef r);
void BigIntRelease(BigIntRef r);
//********************************************************************

view raw
BigInt.h
hosted with ❤ by GitHub

#include <stdio.h>
#include "BigInt.c"
int main(){
BigIntRef a = BigIntCreateWithString("2");
BigIntRef b = BigIntCreateWithString("2");
BigIntRef temp;
int i;
for(i=0;i<999;i++){
temp = BigIntMultiply(a, b);
BigIntRelease(a);
a = temp;
}
BigIntTraverse(a);
printf("2^1000 is : %s\n", BigIntGetDescription(a));
BigIntRelease(a);
BigIntRelease(b);
return 0;
}

view raw
temp.c
hosted with ❤ by GitHub

Swift가 파이썬보다도 비교할 수 없을만큼 빠르며(아마 컴파일한 바이너리로 실행했을 때를 비교하겠지) Objective-C 보다도 더 빠르다고 한다. 그런데 애플의 이런 이야기는 좀 이상한게 경험적으로는 꼭 큰 수의 문제가 아니라, 거의 동일한 알고리듬으로 코드를 짜도 대부분의 실행 결과는 파이썬이 더 빠른 경우가 많았다. 하지만 Swift의 JIT 최적화가 들어가면 어떨까? 단, JIT은 초반에 추적 정보를 쌓는 작업이 들어가야 해서 몇 초 내로 빨리 끝나는 작업의 경우에는 되려 실행 시간이 더 길어지기도 한다. (값만 바꿔서 100!을 구하는 경우에는 최적화 옵션이 들어간 경우에 시간이 더 걸렸다.) 그런데 비슷한 JIT을 지원하는 pypy라면 어떨까? pypy의 경우 cPython보다 수십배 빠른 경우도 있어서(심지어는 비슷한 알고리즘으로 구현한 C 코드보다도 빠를때도 있다.) Swift가 파이썬보다 빠를것이라는 장담은 아직은 시기상조일 듯 하다.

어쨌든 최적화 옵션을 추가해서 실행해보자.

$ time swift -O BigInt.swift

시간은…

real    0m3.284s
user    0m2.794s
sys 0m0.484s

거의 1/4~1/5 수준으로 시간이 팍 줄었다.

이번에는 스크립트로 실행하는 것이 아니라 바이너리로 컴파일하여 실행하는 경우에는 실행시간이 얼마나 걸리는지 보자. 컴파일러는 swiftc라는 명령으로 실행하면 된다.

$ swiftc BigInt.swift -o BigInt; time ./BigInt

상당히 실망스러운 결과이다. 바이너리로 컴파일까지 했는데 이지경이라니…

real    0m15.077s
user    0m15.055s
sys 0m0.020s

최적화 옵션을 안줘서 그런가?

$ swiftc BigInt.swift -O -o BigInt; time ./BigIn

이제 실행시간을 보면…

real    0m0.550s
user    0m0.533s
sys 0m0.003s

오오, 무지막지하게 빨라졌다. 30배 정도 빨라진 셈인가?

순수 파이썬의 동일 알고리듬

파이썬의 큰 수 처리는 매우 빠르므로, 여기서 사용된 허접한 오리지널 알고리듬과 비교하는 것이 반칙이라고 생각할 수도 있기에, 파이썬으로 완전히 동일한 알고리듬을 새로 짰고 이 코드로 300!의 값을 구해보았다.

class BigInt(object):
UNIT_LENGTH = 5
def __init__(self, string):
self.digits = []
if type(string) == str:
self.parse(string)
elif type(string) == list:
for i in string:
self.digits.append(i)
self.negative = False
def parse(self, string):
while True:
if len(string) > BigInt.UNIT_LENGTH:
self.digits.append(int(string[BigInt.UNIT_LENGTH:]))
string = string[:BigInt.UNIT_LENGTH]
else:
self.digits.append(int(string))
break
@property
def description(self):
result = ""
for unit in self.digits:
result = ("000000" + str(unit))[BigInt.UNIT_LENGTH:] + result
result = result.lstrip("0")
if self.negative:
result = '-' + result
return result
def addTo(self, num):
upFlag = 0
resultArray = []
i = 0
UNIT_CUT = 10**BigInt.UNIT_LENGTH
UNIT_LIMIT = UNIT_CUT 1
while True:
nl = self.digits[i] if i < len(self.digits) else 0
rl = num.digits[i] if i < len(num.digits) else 0
d_sum = nl + rl + upFlag
resultArray.append(d_sum % UNIT_CUT)
upFlag = (d_sum // UNIT_CUT)
if d_sum + upFlag == 0:
break
i += 1
return BigInt(resultArray)
def multiplty(self, num):
UNIT_CUT = 10**BigInt.UNIT_LENGTH
UNIT_LIMIT = UNIT_CUT 1
toBeSummed = []
finalResult = []
level = 0
for i in self.digits:
upFlag = 0
tempResult = []
for x in range(0, level):
tempResult.append(0)
for j in num.digits:
d_sum = i * j + upFlag
tempResult.append(d_sum % UNIT_CUT)
upFlag = d_sum // UNIT_CUT
if upFlag != 0:
tempResult.append(upFlag)
toBeSummed.append(tempResult)
level += 1
i = 0
upFlag = 0
while True:
currentSummed = map(lambda x:x[i], filter(lambda x:len(x) > i, toBeSummed))
if len(currentSummed) == 0:
if upFlag != 0:
finalResult.append(upFlag)
break
currentSum = sum(currentSummed) + upFlag
finalResult.append(currentSum % UNIT_CUT)
upFlag = currentSum // UNIT_CUT
i += 1
return BigInt(finalResult)
a = BigInt('1')
for i in xrange(2,300+1):
a = a.multiplty(BigInt(str(i)))
#a = a.addTo(BigInt(str(i)))
print a.description

view raw
BigInt.py
hosted with ❤ by GitHub

파이썬으로 실행한 결과는

real    0m0.659s
user    0m0.443s
sys 0m0.015s

놀랍게도 최적화하여 바이너리로 컴파일한 Swift 버전과 비슷한 속도인데, 심지어 pypy는 더 빠르다.

real    0m0.241s
user    0m0.216s
sys 0m0.023s

결론

  1. Swift는 기본 데이터 타입의 문제인지는 몰라도 애플이 이야기하는 것 만큼의 속도가 나지 않는 것으로 보인다. 특히 최적화가 적용되지 않았을 때의 인터프리터 방식의 실행 성능은 처참하다.
  2. 이론상으로는 Swift로 재작성한 앱은 Objective-C보다는 빨라야 한다. (Swift의 메소드 호출은 C++의 가상함수 테이블과 유사하다). 근데 Objective-C에서 메시징을 제외한 나머지 부분은 C이기 때문에 과연 현재 파이썬보다 느린 Swift가 Objective-C보다 빠를 것인지에 대해서는 장담이 어렵다.
  3. Swift로 커맨드라인툴이나 스크립팅 언어를 대체할만한 가능성은 충분히 크다. 대신, 왠만큼 자주 사용하는 것이고 변경의 소지가 적다면 왠만해선 컴파일 해서 쓰자.

일련의 stackoverflow 질문들에서 swift 상의 정렬이 너무 느리다, 수행 성능이 너무 떨어진다는 이야기가 많이 올라오고 있다. 이 질문의 작성자는 -Ofast 옵션을 발견했는데, 이 옵션으로 컴파일하는 경우 거의 C++ 네이티브 코드 수준으로 성능이 좋아진다고 한다. (아마 아예 C++ 코드로 트랜스 코딩된 다음 컴파일 되는 듯)