استفاده بهینه از memcpy

[UfnCod3r]

به نام خدا و سلام
تو این تاپیک می خوام در مورد تابع memcpy توضیح بدم و بگم که کجا ها باید استفاده کنید و کجا ها نه !
چون خودم هر جا استفاده می کردم و فکر می کردم سریع تره :اشتباه:

خب اول از همه کار این تابع چیست ؟
کارش کپی کردن قسمتی از حافظه هست !
خوب حالا می ریم کدهاشو بررسی کنیم ببینیم چطور کار می کنه ! :متفکر:
این برا MSVC++‎10 هست ! ممکنه تو کامپایلر های دیگه یکمی فرق داشته باشه !

void * __cdecl memcpy ( void * dst, const void * src, size_t count)
{
void * ret = dst;
while (count--)
{
*(char *)dst = *(char *)src;
dst = (char *)dst + 1;
src = (char *)src + 1;
}
return ret;
}

اگه فکر می کنید این ها اون نیست خودتون سرعتشو امتحان کنید ! دقیقا همونه !:لبخندساده:
کارش که واضحه به تعداد count بایت بایت میره جلو و src و می ریزه تو dst

خب حالا من 2 تا نمونه استفاده نادرست رو می زارم !

#include <memory>
int gArray1[1024];
int gArray2[1024];

int main(int _vrgc, char** _argv )
{
memcpy(gArray2, gArray1, sizeof(int[1024]));
}

-

#include <memory>
class Matrix
{
float m[16];
Matrix();
Matrix(const Matrix& _copy);
};

Matrix::Matrix( const Matrix& _copy )
{
memcpy(this, &_copy, sizeof(float[16]));
}


عوض اینا باید از for استفاده کنیم یعنی اینطوری ::


int gArray1[1024];
int gArray2[1024];

int main(int _vrgc, char** _argv )
{
for(int i = 0; i < 1024; i++)
gArray2[i] = gArray1[i];
}

-

class Matrix
{
float m[16];
Matrix();
Matrix(const Matrix& _copy);
};

Matrix::Matrix( const Matrix& _copy )
{
for(int i = 0; i < 16; i++)
m[i] = _copy.m[i];
}


خب چه دلیلی داشت که حلقه گذاشتیم !
به خاطر اینکه وقتی حلقه ما تکرارش تعداد مشخصی باشه ! مثلا 10 بار تکرار بشه !
کامپیلر میاد کد مربوط به اونو خط به خط جایگزین می کنه و بنابراین دیگه شرط و عمل کاهش و یا افزایش انجام نمیشه و کد سریع تر تره !:لبخندساده:
پس این ::

for(int i = 0; i < 4; i++)
a[i] = b[i];

تبدیل می شود به این ::

a[0] = b[0];
a[1] = b[1];
a[2] = b[2];
a[3] = b[3];


امیدوارم همه چی رو متوجه شده باشید !
دیگه باید بدونید که کجا از memcpy استفاده کنید .:تشویق:
تمام شد !
:قلب:

[pswin.pooya]

سلام

بعضی از دوستان از جمله یوزر سپول سعی در بهینه سازی اون کرده بود. مثلا سپول تا اونجا که یادم میاد از SSE استفاده کرده بود. یا میشه برای کپی های بزرگ از OpenMP استفاده کرد ( که عملا کپی داخل جند هسته به صورت همزمان صورت بگیره ). فقط یه سوال مطرح میشه. کد تا چه حد بهینه میشه. یعنی مقدار بهینه شدن ارزش پیچیده شدن سورس رو داره؟!


در مورد بلوکهای کوچیک داده استفاده از قالبهای بزرگتر برای انتقال بهتر از استفاده از مواردی همانند for هست. علتش اینه که زمانی شما دارید از for یا while و یا هر دستور شرطی دیگه استفاده می کنید کامپایلر یک کد شرط غیر قابل پیش بینی رو تولید میکنه. و این نوع شرطها و پرشهای مرتبط با اونها مخالف کانال پردازشی پردازنده هستند. هر بار که پردازنده با همچین دستورانی برخورد میکنه نمی تونه نقطه بعدی رو که پرش به اونجا انجام میگیره رو پیش بینی کنه. در نتیجه کل کانال پردازش خالی میشه و توی برخی از پردازنده ها مثل ARM یه چیزی حدود 13 سیکل برنامه کندتر میشه. پس اگر بجای حلقه توی موارد کوچیک بصورت کدینگ سخت تخصیص رو انجام بدیم کد سریعتر میشه . مثلا توی همون مدل آرم با یه پرش 13 تا تخصیص کار عقب میمونه. یعنی عملا یه چیزی حدود 13 برابر برنامه کندتر میشه (البته پارامترهای زیادی وجود داره این مقدار اخلاف امکان داره بیشتر یا کمتر بشه ). دقیقا بهینه ساز کامپایلر هم همین موارد رو در نظر میگیره.

یه مورد دیگه هم که در مورد کد memcpy وجود داره کپی فراخوانی memcpy هست که epilogue و prologue تابع باعث کندتر شدن میشن. اگر تابع بصورت inline تعریف شه سرعت عملا تفاوت چشمگیری میکنه ( و همینطور حجم برنامه :لبخند: (

[سپول]

@__UFNHGGI_H__:
من شک دارم نتیجه گیری شما درست باشه ...
- اولا در نوشته هاتون هیچگونه benchmark و تایم ای وجود نداره که دو متد رو مقایسه کنه.
- اون تابعی که در مورد memcpy در vc نوشتید رو از کجا آوردید ؟ اون خیلی عجیب هست، چون اولا memcpy بصورت کامپایل شده (به زبان asm) در کتابخانه C سیستم عامل موجود هست و لینک می شه به برنامه نه اینکه سورسش موجود باشه. شاید اون سورس از نسخه دیباگی چیزی باشه (من که vs2010 دارم جایی ندیدم) ... در ضمن memcpy در هر سیستم عامل یکی از پر مصرف ترین توابع و در نتیجه بهینه ترین اونها هست و از انواع الگوریتم ها (بنا به اندازه بافر و alignment) استفاده می کنه. مانند SSE/SSE2 و packing.
- این متدی که میگی فقط در موارد خاص شاید جواب باشه، مثلا انتقال دادن 4 یا 16 تا متغیر، نه بیشتر.
- memcpy ها معمولا از روش های انتقال بلوکی از داده ها استفاده می کنند. مثلا یک بافر 2000 بایتی رو به 31 بلوک 64 بایتی (و چند بایت باقیمانده) تقسیم می کنه و با استفاده از instruction های خاص cpu اونها رو در cache قرار می ده و یک جا انتقال می ده.

[UfnCod3r]

سورسش تو
C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\crt\src
هست .
اتفاقا" منم همین فکرو می کردم ولی اخر به اون کد رسیدم . دیدم سرعتش همون . :متعجب:
من تو نت هم کلی کشتم برا بقیه هم همین مدلی ها بود .
اونی که گذاشتم رو کلی تست کردم سرعتش دقیقا برابر بود .


- memcpy ها معمولا از روش های انتقال بلوکی از داده ها استفاده می کنند. مثلا یک بافر 2000 بایتی رو به 31 بلوک 64 بایتی (و چند بایت باقیمانده) تقسیم می کنه و با استفاده از instruction های خاص cpu اونها رو در cache قرار می ده و یک جا انتقال می ده.

اره . اینو دیدم تو نت .
من یه چندتا خودم نوشتم . مثلا 32 بیت 32بیت کپی کنه ولی نمی دونم چرا اصلا کند تر شد :متفکر: برا حجم های خیلی زیاد هم امتحان کردم .

void XMemCopy32(void* _dst, void* _src, size_t _count)
{
while (_count)
{
_count--;
*((int*)_dst) = *((int*)_src);
_dst = ((int*)_dst) + 1;
_src = ((int*)_src) + 1;
}
}

انقدر با این memcpy ها ور رفتم خسته شدم اخرم بیخیال شدم :قهقهه:
ولی به نظرم خیلی جاها دستی کارکنیم بهتر مخصوصا برا موقعی که حجم نسبتا کمی می خوایم انتقال بدیم خود کامپیلر اپتیمایزش می کنه خوب میشه .
البته یه مسله این که چون تو اون تابع memcpy از ارگومان هاش استفاده شده و 3 تاشون هم تو ثبات هستن سریع تر میشه .:متفکر:
حالا یکی دیگه اون کد رو با memcpy اصلی مقایسه کنه . شاید سیستم من اینطوریه . CPU Core 2 Quad

الان می رم یه تست میارم نتیجه رو هم می دم :قلب:

[UfnCod3r]

اقا من امتحان کردم . نمی دونم چرا الان اونی که من گذاشتم کنده :متعجب:
قبلا امتحان کردم سرعتش همون بود :متعجب:
الان با for نوشتم تو 32 بیتی سریع تره .
ولی تو 64 بیتی با memcpy یکم سریع تره .

با VC++10 کامپایلوندم . Realese, RTTI Off
Intel Core 2 Quad 8300
Win7 x64

#include <stdlib.h>
#include <iostream>
#include <Windows.h>
#include <tchar.h>
#include <vector>

//32bit, ba WOW64
//NO MEMCPY >> 0.299 , 0.305
//MEMCPY >> 0.337 , 0.351
//MyMecpy >> :((

//64Bit
//NO MEMCPY >> 0.244 , 0.250
//MEMCPY >> 0.210 , 0.226
//MyMecpy >> :((

//0 == no memcpy
//1 == memcpy
//2 == mymemcpy
#define USAGE 0


__declspec(noinline) void* __cdecl mymemcpy ( void * dst, const void * src, size_t count)
{
void * ret = dst;
while (count--)
{
*(char *)dst = *(char *)src;
dst = (char *)dst + 1;
src = (char *)src + 1;
}
return ret;
}



#define MATRIX_ELEMENT 16

class Matrix
{
public:
float m[MATRIX_ELEMENT];
__declspec(noinline) void set(const Matrix* _copy);
};

void Matrix::set( const Matrix* _copy )
{
#if USAGE == 0
for(int i = 0; i < MATRIX_ELEMENT; i++)
m[i] = _copy->m[i];
#elif USAGE == 1
memcpy(this, _copy, sizeof(Matrix));
#else
mymemcpy(this, _copy, sizeof(Matrix));
#endif
}

int _tmain(int argc, _TCHAR* argv[])
{
system("pause");

int $n = 4000 + (rand() % 2);
Matrix* $mats = new Matrix[$n];
LARGE_INTEGER $t1, $t2, $freg;
for( int k = 0; k < 8; k++)
{
QueryPerformanceCounter(&$t1);
int $rep = 1024 + (rand() % 2);

for(int j = 0; j < $rep; j++)
for(int i = 0; i < $n; i++)
{
$mats[i].set(&$mats[rand() % $n]);
$mats[j].set( &$mats[i] );
$mats[k].set( &$mats[i] );
}

QueryPerformanceCounter(&$t2);
QueryPerformanceFrequency(&$freg);

float $elpased = ($t2.QuadPart - $t1.QuadPart) / ((double) $freg.QuadPart);

printf("%d Elapsed: %f M: %f\n", k, $elpased, $mats[rand() % $n].m[0]);
}

system("pause");
delete $mats;
return 0;
}

[سپول]

اون implementation قاعدتا نباید اونی باشه که تو برنامه شما اجرا می شه...
در ضمن در 64 بیت بهتره که از انتقال متغیر با استفاده از رجیستر های 64 بیتی استفاده کنی.

memcpy باز هم تاکید می کنم که بهینه سازی بیشتری از این حرفها داره ... به عنوان مثال برای memset مقدار زیادی از حافظه من از حافظه align شده و تابع زیر استفاده می کنم :
http://www.hmrengine.com/blog/?p=205

مورد دیگه اینکه اگه می خوای ببینی واقعا چه کدی اجرا می شه از disassembler وِیژوال استودیو استفاده کن. اونی که اونجا هست و در کامنت ها هست احتمالا psuedo code هست که فقط می خواد الگوریتم کلی کار رو بگه.
به عنوان مثال در vs2010 + ICC من disassembler ، کد زیر رو برای memcpy نشون می ده :



% public _MEM_
_MEM_ proc \
dst:ptr byte, \
src:ptr byte, \
count:IWORD

; destination pointer
; source pointer
; number of bytes to copy

; push ebp ;U - save old frame pointer
; mov ebp, esp ;V - set new frame pointer

push edi ;U - save edi
push esi ;V - save esi

mov esi,[src] ;U - esi = source
mov ecx,[count] ;V - ecx = number of bytes to move

mov edi,[dst] ;U - edi = dest

;
; Check for overlapping buffers:
; If (dst <= src) Or (dst >= src + Count) Then
; Do normal (Upwards) Copy
; Else
; Do Downwards Copy to avoid propagation
;

mov eax,ecx ;V - eax = byte count...

mov edx,ecx ;U - edx = byte count...
add eax,esi ;V - eax = point past source end

cmp edi,esi ;U - dst <= src ?
jbe short CopyUp ;V - yes, copy toward higher addresses

cmp edi,eax ;U - dst < (src + count) ?
jb CopyDown ;V - yes, copy toward lower addresses

;
; Copy toward higher addresses.
;
CopyUp:
;
; First, see if we can use a "fast" copy SSE2 routine
; block size greater than min threshold?
cmp ecx,080h
jb Dword_align
; SSE2 supported?
cmp DWORD PTR __sse2_available,0
je Dword_align
; alignments equal?
push edi
push esi
and edi,15
and esi,15
cmp edi,esi
pop esi
pop edi
jne Dword_align

; do fast SSE2 copy, params already set
jmp _VEC_memcpy
; no return
.... (کد ادامه دارد ...)

همونطور که می بینی اون لوپ ساده نیست و چند جور چک (و بهینه سازی) داره و حتی یک جا چک می کنه که SSE2 داری یا نه و من چون cpu ام این قابلیت رو داشت، تابع _VEC_memcpy رو صدا می زنه.

[UfnCod3r]

دمت گرم . راست می گی . ممنون !
:قلب:
:قلب: