C API strcat을 무조건 신뢰하면 안되는 이유

회사에서 한창 마이크로그리드 플랫폼 프로젝트 진행 중에

C로 개발된 통신 프로그램의 성능이슈가 있어,

성능개선 작업중에 발견했던 문제를 공유합니다.

 

C에서 문자열을 합칠 때, 흔히들 내장 API로 제공되는 sprintf 혹은 strcat을 많이 사용합니다.

하지만, 우리가 사용하는 strcat은 누적해서 문자열을 더해나가는 조건에선

상당히 비효율적으로 문자열을 합친다는 거 알고계셨나요??

strcat은 기본적으로 destination으로 주어진 문자열을

처음부터 문자열의 끝을 의미하는 '\0'를 만날 때까지 탐색한 뒤,

'\0'부터 입력으로 주어진 source 문자열을 더해나갑니다.

 

만약 아래와 같은 코드가 실행된다고 가정해 봅시다.

#define MAX_BUF 1000000

int main()
{
	char buf[MAX_BUF];
	int u;
	for(u=0; u<10000; u++)
	{
    	strcat(buf, "abc")
	}
	return 0;
}

buf변수에 누적해서 "abc"라는 단어를 붙여간다고 했을 때, 

처음 반복문이 실행되면(u=0), buf는 "abc"가 됩니다.

그다음 u=1일 때, buf에 문자열 "abc"를 탐색한 뒤, "abc"를 붙입니다.

u=2일 때, buf에 문자열 "abcabc"를 탐색한 뒤, "abc"를 붙입니다.

u=3일 때, buf에 문자열 "abcabcabc"를 탐색한 뒤, "abc"를 붙입니다.

...

붙여야 될 문자열의 총길이가 n이라고 가정했을 때, 시간복잡도는 O(n^2)가 됩니다. 

단순히 문자열 끝에 붙이기만 하는 로직인데, 붙일 때마다 destination 문자열을 탐색하는 로직은 비효율적으로 보입니다.

 

그럼 어떻게 개선할 수 있을까요??

붙여질 문자열의 끝이 어디인지를 기억하고 있으면 됩니다.

strcat을 수행한 뒤, destination 문자열의 '\0'를 가리키는 포인터를 저장해 두는 것이죠.

아래 코드로 수행한다면, O(n) 시간으로 문자열을 합칠 수 있습니다.

 

#define MAX_BUF 1000000

char* mystrcat(char* dest, const char* src)
{
	while (*dest) dest++;
	while (*dest++ = *src++);
	return --dest;
}

int main()
{
	char buf[MAX_BUF];
	char *p = buf;
	buf[0] = '\0';
	int u;
	for(u=0; u<10000; u++)
	{
    	p = mystrcat(p, "abc");
	}
	return 0;
}

기존 strcat을 개선한 mystrcat이라는 함수를 만듭니다.

함수의 인자는 기존 strcat과 동일한 destination과 source문자열을 입력으로 받습니다.

5번째 라인에서 destination이 문자열 끝일 때까지 위치를 찾습니다.

6번째 라인에서 destination의 끝부터 source를 문자열을 붙여나갑니다.

여기까지는 기존 strcat과 동일합니다.

6번째 라인에서 destination은 이미 문자열의 끝인 '\0'까지 복사를 완료한 상태입니다.

7번째 라인에선 현재 destination이 위치한 포인터에서 바로 직전 포인터를 리턴합니다.

단순히 destination의 포인터를 리턴할 뿐인데, 많은 것이 달라집니다.

 

18번째 라인을 보면, 초기 p에 할당된 buf주소를 시작으로 buf에 기록된 문자열의 끝 포인터를 리턴 받아,

다음 반복문에서 입력으로 사용해 계속해서 끝 위치를 가르키도록 작성되었습니다.

즉, 끝위치를 반복해서 찾을 필요가 없어졌습니다.

 

strcat의 고질적인 문제를 해결할 수 있는 방법을 제시드렸지만,

사실 C는 문자열을 다루기에 적합하지도 않을뿐더러, strcat을 개선할만큼 특수한 상황이 많진 않습니다.

하지만, 단 1ms이라도 속도를 개선해야 되는 프로그램을 작성할 땐 많은 도움이 될 수도 있기에

뭐든 상황에 맞게 사용하는 게 중요한 듯합니다.

 

아래는 참고했던 사이트입니다. 

 

https://beribey.medium.com/why-string-concatenation-so-slow-745f79e22eeb

Why String Concatenation so Slow?