arrays - 240 বা ততোধিক উপাদানগুলির সাথে কোনও অ্যারে লুপ করার সময় কেন একটি বৃহত পারফরম্যান্স প্রভাব রয়েছে?




performance rust (2)

মরিচায় একটি অ্যারের উপরে যোগফল লুপ চালানোর সময় আমি CAPACITY > = 240 যখন একটি বিশাল পারফরম্যান্স ড্রপ লক্ষ্য করেছি C CAPACITY = 239 প্রায় 80 গুণ বেশি গতিযুক্ত।

"সংক্ষিপ্ত" অ্যারেগুলির জন্য কোনও বিশেষ সংকলন অপ্টিমাইজেশন জাস্ট কাজ করছে?

rustc -C opt-level=3 দিয়ে সংকলিত।

use std::time::Instant;

const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;

fn main() {
    let mut arr = [0; CAPACITY];
    for i in 0..CAPACITY {
        arr[i] = i;
    }
    let mut sum = 0;
    let now = Instant::now();
    for _ in 0..IN_LOOPS {
        let mut s = 0;
        for i in 0..arr.len() {
            s += arr[i];
        }
        sum += s;
    }
    println!("sum:{} time:{:?}", sum, now.elapsed());
}

লুকাসের উত্তর ছাড়াও, আপনি যদি পুনরুক্তি ব্যবহার করতে চান তবে এটি চেষ্টা করুন:

const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;

pub fn bar() -> usize {
    (0..CAPACITY).sum::<usize>() * IN_LOOPS
}

পরিসীমা প্যাটার্ন সম্পর্কে পরামর্শের জন্য @ ক্রিস মরগানকে ধন্যবাদ।

অনুকূলিত সমাবেশটি বেশ ভাল:

example::bar:
        movabs  rax, 14340000000
        ret

সংক্ষিপ্তসার : 240 এর নীচে, এলএলভিএম পুরোপুরি অভ্যন্তরীণ লুপটিকে তালিকাভুক্ত করে এবং এটি আপনাকে লক্ষ্য করতে দেয় যে এটি আপনার মানদণ্ডকে ভেঙে পুনরাবৃত্তি লুপটিকে অপ্টিমাইজ করতে পারে।


আপনি একটি যাদু থ্রেশহোল্ড পেয়েছেন যার উপরে এলএলভিএম নির্দিষ্ট অপ্টিমাইজেশন সম্পাদন বন্ধ করে দিয়েছে । প্রান্তিকতা 8 বাইট * 240 = 1920 বাইট (আপনার অ্যারেটি usize একটি অ্যারে, সুতরাং usize বাইট দ্বারা গুণিত হবে, x86-64 সিপিইউ ধরে নেওয়া হবে)। এই মানদণ্ডে, একটি নির্দিষ্ট অপ্টিমাইজেশন - কেবল দৈর্ঘ্যের 239 এর জন্য সম্পাদিত - বিশাল গতির পার্থক্যের জন্য দায়ী। তবে আস্তে আস্তে শুরু করা যাক:

(এই উত্তরের সমস্ত -C opt-level=3 দিয়ে সংকলিত)

pub fn foo() -> usize {
    let arr = [0; 240];
    let mut s = 0;
    for i in 0..arr.len() {
        s += arr[i];
    }
    s
}

এই সাধারণ কোডটি মোটামুটি এক জন সমাবেশের আশা করবে: একটি লুপ উপাদান যুক্ত করবে। তবে, আপনি যদি 240 থেকে 239 পরিবর্তন করেন তবে নির্গত সমাবেশটি অনেকটা আলাদা হয়। গডবোল্ট কম্পাইলার এক্সপ্লোরারে এটি দেখুন । এখানে সমাবেশের একটি ছোট অংশ রয়েছে:

movdqa  xmm1, xmmword ptr [rsp + 32]
movdqa  xmm0, xmmword ptr [rsp + 48]
paddq   xmm1, xmmword ptr [rsp]
paddq   xmm0, xmmword ptr [rsp + 16]
paddq   xmm1, xmmword ptr [rsp + 64]
; more stuff omitted here ...
paddq   xmm0, xmmword ptr [rsp + 1840]
paddq   xmm1, xmmword ptr [rsp + 1856]
paddq   xmm0, xmmword ptr [rsp + 1872]
paddq   xmm0, xmm1
pshufd  xmm1, xmm0, 78
paddq   xmm1, xmm0

এটাকেই লুপ আন্রোলিং বলা হয়: এলএলভিএম সেই সমস্ত "লুপ পরিচালন নির্দেশাবলী" চালানো এড়াতে লুপের বডিটিকে অনেক সময় ব্যয় করে, লুপের পরিবর্তনশীল বৃদ্ধি করে, লুপটি শেষ হয়েছে কিনা এবং লুপের শুরুতে লাফটি পরীক্ষা করে দেখুন? ।

আপনি যদি ভাবছেন: paddq এবং অনুরূপ নির্দেশাবলী paddq নির্দেশাবলী যা সমান্তরালভাবে একাধিক মান paddq করতে দেয়। xmm0 , দুটি 16-বাইট xmm0 রেজিস্টারগুলি ( xmm0 এবং xmm1 ) সমান্তরালভাবে ব্যবহৃত হয় যাতে সিপিইউর নির্দেশ-স্তরের সমান্তরালতা মূলত একই সাথে দুটি নির্দেশকে কার্যকর করতে পারে। সর্বোপরি, তারা একে অপরের থেকে স্বাধীন। শেষ পর্যন্ত, উভয় নিবন্ধগুলি একসাথে যুক্ত করা হয় এবং তারপরে অনুভূমিকভাবে স্কেলারের ফলাফলের সংক্ষিপ্তসার করা হয়।

আধুনিক মূলধারার x86 সিপিইউগুলি (লো-পাওয়ার অ্যাটম নয়) তারা এল 1 ডি ক্যাশে আঘাত করলে ঘড়ি প্রতি 2 ভেক্টর বোঝা সত্যিই করতে পারে এবং বেশিরভাগ সিপিইউতে 1 চক্রের বিলম্বের সাথে paddq প্রতি ঘড়িতে কমপক্ষে 2 হয়। https://agner.org/optimize/ এবং এছাড়াও একাধিক আহরণকারী (কোনও ডট পণ্যের জন্য এফপি এফএমএর) আড়াল করতে এবং এর পরিবর্তে থ্রুপুটটিতে বাধা সম্পর্কে এই প্রশ্নোত্তর দেখুন।

LLVM ছোট লুপগুলিকে কিছুটা আনআরোল করে না যখন এটি সম্পূর্ণরূপে তালিকাভুক্ত না হয় এবং এখনও একাধিক সংযোজক ব্যবহার করে। সুতরাং সাধারণত, সম্পূর্ণ আনআরলিং না করে এমনকি এলএলভিএম-উত্পাদিত লুপগুলির জন্য ফ্রন্ট-এন্ড ব্যান্ডউইথ এবং ব্যাক-এন্ড ল্যাটেন্সির বাধাগুলি কোনও বিশাল সমস্যা নয়।

তবে লুপ আন্রোলিং 80 গুণমানের পারফরম্যান্সের পার্থক্যের জন্য দায়ী নয়! অন্তত একা অনিয়ন্ত্রিত লুপ না। আসুন আসল বেঞ্চমার্কিং কোডটি একবার দেখুন, যা একটি লুপটিকে অন্য একটিটির ভিতরে রাখে:

const CAPACITY: usize = 239;
const IN_LOOPS: usize = 500000;

pub fn foo() -> usize {
    let mut arr = [0; CAPACITY];
    for i in 0..CAPACITY {
        arr[i] = i;
    }

    let mut sum = 0;
    for _ in 0..IN_LOOPS {
        let mut s = 0;
        for i in 0..arr.len() {
            s += arr[i];
        }
        sum += s;
    }

    sum
}

( গডবোল্ট সংকলক এক্সপ্লোরার এ )

CAPACITY = 240 জন্য CAPACITY = 240 সাধারণ দেখাচ্ছে: দুটি নেস্ট লুপ। (ফাংশনটির শুরুতে কেবল কিছু শুরু করার জন্য বেশ কয়েকটি কোড রয়েছে, যা আমরা এড়িয়ে যাব)) 239 এর জন্য, এটি দেখতে খুব আলাদা দেখাচ্ছে! আমরা দেখতে পাই যে প্রারম্ভকৃত লুপ এবং অভ্যন্তরীণ লুপটি নিবন্ধবিহীন হয়ে গেছে: এখনও পর্যন্ত এটি প্রত্যাশিত।

গুরুত্বপূর্ণ পার্থক্যটি হল যে 239 এর জন্য, এলএলভিএম এটি নির্ধারণ করতে সক্ষম হয়েছিল যে অভ্যন্তরীণ লুপের ফলাফলটি বাইরের লুপের উপর নির্ভর করে না! ফলস্বরূপ, এলএলভিএম কোডটি নির্গত করে যা মূলত কেবলমাত্র কেবলমাত্র অভ্যন্তরীণ লুপটি নির্বাহ করে (যোগফল গণনা করে) এবং তারপরে একগুচ্ছ sum যোগ করে বাইরের লুপকে সিমুলেট করে!

প্রথমে আমরা উপরের মত প্রায় একই সমাবেশটি দেখতে পাই (সমাবেশটি অভ্যন্তরীণ লুপকে উপস্থাপন করে)। এরপরে আমরা এটি দেখতে পেয়েছি (আমি সমাবেশটি ব্যাখ্যা করার জন্য মন্তব্য করেছি; * এর সাথে মন্তব্যগুলি বিশেষত গুরুত্বপূর্ণ):

        ; at the start of the function, `rbx` was set to 0

        movq    rax, xmm1     ; result of SIMD summing up stored in `rax`
        add     rax, 711      ; add up missing terms from loop unrolling
        mov     ecx, 500000   ; * init loop variable outer loop
.LBB0_1:
        add     rbx, rax      ; * rbx += rax
        add     rcx, -1       ; * decrement loop variable
        jne     .LBB0_1       ; * if loop variable != 0 jump to LBB0_1
        mov     rax, rbx      ; move rbx (the sum) back to rax
        ; two unimportant instructions omitted
        ret                   ; the return value is stored in `rax`

আপনি এখানে দেখতে পাচ্ছেন, অভ্যন্তরীণ লুপটির ফলাফল নেওয়া হবে, যতক্ষণ না বাইরের লুপটি দৌড়ে যেত এবং তারপরে ফিরে আসত। এলএলভিএম কেবলমাত্র এই অপটিমাইজেশন সম্পাদন করতে পারে কারণ এটি বুঝতে পেরেছিল যে অভ্যন্তরীণ লুপটি বাইরেরটির চেয়ে স্বতন্ত্র।

এর অর্থ CAPACITY * IN_LOOPS থেকে CAPACITY + IN_LOOPS । এবং এটি বিশাল পারফরম্যান্সের পার্থক্যের জন্য দায়ী।

একটি অতিরিক্ত নোট: আপনি এই সম্পর্কে কিছু করতে পারেন? আসলে তা না. এলএলভিএম এর যেমন জাদু থ্রেশহোল্ড থাকতে হবে সেগুলি ছাড়া এলএলভিএম-অপটিমাইজেশন নির্দিষ্ট কোডে সম্পূর্ণ হতে চিরতরে নিতে পারে। তবে আমরা সম্মত হতে পারি যে এই কোডটি অত্যন্ত কৃত্রিম ছিল। বাস্তবে, আমি সন্দেহ করি যে এত বড় পার্থক্য ঘটবে। সম্পূর্ণ লুপ আন্রোলিংয়ের কারণে পার্থক্য সাধারণত এই ক্ষেত্রে 2 ফ্যাক্টর হয় না। সুতরাং আসল ব্যবহারের ক্ষেত্রে চিন্তা করার দরকার নেই।

arr.iter().sum() কোড সম্পর্কে একটি সর্বশেষ নোট হিসাবে: arr.iter().sum() একটি অ্যারের সমস্ত উপাদান যোগ করার জন্য একটি ভাল উপায়। এবং দ্বিতীয় উদাহরণে এটি পরিবর্তন করার ফলে নির্গত সমাবেশে কোনও উল্লেখযোগ্য পার্থক্য দেখা যায় না। আপনি সংক্ষিপ্ত এবং আইডোমেটিক সংস্করণগুলি ব্যবহার করা উচিত যদি না আপনি পরিমাপ করেন যে এটির কার্যকারিতা ব্যথা করে।







llvm-codegen