the - অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং এবং c++ pdf




64-বিট সহ একটি 32 বিট লুপ পাল্টা প্রতিস্থাপন পাগল কর্মক্ষমতা বিচ্যুতি প্রবর্তন করে (6)

আপনি কি GCC -funroll-loops -fprefetch-loop-arrays পাস করার চেষ্টা করেছেন?

আমি এই অতিরিক্ত অপ্টিমাইজেশান সঙ্গে নিম্নলিখিত ফলাফল পেতে:

[1829] /tmp/so_25078285 $ cat /proc/cpuinfo |grep CPU|head -n1
model name      : Intel(R) Core(TM) i3-3225 CPU @ 3.30GHz
[1829] /tmp/so_25078285 $ g++ --version|head -n1
g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3

[1829] /tmp/so_25078285 $ g++ -O3 -march=native -std=c++11 test.cpp -o test_o3
[1829] /tmp/so_25078285 $ g++ -O3 -march=native -funroll-loops -fprefetch-loop-arrays -std=c++11     test.cpp -o test_o3_unroll_loops__and__prefetch_loop_arrays

[1829] /tmp/so_25078285 $ ./test_o3 1
unsigned        41959360000     0.595 sec       17.6231 GB/s
uint64_t        41959360000     0.898626 sec    11.6687 GB/s

[1829] /tmp/so_25078285 $ ./test_o3_unroll_loops__and__prefetch_loop_arrays 1
unsigned        41959360000     0.618222 sec    16.9612 GB/s
uint64_t        41959360000     0.407304 sec    25.7443 GB/s

আমি তথ্য বৃহৎ অ্যারে popcount দ্রুততম উপায় খুঁজছেন ছিল। আমি একটি খুব অদ্ভুত প্রভাব সম্মুখীন: uint64_t থেকে unsigned লুপ পরিবর্তনশীল পরিবর্তন আমার পিসি উপর 50% দ্বারা কর্মক্ষমতা ড্রপ।

বেঞ্চমার্ক

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

    using namespace std;
    if (argc != 2) {
       cerr << "usage: array_size in MB" << endl;
       return -1;
    }

    uint64_t size = atol(argv[1])<<20;
    uint64_t* buffer = new uint64_t[size/8];
    char* charbuffer = reinterpret_cast<char*>(buffer);
    for (unsigned i=0; i<size; ++i)
        charbuffer[i] = rand()%256;

    uint64_t count,duration;
    chrono::time_point<chrono::system_clock> startP,endP;
    {
        startP = chrono::system_clock::now();
        count = 0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with unsigned
            for (unsigned i=0; i<size/8; i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "unsigned\t" << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }
    {
        startP = chrono::system_clock::now();
        count=0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with uint64_t
            for (uint64_t i=0;i<size/8;i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }

    free(charbuffer);
}

যেমন আপনি দেখেন, আমরা র্যান্ডম ডেটার একটি বাফার তৈরি করি, আকার x মেগাবাইট হচ্ছে যেখানে x কমান্ড লাইন থেকে পড়তে হয়। popcount , আমরা বাফারের উপর পুনরাবৃত্তি করি এবং popcount সম্পাদন করতে x86 popcount অভ্যন্তরীণ একটি popcount সংস্করণ ব্যবহার করি। আরো সুনির্দিষ্ট ফলাফল পেতে, আমরা 10,000 বার popcount না। আমরা popcount জন্য বার পরিমাপ। উপরের ক্ষেত্রে, অভ্যন্তরীণ লুপ পরিবর্তনশীল unsigned , নিম্ন ক্ষেত্রে, অভ্যন্তরীণ লুপ পরিবর্তনশীল uint64_t । আমি এই কোন পার্থক্য করা উচিত মনে করেন, কিন্তু বিপরীত ক্ষেত্রে হয়।

(একেবারে পাগল) ফলাফল

আমি এটি কম্পাইল (g ++ সংস্করণ: উবুন্টু 4.8.2-19ubuntu1):

g++ -O3 -march=native -std=c++11 test.cpp -o test

এখানে আমার Haswell কোর i7-4770K CPU @ 3.50 GHz এর ফলাফল, চলমান test 1 (তাই 1 মেগাবাইট র্যান্ডম ডেটা):

  • স্বাক্ষরিত 41959360000 0.401554 সেকেন্ড 26.113 গিগাবাইট / সেকেন্ড
  • uint64_t 41959360000 0.7598২২ সেকেন্ড 13.8003 গিগাবাইট / সেকেন্ড

আপনি দেখেন, uint64_t সংস্করণটির থ্রুপুট uint64_t সংস্করণে মাত্র অর্ধেক ! মনে হচ্ছে সমস্যা হচ্ছে ভিন্ন সমাবেশে, কিন্তু কেন? প্রথমত, আমি একটি কম্পাইলার বাগ সম্পর্কে চিন্তা করেছি, তাই আমি clang clang++ (উবুন্টু Clang সংস্করণ 3.4-1ubuntu3) চেষ্টা করেছি:

clang++ -O3 -march=native -std=c++11 teest.cpp -o test

ফলাফল: test 1

  • স্বাক্ষরিত 41959360000 0.398293 সেকেন্ড 26.3267 গিগাবাইট / সেকেন্ড
  • uint64_t 41959360000 0.680954 সেকেন্ড 15.3986 গিগাবাইট / সেকেন্ড

সুতরাং, এটি প্রায় একই ফলাফল এবং এখনও অদ্ভুত। কিন্তু এখন এটা অদ্ভুত পায়। আমি ধ্রুবক 1 দিয়ে ইনপুট থেকে পড়া যে বাফার আকার প্রতিস্থাপন, তাই আমি পরিবর্তন:

uint64_t size = atol(argv[1]) << 20;

থেকে

uint64_t size = 1 << 20;

সুতরাং, কম্পাইলার কম্পাইল সময় এখন বাফার আকার জানেন। হয়তো এটি কিছু অপ্টিমাইজেশান যোগ করতে পারেন! এখানে g++ জন্য সংখ্যা রয়েছে:

  • স্বাক্ষরিত 41959360000 0.509156 সেকেন্ড 20.5944 গিগাবাইট / সেকেন্ড
  • uint64_t 41959360000 0.508673 সেকেন্ড 20.6139 গিগাবাইট / সেকেন্ড

এখন, উভয় সংস্করণ সমানভাবে দ্রুত। যাইহোক, unsigned এমনকি ধীর পেয়েছিলাম ! এটি 26 থেকে 20 GB/s থেকে নেমে গেছে, ফলে একটি ধ্রুবক মানের দ্বারা একটি অ ধ্রুবক প্রতিস্থাপন করা হয় একটি deoptimization সীসা। সত্যি বলতে কি, এখানে কি চলছে আমার কোন সূত্র নেই! কিন্তু এখন নতুন সংস্করণের সাথে clang++ করতে:

  • স্বাক্ষরিত 41959360000 0.677009 সেকেন্ড 15.4884 গিগাবাইট / সেকেন্ড
  • uint64_t 41959360000 0.676909 সেকেন্ড 15.4906 গিগাবাইট / সেকেন্ড

কিসের অপেক্ষা? এখন, উভয় সংস্করণ ধীরে ধীরে 15 গিগাবাইট / সেকেন্ডে চলে গেছে। সুতরাং, একটি ধ্রুবক মান দ্বারা একটি অ ধ্রুবক প্রতিস্থাপন এমনকি Clang জন্য উভয় ক্ষেত্রে ধীর কোড হতে!

আমি আমার বেঞ্চমার্ক কম্পাইল করার জন্য একটি আইভি ব্রিজ CPU সহ একটি সহকর্মী জিজ্ঞাসা। তিনি অনুরূপ ফলাফল পেয়েছেন, তাই এটা Haswell হতে বলে মনে হচ্ছে না। কারণ দুটি কম্পাইলার এখানে অদ্ভুত ফলাফল উত্পাদন করে, এটি একটি কম্পাইলার বাগ বলে মনে হচ্ছে না। আমাদের এখানে একটি এএমডি CPU নেই, তাই আমরা কেবল Intel এর সাথে পরীক্ষা করতে পারি।

আরো পাগলামি, দয়া করে!

প্রথম উদাহরণটি নিন ( atol(argv[1]) with atol(argv[1]) ) এবং পরিবর্তনশীলের আগে একটি static , অর্থাত্:

static uint64_t size=atol(argv[1])<<20;

এখানে আমার ফলাফল g ++:

  • স্বাক্ষরিত 41959360000 0.396728 সেকেন্ড 26.4306 গিগাবাইট / সেকেন্ড
  • uint64_t 41959360000 0.509484 সেকেন্ড 20.5811 গিগাবাইট / সেকেন্ড

হ্যাঁ, এখনো অন্য বিকল্প । আমাদের এখনও ২3 গিগাবাইট দ্রুত ২6 গিগাবাইট / এস, তবে আমরা কমপক্ষে 13 গিগাবাইট / সেকেন্ড থেকে 20 গিগাবাইট / সেকেন্ডে u64 পেতে u64 ! আমার u64 পিসিতে, u64 সংস্করণটি u64 সংস্করণের চেয়ে আরও দ্রুত হয়ে উঠেছে, যার ফলে দ্রুততম ফলাফল পাওয়া যায়। দুঃখজনকভাবে, এই শুধুমাত্র g++ জন্য কাজ করে, clang++ static সম্পর্কে যত্ন বলে মনে হচ্ছে না।

আমার প্রশ্ন

আপনি এই ফলাফল ব্যাখ্যা করতে পারেন? বিশেষ করে:

  • কিভাবে u32 এবং u64 মধ্যে একটি পার্থক্য হতে পারে?
  • কিভাবে একটি ধ্রুবক বাফার আকার কম অটিস্টিক কোড ট্রিগার একটি অ ধ্রুবক প্রতিস্থাপন করতে পারেন?
  • কিভাবে static কীওয়ার্ড সন্নিবেশ করা u64 লুপ দ্রুত করতে পারেন? এমনকি আমার কম্পিউটারের মূল কোডের তুলনায় দ্রুত!

আমি জানি যে অপ্টিমাইজেশান একটি চতুর অঞ্চল, তবে, আমি কখনোই ভাবিনি যে এই ধরনের ছোট্ট পরিবর্তনগুলি কার্যকর সময়গুলিতে 100% পার্থক্য হতে পারে এবং ধ্রুব বাফার আকারের মতো ছোট কারণগুলি আবার সম্পূর্ণ ফলাফলগুলি মিশ্রিত করতে পারে। অবশ্যই, আমি সবসময় এমন সংস্করণটি পেতে চাই যা 26 গিগাবাইট / সেকেন্ডের পপকাউন্ট করতে সক্ষম। আমি বিশ্বাস করতে পারেন শুধুমাত্র নির্ভরযোগ্য উপায় এই ক্ষেত্রে জন্য সমাবেশ পেস্ট এবং অনুলিপি সমাবেশ ব্যবহার করুন। এই একমাত্র উপায় আমি ছোট পরিবর্তনগুলিতে পাগল হয়ে যাচ্ছি এমন কম্পাইলারদের পরিত্রাণ পেতে পারি। আপনি কি মনে করেন? সবচেয়ে কর্মক্ষমতা সঙ্গে কোডটি নির্ভরযোগ্যভাবে পেতে অন্য উপায় আছে কি?

Disassembly

এখানে বিভিন্ন ফলাফলের জন্য disassembly হয়:

G ++ / u32 / non-const bufsize থেকে 26 গিগাবাইট / গুলি সংস্করণ:

0x400af8:
lea 0x1(%rdx),%eax
popcnt (%rbx,%rax,8),%r9
lea 0x2(%rdx),%edi
popcnt (%rbx,%rcx,8),%rax
lea 0x3(%rdx),%esi
add %r9,%rax
popcnt (%rbx,%rdi,8),%rcx
add $0x4,%edx
add %rcx,%rax
popcnt (%rbx,%rsi,8),%rcx
add %rcx,%rax
mov %edx,%ecx
add %rax,%r14
cmp %rbp,%rcx
jb 0x400af8

G ++ / u64 / non-const বা bufsize থেকে 13 গিগাবাইট / গুলি সংস্করণ:

0x400c00:
popcnt 0x8(%rbx,%rdx,8),%rcx
popcnt (%rbx,%rdx,8),%rax
add %rcx,%rax
popcnt 0x10(%rbx,%rdx,8),%rcx
add %rcx,%rax
popcnt 0x18(%rbx,%rdx,8),%rcx
add $0x4,%rdx
add %rcx,%rax
add %rax,%r12
cmp %rbp,%rdx
jb 0x400c00

15 গিগাবাইট / সেকেন্ড সংস্করণ clang ++ / u64 / অ-কন্স বাফেসাইজ থেকে :

0x400e50:
popcnt (%r15,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r15,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r15,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r15,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp %rbp,%rcx
jb 0x400e50

G ++ / u32 এবং u64 / const bufsize থেকে 20 গিগাবাইট / গুলি সংস্করণ:

0x400a68:
popcnt (%rbx,%rdx,1),%rax
popcnt 0x8(%rbx,%rdx,1),%rcx
add %rax,%rcx
popcnt 0x10(%rbx,%rdx,1),%rax
add %rax,%rcx
popcnt 0x18(%rbx,%rdx,1),%rsi
add $0x20,%rdx
add %rsi,%rcx
add %rcx,%rbp
cmp $0x100000,%rdx
jne 0x400a68

15 গিগাবাইট / সেকেন্ড সংস্করণ clang ++ / u32 & u64 / cs bfsize থেকে :

0x400dd0:
popcnt (%r14,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r14,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r14,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r14,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp $0x20000,%rcx
jb 0x400dd0

মজার, দ্রুততম (২6 গিগাবাইট / সেকেন্ড) সংস্করণও দীর্ঘতম! এটি একমাত্র সমাধান যা lea ব্যবহার করে বলে মনে হয়। কিছু সংস্করণ jb jump ব্যবহার করে, অন্যরা jne ব্যবহার করে। কিন্তু যে ছাড়া, সব সংস্করণ তুলনীয় বলে মনে হচ্ছে। 100% পারফরম্যান্স ফাঁক থেকে উদ্ভূত হতে পারে তা আমি দেখতে পাচ্ছি না, তবে আমি সমাবেশকে ডাইফারের ব্যাপারে খুব বেশি মনোযোগ দিই না। ধীরতম (13 গিগাবাইট / গুলি) সংস্করণ এমনকি খুব ছোট এবং ভাল দেখায়। কেউ এই ব্যাখ্যা করতে পারেন?

পাঠ শিখেছি

কোন ব্যাপার কি এই প্রশ্নের উত্তর হতে হবে; আমি শিখেছি যে সত্যিই গরম loops মধ্যে প্রতিটি বিস্তারিত ব্যাপার হতে পারে, এমনকি যে বিবরণ গরম কোড কোন অ্যাসোসিয়েশন বলে মনে হচ্ছে না । আমি কোনও লুপ পরিবর্তনশীলের জন্য কী ধরনের ব্যবহার করতে পারি তা নিয়ে ভাবিনি, কিন্তু আপনি যেমন একটি ছোটখাট পরিবর্তন দেখতে পারেন 100% পার্থক্য! এমনকি একটি বাফারের স্টোরেজ প্রকারটিও বিশাল পার্থক্য তৈরি করতে পারে, যেমন আমরা আকার পরিবর্তনশীলের সামনে static কীওয়ার্ড সন্নিবেশ করে দেখেছি! ভবিষ্যতে, আমি সর্বদা বিভিন্ন কম্পাইলারগুলির উপর বিভিন্ন বিকল্প পরীক্ষা করব যখন সিস্টেমের কার্যকারিতাগুলির জন্য অত্যন্ত কঠিন এবং গরম লুপগুলি লিখতে হবে।

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


আপনি লুপ বাইরে হ্রাস পদক্ষেপ চলন্ত চেষ্টা করেছেন? ঠিক এখন আপনি একটি তথ্য নির্ভরতা আছে যে সত্যিই প্রয়োজন হয় না।

চেষ্টা করুন:

  uint64_t subset_counts[4] = {};
  for( unsigned k = 0; k < 10000; k++){
     // Tight unrolled loop with unsigned
     unsigned i=0;
     while (i < size/8) {
        subset_counts[0] += _mm_popcnt_u64(buffer[i]);
        subset_counts[1] += _mm_popcnt_u64(buffer[i+1]);
        subset_counts[2] += _mm_popcnt_u64(buffer[i+2]);
        subset_counts[3] += _mm_popcnt_u64(buffer[i+3]);
        i += 4;
     }
  }
  count = subset_counts[0] + subset_counts[1] + subset_counts[2] + subset_counts[3];

আপনি কিছু অদ্ভুত aliasing যাচ্ছে যাচ্ছে, আমি নিশ্চিত না যে কঠোর aliasing নিয়ম অনুসারে।


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

তাই শীর্ষ পাইপলাইন এবং একাধিক প্রেরণ কর্মক্ষমতা এবং এই প্রক্রিয়া ব্যর্থতা মধ্যে, আমরা কর্মক্ষমতা ছয় একটি ফ্যাক্টর আছে। এটি খুব ভালভাবে জানা গেছে যে x86 নির্দেশ সেটের জটিলতাটি কোঁকড়া ভাঙ্গার ঘটনার পক্ষে এটি সহজ করে তোলে। উপরে দস্তাবেজ একটি মহান উদাহরণ আছে:

64-বিট ডান পাল্টানোর জন্য পেন্টিয়াম 4 কার্যক্ষমতা সত্যিই দরিদ্র। 64-বিট বাম স্থানান্তরের পাশাপাশি সমস্ত 32 বিট পাল্টা গ্রহণযোগ্য কর্মক্ষমতা আছে। এটি উপরের 32 বিট থেকে নিম্ন 32 বিট থেকে ডাটা পথটি ডিজাইন করা ভাল নয়।

আমি ব্যক্তিগতভাবে একটি অদ্ভুত ক্ষেত্রে দৌড়ে যেখানে একটি গরম লুপ একটি চার কোর চিপ একটি নির্দিষ্ট কোর উপর ধীর গতির দৌড়ে (AMD যদি আমি মনে রাখবেন)। আমরা মূল বন্ধ যে বাঁক দ্বারা একটি মানচিত্র-হ্রাস গণনা ভাল পারফরম্যান্স পেয়েছিলাম।

এখানে আমার অনুমান পূর্ণসংখ্যা popcnt জন্য মতবিরোধ: popcnt , লুপ পাল্টা এবং ঠিকানা গণনাগুলি কেবলমাত্র 32-বিট প্রশস্ত কাউন্টারের সাথে সম্পূর্ণ গতিতে চালাতে পারে তবে 64-বিট কাউন্টারটি বিরোধ এবং পাইপলাইন স্টলগুলিকে কারণ করে। যেহেতু মাত্র 1২ টি চক্র রয়েছে, সম্ভবত একাধিক প্রেরণের সাথে 4 টি চক্র, প্রতি লুপ শরীরের সঞ্চালন, একটি স্টল চালানোর কারণে 2 এর কার্যাবলী দ্বারা রান সময় প্রভাবিত করতে পারে।

একটি স্ট্যাটিক পরিবর্তনশীল ব্যবহার করে প্রবর্তিত পরিবর্তন, যা আমি অনুমান করছি কেবল নির্দেশাবলীর একটি ছোটখাট পুনর্বহালের কারণ হয়ে দাঁড়িয়েছে, আরেকটি সূত্র যেটি 32-বিট কোড বিতর্কের জন্য কিছু টিপিং পয়েন্টে রয়েছে।

আমি জানি এটি একটি কঠোর বিশ্লেষণ নয়, কিন্তু এটি একটি সম্ভাব্য ব্যাখ্যা।


আমি পরীক্ষা করার জন্য একটি সমতুল্য সি প্রোগ্রাম আপ কোডেড, এবং আমি এই অদ্ভুত আচরণ নিশ্চিত করতে পারেন। আরো কি, gcc বিশ্বাস করে 64-বিট পূর্ণসংখ্যা (যেটি সম্ভবত uint_fast32_t হতে পারে ...) হওয়া উচিত, uint_fast32_t ব্যবহার করে gcc 64-বিট UIint ব্যবহার করে।

আমি সমাবেশ সঙ্গে প্রায় mucking একটি বিট করেনি:
কেবল 32-বিট সংস্করণটি গ্রহণ করুন, 64-বিট সংস্করণের সাথে সমস্ত 32-বিট নির্দেশাবলী / নিবন্ধকদের প্রতিস্থাপন করুন প্রোগ্রামটির ভিতরের পপকাউন্ট-লুপে। পর্যবেক্ষণ: কোডটি 32-বিট সংস্করণের মতো দ্রুত!

এটি সম্ভবত একটি হ্যাক, কারণ ভেরিয়েবলের আকারটি সত্যিই 64 বিট নয়, প্রোগ্রামের অন্যান্য অংশগুলি এখনও 32-বিট সংস্করণ ব্যবহার করে, কিন্তু যতক্ষণ অভ্যন্তরীণ পপকাউন্ট-লুপ কর্মক্ষমতা প্রভাবিত করে, এটি একটি ভাল শুরু ।

আমি তখন প্রোগ্রামের 32-বিট সংস্করণ থেকে অভ্যন্তরীণ লুপ কোড অনুলিপি করে 64 বিট সংস্করণে এটি হ্যাক করেছিলাম, এটি 64-বিট সংস্করণের অভ্যন্তরীণ লুপের জন্য প্রতিস্থাপনের জন্য নিবন্ধকদের সাথে ফুটিয়ে তুলেছিল। এই কোডটি 32-বিট সংস্করণ হিসাবে দ্রুত চালায়।

আমার উপসংহার এই 32-বিট নির্দেশাবলী প্রকৃত গতি / বিলম্বিত সুবিধা নয়, কম্পাইলার দ্বারা খারাপ নির্দেশ সময়সূচী হয়।

(ক্যাভিট: আমি সমাবেশকে হ্যাক করেছি, কিছু দেখলেই ভাঙ্গতে পারতাম। আমি তাই মনে করি না।)


টিএল; ডিআর: পরিবর্তে __builtin intrinsics ব্যবহার করুন।

আমি gcc 4.8.4 (এবং এমনকি gcc.godbolt.org এ 4.7.3) তৈরি করতে সক্ষম হয়েছিলাম __builtin_popcountll ব্যবহার করে __builtin_popcountll সর্বোত্তম কোড তৈরি করে যা একই অ্যাসেম্বলেশন নির্দেশনা ব্যবহার করে তবে মিথ্যা নির্ভরতা বাগ নেই।

আমি আমার বেঞ্চমার্কিং কোডের 100% নিশ্চিত নই, তবে objdumpআউটপুট আমার মতামত ভাগ করে নেওয়ার মতো মনে হয়। আমি কোন নির্দেশ ছাড়াই আমার জন্য কম্পাইলার আনলল লুপ করতে কিছু অন্যান্য কৌশল ( ++iবনাম i++) ব্যবহার করুন movl(অদ্ভুত আচরণ, আমি বলতে হবে)।

ফলাফল:

Count: 20318230000  Elapsed: 0.411156 seconds   Speed: 25.503118 GB/s

বেঞ্চমার্কিং কোড:

#include <stdint.h>
#include <stddef.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

uint64_t builtin_popcnt(const uint64_t* buf, size_t len){
  uint64_t cnt = 0;
  for(size_t i = 0; i < len; ++i){
    cnt += __builtin_popcountll(buf[i]);
  }
  return cnt;
}

int main(int argc, char** argv){
  if(argc != 2){
    printf("Usage: %s <buffer size in MB>\n", argv[0]);
    return -1;
  }
  uint64_t size = atol(argv[1]) << 20;
  uint64_t* buffer = (uint64_t*)malloc((size/8)*sizeof(*buffer));

  // Spoil copy-on-write memory allocation on *nix
  for (size_t i = 0; i < (size / 8); i++) {
    buffer[i] = random();
  }
  uint64_t count = 0;
  clock_t tic = clock();
  for(size_t i = 0; i < 10000; ++i){
    count += builtin_popcnt(buffer, size/8);
  }
  clock_t toc = clock();
  printf("Count: %lu\tElapsed: %f seconds\tSpeed: %f GB/s\n", count, (double)(toc - tic) / CLOCKS_PER_SEC, ((10000.0*size)/(((double)(toc - tic)*1e+9) / CLOCKS_PER_SEC)));
  return 0;
}

কম্পাইল অপশন:

gcc --std=gnu99 -mpopcnt -O3 -funroll-loops -march=native bench.c -o bench

জিसीसी সংস্করণ:

gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4

লিনাক্স কার্নেল সংস্করণ:

3.19.0-58-generic

CPU তথ্য:

processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 70
model name  : Intel(R) Core(TM) i7-4870HQ CPU @ 2.50 GHz
stepping    : 1
microcode   : 0xf
cpu MHz     : 2494.226
cache size  : 6144 KB
physical id : 0
siblings    : 1
core id     : 0
cpu cores   : 1
apicid      : 0
initial apicid  : 0
fpu     : yes
fpu_exception   : yes
cpuid level : 13
wp      : yes
flags       : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx rdtscp lm constant_tsc nopl xtopology nonstop_tsc eagerfpu pni pclmulqdq ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand hypervisor lahf_lm abm arat pln pts dtherm fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 invpcid xsaveopt
bugs        :
bogomips    : 4988.45
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

Culprit: মিথ্যা তথ্য নির্ভরতা (এবং কম্পাইলার এমনকি এটি সচেতন নয়)

স্যান্ডি / আইভি ব্রিজ এবং হ্যাশওয়াল প্রসেসরগুলিতে, নির্দেশনা:

popcnt  src, dest

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

এই নির্ভরতাটি কেবলমাত্র একটি লুপ পুনরাবৃত্তি থেকে 4 টি popcnt গুলি ধরে রাখে না। এটি লুপ পুনরাবৃত্তি জুড়ে বহন করতে পারে প্রসেসর বিভিন্ন লুপ পুনরাবৃত্তি সমান্তরাল করতে অসম্ভব।

uint64_t বনাম uint64_t এবং অন্যান্য tweaks সরাসরি সমস্যা প্রভাবিত করে না। কিন্তু তারা রেজিস্ট্রেশন অ্যালকোটারকে প্রভাবিত করে যা ভেরিয়েবলদের নিবন্ধন করে।

আপনার ক্ষেত্রে, গতি নিবন্ধক অ্যালকোটারের সিদ্ধান্ত নেওয়ার সিদ্ধান্তের উপর নির্ভর করে (মিথ্যা) নির্ভরতা শৃঙ্খলে আটকে থাকা সরাসরি ফলাফল।

  • 13 গিগাবাইট / গুলি একটি চেইন আছে: popcnt - add - popcnt - popcnt → পরবর্তী পুনরাবৃত্তি
  • 15 গিগাবাইট / গুলি একটি চেইন আছে: popcnt - add - popcnt - add → পরবর্তী পুনরাবৃত্তি
  • 20 গিগাবাইট / গুলি একটি চেইন আছে: popcnt - popcnt → পরবর্তী পুনরাবৃত্তি
  • 26 গিগাবাইট / গুলি একটি চেইন আছে: popcnt - popcnt → পরবর্তী পুনরাবৃত্তি

২0 গিগাবাইট / সেকেন্ড এবং ২6 গিগাবাইট / সেকেন্ডের মধ্যে পার্থক্য পরোক্ষ অ্যাড্রেসিংয়ের একটি ছোটখাট আর্টিফেক্ট বলে মনে হয়। যেকোন উপায়ে, আপনি এই গতিতে পৌঁছানোর পরে প্রসেসরটি অন্যান্য সমস্যাগুলি হিট করতে শুরু করে।

এই পরীক্ষা করার জন্য, আমি কম্পাইলার বাইপাস এবং আমি চান সমাবেশ ঠিক পেতে ইনলাইন সমাবেশ ব্যবহৃত। আমি count পরিবর্তনশীলকে বিভক্ত করতে অন্য সমস্ত নির্ভরতা ভাঙ্গতে যা বঞ্চমার্কগুলির সাথে জগাখিচুড়ি হতে পারে।

এখানে ফলাফল:

স্যান্ডি সেতু Xeon @ 3.5 গিগাহার্জঃ (সম্পূর্ণ পরীক্ষার কোড নীচে পাওয়া যেতে পারে)

  • GCC 4.6.3: g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
  • উবুন্টু 1২

বিভিন্ন রেজিস্ট্রি: 18.6195 গিগাবাইট / সেকেন্ড

.L4:
    movq    (%rbx,%rax,8), %r8
    movq    8(%rbx,%rax,8), %r9
    movq    16(%rbx,%rax,8), %r10
    movq    24(%rbx,%rax,8), %r11
    addq    $4, %rax

    popcnt %r8, %r8
    add    %r8, %rdx
    popcnt %r9, %r9
    add    %r9, %rcx
    popcnt %r10, %r10
    add    %r10, %rdi
    popcnt %r11, %r11
    add    %r11, %rsi

    cmpq    $131072, %rax
    jne .L4

একই নিবন্ধন: 8.492২7 গিগাবাইট / সেকেন্ড

.L9:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # This time reuse "rax" for all the popcnts.
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L9

ভাঙা চেইন সঙ্গে একই নিবন্ধন: 17.8869 গিগাবাইট / গুলি

.L14:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # Reuse "rax" for all the popcnts.
    xor    %rax, %rax    # Break the cross-iteration dependency by zeroing "rax".
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L14

তাই কম্পাইলার সঙ্গে কি ভুল হয়েছে?

মনে হয় যে জি সি সি এবং ভিসুয়াল popcnt সচেতন নয় যে popcnt এ ধরনের মিথ্যা নির্ভরতা রয়েছে। তবুও, এই মিথ্যা নির্ভরতা অস্বাভাবিক নয়। এটা কম্পাইলার এটা সচেতন কিনা শুধু একটি ব্যাপার।

popcnt ঠিক সবচেয়ে ব্যবহৃত নির্দেশ হয় না। সুতরাং এটি একটি বিস্ময়কর বিষয় নয় যে একটি প্রধান কম্পাইলার এইরকম কিছু মিস করতে পারে। এই সমস্যা উল্লেখ যে কোথাও কোন ডকুমেন্টেশন প্রদর্শিত হবে। যদি ইন্টেলটি প্রকাশ না করে তবে বাইরে কেউ তা জানবে না যতক্ষন না কেউ এটির দ্বারা সুযোগ পায়।

( আপডেট: সংস্করণ 4.9.2 অনুসারে , জিसीसी এই মিথ্যা-নির্ভরতা সম্পর্কে সচেতন এবং অপ্টিমাইজেশানগুলি সক্ষম করার সময় এটি ক্ষতিপূরণ করার জন্য কোড তৈরি করে। ক্লাং, এমএসভিসি এবং এমনকি ইন্টেলের নিজস্ব আইসিসি সহ অন্যান্য বিক্রেতাদের প্রধান কম্পাইলারগুলি এখনও সচেতন নয়। এই microarchitectural ত্রুটি-বিচ্যুতি এবং এটি জন্য ক্ষতিপূরণ যে কোড নির্গমন করবে না।)

কেন সিপিইউ যেমন মিথ্যা নির্ভরতা আছে?

আমরা কেবল অনুমান করতে পারি, কিন্তু সম্ভবত এটি দুটি অপারেণ্ডার নির্দেশাবলীর জন্য একই হ্যান্ডলিংয়ের সম্ভাবনা রয়েছে। মত সাধারণ নির্দেশাবলী, sub দুটি ইনপুট যা উভয় ইনপুট নিতে। তাই প্রসেসর নকশাটি সহজ রাখতে ইন্টেল সম্ভবত একই বিভাগে popcnt shoved।

এএমডি প্রসেসর এই মিথ্যা নির্ভরতা আছে বলে মনে হচ্ছে না।

সম্পূর্ণ পরীক্ষা কোড রেফারেন্সের জন্য নিচের:

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

   using namespace std;
   uint64_t size=1<<20;

   uint64_t* buffer = new uint64_t[size/8];
   char* charbuffer=reinterpret_cast<char*>(buffer);
   for (unsigned i=0;i<size;++i) charbuffer[i]=rand()%256;

   uint64_t count,duration;
   chrono::time_point<chrono::system_clock> startP,endP;
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %4  \n\t"
                "add %4, %0     \n\t"
                "popcnt %5, %5  \n\t"
                "add %5, %1     \n\t"
                "popcnt %6, %6  \n\t"
                "add %6, %2     \n\t"
                "popcnt %7, %7  \n\t"
                "add %7, %3     \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "No Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Chain 4   \t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "xor %%rax, %%rax   \n\t"   // <--- Break the chain.
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Broken Chain\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }

   free(charbuffer);
}

একটি সমানভাবে আকর্ষণীয় বেঞ্চমার্ক এখানে পাওয়া যাবে: http://pastebin.com/kbzgL8si
এই বেঞ্চমার্কটি (মিথ্যা) নির্ভরতা শৃঙ্খলে থাকা popcnt সংখ্যা পরিবর্তিত করে।

False Chain 0:  41959360000 0.57748 sec     18.1578 GB/s
False Chain 1:  41959360000 0.585398 sec    17.9122 GB/s
False Chain 2:  41959360000 0.645483 sec    16.2448 GB/s
False Chain 3:  41959360000 0.929718 sec    11.2784 GB/s
False Chain 4:  41959360000 1.23572 sec     8.48557 GB/s




compiler-optimization