c++ - হাতের লিখিত সমাবেশের চেয়ে কোলাটজ অনুমানটি দ্রুত পরীক্ষার জন্য সি++ কোড-কেন?




performance assembly (8)

আপনি সংকলকটির দ্বারা উত্পন্ন কোডটি পোস্ট করেননি, সুতরাং এখানে কিছু অনুমানক রয়েছে, তবে এটি না দেখেও কেউ বলতে পারেন যে এটি:

test rax, 1
jpe even

... শাখার ভুল ধারণা করার 50% সম্ভাবনা রয়েছে এবং এটি ব্যয়বহুল হবে।

সংকলক প্রায় অবশ্যই উভয় গণনা করে (যা ডিভ / মোড দীর্ঘ লম্বা লম্বা হওয়ার কারণে অবহেলিতভাবে বেশি খরচ হয়, সুতরাং গুণক-অ্যাড "ফ্রি") এবং একটি সিএমওভের সাথে অনুসরণ করে। যার অবশ্যই অপ্রকাশিত হওয়ার শূন্য শতাংশ সম্ভাবনা রয়েছে।

আমি এই দুটি সমাধান প্রজেক্ট ইউলারের কিউ 14 , সমাবেশ এবং সি ++ এ লিখেছি। কোলাটজ অনুমানের পরীক্ষার জন্য এগুলি একই অভিন্ন বৌদ্ধ শক্তি পদ্ধতির। সমাবেশ সমাধান একত্রিত হয়েছিল

nasm -felf64 p14.asm && gcc p14.o -o p14

সি ++ এর সাথে সংকলিত হয়েছিল

g++ p14.cpp -o p14

সমাবেশ, p14.asm

section .data
    fmt db "%d", 10, 0

global main
extern printf

section .text

main:
    mov rcx, 1000000
    xor rdi, rdi        ; max i
    xor rsi, rsi        ; i

l1:
    dec rcx
    xor r10, r10        ; count
    mov rax, rcx

l2:
    test rax, 1
    jpe even

    mov rbx, 3
    mul rbx
    inc rax
    jmp c1

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

c1:
    inc r10
    cmp rax, 1
    jne l2

    cmp rdi, r10
    cmovl rdi, r10
    cmovl rsi, rcx

    cmp rcx, 2
    jne l1

    mov rdi, fmt
    xor rax, rax
    call printf
    ret

সি ++, পি 14 সি পি পি

#include <iostream>

using namespace std;

int sequence(long n) {
    int count = 1;
    while (n != 1) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = n*3 + 1;

        ++count;
    }

    return count;
}

int main() {
    int max = 0, maxi;
    for (int i = 999999; i > 0; --i) {
        int s = sequence(i);
        if (s > max) {
            max = s;
            maxi = i;
        }
    }

    cout << maxi << endl;
}

আমি গতি এবং সবকিছু উন্নত করতে সংকলক অনুকূলিতকরণ সম্পর্কে জানি, তবে আমি আমার সমাবেশ সমাধানটি আরও অনুকূল করার অনেক উপায় দেখতে পাচ্ছি না (প্রোগ্রামিকভাবে গাণিতিকভাবে নয়) speaking

সি ++ কোডে প্রতিটি শব্দ এবং বিভাজন প্রতি পদে মডিউল থাকে, যেখানে সমাবেশ এমনকি প্রতিটি পদে মাত্র একটি বিভাগ থাকে।

তবে সমাবেশটি সি ++ সমাধানের চেয়ে গড়ে 1 সেকেন্ড বেশি সময় নিচ্ছে। কেন? আমি প্রধানত কৌতূহল জিজ্ঞাসা করছি।

ফাঁসির সময়

আমার সিস্টেম: 1.4 গিগাহার্টজ ইন্টেল সেলারন 2955U (হাসওয়েল মাইক্রোআরকিটেকচার) এ 64 বিট লিনাক্স।


একটি জেনেরিক উত্তর হিসাবে, বিশেষ করে এই কাজটিতে নির্দেশিত নয়: অনেক ক্ষেত্রে আপনি উচ্চ স্তরে উন্নতি করে যে কোনও প্রোগ্রামকে উল্লেখযোগ্যভাবে গতি দিতে পারেন। একাধিকবারের পরিবর্তে একবারে ডেটা গণনা করা, অপ্রয়োজনীয় কাজ পুরোপুরি এড়ানো, সর্বোত্তম উপায়ে ক্যাশে ব্যবহার করা ইত্যাদি on এই জিনিসগুলি একটি উচ্চ স্তরের ভাষায় করা আরও সহজ।

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

ইউলারের সমস্যাগুলিতে, বেশিরভাগ সময় আপনি কোনও কিছু তৈরি করে, এটি ধীর কেন হয় তা অনুসন্ধান করে, আরও ভাল কিছু তৈরি করে, কেন ধীর হয় তা সন্ধান করে এবং আরও অনেক কিছুতে সফল হন। এটি খুব, খুব কঠিন এসেম্বেলার ব্যবহার করে using অর্ধেক সম্ভাব্য গতিতে একটি ভাল অ্যালগরিদম সাধারণত সম্পূর্ণ গতিতে আরও খারাপ অ্যালগরিদমকে পরাস্ত করে, এবং এসেম্বলারের মধ্যে পূর্ণ গতি পাওয়া তুচ্ছ নয়।


কোলাটজ সমস্যার জন্য, আপনি "লেজগুলি" ক্যাশে করে পারফরম্যান্সে একটি উল্লেখযোগ্য উত্সাহ পেতে পারেন। এটি একটি সময় / মেমরি ট্রেড অফ। দেখুন: মেমোয়েজেশন ( https://en.wikipedia.org/wiki/Memoization মেমোমাইজেশন )। আপনি অন্যান্য সময় / মেমরি ট্রেড-অফগুলির জন্য ডায়নামিক প্রোগ্রামিং সমাধানগুলিও দেখতে পারেন।

অজগর বাস্তবায়ন উদাহরণ:

import sys

inner_loop = 0

def collatz_sequence(N, cache):
    global inner_loop

    l = [ ]
    stop = False
    n = N

    tails = [ ]

    while not stop:
        inner_loop += 1
        tmp = n
        l.append(n)
        if n <= 1:
            stop = True  
        elif n in cache:
            stop = True
        elif n % 2:
            n = 3*n + 1
        else:
            n = n // 2
        tails.append((tmp, len(l)))

    for key, offset in tails:
        if not key in cache:
            cache[key] = l[offset:]

    return l

def gen_sequence(l, cache):
    for elem in l:
        yield elem
        if elem in cache:
            yield from gen_sequence(cache[elem], cache)
            raise StopIteration

if __name__ == "__main__":
    le_cache = {}

    for n in range(1, 4711, 5):
        l = collatz_sequence(n, le_cache)
        print("{}: {}".format(n, len(list(gen_sequence(l, le_cache)))))

    print("inner_loop = {}".format(inner_loop))

বরং সম্পর্কিত সম্পর্কিত নোটে: আরও পারফরম্যান্স হ্যাক!

  • [প্রথম ject অনুমান finally অবশেষে @ShreevatsaR দ্বারা প্রকাশিত হয়েছে; মুছে]

  • সিকোয়েন্সটি ট্র্যাভার করার সময়, আমরা কেবলমাত্র বর্তমান উপাদানটির 2-পাড়ায় 3 টি সম্ভাব্য কেস পেতে পারি N (প্রথমে দেখানো হয়েছে):

    1. [এমনকি] [বিজোড়]
    2. [বিজোড়] [এমনকি]
    3. [এমনকি] [এমনকি]

    গত এই উপাদান 2 লিপ করতে গনা মানে (N >> 1) + N + 1 , ((N << 1) + N + 1) >> 1 এবং N >> 2 যথাক্রমে।

    আসুন প্রমাণ করুন যে উভয় ক্ষেত্রে (1) এবং (2) প্রথম সূত্র ব্যবহার করা সম্ভব (N >> 1) + N + 1 ,।

    কেস (1) সুস্পষ্ট। কেস (২) বোঝাচ্ছে (N & 1) == 1 , সুতরাং যদি আমরা ধরে নিই (সাধারণতার ক্ষতি ছাড়াই) এন 2-বিট লম্বা এবং এর বিটগুলি ba সর্বাধিক থেকে কমপক্ষে-তাত্পর্যপূর্ণ হয় a = 1 , এবং নিম্নলিখিতটি ধারণ করে:

    (N << 1) + N + 1:     (N >> 1) + N + 1:
    
            b10                    b1
             b1                     b
           +  1                   + 1
           ----                   ---
           bBb0                   bBb

    যেখানে B = !b । প্রথম ফলাফলটি ডান-শিফটিং আমাদের ঠিক যা চায় তা দেয় gives

    Qed: (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1

    প্রমাণিত হিসাবে, আমরা একক ত্রৈমাসিক ক্রিয়াকলাপটি ব্যবহার করে একযোগে সিকোয়েন্স 2 উপাদানগুলি অতিক্রম করতে পারি। আরও 2 × সময় হ্রাস।

ফলস্বরূপ অ্যালগরিদম এরকম দেখাচ্ছে:

uint64_t sequence(uint64_t size, uint64_t *path) {
    uint64_t n, i, c, maxi = 0, maxc = 0;

    for (n = i = (size - 1) | 1; i > 2; n = i -= 2) {
        c = 2;
        while ((n = ((n & 3)? (n >> 1) + n + 1 : (n >> 2))) > 2)
            c += 2;
        if (n == 2)
            c++;
        if (c > maxc) {
            maxi = i;
            maxc = c;
        }
    }
    *path = maxc;
    return maxi;
}

int main() {
    uint64_t maxi, maxc;

    maxi = sequence(1000000, &maxc);
    printf("%llu, %llu\n", maxi, maxc);
    return 0;
}

এখানে আমরা তুলনা করছি n > 2 কারণ ক্রমের মোট দৈর্ঘ্যটি বিজোড় হলে প্রক্রিয়াটি 1 এর পরিবর্তে 2 এ থামতে পারে।

[Edit:]

আসুন এটি সমাবেশে অনুবাদ করুন!

MOV RCX, 1000000;



DEC RCX;
AND RCX, -2;
XOR RAX, RAX;
MOV RBX, RAX;

@main:
  XOR RSI, RSI;
  LEA RDI, [RCX + 1];

  @loop:
    ADD RSI, 2;
    LEA RDX, [RDI + RDI*2 + 2];
    SHR RDX, 1;
    SHRD RDI, RDI, 2;    ror rdi,2   would do the same thing
    CMOVL RDI, RDX;      Note that SHRD leaves OF = undefined with count>1, and this doesn't work on all CPUs.
    CMOVS RDI, RDX;
    CMP RDI, 2;
  JA @loop;

  LEA RDX, [RSI + 1];
  CMOVE RSI, RDX;

  CMP RAX, RSI;
  CMOVB RAX, RSI;
  CMOVB RBX, RCX;

  SUB RCX, 2;
JA @main;



MOV RDI, RCX;
ADD RCX, 10;
PUSH RDI;
PUSH RCX;

@itoa:
  XOR RDX, RDX;
  DIV RCX;
  ADD RDX, '0';
  PUSH RDX;
  TEST RAX, RAX;
JNE @itoa;

  PUSH RCX;
  LEA RAX, [RBX + 1];
  TEST RBX, RBX;
  MOV RBX, RDI;
JNE @itoa;

POP RCX;
INC RDI;
MOV RDX, RDI;

@outp:
  MOV RSI, RSP;
  MOV RAX, RDI;
  SYSCALL;
  POP RAX;
  TEST RAX, RAX;
JNE @outp;

LEA RAX, [RDI + 59];
DEC RDI;
SYSCALL;

সংকলনের জন্য এই আদেশগুলি ব্যবহার করুন:

nasm -f elf64 file.asm
ld -o file file.o

গডবোল্টে পিটার কর্ডেস কর্তৃক এএসএমটির সি এবং উন্নত / বাগফিক্সড সংস্করণ দেখুন । (সম্পাদক এর নোট: আপনার উত্তরে আমার জিনিস রাখার জন্য দুঃখিত, তবে আমার উত্তর গডবোল্ট লিঙ্কগুলি + পাঠ্য থেকে 30k চর সীমাতে আঘাত করেছে!)


সহজ উত্তর:

  • একটি এমওভি আরবিএক্স, 3 এবং মুল আরবিএক্স করা ব্যয়বহুল; কেবল আরবিএক্স, দুবার আরবিএক্স যুক্ত করুন

  • ADD 1 সম্ভবত এখানে INC এর চেয়ে দ্রুত

  • এমওভি 2 এবং ডিআইভি খুব ব্যয়বহুল; শুধু ডান স্থানান্তর

  • -৪-বিট কোডটি সাধারণত 32-বিট কোডের চেয়ে কম ধীরে ধীরে হয় এবং প্রান্তিককরণের সমস্যাগুলি আরও জটিল হয়; এই জাতীয় ছোট প্রোগ্রামের সাথে আপনাকে সেগুলি প্যাক করতে হবে যাতে আপনি 32-বিট কোডের চেয়ে দ্রুত হওয়ার কোনও সম্ভাবনা পাওয়ার জন্য সমান্তরাল গণনা করছেন

আপনি যদি আপনার সি ++ প্রোগ্রামের জন্য সমাবেশ তালিকা উত্পন্ন করেন তবে আপনি দেখতে পাবেন এটি কীভাবে আপনার সমাবেশ থেকে আলাদা fers


সোর্স কোড থেকে মেশিন কোড তৈরির সময় সি ++ প্রোগ্রামগুলি সমাবেশ প্রোগ্রামগুলিতে অনুবাদ করা হয়। এটি বলা কার্যত ভুল হবে যে সমাবেশটি সি ++ এর চেয়ে ধীর। তদতিরিক্ত, বাইনারি কোড উত্পন্ন সংকলক থেকে সংকলক থেকে পৃথক। সুতরাং একটি স্মার্ট সি ++ সংকলক বোবা এসেম্বলারের কোডের চেয়ে বাইনারি কোডটি আরও অনুকূল এবং দক্ষ তৈরি করতে পারে।

তবে আমি বিশ্বাস করি আপনার প্রোফাইলিং পদ্ধতিতে কিছু ত্রুটি রয়েছে। নিম্নলিখিতটি প্রোফাইলিংয়ের জন্য সাধারণ নির্দেশিকা:

  1. আপনার সিস্টেমটি স্বাভাবিক / নিষ্ক্রিয় অবস্থায় রয়েছে তা নিশ্চিত করুন। আপনি যে সমস্ত চলমান প্রক্রিয়াগুলি (অ্যাপ্লিকেশনগুলি) শুরু করেছেন সেগুলি বন্ধ করুন বা সিপিইউ নিবিড়ভাবে ব্যবহার করুন (বা নেটওয়ার্কের মাধ্যমে পোল করুন)।
  2. আপনার ডেটাসাইজটি আকারে অবশ্যই বড় হতে হবে।
  3. আপনার পরীক্ষা অবশ্যই 5-10 সেকেন্ডেরও বেশি কিছুতে চলতে পারে।
  4. একটি মাত্র নমুনার উপর নির্ভর করবেন না। আপনার পরীক্ষা এন বার সম্পাদন করুন। ফলাফল সংগ্রহ করুন এবং ফলাফলটির গড় বা মধ্যমা গণনা করুন।

যদি আপনি মনে করেন একটি 64৪-বিট ডিআইভি নির্দেশকে দুটি দ্বারা বিভক্ত করার একটি ভাল উপায়, তবে কোনও আশ্চর্য হওয়ার কারণ নেই যে -O0 আউটপুট আপনার হাতের লিখিত -O0 , এমনকি -O0 (দ্রুত সংকলন করুন, কোনও অতিরিক্ত অপ্টিমাইজেশন নেই, এবং মেমোরিতে সঞ্চয় / পুনরায় লোড করুন) প্রতিটি সি স্টেটমেন্টের পরে / এর আগে যাতে কোনও ডিবাগার ভেরিয়েবলগুলি সংশোধন করতে পারে)।

দক্ষ asm কীভাবে লিখতে হয় তা শিখতে Agner Fog এর অপ্টিমাইজিং অ্যাসেমব্লিক গাইডটি দেখুন। নির্দিষ্ট সিপিইউগুলির জন্য সুনির্দিষ্ট বিবরণের জন্য তার নির্দেশাবলী টেবিল এবং একটি মাইক্রোয়ার্ক গাইডও রয়েছে। আরও পারফেক্ট লিঙ্কের জন্য x86 ট্যাগ উইকিটিও দেখুন।

হাতে লিখিত asm দিয়ে সংকলককে প্রহার করার বিষয়ে এই আরও সাধারণ প্রশ্নটি দেখুন: কী ইনলাইন সমাবেশের ভাষা স্থানীয় সি ++ কোডের চেয়ে ধীর হয়? । টিএল: ডিআর: হ্যাঁ যদি আপনি এটি ভুল করেন (এই প্রশ্নের মতো)।

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

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

ইনটেল div r64 , div r64 হ'ল 36 উফ, যার 32-296 চক্রের বিলম্ব রয়েছে , এবং 21-74 চক্র প্রতি একের একটি থ্রুপুট। (আরবিএক্স এবং শূন্য আরডিএক্স সেটআপ করতে 2 টি উওস প্লাস করুন, তবে আউট-অফ-অর্ডার এক্সিকিউশনটি তাড়াতাড়ি চালাতে পারে)। ডিআইভির মতো উচ্চ-উওপ-কাউন্টের নির্দেশাবলী মাইক্রোকোডযুক্ত, এটি ফ্রন্ট-এন্ড বাধাও সৃষ্টি করতে পারে। এই ক্ষেত্রে, বিলম্বিতা সবচেয়ে প্রাসঙ্গিক কারণ কারণ এটি লুপ বহনকারী নির্ভরতা শৃঙ্খলার অংশ।

shr rax, 1 একই স্বাক্ষরবিহীন বিভাগ করে: এটি 1 ইউওপ, 1 সি ল্যাটেন্সি সহ এবং প্রতি ক্লক চক্র 2 চালাতে পারে।

তুলনার জন্য, 32-বিট বিভাগ দ্রুত, তবে এখনও ভয়ঙ্কর বনাম শিফট। idiv r32 9 টি উওস, 22-29 সি ল্যাটেন্সি এবং প্রতি 8-11c থ্রুপুট।

আপনি যেমনটি -O0 আউটপুট ( গডবোল্ট সংকলক এক্সপ্লোরার ) দেখে দেখে নিতে পারেন, এটি কেবল শিফট নির্দেশাবলী ব্যবহার করে -O0 আপনি ভেবেছিলেন -O0 সংকলন করে, এমনকি 64৪-বিট আইডিআইভিও দু'বার ব্যবহার করে। (অপ্টিমাইজ করার সময়, সংকলকগুলি আইডিআইভির উভয় আউটপুট ব্যবহার করে যখন উত্সটি একই অপারেশনগুলির সাথে বিভাগ এবং মডিউলাস করে, যদি তারা আইডিআইভি ব্যবহার করে তবে)

জিসিসির সম্পূর্ণরূপে নিষ্পাপ মোড নেই; এটি সর্বদা জিম্পলের মাধ্যমে রূপান্তরিত হয় যার অর্থ কিছু "অপ্টিমাইজেশন" অক্ষম করা যায় না । এর মধ্যে বিভাগ-বাই-ধ্রুবককে স্বীকৃতি দেওয়া এবং আইডিআইভি এড়ানোর জন্য শিফ্টগুলি (2 পাওয়ার) বা একটি স্থির-পয়েন্ট গুণিত ইনভার্স (2 এর শক্তি নয়) অন্তর্ভুক্ত রয়েছে (উপরের গডবোল্ট লিঙ্কে div_by_13 দেখুন)।

gcc -Os (আকারের জন্য অনুকূলিতকরণ) অ-পাওয়ার-অফ -2 বিভাগের জন্য আইডিআইভি ব্যবহার করে , দুর্ভাগ্যক্রমে এমনকি এমন ক্ষেত্রেও যেখানে গুণিতক বিপরীত কোডটি কিছুটা বড় তবে খুব দ্রুত much

সংকলককে সহায়তা করছে

(এই ক্ষেত্রে সারাংশ: uint64_t n ব্যবহার করুন)

প্রথমত, কেবলমাত্র অনুকূলিত সংকলক আউটপুটটি দেখতে আকর্ষণীয়। ( -O3 ) -O0 গতি মূলত অর্থহীন।

আপনার asm আউটপুটটি দেখুন (গডবোল্টে, বা জিসিসি / ঝনঝন সমাবেশ আউটপুট থেকে "শব্দ" কীভাবে সরিয়ে ফেলবেন তা দেখুন)। যখন সংকলকটি প্রথমে সর্বোত্তম কোডটি তৈরি করে না: আপনার সি / সি ++ উত্সটি এমনভাবে লিখুন যাতে সংকলককে আরও ভাল কোড তৈরি করতে পরিচালিত করা সাধারণত সর্বোত্তম পন্থা । আপনাকে asm জানতে হবে, এবং কী দক্ষ তা জানতে হবে তবে আপনি এই জ্ঞানকে পরোক্ষভাবে প্রয়োগ করেন। সংকলকগুলিও ধারণাগুলির একটি ভাল উত্স: কখনও কখনও ঝনঝন কিছু ভাল কাজ করে, এবং আপনি একই কাজটি করার জন্য জিসিসি হ্যান্ড হোল্ড করতে পারেন: এই উত্তরটি দেখুন এবং নীচে @ ভিড্রাকের কোডটিতে অ-নিবন্ধভুক্ত লুপটি দিয়ে আমি কী করেছি))

এই পদ্ধতির বহনযোগ্য, এবং 20 বছরের মধ্যে কিছু ভবিষ্যতের সংকলক ভবিষ্যতের হার্ডওয়্যার (x86 বা না) এর ক্ষেত্রে দক্ষ যা কিছু এটি সংকলন করতে পারে, সম্ভবত নতুন আইএসএ এক্সটেনশন বা অটো-ভেক্টরাইজিং ব্যবহার করে। 15 বছর আগে হাত থেকে লিখিত x86-64 asm সাধারণত স্কাইলেকের জন্য অনুকূলভাবে সুর করা যায় না। যেমন তুলনা করুন & ব্রাঞ্চ ম্যাক্রো-ফিউশন তখন আর বিদ্যমান ছিল না। একটি মাইক্রোআরকিটেকচারের জন্য হস্তনির্মিত এএসএমের জন্য এখন সর্বোত্তম কী অন্যান্য বর্তমান এবং ভবিষ্যতের সিপিইউগুলির জন্য অনুকূল নাও হতে পারে। @ জনফাউন্ডের উত্তরে মন্তব্যগুলি এএমডি বুলডোজার এবং ইন্টেল হাসওয়ের মধ্যে প্রধান পার্থক্য নিয়ে আলোচনা করেছে, যা এই কোডটিতে একটি বড় প্রভাব ফেলে। তবে তত্ত্বের ক্ষেত্রে, g++ -O3 -march=bdver3 এবং g++ -O3 -march=skylake সঠিক কাজ করবে। (অথবা -march=native ।) বা -mtune=... টিউন করার জন্য, অন্য সিপিইউগুলি সমর্থন না করতে পারে এমন নির্দেশাবলী ব্যবহার না করে।

আমার অনুভূতিটি হ'ল সংকলককে Asm করতে গাইড করা যা আপনার বর্তমান CPU এর পক্ষে ভাল যা ভবিষ্যতের কম্পাইলারদের জন্য সমস্যা হওয়া উচিত নয়। কোডটি রূপান্তর করার উপায়গুলি খুঁজতে তারা বর্তমান সংকলকগুলির চেয়ে আশাবাদী এবং ভবিষ্যতের সিপিইউগুলির জন্য কাজ করে এমন কোনও উপায় খুঁজে পেতে পারে। নির্বিশেষে, ভবিষ্যতের x86 সম্ভবত বর্তমান x86 এর পক্ষে ভাল কিছু হতে পারে না এবং ভবিষ্যতে সংকলক আপনার সি উত্স থেকে ডেটা চলাচলের মতো কিছু বাস্তবায়নের সময় কোনও asm-সুনির্দিষ্ট সমস্যাগুলি এড়াতে পারে, যদি এটি আরও ভাল কিছু না দেখায়।

হস্ত-লিখিত asm অপ্টিমাইজারের জন্য একটি কালো-বাক্স, সুতরাং যখন ইনলাইনিং কোনও ইনপুটকে একটি সংকলন-সময় ধ্রুবক করে তখন ধ্রুবক-প্রচার কাজ করে না। অন্যান্য অপ্টিমাইজেশানগুলিও প্রভাবিত হয়। Asm ব্যবহার করার আগে https://gcc.gnu.org/wiki/DontUseInlineAsm পড়ুন। (এবং এমএসভিসি-স্টাইলের ইনলাইন asm এড়ান: ইনপুট / আউটপুটগুলিকে মেমরির মধ্য দিয়ে যেতে হবে যা ওভারহেড যুক্ত করে ))

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

আপনার uint64_t n ব্যবহার করা উচিত ছিল, সুতরাং এটি কেবল SHR করতে পারে। এবং সুতরাং এটি এমন সিস্টেমে পোর্টেবল যেখানে long মাত্র 32-বিট (যেমন x86-64 উইন্ডোজ)।

বিটিডাব্লু, জিসিসির অপ্টিমাইজড এএসএম আউটপুটটি বেশ ভাল দেখাচ্ছে ( unsigned long n ব্যবহার করে) : অভ্যন্তরীণ লুপটি এতে মেইল main() করে:

 # from gcc5.4 -O3  plus my comments

 # edx= count=1
 # rax= uint64_t n

.L9:                   # do{
    lea    rcx, [rax+1+rax*2]   # rcx = 3*n + 1
    mov    rdi, rax
    shr    rdi         # rdi = n>>1;
    test   al, 1       # set flags based on n%2 (aka n&1)
    mov    rax, rcx
    cmove  rax, rdi    # n= (n%2) ? 3*n+1 : n/2;
    add    edx, 1      # ++count;
    cmp    rax, 1
    jne   .L9          #}while(n!=1)

  cmp/branch to update max and maxi, and then do the next n

অভ্যন্তরীণ লুপটি শাখাবিহীন এবং লুপ বহনকারী নির্ভরতা শৃঙ্খলার সমালোচনাপূর্ণ পথ:

  • 3-উপাদান এলইএ (3 চক্র)
  • সেমিভভ (হাসওয়েলে 2 টি চক্র, ব্রডওয়েলে 1c বা তার পরে)।

মোট: পুনরাবৃত্তি প্রতি 5 চক্র, বিলম্ব বাধা । আউট-অফ-অর্ডার এক্সিকিউশন এটির সাথে সমান্তরালভাবে সমস্ত কিছুর যত্ন নেয় (তত্ত্ব অনুসারে: আমি সত্যিই 5c / iter এ চলে কিনা তা দেখার জন্য পারফ কাউন্টারগুলির সাথে পরীক্ষা করিনি)।

cmov ইনপুট (টেস্ট দ্বারা উত্পাদিত) RAX ইনপুট (এলইএ-> এমওভি থেকে) তুলনায় দ্রুততর হয়, সুতরাং এটি সমালোচনামূলক পথে নয়।

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

সিএমপি / জেনও সমালোচনামূলক পথের অংশ নয়: এটি লুপ বহনকারী নয়, কারণ নিয়ন্ত্রণের নির্ভরতাগুলি সমালোচনামূলক পথে ডেটা নির্ভরতার বিপরীতে শাখার পূর্বাভাস + অনুমানমূলক সম্পাদন দ্বারা পরিচালিত হয়।

সংকলককে মারধর করছে

জিসিসি এখানে বেশ ভাল কাজ করেছে। এটি add edx, 1 পরিবর্তে inc edx ব্যবহার করে একটি কোড বাইট সংরক্ষণ করতে পারে কারণ আংশিক-পতাকা-সংশোধন নির্দেশাবলীর জন্য কেউ পি 4 এবং এর মিথ্যা-নির্ভরতার বিষয়ে চিন্তা করে না।

এটি সমস্ত এমওভি নির্দেশাবলী এবং cmovc করতে পারে: cmovc সিএফ = সেট করে বিট বিট সরিয়ে ফেলেছে, তাই আমরা test / cmovz পরিবর্তে cmovc ব্যবহার করতে cmovz

 ### Hand-optimized version of what gcc does
.L9:                       #do{
    lea     rcx, [rax+1+rax*2] # rcx = 3*n + 1
    shr     rax, 1         # n>>=1;    CF = n&1 = n%2
    cmovc   rax, rcx       # n= (n&1) ? 3*n+1 : n/2;
    inc     edx            # ++count;
    cmp     rax, 1
    jne     .L9            #}while(n!=1)

আরেকটি চতুর কৌতূহলের জন্য @ জনফাউন্ডের উত্তর দেখুন: এসএইচআর এর পতাকা ফলাফলের উপর শাখা করে সিএমওপি সরিয়ে ফেলুন পাশাপাশি এটি সিএমওভের জন্য ব্যবহার করুন: শুরু হলে এন 1 (বা 0) হলে শূন্য। (মজাদার ঘটনা: নেহালেম বা তার আগেরের গণনা সহ এসএইচআর! আপনি পতাকাটির ফলাফল পড়লে স্টল তৈরি করে। তারা এটিকে এটিকে এককভাবে উওপ বানিয়েছে। শিফট-বাই -1 বিশেষ এনকোডিং ঠিক আছে, যদিও)

এমওভি এড়ানো এলোমেলোভাবে হাসওলে মোটেও সহায়তা করে না ( x86 এর এমওভি আসলেই কি "মুক্ত" হতে পারে? কেন আমি এটিকে পুনরুত্পাদন করতে পারি না? )। এটি ইনটেল প্রি-আইভিবি, এবং এএমডি বুলডোজার-পরিবারের মতো সিপিইউগুলিতে উল্লেখযোগ্যভাবে সহায়তা করে, যেখানে এমওভি শূন্য-বিলম্বিত নয়। সংকলকটির নষ্ট MOV নির্দেশাবলী সমালোচনামূলক পথে প্রভাবিত করে। বিডির জটিল-এলইএ এবং সিএমওভ উভয়ই কম ল্যাটেন্সি (যথাক্রমে 2 সি এবং 1 সি), সুতরাং এটি বিলম্বের একটি বড় ভগ্নাংশ। এছাড়াও, থ্রুপুট বাধাগুলি একটি সমস্যা হয়ে দাঁড়ায়, কারণ এতে কেবল দুটি পূর্ণসংখ্যক ALU পাইপ রয়েছে। @ জনফাউন্ডের উত্তর দেখুন , যেখানে তার একটি এএমডি সিপিইউ থেকে সময় ফলাফল রয়েছে।

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

এলইএর বিলম্বিতা ইন্টেল এসএনবি-পরিবার সিপিইউগুলিতে ঠিকানা মোডের উপর নির্ভর করে । 3 সি 3 উপাদানগুলির জন্য ( [base+idx+const] , যা দুটি পৃথক সংযোজন নেয়), তবে 2 বা কম উপাদান (1 টি যোগ) সহ কেবল 1 সি। কিছু সিপিইউ (যেমন কোর 2) এমনকি একটি একক চক্রের 3-উপাদান এলইএ করে, তবে এসএনবি-পরিবার তা করে না। সবচেয়ে খারাপ, ইনটেল এসএনবি-পরিবার বিলম্বকে মানসম্পন্ন করে যাতে 2c উওস না থাকে , অন্যথায় 3-উপাদান এলইএ বুলডোজারের মতো কেবল 2 সি হবে। (3-উপাদান এলইএ এএমডি-তেও ধীরে ধীরে, কেবল তত বেশি নয়)।

সুতরাং lea rcx, [rax + rax*2] / inc rcx হ্যাসওলের মতো ইনটেল এসএনবি-ফ্যামিলি সিপিইউগুলিতে lea rcx, [rax + rax*2 + 1] চেয়ে দ্রুত lea rcx, [rax + rax*2 + 1] মাত্র ২ সি ল্যাটেন্সি। ব্রেক-ইন্ বিডি-তে, এবং কোর 2-এ আরও খারাপ। এটির জন্য অতিরিক্ত ইউওপ ব্যয় হয়, যা সাধারণত 1 সি লেটেন্সি বাঁচাতে উপযুক্ত নয়, তবে ল্যাটেন্সি এখানে প্রধান প্রধান বাধা এবং অতিরিক্ত ইউওপ থ্রুপুট পরিচালনা করতে হাসওয়েলের যথেষ্ট প্রশস্ত পাইপলাইন রয়েছে।

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

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

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

কৌশলটি সিদ্ধান্ত নিচ্ছে যে সমস্ত n মানগুলি আরম্ভ করার আগে n মানগুলি আরও 1 পেতে পৌঁছা পর্যন্ত অপেক্ষা করা হবে কিনা, অথবা কেবলমাত্র একটির জন্য একটি নতুন সূচনা পয়েন্ট পাওয়া যাবে যা শেষ শর্তে পৌঁছেছে, এর জন্য নিবন্ধগুলিকে স্পর্শ না করে অন্যান্য ক্রম। সম্ভবত প্রতিটি চেইন দরকারী ডেটাতে কাজ করা সবচেয়ে ভাল, অন্যথায় আপনাকে শর্তসাপেক্ষে এর পাল্টা বাড়িয়ে তুলতে হবে।

আপনি এমনকি এসএসই প্যাকড-তুলনা স্টাফ দিয়ে শর্তসাপেক্ষে ভেক্টর উপাদানগুলির জন্য কাউন্টারকে বাড়ানোর জন্য করতে পারেন যেখানে n এখনও 1 পৌঁছেছে না। এবং তারপরে সিমডাল শর্তসাপেক্ষ-বৃদ্ধির বাস্তবায়নের আরও দীর্ঘতর লম্বাতাটি আড়াল করার জন্য আপনাকে n মানগুলির আরও ভেক্টরগুলিকে বাতাসে রাখা দরকার। uint64_t ভেক্টর (4x uint64_t ) দিয়ে কেবল মূল্যবান।

আমি মনে করি যে 1 "স্টিকি" সনাক্তকরণের সর্বোত্তম কৌশলটি হ'ল আপনি কাউন্টারকে বাড়ানোর ক্ষেত্রে যুক্ত করা সমস্ত-এর ভেক্টরকে মাস্ক করা। সুতরাং আপনি কোনও এলিমেন্টে 1 পরে, ইনক্রিমেন্ট-ভেক্টরের শূন্য থাকবে এবং + = 0 একটি অপ-বিকল্প হবে।

ম্যানুয়াল ভেক্টরাইজেশনের জন্য অনির্ধারিত ধারণা

# starting with YMM0 = [ n_d, n_c, n_b, n_a ]  (64-bit elements)
# ymm4 = _mm256_set1_epi64x(1):  increment vector
# ymm5 = all-zeros:  count vector

.inner_loop:
    vpaddq    ymm1, ymm0, xmm0
    vpaddq    ymm1, ymm1, xmm0
    vpaddq    ymm1, ymm1, set1_epi64(1)     # ymm1= 3*n + 1.  Maybe could do this more efficiently?

    vprllq    ymm3, ymm0, 63                # shift bit 1 to the sign bit

    vpsrlq    ymm0, ymm0, 1                 # n /= 2

    # There may be a better way to do this blend, avoiding the bypass delay for an FP blend between integer insns, not sure.  Probably worth it
    vpblendvpd ymm0, ymm0, ymm1, ymm3       # variable blend controlled by the sign bit of each 64-bit element.  I might have the source operands backwards, I always have to look this up.

    # ymm0 = updated n  in each element.

    vpcmpeqq ymm1, ymm0, set1_epi64(1)
    vpandn   ymm4, ymm1, ymm4         # zero out elements of ymm4 where the compare was true

    vpaddq   ymm5, ymm5, ymm4         # count++ in elements where n has never been == 1

    vptest   ymm4, ymm4
    jnz  .inner_loop
    # Fall through when all the n values have reached 1 at some point, and our increment vector is all-zero

    vextracti128 ymm0, ymm5, 1
    vpmaxq .... crap this doesn't exist
    # Actually just delay doing a horizontal max until the very very end.  But you need some way to record max and maxi.

আপনার হাতে লিখিত asm এর পরিবর্তে, অন্তর্নিহিতগুলি দিয়ে এটি প্রয়োগ করতে এবং করা উচিত।

অ্যালগরিদমিক / বাস্তবায়ন উন্নতি:

আরও দক্ষ asm সহ কেবল একই যুক্তিকে বাস্তবায়ন করার পাশাপাশি যুক্তিটি সহজ করার উপায়গুলি অনুসন্ধান করুন বা অপ্রয়োজনীয় কাজ এড়ানো উচিত। উদাহরণ অনুসারে ক্রমগুলির সাধারণ পরিণতি সনাক্ত করতে মেমোয়েজ করুন। বা আরও ভাল, একবারে 8 টি ট্রেলিং বিট দেখুন (জ্ঞানারের উত্তর)

@EF টি নির্দেশ করে যে tzcnt (বা tzcnt ) এক ধাপে একাধিক n/=2 পুনরাবৃত্তি করতে ব্যবহৃত হতে পারে। এটি সম্ভবত সিমডি ভেক্টরাইজিংয়ের চেয়ে ভাল, কারণ কোনও এসএসই বা AVX নির্দেশনা এটি করতে পারে না। যদিও এটি বিভিন্ন পূর্ণসংখ্যার নিবন্ধগুলিতে সমান্তরালে একাধিক স্কেলার n গুলি করার সাথে সামঞ্জস্যপূর্ণ।

সুতরাং লুপটি দেখতে এটি দেখতে পারে:

goto loop_entry;  // C++ structured like the asm, for illustration only
do {
   n = n*3 + 1;
  loop_entry:
   shift = _tzcnt_u64(n);
   n >>= shift;
   count += shift;
} while(n != 1);

এটি উল্লেখযোগ্যভাবে কম পুনরাবৃত্তি করতে পারে, তবে ভেরিয়েবল-কাউন্ট শিফট BMI2 ছাড়াই ইন্টেল এসএনবি-পরিবার সিপিইউতে ধীর হয়। 3 উফ, 2 সি ল্যাটেন্সি (এফএএলজিএসে তাদের একটি ইনপুট নির্ভরতা রয়েছে কারণ গণনা = 0 এর অর্থ পতাকাগুলি অশোধিত নয় They তারা এটিকে ডেটা নির্ভরতা হিসাবে পরিচালনা করে এবং একাধিক উফ গ্রহণ করে কারণ একটি উওপটিতে কেবল 2 ইনপুট থাকতে পারে (যাইহোক প্রাক-এইচএসডাব্লু / বিডিডাব্লু))। X86 এর পাগল-সিআইএসসি ডিজাইনের বিষয়ে লোকেরা অভিযোগ করার বিষয়টি উল্লেখ করছে। এটি x86 সিপিইউগুলিকে তাদের চেয়ে ধীর করে তোলে যদি আজ আইএসএ স্ক্র্যাচ থেকে তৈরি করা হয়েছিল এমনকি এমনকি বেশিরভাগ ক্ষেত্রে। (অর্থাত্ এটি "x86 ট্যাক্স" এর অংশ যা গতি / শক্তি ব্যয় করে SH) SHRX / SHLX / SARX (BMI2) একটি বড় জয় (1 টি ইউওপ / 1 সি ল্যাটেন্সি)।

এটি tzcnt (হাসওয়েলের উপর 3c এবং পরবর্তীকালে) সমালোচনামূলক পথে ফেলেছে, সুতরাং এটি লুপ বহনকারী নির্ভরতা শৃঙ্খলের মোট বিলম্বকে উল্লেখযোগ্যভাবে দীর্ঘায়িত করে। যদিও এটি কোনও সিএমওভের জন্য, অথবা n>>1 হোল্ডার রেজিস্টার প্রস্তুত করার জন্য কোনও প্রয়োজন সরিয়ে দেয়। @ ভিড্রাকের উত্তর একাধিক পুনরাবৃত্তির জন্য tzcnt / শিফট স্থগিত করে এগুলি কাটিয়ে উঠেছে, যা অত্যন্ত কার্যকর (নীচে দেখুন)।

আমরা নিরাপদে BSF বা TZCNT বিনিময়যোগ্যভাবে ব্যবহার করতে পারি, কারণ n কখনই শূন্য হতে পারে না। বিএমআই 1 সমর্থন করে না এমন সিপিইউতে টিজেডিসিএনটির মেশিন-কোড বিএসএফ হিসাবে ডিকোড করে। (অর্থহীন উপসর্গগুলি উপেক্ষা করা হয়, তাই আরইপি বিএসএফ বিএসএফ হিসাবে চালিত হয়)।

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

তারা ইন্টেল সিপিইউগুলিতে একই সম্পাদন করে, তাই কেবলমাত্র বাইটটি সংরক্ষণ করুন যদি এটি গুরুত্বপূর্ণ। ইনটেলের টিজেডিসিএনটি (প্রাক-স্কাইলেক) এখনও বিএসএফের মতো অনুমিত রাইটিং-আউটপুট অপারেন্ডের উপর একটি মিথ্যা-নির্ভরতা রয়েছে যা ইনপুট = 0 দিয়ে বিএসএফ তার গন্তব্যটি অবিচ্ছিন্ন ছেড়ে দেয় the সুতরাং আপনাকে কেবলমাত্র স্কাইলেকে অনুকূলকরণ না করাতে সেদিকেই কাজ করা উচিত, তাই অতিরিক্ত আরইপি বাইট থেকে লাভের কিছুই নেই। (ইন্টেল প্রায়শই x86 আইএসএ ম্যানুয়াল যা প্রয়োজন তার উপর নির্ভর করে এবং এর বাইরে চলে যায়, যা ব্যবহার করা উচিত নয় এমন কোনও বিষয়ের উপর নির্ভর করে বা এটি প্রত্যাখ্যানজনকভাবে বাতিল নয় eg যেমন উইন্ডোজ 9 এক্স এর টিএলবি এন্ট্রিগুলির কোনও অনুমানমূলক প্রিফেচিং ধরে নেই , যা নিরাপদ ছিল কোডটি যখন লেখা হয়েছিল, তার আগে ইনটেল টিএলবি পরিচালনার নিয়ম আপডেট করেছিল ))

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

অন্যান্য উত্তর থেকে ধারণা / কোডে উন্নতি:

@ হিডফ্র্যামকজিবি এর উত্তরে একটি সুন্দর পর্যবেক্ষণ রয়েছে যে আপনি 3n + 1 এর পরে একটি ডান শিফট করতে সক্ষম হওয়ার গ্যারান্টিযুক্ত। আপনি আরও বেশি দক্ষতার সাথে এটি গণনা করতে পারেন কেবলমাত্র পদক্ষেপের মধ্যে চেক না রেখে। এই উত্তরে asm বাস্তবায়ন ভেঙে গেছে, যদিও (এটি OF এর উপর নির্ভর করে যা একটি গণনা> 1 এর সাথে SHRD এর পরে অপরিবর্তিত রয়েছে) এবং ধীর: ROR rdi,2 SHRD rdi,rdi,2 চেয়ে দ্রুত এবং দুটি CMOV নির্দেশাবলী ব্যবহার করে সমালোচনামূলক পথে অতিরিক্ত অতিরিক্ত টেস্টের চেয়ে ধীরে ধীরে ধীরে ধীরে ধীরে ধীরে চলতে পারে।

আমি পরিপাটি / উন্নত সি রেখেছি (যা সংকলককে আরও ভাল asm উত্পাদন করতে গাইড করে), এবং + গডবোল্টে আরও দ্রুত asm (সি এর নীচে মন্তব্যে) কাজ করে পরীক্ষা করেছি: @ হাইডফ্র্যামকজিবি এর উত্তরের লিঙ্কটি দেখুন। (এই উত্তরটি বৃহত গডবোল্ট ইউআরএলগুলি থেকে 30k চর সীমাতে আঘাত করেছে তবে শর্টলিঙ্কগুলি পচতে পারে এবং যাইহোক goo.gl এর জন্য খুব দীর্ঘ ছিল))

স্ট্রিংতে রূপান্তর করতে এবং একবারে একটি লেখার পরিবর্তে একটি লেখার write() লেখার জন্য আউটপুট-মুদ্রণকে আরও উন্নত করে। এটি পুরো প্রোগ্রামটি perf stat ./collatz (পারফরম্যান্স কাউন্টারগুলিতে রেকর্ড করতে) সহ সময়সীমার উপর প্রভাবকে হ্রাস করে এবং আমি কিছু অ-সমালোচক perf stat ./collatz করেছিলাম।

@ Veedrac এর কোড

ডান স্থানান্তর থেকে আমাদের যতটা করা প্রয়োজন জানি এবং লুপটি চালিয়ে যাওয়ার জন্য চেক করা থেকে আমি একটি খুব ছোট স্পিডআপ পেয়েছি। কোরের টু ডুও (মেরম) এ 16 এর আনারল ফ্যাক্টর সহ = 1e8 কমিয়ে 7.275 এ 7.5s থেকে।

কোড + গডবোল্ট সম্পর্কে মন্তব্য। ঝাঁকুনি সহ এই সংস্করণটি ব্যবহার করবেন না; এটি ডিফার-লুপের সাথে নির্বোধ কিছু করে। একটি টেম্প কাউন্টার k ব্যবহার করে এবং তারপরে এটি count পরে কী পরিবর্তন হয় তা count করার জন্য যুক্ত করে তবে এটি জিসিসিতে কিছুটা ব্যথা করে।

মন্তব্যে আলোচনাটি দেখুন: বিএমআই 1 (যেমন সেলেরন / পেন্টিয়াম নয়) সহ সিপিইউগুলিতে ভিড্র্যাকের কোডটি দুর্দান্ত


সি ++ সংকলক সক্ষম সংসদীয় ভাষা প্রোগ্রামারের তুলনায় আরও অনুকূল কোড তৈরি করতে পারে এমন দাবি করা খুব খারাপ ভুল। এবং বিশেষত এই ক্ষেত্রে। মানব সবসময় সংকলক যে কোডটি করতে পারে তা আরও উন্নত করতে পারে এবং এই নির্দিষ্ট পরিস্থিতিটি এই দাবির ভাল চিত্রণ।

আপনি যে সময়সীমার পার্থক্যটি দেখছেন তা হ'ল কারণ প্রশ্নটির সমাবেশ কোডটি অভ্যন্তরীণ লুপগুলিতে অনুকূল থেকে খুব দূরে।

(নীচের কোডটি 32-বিট, তবে সহজেই 64-বিটে রূপান্তরিত হতে পারে)

উদাহরণস্বরূপ, সিকোয়েন্স ফাংশনটি কেবলমাত্র 5 টি নির্দেশকে অনুকূলিত করা যেতে পারে:

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

পুরো কোডটি দেখে মনে হচ্ছে:

include "%lib%/freshlib.inc"
@BinaryType console, compact
options.DebugMode = 1
include "%lib%/freshlib.asm"

start:
        InitializeAll
        mov ecx, 999999
        xor edi, edi        ; max
        xor ebx, ebx        ; max i

    .main_loop:

        xor     esi, esi
        mov     eax, ecx

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

        cmp     edi, esi
        cmovb   edi, esi
        cmovb   ebx, ecx

        dec     ecx
        jnz     .main_loop

        OutputValue "Max sequence: ", edi, 10, -1
        OutputValue "Max index: ", ebx, 10, -1

        FinalizeAll
        stdcall TerminateAll, 0

এই কোডটি সংকলন করার জন্য, ফ্রেশলিব প্রয়োজন।

আমার পরীক্ষায় (1 গিগাহার্টজ এএমডি এ 4-1200 প্রসেসর), উপরের কোডটি প্রশ্ন থেকে সি ++ কোডের চেয়ে প্রায় চারগুণ দ্রুত (যখন -O0 : 430 এমএস বনাম 1900 এমএস সহ সংকলিত হবে) এবং -O0 বেশি দ্রুত (430 এমএস বনাম 830 এমএস) যখন সি ++ কোড -O3 দিয়ে সংকলিত হয়।

উভয় প্রোগ্রামের আউটপুট একই: i = 837799 এ সর্বোচ্চ সিকোয়েন্স = 525।








x86