C언어에서 이런 용도에서 memcpy를 대신할 빠른 메소드
글쓴이: mandugukbap / 작성시간: 화, 2013/09/03 - 7:17오후
C언어에서 데이터 블록(10KB)을 매우 잦은 빈도로 복사하는 상황입니다.
int collect(mydata* d, void *data, int length)
int new_length = d->length + length;
void *t = (void *) malloc(new_length);
memset(t, 0, new_length);
memcpy(t, d->data, d->length);
memcpy(t + d->length, data, length);
free(d->data);
d->data = NULL;
d->data = t;
d->length = new_length;
... 하략 ...
}뭐 대충 이러한 코드입니다. 별생각 없이 메모리 블록 복사를 했는데 퍼포먼스에 큰 문제가 있네요.
첫째는, 위의 코드가 그리 엘레강트하지 않아서 쓸데없는 딜레이가 심해진거 같고
둘째는, memcpy가 아닌 포인터만을 이용해서 d에 데이터를 계속 누적시키는게 올바른 방법인 듯 한데
가장 효율적이고 정석이라고 부를 수 있는 방법을 찾고 싶습니다. 부디 고수님들의 해법을 기대해 봅니다.
Forums:
사이즈가 10kB 로 정해져 있다면 매번
사이즈가 10kB 로 정해져 있다면
매번 malloc 을 할 필요가 없죠. 어디서 한번만 하고 그걸 계속 쓰는 걸 추천합니다.
그리고 10 kB의 모든 공간을 쓴다면 memset 으로 초기화할 필요도 없죠.
overhead는 malloc(), free(), memset()의 호출에 있는 것 같네요.
답변 감사합니다. timestamp로 프로세싱
답변 감사합니다.
timestamp로 프로세싱 타임을 측정해 본 결과 memcpy() 역시 예상보다 많은 오버헤드가 있는거 같네요.
데이터(void *data) 의 사이즈는 10KB 로 정해져 있지 않습니다. 예를 든거지요. 실제로는 1KB ~ 100KB까지 다양합니다. 그리고, 재사용할 수 있는 시점은 데이터가 일정 크기로 모아진 상태입니다. 즉, 저 코드는 일정 microseconds마다 첨가되는 10KB 정도씩의 데이터를 어떤 버퍼에 모우는 역활을 합니다. 그 버퍼(d->data)가 예를들어 10MB가 되면 처리를 하고 해당 버퍼를 재사용할 수 있게 됩니다.
버퍼에 모으는 일이라면 충분히 큰 버퍼를 만들어두고
버퍼에 모으는 일이라면 충분히 큰 버퍼를 만들어두고 거기에서 계속 뒤에 덧붙이는 것도 한 방법입니다.
memcpy 가 오버헤드를 줄 정도라면 자작해도 크게 좋아지지 않을 확률이 크고요.
오버헤드에 영향을 가는한 작게 줄려면 dma 를 쓰는 방법도 있겠죠.
저기서 변수 mydata가 이미 구조체라면 구조체
저기서 변수 mydata가 이미 구조체라면 구조체 정의를 조금 고쳐서 linked list를 쓰면 되지 않나요?
//대충 이렇다 치고 struct mydata { void* data; int length; mydata next; }; void collect(mydata* d, void *data, int length){ mydata* newdata = (mydata*)malloc(sizeof(mydata)); void* newdata->data = (void*)malloc(length); newdata->data = data; d->next = newdata; }C문법이 기억이 안나서 대충 적었는데요, 이런 루틴이면 안될까요?
나중에 사용할 때는 next만 따라가면서 한번에 복사하면 되지 싶은데요
피할 수 있을때 즐겨라! http://melotopia.net/b
답변 감사 드립니다. Linked List라면
답변 감사 드립니다.
Linked List라면 확실히 몇개의 비싼 오퍼레이션을 줄일 수 있겠군요.
대부분 리눅스 배포판에서 사용하는 최근 glibc
대부분 리눅스 배포판에서 사용하는 최근 glibc 라이브러리의 memcpy() 함수는 이미 mmx / sse2 등으로 최적화되어 있습니다. 그럼에도 불구하고 성능상의 병목이라면 구조적인 설계 변경이 필요합니다. 예를 들어 작업 자체를 멀티쓰레드로 분산시키던가 아예 복사 작업을 더 잘게 나누어 OpenMP 등과 같은 병렬 프로그래밍 기법을 사용해야 하겠죠.
데이터 맵을 만들면 되지 않을까요?
만약 형식이 일정한 데이터가 들어온다면.
해시맵 같은걸 만들어서.
이런거면 1 ABCDEFG
이런거면 2 ABCDE
이런거면 3 AB
******
******
******
******
*
***
*****
모양도 되구요.
한글 조합 완성형 문자가 그런 형태라고 생각됩니다.
----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.
매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.
각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com
우선, 논지와 벗어난 이야기이지만 현재의 코드는
우선, 논지와 벗어난 이야기이지만 현재의 코드는 realloc() 동작방식과 거의 겹치므로
아래와 같이 코드를 단순화할 수 있을 것 같습니다.
int collect(mydata* d, void *data, int length) int new_length = d->length + length; d->data = realloc(d->data, new_length); d->length = new_length; memcpy(d->data + d->length, data, length); ... 하략 ... }그리고 이렇게 바꿔도 어차피 계속 재할당이 일어나게 되므로 그 상황을 피하려면,
만약 10MB 정도의 데이터가 모이기까지 사용하는 임시버퍼가 1개뿐이거나
혹은 복수개이더라도 갯수가 많지 않다면 그냥 충분한 크기로 선할당해두고 쓰시면 되지 않나요?
대신 아래와 같이 현재의 버퍼 실사용량을 관리할 변수(예: pos)가 필요하겠네요.
typedef struct tag_mydata { char *data; size_t length; /* 버퍼 전체크기 */ size_t pos; /* 버퍼 실사용량 */ ... } mydata;...
첨엔 그냥 지나갔는데 자세히 보니 전형적인 O(n^2) 케이스로군요. collect를 n번 부르면 첫번째 블럭은 n번, 두번째는 n-1번, 세번째는 n-2번... 이렇게 되어서 합계 O(n^2) 번 복사가 일어나게 됩니다.
이대로는 무슨 짓을 해도 절대 속도가 빠르게 될 수 없습니다.
굳이 하나의 버퍼에 모아야 한다면 한가지 좋은 방법이 있는데, 새로 malloc할 때 (기존버퍼 크기 + 새 데이터 크기)로 하지 말고 무조건 넉넉하게 (기존버퍼 크기 * 2)로 하는 것입니다. 예를 들면 처음에 1k 버퍼를 할당해서 채워넣다가 버퍼가 꽉 차면 (단지 1바이트만 모자라더라도) 2k로 재할당, 그게 다 차면 4k... 이렇게 할 수 있습니다.
"아니 그러면 최악의 경우 메모리가 반이나 남잖아?"라고 고개를 갸우뚱하시겠지만 실제로 계산해보면 O(n) 알고리즘이라 월등히 빠릅니다.
(실제로 C++의 vector가 이와 비슷하게 동작합니다. 뒤에 원소를 한개씩 N번 추가하면 시간복잡도가 O(N)이 됩니다.)
전형적인 통신 버퍼 같은데요
일정 데이터 쌓아서 그걸 사용하는거면 통신에서 많이 사용하는 버퍼같은데요
boost 에 링버퍼 한번 사용해보세요
http://www.boost.org/doc/libs/1_37_0/libs/circular_buffer/doc/circular_buffer.html
1. memset 은 불필요 합니다.2. 사용하고
1. memset 은 불필요 합니다.
2. 사용하고 계신 SDK의 c런타임 라이브러리 memcpy 구현을 살펴보시고,
1byte씩 복사되고 있는 코드라면, 4byte씩복사 하도록 새 함수를 만드세요.
(char 대신 uint32_t 등으로요.. 루프를 펼치는 것보다 좋을겁니다)
register 키워드(철자가 가물가물) 잘 활용하시면, 컴파일러 최적화 옵션에 좀 덜 영향을 받는
빠른 함수를 얻을 수 도 있습니다.
최악의 경우, 3byte 오버런이 생길수 있지만, 버퍼를 좀더 크게 잡으면 됩니다.
어차피 length가 있으니 쓰레기 값은 구분됩니다.
임베디드 환경에서는 효과를 본 기억이 있습니다.
3. 좀더 어렵게는, 최초의 데이터 생성/수신 위치를 이미 목적한 곳으로 하는겁니다.
이경우 버퍼를 미리 크게 잡아놔야 하겠네요..
예를 들면, 임시버퍼에 수신, 임시버퍼를 버퍼에 추가, 길이 업데이트..가 아니라
버퍼 마지막 부분에 수신, 길이 업데이트.. 같은식입니다.
댓글 달기