تاثیر ترتیب حلقه ها در سرعت دسترسی به همه ی اعضای آرایه ۲ بعدی

Question

من یک آرایه ۲ بعدی داشتم به این شکل :

float img[SIZE][SIZE];

 

میخواستم بدونم اگر به این شکل آرایه رو پردازش کنم :

for(i=0;i<SIZE;i++) 
    for(j=0;j<SIZE;j++) 
        img[j][i] = (2*j+i)%128;

با  کد زیر فرقی از نظر سرعت می کنه ؟

for(i=0;i<SIZE;i++) 
    for(j=0;j<SIZE;j++) 
        img[i][j] = (2*j+i)%128;

آخه من تست کردم عجیبه مورد دوم سریع تره ولی نمیدونم چرا ؟!

Answer 1

سلام

بخاطر ساختار آرایس  که اعضاش پشت سرهم در حافظه قرار میگیرند . و توجه کن که متغییر دوم در هر بار اجرای حلقه اول دوباره تعریف و مقدار دهی میشه

Answer 2

کد دوم بهتره دلیلش هم اینه که آرایه img در به صورت partial در l1 کش میشه  و نحوه ذخیره  آرایه  هم به صورت سطری هستش  ولی در کد اول miss cache بیشتری خواهید داشت یعنی هر بار با استفاده از یک خانه حافظه در هر سطر و رفتن به سطر بعدی miss cache صورت می گیره که البته این miss cache به ابعاد آرایه شما بستگی داره.

Answer 3

وکتور یا آرایه  در ++C  مثل آرایه حافظش پیوستست یعنی خانه های داخلش بترتیب داخل حافظه قرار گرفتن( list در c# هم همین طوره البته بخاطر new کردن به این شکل پیوسته نیست که یکی از دلایل کمتر بودن سرعت #C هم نسبت به ++C هستش )

 مثلا فرض کنید اگر 

vector<int> vec(5);

 

داشته باشیم 

آدرس خونه هاش بترتیب به این شکل میشه 

address vec[0] --> 0x9a47008
address vec[1] --> 0x9a4700c
address vec[2] --> 0x9a47010
address vec[3] --> 0x9a47014
address vec[4] --> 0x9a47018

برنامه روبرو رو برای دیدن آدرس ها ببینید :‌ https://ideone.com/hwa8us

آدرس ها به hex هستن اگر به decimal تبدیل شن به راحتی میشه دید که هر خونه که جلو میریم آدرس ۴ واحد بییشتر میشه (چون این جا چون vector از نوع int هستش ۴ بیت  ۴ بیت که همون اندازه int هست  آدرس بیشتر میشه )

بعد حالا نحوه قرار گیری خونه های حافظه ۱ بعدیه یعنی ما اگر یک vector دو بعدی الان داشته باشیم 

vector<vector<int>> vec;

توی ++C به این شکل  سطری داخل حافظه ذخخیره میشه یعنی یک آرایه ۲ بعدی به شکل یک آرایه یک بعدی  بزرگ داخل حافظه ذخیره میشه 

 مثلا اگر یک vector با اندازه 3*5 داشته باشیم به این شکل ذخیره میشه که :

std::vector<std::vector<int>> vec(5);
    for( auto& i : vec)
        vec.push_back(std::vector<int>(3));

Gharar giri dar hafeze : 

 vec[0][0]- vec[0][1]- vec[0][2]-vec[1][0]- vec[1][1]- vec[1][2] .....vec[4][0]- vec[4][1]- vec[4][2]

 

اجرای کد :  https://ideone.com/BcUtgW

آدرس ها هم باز هم مشخصه که ۴ تا ۴ تا میرن جلو و وقتی که به سطر بعدی میریم یک جهش به اندازه ۱۲ واحد میکنن ( چون ۳ تا ستون داره ۳*۴)

محل هایی از ram که قرار cpu دستور العمل هاشو روشون اجرا کنه برای سرعت بیشتر داخل یکسری حافظه فوق العاده سریع که بهشون cache هم گفته میشه ذخیره میشن که l1 یکیشونه (‌داخل این سوال کاملتر توضیح دادم کلیک کنید )

حالا وقتی که بصورت دوم به آرایه دسترسی دارین دارین خونه های حافظه رو بترتیب و به شکلی که داخل حافظه ذخیره شدن می خونین کامپایلر میتونه هر سطر رو قبل از انجام محاسبات داخل L1 ذخیره کنه که باعث سرعت بیشتر میشه

ولی به شکل اول چون نمی تونه دقیق خونه ها رو پیدا کنه مثادیر داخل L1 ذخیره نمیشن یا به اشتباه ذخیره میشن که اصطلاحا بهش miss caching هم می گن  .

البته اگر سایز آرایه کوچیک باشه این مشکل وجود نداره چون کل آرایه داخل L1 جا میشه و کلش ذخیره میشه .