C언어에서 이런 용도에서 memcpy를 대신할 빠른 메소드

mandugukbap의 이미지

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에 데이터를 계속 누적시키는게 올바른 방법인 듯 한데

가장 효율적이고 정석이라고 부를 수 있는 방법을 찾고 싶습니다. 부디 고수님들의 해법을 기대해 봅니다.

라스코니의 이미지

사이즈가 10kB 로 정해져 있다면
매번 malloc 을 할 필요가 없죠. 어디서 한번만 하고 그걸 계속 쓰는 걸 추천합니다.

그리고 10 kB의 모든 공간을 쓴다면 memset 으로 초기화할 필요도 없죠.

overhead는 malloc(), free(), memset()의 호출에 있는 것 같네요.

mandugukbap의 이미지

답변 감사합니다.

timestamp로 프로세싱 타임을 측정해 본 결과 memcpy() 역시 예상보다 많은 오버헤드가 있는거 같네요.

데이터(void *data) 의 사이즈는 10KB 로 정해져 있지 않습니다. 예를 든거지요. 실제로는 1KB ~ 100KB까지 다양합니다. 그리고, 재사용할 수 있는 시점은 데이터가 일정 크기로 모아진 상태입니다. 즉, 저 코드는 일정 microseconds마다 첨가되는 10KB 정도씩의 데이터를 어떤 버퍼에 모우는 역활을 합니다. 그 버퍼(d->data)가 예를들어 10MB가 되면 처리를 하고 해당 버퍼를 재사용할 수 있게 됩니다.

라스코니의 이미지

버퍼에 모으는 일이라면 충분히 큰 버퍼를 만들어두고 거기에서 계속 뒤에 덧붙이는 것도 한 방법입니다.
memcpy 가 오버헤드를 줄 정도라면 자작해도 크게 좋아지지 않을 확률이 크고요.

오버헤드에 영향을 가는한 작게 줄려면 dma 를 쓰는 방법도 있겠죠.

snowall의 이미지

저기서 변수 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

mandugukbap의 이미지

답변 감사 드립니다.

Linked List라면 확실히 몇개의 비싼 오퍼레이션을 줄일 수 있겠군요.

익명 사용자의 이미지

대부분 리눅스 배포판에서 사용하는 최근 glibc 라이브러리의 memcpy() 함수는 이미 mmx / sse2 등으로 최적화되어 있습니다. 그럼에도 불구하고 성능상의 병목이라면 구조적인 설계 변경이 필요합니다. 예를 들어 작업 자체를 멀티쓰레드로 분산시키던가 아예 복사 작업을 더 잘게 나누어 OpenMP 등과 같은 병렬 프로그래밍 기법을 사용해야 하겠죠.

shint의 이미지

만약 형식이 일정한 데이터가 들어온다면.
해시맵 같은걸 만들어서.

이런거면 1 ABCDEFG
이런거면 2 ABCDE
이런거면 3 AB

******
******
******
******

*
***
*****

모양도 되구요.

한글 조합 완성형 문자가 그런 형태라고 생각됩니다.

----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.

매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.

각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com

chanik의 이미지

우선, 논지와 벗어난 이야기이지만 현재의 코드는 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;

jick의 이미지

첨엔 그냥 지나갔는데 자세히 보니 전형적인 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)이 됩니다.)

pokev25의 이미지

일정 데이터 쌓아서 그걸 사용하는거면 통신에서 많이 사용하는 버퍼같은데요

boost 에 링버퍼 한번 사용해보세요

http://www.boost.org/doc/libs/1_37_0/libs/circular_buffer/doc/circular_buffer.html

Anti-Lock의 이미지

1. memset 은 불필요 합니다.
2. 사용하고 계신 SDK의 c런타임 라이브러리 memcpy 구현을 살펴보시고,
1byte씩 복사되고 있는 코드라면, 4byte씩복사 하도록 새 함수를 만드세요.
(char 대신 uint32_t 등으로요.. 루프를 펼치는 것보다 좋을겁니다)
register 키워드(철자가 가물가물) 잘 활용하시면, 컴파일러 최적화 옵션에 좀 덜 영향을 받는
빠른 함수를 얻을 수 도 있습니다.
최악의 경우, 3byte 오버런이 생길수 있지만, 버퍼를 좀더 크게 잡으면 됩니다.
어차피 length가 있으니 쓰레기 값은 구분됩니다.
임베디드 환경에서는 효과를 본 기억이 있습니다.
3. 좀더 어렵게는, 최초의 데이터 생성/수신 위치를 이미 목적한 곳으로 하는겁니다.
이경우 버퍼를 미리 크게 잡아놔야 하겠네요..
예를 들면, 임시버퍼에 수신, 임시버퍼를 버퍼에 추가, 길이 업데이트..가 아니라
버퍼 마지막 부분에 수신, 길이 업데이트.. 같은식입니다.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.