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를 쓰면 되지 않나요?
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() 동작방식과 거의 겹치므로
아래와 같이 코드를 단순화할 수 있을 것 같습니다.
그리고 이렇게 바꿔도 어차피 계속 재할당이 일어나게 되므로 그 상황을 피하려면,
만약 10MB 정도의 데이터가 모이기까지 사용하는 임시버퍼가 1개뿐이거나
혹은 복수개이더라도 갯수가 많지 않다면 그냥 충분한 크기로 선할당해두고 쓰시면 되지 않나요?
대신 아래와 같이 현재의 버퍼 실사용량을 관리할 변수(예: pos)가 필요하겠네요.
...
첨엔 그냥 지나갔는데 자세히 보니 전형적인 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. 좀더 어렵게는, 최초의 데이터 생성/수신 위치를 이미 목적한 곳으로 하는겁니다.
이경우 버퍼를 미리 크게 잡아놔야 하겠네요..
예를 들면, 임시버퍼에 수신, 임시버퍼를 버퍼에 추가, 길이 업데이트..가 아니라
버퍼 마지막 부분에 수신, 길이 업데이트.. 같은식입니다.
댓글 달기