c - একটি 2D অ্যারের উপর পুনরাবৃত্তি যখন loops আদেশ কর্মক্ষমতা প্রভাবিত করে কেন?




performance for-loop (5)

নীচে দুইটি প্রোগ্রাম যা প্রায় অভিন্ন, ব্যতীত আমি i এবং j ভেরিয়েবলগুলিকে স্যুইচ করেছি। তারা উভয় সময় বিভিন্ন পরিমাণে চালানো। কেউ কি এই ঘটনার ব্যাখ্যা দিতে পারে?

সংস্করণ 1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

সংস্করণ 2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i + j; }
   }
}

অন্যরা বলেছে, ইস্যুটি হল অ্যারের মেমরি অবস্থানের দোকান: x[i][j] । এখানে অন্তর্দৃষ্টি একটি বিট কেন:

আপনার একটি 2-মাত্রিক অ্যারের আছে, তবে কম্পিউটারে মেমরিটি স্বতঃস্ফূর্তভাবে 1-মাত্রিক। সুতরাং যখন আপনি আপনার অ্যারের এই মত কল্পনা:

0,0 | 0,1 | 0,2 | 0,3
----+-----+-----+----
1,0 | 1,1 | 1,2 | 1,3
----+-----+-----+----
2,0 | 2,1 | 2,2 | 2,3

আপনার কম্পিউটারটি এটি একটি একক লাইন হিসাবে মেমরিতে সঞ্চয় করে:

0,0 | 0,1 | 0,2 | 0,3 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,1 | 2,2 | 2,3

দ্বিতীয় উদাহরণে, আপনি অ্যারে অ্যাক্সেস অ্যাক্সেস অ্যাক্সেস অ্যাক্সেস অ্যাক্সেস অ্যাক্সেস অ্যাক্সেস অ্যাক্সেস অ্যাক্সেস অ্যাক্সেস অ্যাক্সেস প্রথম, যেমন

x[0][0] 
        x[0][1]
                x[0][2]
                        x[0][3]
                                x[1][0] etc...

আপনি যাতে সব তাদের আঘাত করছি মানে। এখন 1 ম সংস্করণ তাকান। আপনি করছেন:

x[0][0]
                                x[1][0]
                                                                x[2][0]
        x[0][1]
                                        x[1][1] etc...

মেমরির মধ্যে 2-ডি অ্যারের মত সিটিয়ের কারণে, আপনি এটি সমস্ত জায়গাতে লাফ দিতে বলছেন। কিন্তু এখন kicker জন্য: কেন এই ব্যাপার? সমস্ত মেমরি অ্যাক্সেস একই, ডান?

না: কারণ ক্যাশে। আপনার মেমরি থেকে ডেটা সামান্য অংশে (যা 'ক্যাশ লাইন' বলা হয়) CPU- তে আনা হয়, সাধারণত 64 বাইট। যদি আপনার 4-বাইট পূর্ণসংখ্যা থাকে তবে এর অর্থ হল আপনি একটি সুগন্ধি ছোট্ট বান্ডিলের 16 টি ক্রমাগত পূর্ণসংখ্যা পাবেন। এটা আসলে মেমরি এই অংশ আনতে মোটামুটি ধীর; একটি সিউশ ক্যাশ লাইন লোড করার সময় আপনার CPU অনেক কাজ করতে পারে।

এখন অ্যাক্সেসের নির্দেশে ফিরে দেখুন: দ্বিতীয় উদাহরণটি হল (1) 16 টি ইন্টের একটি অংশ ধরে রাখা, (2) তাদের সকলকে সংশোধন করা, (3) 4000 * 4000/16 বার পুনরাবৃত্তি করুন। এটা চমৎকার এবং দ্রুত, এবং CPU এ সবসময় কাজ করার কিছু আছে।

প্রথম উদাহরণ হল (1) 16 ইটের একটি অংশ দখল করুন, (2) শুধুমাত্র তাদের মধ্যে একটি সংশোধন করুন, (3) 4000 * 4000 বার পুনরাবৃত্তি করুন। যে মেমরি থেকে "fetches" সংখ্যা 16 বার প্রয়োজন হবে। আপনার CPU- র প্রকৃতপক্ষে যে মেমরিটি দেখানোর জন্য অপেক্ষায় বসে থাকা সময় ব্যয় করতে হবে এবং এটি যখন আপনার কাছে বসে থাকবে তখন মূল্যবান সময় নষ্ট হচ্ছে।

গুরুত্বপূর্ণ তথ্য:

এখন আপনার উত্তর আছে, এখানে একটি আকর্ষণীয় নোট রয়েছে: আপনার দ্বিতীয় উদাহরণটি দ্রুত হওয়া উচিত এমন কোনো অন্তর্নিহিত কারণ নেই। উদাহরণস্বরূপ, ফোর্টান ইন, প্রথম উদাহরণ দ্রুত এবং দ্বিতীয় ধীর হবে। এর কারণ হল সি মত ধারণাগত "সারি" মধ্যে জিনিসগুলি প্রসারিত করার পরিবর্তে, ফোর্টানান "কলাম" এ বিস্তৃত, অর্থাত্:

0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 | 0,3 | 1,3 | 2,3

সিটির লেআউটটি 'সারি-প্রধান' এবং ফোর্ট্রানকে 'কলাম-মেজর' বলা হয়। আপনি দেখতে পারেন, আপনার প্রোগ্রামিং ভাষা সারি-প্রধান বা কলাম-প্রধান কিনা তা জানা খুবই গুরুত্বপূর্ণ! এখানে আরও তথ্যের জন্য একটি লিঙ্ক রয়েছে: http://en.wikipedia.org/wiki/Row-major_order


এই লাইন অপরাধী:

x[j][i]=i+j;

দ্বিতীয় সংস্করণটি ক্রমাগত দ্রুত মেমরি ব্যবহার করে।

আমি চেষ্টা করেছিলাম

x[50000][50000];

এবং execution সময় সংস্করণ 1 এর জন্য সংস্করণ 1 vs 0.6s জন্য 13s হয়।


ক্যাশে হিটগুলিতে অন্যান্য চমৎকার উত্তরগুলির পাশাপাশি, সম্ভাব্য অপটিমাইজেশন পার্থক্য রয়েছে। আপনার দ্বিতীয় লুপটি সমতুল্য কিছুতে কম্পাইলার দ্বারা অপ্টিমাইজ করা যেতে পারে:

  for (j=0; j<4000; j++) {
    int *p = x[j];
    for (i=0; i<4000; i++) {
      *p++ = i+j;
    }
  }

এটি প্রথম লুপের জন্য কম সম্ভাবনা, কারণ এটি প্রত্যেক সময় 4000 দিয়ে পয়েন্টার "পি" বৃদ্ধি করতে হবে।

সম্পাদনা করুন: p++ এবং এমনকি *p++ = .. সর্বাধিক সিপিইউ এর একটি সিপিএল নির্দেশনার জন্য কম্পাইল করা যেতে পারে। *p = ..; p += 4000 *p = ..; p += 4000 করতে পারে না, তাই এটি অপ্টিমাইজেশান কম সুবিধা আছে। এটি আরও কঠিন, কারণ কম্পাইলারটি অভ্যন্তরীণ অ্যারের আকার জানতে এবং ব্যবহার করতে হবে। এবং এটি প্রায়শই স্বাভাবিক কোডের অভ্যন্তরীণ লুপে ঘটে না (এটি শুধুমাত্র বহুমাত্রিক অ্যারেগুলির জন্য ঘটে থাকে, যেখানে শেষ সূচীটি লুপে ধ্রুবক রাখা হয় এবং দ্বিতীয় থেকে শেষটি ধাপে ধাপে রাখা হয়), তাই অপ্টিমাইজেশনটি অগ্রাধিকার কম ।


সংস্করণ 2 আরও দ্রুত চালনা করবে কারণ এটি আপনার কম্পিউটারের ক্যাশে সংস্করণ 1 এর চেয়ে ভালভাবে ব্যবহার করে। যদি আপনি এটি সম্পর্কে চিন্তা করেন, অ্যারেগুলি কেবল মেমরির সামঞ্জস্যপূর্ণ এলাকা। যখন আপনি একটি অ্যারেতে একটি উপাদান অনুরোধ করেন, তখন আপনার ওএস সম্ভবত একটি মেমরি পৃষ্ঠাটিকে ক্যাশে আনবে যা এতে রয়েছে। যাইহোক, যেহেতু পরের কয়েকটি উপাদান সেই পৃষ্ঠায় রয়েছে (কারণ তারা সংস্পর্শী), পরবর্তী অ্যাক্সেস ইতিমধ্যে ক্যাশে থাকবে! এই সংস্করণ 2 এটি গতি আপ পেতে কি করছে।

অন্যদিকে, সংস্করণ 1, কলাম অনুযায়ী উপাদানগুলি অ্যাক্সেস করছে এবং সারি অনুসারে নয়। অ্যাক্সেসের এই ধরণের মেমরি স্তরের সাথে সামঞ্জস্যপূর্ণ নয়, তাই প্রোগ্রামটি OS ক্যাশিংয়ের যত বেশি সুবিধা নিতে পারে না।


আমি একটি জেনেরিক উত্তর দিতে চেষ্টা করুন।

কারণ i[y][x] *(i + y*array_width + x) জন্য একটি শর্ট্যান্ড *(i + y*array_width + x) C শ্রেণীবিশিষ্ট int P[3]; 0[P] = 0xBEEF; )।

আপনি y উপর পুনরাবৃত্তি হিসাবে, আপনি array_width * sizeof(array_element) আকারের অংশগুলির উপর পুনরাবৃত্তি করুন। আপনার যদি আপনার অভ্যন্তরীণ লুপে এটি থাকে, তবে আপনার সেই অংশগুলিতে array_width * array_height পুনরাবৃত্তি থাকবে।

অর্ডারটি ফ্লিপ করার মাধ্যমে, আপনার কেবলমাত্র array_height -iterations থাকবে এবং যেকোনো array_width পুনরাবৃত্তির মধ্যে আপনার কেবল sizeof(array_element) এর array_width পুনরাবৃত্তি থাকবে।

যদিও সত্যিই পুরানো x86-CPUs এটার কোনও গুরুত্ব দেয় না, আজকাল 'x86 অনেকগুলি প্রিফচিং এবং ডেটা ক্যাশিং করে। আপনি সম্ভবত আপনার ধীর পুনরাবৃত্তি ক্রম অনেক ক্যাশে মিস উত্পাদন।





cpu-cache