c++ - কেন আমার প্রোগ্রাম ধীর যখন ঠিক 8192 উপাদান looping?




performance memory-management (2)

নিম্নলিখিত পরীক্ষাগুলি ভিসুয়াল সি ++ কম্পাইলারের সাথে সম্পন্ন হয়েছে কারণ এটি ডিফল্ট QT নির্মাতার ইনস্টলেশনের দ্বারা ব্যবহৃত হয় (আমি কোন অপ্টিমাইজেশান ফ্ল্যাগ সহ অনুমান করি)। জিसीसी ব্যবহার করার সময়, রহস্যময় সংস্করণ এবং আমার "অপ্টিমাইজড" কোডের মধ্যে কোন বড় পার্থক্য নেই। তাই উপসংহার যে কম্পাইলার অপ্টিমাইজেশান মানুষের চেয়ে মাইক্রো অপ্টিমাইজেশান ভাল যত্ন নিতে (শেষ পর্যন্ত আমি)। আমি রেফারেন্সের জন্য আমার উত্তর বাকি।

এটা এই ভাবে ইমেজ প্রক্রিয়া দক্ষ নয়। একক মাত্রা অ্যারে ব্যবহার করা ভাল। সমস্ত পিক্সেল প্রক্রিয়াকরণ এক লুপ সম্পন্ন করা হয়। পয়েন্টগুলিতে র্যান্ডম অ্যাক্সেস ব্যবহার করা যেতে পারে:

pointer + (x + y*width)*(sizeOfOnePixel)

এই বিশেষ ক্ষেত্রে, তিনটি পিক্সেল গোষ্ঠীর সমষ্টি অনুপাত এবং ক্যাশে করা ভাল কারণ এটি তিনটি বার ব্যবহার করা হয়।

আমি কিছু পরীক্ষা করেছি এবং আমি ভাগ করে নেওয়ার মূল্য মনে করি। প্রতিটি ফলাফল পাঁচটি পরীক্ষা গড়।

ব্যবহারকারী 1615209 দ্বারা মূল কোড:

8193: 4392 ms
8192: 9570 ms

রহস্যময় সংস্করণ:

8193: 2393 ms
8192: 2190 ms

একটি 1 ডি অ্যারে ব্যবহার করে দুটি পাস: প্রথম অনুভূমিক রেখার জন্য পাস, উল্লম্ব সমষ্টি এবং গড়ের জন্য দ্বিতীয়। দুটি পয়েন্টার সম্বলিত দুটি পাস এবং এইরকম বৃদ্ধি মাত্র:

imgPointer1 = &avg1[0][0];
imgPointer2 = &avg1[0][SIZE];
imgPointer3 = &avg1[0][SIZE+SIZE];

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(*(imgPointer1++)+*(imgPointer2++)+*(imgPointer3++))/9;
}

8193: 938 ms
8192: 974 ms

একটি 1D অ্যারে ব্যবহার করে দুটি পাস এবং এই মত ঠিকানা:

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(hsumPointer[i-SIZE]+hsumPointer[i]+hsumPointer[i+SIZE])/9;
}

8193: 932 ms
8192: 925 ms

এক পাস ক্যাশিং অনুভূমিক রেখার মাত্র এক সারি যাতে তারা ক্যাশে থাকে:

// Horizontal sums for the first two lines
for(i=1;i<SIZE*2;i++){
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
}
// Rest of the computation
for(;i<totalSize;i++){
    // Compute horizontal sum for next line
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
    // Final result
    resPointer[i-SIZE]=(hsumPointer[i-SIZE-SIZE]+hsumPointer[i-SIZE]+hsumPointer[i])/9;
}

8193: 599 ms
8192: 652 ms

উপসংহার:

  • কয়েক পয়েন্টার এবং মাত্র বৃদ্ধি ব্যবহার কোন সুবিধা (আমি এটা দ্রুত হয়েছে মনে হয়)
  • অনুভূমিক অনুচ্ছেদের ক্যাশে তাদের বেশ কয়েকবার কম্পিউটিং তুলনায় ভাল।
  • দুই পাস শুধুমাত্র তিনবার দ্রুত নয়, দুই বার।
  • একটি একক পাস এবং একটি মধ্যবর্তী ফলাফল ক্যাশিং ব্যবহার করে 3.6 গুণ দ্রুততর অর্জন করা সম্ভব

আমি নিশ্চিত এটা অনেক ভাল করতে সম্ভব।

উল্লেখ্য, দয়া করে মনে রাখবেন যে আমি এই উত্তরটি জেনারেল পারফরম্যান্সের বিষয়গুলি লক্ষ্য করার পরিবর্তে মিস্টিকালের চমৎকার উত্তরে ব্যাখ্যা করা ক্যাশে সমস্যাটি লক্ষ্য করে লিখেছি। শুরুতে এটি শুধু ছদ্ম কোড ছিল। আমি মন্তব্য পরীক্ষা করতে বলা হয় ... এখানে পরীক্ষা সঙ্গে একটি সম্পূর্ণ refactored সংস্করণ।

এখানে প্রশ্ন প্রোগ্রাম থেকে নির্যাস হয়। ম্যাট্রিক্স img[][] আকার SIZE × SIZE আছে, এবং এ আরম্ভ করা হয়:

img[j][i] = 2 * j + i

তারপরে, আপনি একটি ম্যাট্রিক্স res[][] , এবং এখানে প্রতিটি ক্ষেত্রটি আইজিগ ম্যাট্রিক্সে এটির 9টি ক্ষেত্রের গড় হিসাবে তৈরি করা হয়। সীমান্ত সরলতার জন্য 0 এ বামে।

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

যে সব প্রোগ্রাম আছে। সম্পূর্ণতা জন্য 'অনুরোধ, এখানে কি আসে আগে। কোন কোড পরে আসে। আপনি দেখতে পারেন, এটি শুধু আরম্ভ।

#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; //result of mean filter
int i,j,k,l;
for(i=0;i<SIZE;i++) 
    for(j=0;j<SIZE;j++) 
        img[j][i] = (2*j+i)%8196;

মূলত, SIZE যখন ২048 এর একাধিক হয় তখন এই প্রোগ্রামটি ধীর হয়, যেমন মৃত্যুদণ্ডের সময়:

SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

কম্পাইলার জিसीसी হয়। আমি যা জানি তা থেকে, এটি মেমরি পরিচালনার কারণে, কিন্তু আমি সত্যিই সেই বিষয় সম্পর্কে খুব বেশি কিছু জানি না, তাই আমি এখানে জিজ্ঞাসা করছি।

এছাড়াও কিভাবে এটি ঠিক করা ভাল হবে, কিন্তু কেউ এই নির্বাহের বার ব্যাখ্যা করতে পারে যদি আমি ইতিমধ্যে যথেষ্ট খুশি হতে চাই।

আমি ইতিমধ্যে malloc / বিনামূল্যে জানি, কিন্তু সমস্যাটি ব্যবহৃত মেমরির পরিমাণ নয়, এটি কেবলমাত্র কার্যকর সময়, তাই আমি জানি না যে এটি কীভাবে সাহায্য করবে।


পার্থক্য নিম্নলিখিত সম্পর্কিত প্রশ্ন থেকে একই সুপার-অ্যালাইনমেন্ট সমস্যা দ্বারা সৃষ্ট হয়:

  • 513x513 এর একটি ম্যাট্রিক্স ট্রান্সফোজ করার চেয়ে 512x512 এর একটি ম্যাট্রিক্স ট্রান্সপোজ করছে কেন?
  • ম্যাট্রিক্স গুণ: ম্যাট্রিক্স আকার ছোট সময়, পার্থক্য বড় পার্থক্য

কিন্তু কোডের সাথে অন্য সমস্যা থাকলেই এটি শুধুমাত্র।

মূল লুপ থেকে শুরু হচ্ছে:

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

প্রথম অভ্যন্তরীণ loops তুচ্ছ যে প্রথম নোটিশ। তারা নীচের হিসাবে unrolled করা যেতে পারে:

for(i=1;i<SIZE-1;i++) {
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

সুতরাং যে আমরা আগ্রহী দুই বাইরের loops পাতা।

এখন আমরা এই প্রশ্নের মধ্যে একই সমস্যা দেখতে পাচ্ছি: 2 ডি অ্যারের উপর পুনরাবৃত্তি করার সময় লুপগুলির ক্রম কর্মক্ষমতা প্রভাবিত করে কেন?

আপনি সারি অনুসারে পরিবর্তে ম্যাট্রিক্স কলাম-এর পুনরাবৃত্তি করছেন।

এই সমস্যা সমাধানের জন্য, আপনি দুটি loops বিনিময় করা উচিত।

for(j=1;j<SIZE-1;j++) {
    for(i=1;i<SIZE-1;i++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

এটি সমস্ত অ-অনুক্রমিক অ্যাক্সেসকে সম্পূর্ণরূপে নির্মূল করে যাতে আপনি আর বড় শক্তিগুলির উপর র্যান্ডম স্লো-ডাউনগুলি পান না।

কোর i7 920 @ 3.5 গিগাহার্জ

মূল কোড:

8191: 1.499 seconds
8192: 2.122 seconds
8193: 1.582 seconds

বিনিময়ে বাইরের-লুটপাট:

8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds




gcc