हाथ से लिखे गए विधानसभा की तुलना में Collatz अनुमान का परीक्षण करने के लिए C++ कोड-क्यों?




performance assembly (8)

Collatz समस्या के लिए, आप "पूंछ" को कैशिंग करके प्रदर्शन में उल्लेखनीय वृद्धि प्राप्त कर सकते हैं। यह एक समय / स्मृति व्यापार बंद है। देखें: संस्मरण ( 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))

मैंने प्रोजेक्ट ईयूलर Q14 के लिए , असेंबली में और C ++ में ये दो समाधान लिखे। Collatz अनुमान का परीक्षण करने के लिए वे समान समान बल बल दृष्टिकोण हैं। विधानसभा समाधान के साथ इकट्ठा किया गया था

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

C ++ के साथ संकलित किया गया था

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

C ++, p14.cpp

#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;
}

मुझे गति और सब कुछ सुधारने के लिए कंपाइलर ऑप्टिमाइज़ेशन के बारे में पता है, लेकिन मुझे अपने असेंबली सॉल्यूशन को आगे बढ़ाने के लिए कई तरीके नहीं दिखते हैं (प्रोग्राम को गणितीय रूप से नहीं)।

C ++ कोड में हर पद और हर पद के लिए मापांक होता है, जहां असेंबली प्रति शब्द केवल एक विभाजन है।

लेकिन विधानसभा C ++ समाधान की तुलना में औसतन 1 सेकंड अधिक समय ले रही है। ऐसा क्यों है? मैं मुख्य रूप से जिज्ञासा से बाहर पूछ रहा हूं।

निष्पादन समय

मेरा सिस्टम: 1.4 गीगाहर्ट्ज़ इंटेल सेलेरॉन 2955U (हैसवेल माइक्रोआर्किटेक्चर) पर 64 बिट लिनक्स।


असेंबली को देखे बिना भी, सबसे स्पष्ट कारण यह है कि /= 2 संभवतः इसे अनुकूलित किया गया है >>=1 और कई प्रोसेसरों में बहुत तेज बदलाव ऑपरेशन है। लेकिन भले ही किसी प्रोसेसर में शिफ्ट ऑपरेशन न हो, पूर्णांक विभाजन फ्लोटिंग पॉइंट डिवीजन की तुलना में तेज़ होता है।

संपादित करें: आपके मिलन के ऊपर "पूर्णांक विभाजन फ़्लोटिंग पॉइंट डिवीजन से तेज़ है" कथन के अनुसार भिन्न हो सकता है। नीचे दी गई टिप्पणियों से पता चलता है कि आधुनिक प्रोसेसर ने पूर्णांक विभाजन पर fp डिवीजन को अनुकूलित करने को प्राथमिकता दी है। इसलिए अगर कोई स्पीडअप के सबसे संभावित कारण की तलाश कर रहा था, जिसके बारे में थ्रेड का सवाल पूछता है, तो कंपाइलर ऑप्टिमाइज़िंग के /=2 रूप >>=1 में सबसे अच्छा 1 स्थान होगा।

एक असंबंधित नोट पर , यदि n विषम है, तो अभिव्यक्ति n*3+1 हमेशा भी होगी। इसलिए जांच की कोई जरूरत नहीं है। आप उस शाखा को बदल सकते हैं

{
   n = (n*3+1) >> 1;
   count += 2;
}

तो पूरा बयान तब होगा

if (n & 1)
{
    n = (n*3 + 1) >> 1;
    count += 2;
}
else
{
    n >>= 1;
    ++count;
}

एक सामान्य उत्तर के रूप में, विशेष रूप से इस कार्य पर निर्देशित नहीं है: कई मामलों में, आप उच्च स्तर पर सुधार करके किसी भी कार्यक्रम को तेज कर सकते हैं। जैसे कई बार के बजाय एक बार डेटा की गणना करना, अनावश्यक काम से पूरी तरह से बचना, सबसे अच्छे तरीके से कैश का उपयोग करना, और इसी तरह। ये चीजें उच्च स्तरीय भाषा में करना बहुत आसान हैं।

कोडांतरक कोड लिखना, यह बेहतर करना संभव है कि एक अनुकूलन कंपाइलर क्या करता है, लेकिन यह कड़ी मेहनत है। और एक बार जब यह हो जाता है, तो आपका कोड संशोधित करना बहुत कठिन है, इसलिए एल्गोरिथम सुधार को जोड़ना अधिक कठिन है। कभी-कभी प्रोसेसर में कार्यक्षमता होती है जिसे आप उच्च स्तर की भाषा से उपयोग नहीं कर सकते, इन मामलों में इनलाइन असेंबली अक्सर उपयोगी होती है और फिर भी आपको उच्च स्तर की भाषा का उपयोग करने देती है।

यूलर समस्याओं में, अधिकांश समय आप किसी चीज के निर्माण में सफल होते हैं, यह पता लगाते हैं कि यह धीमा क्यों है, कुछ बेहतर निर्माण कर रहा है, यह पता लगाता है कि यह धीमा क्यों है, और इसी तरह इत्यादि। असेंबलर का उपयोग करना बहुत कठिन है। आधी संभव गति पर एक बेहतर एल्गोरिथ्म आमतौर पर पूर्ण गति पर एक बदतर एल्गोरिथ्म को हरा देगा, और असेंबलर में पूर्ण गति प्राप्त करना तुच्छ नहीं है।


टिप्पणियों से:

लेकिन, यह कोड कभी नहीं रुकता है (पूर्णांक अतिप्रवाह के कारण)! यवेस डावाड

कई नंबरों के लिए यह अतिप्रवाह नहीं होगा ।

यदि यह अतिप्रवाह करेगा - उन अशुभ प्रारंभिक बीजों में से एक के लिए, अतिप्रवाह संख्या एक और अतिप्रवाह के बिना 1 की ओर अभिसरण होगी।

फिर भी यह दिलचस्प सवाल है, क्या कुछ अतिप्रवाह-चक्रीय बीज संख्या है?

कोई भी सरल अंतिम रूपांतरित श्रृंखला दो मूल्य (स्पष्ट रूप से पर्याप्त?) की शक्ति से शुरू होती है।

2 ^ 64 ओवरफ्लो हो जाएगा शून्य पर, जो एल्गोरिथ्म के अनुसार अपरिभाषित अनंत लूप है (केवल 1 के साथ समाप्त होता है), लेकिन उत्तर में सबसे इष्टतम समाधान shr rax ZF = 1 के उत्पादन के कारण खत्म हो जाएगा ।

क्या हम 2 ^ 64 का उत्पादन कर सकते हैं? यदि शुरुआती संख्या है 0x5555555555555555 , तो यह विषम संख्या है, अगला नंबर 3n + 1 है, जो कि 0xFFFFFFFFFFFFFFFF + 1 = है 0 । एल्गोरिथम की अपरिभाषित स्थिति में सैद्धांतिक रूप से, लेकिन जॉन्फाउंड का अनुकूलित उत्तर ZF = 1 पर बाहर निकलने से ठीक हो जाएगा। cmp rax,1 पीटर Cordes की अनंत लूप में खत्म हो जाएगा (QED संस्करण 1, अपरिभाषित के माध्यम से "cheapo" 0 संख्या)।

कैसे कुछ और अधिक जटिल संख्या के बारे में, जो बिना चक्र बनाएगा 0 ? सच कहूँ तो, मुझे यकीन नहीं है, मेरा गणित सिद्धांत किसी भी गंभीर विचार को प्राप्त करने के लिए बहुत जल्दबाजी में है, इसके साथ गंभीर तरीके से कैसे निपटें। लेकिन सहज रूप से मैं कहूंगा कि श्रृंखला प्रत्येक संख्या के लिए 1 में परिवर्तित हो जाएगी: 0 <संख्या, चूंकि 3n + 1 सूत्र धीरे-धीरे मूल संख्या (या मध्यवर्ती) के प्रत्येक गैर -2 प्रमुख कारक को 2, कुछ या बाद की शक्ति में बदल देगा। । इसलिए हमें मूल श्रृंखला के लिए अनंत लूप के बारे में चिंता करने की आवश्यकता नहीं है, केवल अतिप्रवाह हमें बाधित कर सकता है।

इसलिए मैंने बस कुछ नंबरों को शीट में डाल दिया और 8 बिट्स को काट दिया।

करने के लिए बह निकला तीन मान नहीं होता 0 : 227 , 170 और 85 ( 85 तक जाया जा सकता 0 है, अन्य दो की ओर से प्रगति कर 85 )।

लेकिन चक्रीय अतिप्रवाह बीज बनाने का कोई मूल्य नहीं है।

पर्याप्त रूप से मैंने एक चेक किया, जो कि 8 बिट ट्रंकेशन से पीड़ित होने वाला पहला नंबर है, और पहले 27 से ही प्रभावित है! यह 9232 उचित गैर-काट-छाँट श्रृंखला में मूल्य तक पहुँचता है (पहले 322 छँटा हुआ मूल्य 12 वें चरण में है), और गैर-छँटाई तरीके से 2-255 इनपुट संख्याओं में से किसी के लिए अधिकतम मूल्य पहुँच गया है 13120 ( 255 स्वयं के लिए), अधिकतम संख्या में कदम करने के लिए 1 है के बारे में 128 (+ -2, यकीन है कि अगर "1" गिनती करने के लिए नहीं है, आदि ...)।

दिलचस्प रूप से पर्याप्त (मेरे लिए) संख्या 9232 कई अन्य स्रोत संख्याओं के लिए अधिकतम है, इसके बारे में क्या खास है? : -ओ 9232 = 0x2410 ... हम्मम .. कोई आइडिया नहीं।

दुर्भाग्य से मुझे इस श्रृंखला की कोई गहरी समझ नहीं मिल पा रही है, यह क्यों अभिसिंचित होती है और इन्हें k बिट्स cmp number,1 में विभाजित करने के क्या निहितार्थ हैं , लेकिन शर्त को समाप्त करने के साथ निश्चित रूप से एल्गोरिथ्म को अनंत लूप में डालना संभव है, विशेष इनपुट मूल्य के साथ समाप्त होने के 0 बाद काट-छांट।

लेकिन 27 8 बिट मामले के लिए ओवरफ्लो करने वाला मूल्य अलर्ट करने जैसा है, यह इस तरह दिखता है यदि आप मूल्य तक पहुंचने के लिए चरणों की संख्या की गणना करते हैं 1 , तो आपको पूर्णांक के कुल के-बिट सेट से अधिकांश संख्याओं के लिए गलत परिणाम मिलेगा। 8 बिट पूर्णांकों के लिए 256 में से 146 संख्याओं ने छंटनी द्वारा श्रृंखला को प्रभावित किया है (उनमें से कुछ अभी भी दुर्घटना से सही संख्या में कदम उठा सकते हैं, शायद मैं जांच के लिए बहुत आलसी हूं)।


सरल उत्तर:

  • MOV RBX, 3 और MUL RBX करना महंगा है; सिर्फ ADD RBX, RBX दो बार

  • ADD 1 शायद INC से भी तेज है

  • MOV 2 और DIV बहुत महंगा है; बस सही बदलाव

  • 64-बिट कोड आमतौर पर 32-बिट कोड की तुलना में काफी धीमा है और संरेखण मुद्दे अधिक जटिल हैं; इस तरह के छोटे कार्यक्रमों के साथ आपको उन्हें पैक करना होगा ताकि आप 32-बिट कोड से अधिक तेज़ होने की किसी भी संभावना के समानांतर गणना कर रहे हों

यदि आप अपने C ++ प्रोग्राम के लिए असेंबली लिस्टिंग जेनरेट करते हैं, तो आप देख सकते हैं कि यह आपके असेंबली से कैसे भिन्न है।


स्रोत कोड से मशीन कोड के निर्माण के दौरान सी ++ कार्यक्रमों को विधानसभा कार्यक्रमों में अनुवाद किया जाता है। यह कहना गलत होगा कि विधानसभा C ++ की तुलना में धीमी है। इसके अलावा, उत्पन्न बाइनरी कोड संकलक से संकलक तक भिन्न होता है। तो एक स्मार्ट C ++ कम्पाइलर सकता है बाइनरी कोड अधिक इष्टतम और एक गूंगा कोडांतरक के कोड से कुशल उत्पादन।

हालाँकि मेरा मानना ​​है कि आपकी रूपरेखा पद्धति में कुछ दोष हैं। प्रोफाइलिंग के लिए सामान्य दिशानिर्देश निम्नलिखित हैं:

  1. सुनिश्चित करें कि आपका सिस्टम अपनी सामान्य / निष्क्रिय अवस्था में है। उन सभी चल रही प्रक्रियाओं (एप्लिकेशन) को बंद करें जिन्हें आपने शुरू किया था या जो कि गहनता से सीपीयू का उपयोग करते हैं (या नेटवर्क पर सर्वेक्षण)।
  2. आपका डेटा आकार में बड़ा होना चाहिए।
  3. आपका परीक्षण 5-10 सेकंड से अधिक के लिए चलना चाहिए।
  4. सिर्फ एक नमूने पर भरोसा न करें। अपना टेस्ट N बार करें। परिणाम एकत्र करें और परिणाम के औसत या माध्य की गणना करें।

यदि आपको लगता है कि 64-बिट DIV निर्देश दो से विभाजित करने का एक अच्छा तरीका है, तो कोई आश्चर्य नहीं कि संकलक के एसएसएम आउटपुट ने आपके हाथ से लिखे गए कोड को हरा दिया, यहां तक ​​कि -O0 (संकलन तेज, कोई अतिरिक्त अनुकूलन नहीं, और मेमोरी को पुनः लोड करने के लिए) प्रत्येक सी स्टेटमेंट से पहले / बाद में एक डिबगर चर को संशोधित कर सकता है)।

कुशल एएसएम लिखने का तरीका जानने के लिए एग्नेर फॉग के ऑप्टिमाइज़िंग असेंबली गाइड देखें। उसके पास निर्देश सारणी और विशिष्ट सीपीयू के लिए विशिष्ट विवरण के लिए एक माइक्रो-गाइड भी है। अधिक पूर्ण लिंक के लिए x86 टैग विकी भी देखें।

संकलक को हाथ से लिखे हुए आसमाँ से पिटाई के बारे में यह और भी सामान्य प्रश्न देखें: क्या इनलाइन असेंबली भाषा देशी C ++ कोड से धीमी है? । TL: DR: हाँ अगर आप इसे गलत करते हैं (जैसे यह प्रश्न)।

आमतौर पर आप ठीक कर रहे हैं संकलक अपनी बात करते हैं, खासकर यदि आप C ++ लिखने की कोशिश करते हैं जो कुशलता से संकलित कर सकते हैं । यह भी देखें कि संकलित भाषाओं की तुलना में विधानसभा तेज है? इन सी स्लाइड के उत्तर में से एक यह दिखाता है कि विभिन्न सी कंपाइलर शांत चाल के साथ कुछ बहुत ही सरल कार्यों का अनुकूलन करते हैं।

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

Intel Haswell पर, div r64 36 uops है, जिसमें 32-96 चक्रों की विलंबता है , और प्रति 21-74 चक्रों में से एक थ्रूपुट है। (प्लस आरबीएक्स और शून्य आरडीएक्स स्थापित करने के लिए 2 यूओपीएस, लेकिन ऑर्डर-आउट निष्पादन जल्दी चला सकते हैं)। DIV जैसे उच्च-यूओपी-गिनती निर्देश माइक्रोकोडेड हैं, जो फ्रंट-एंड अड़चनों का कारण भी बन सकते हैं। इस मामले में, विलंबता सबसे प्रासंगिक कारक है क्योंकि यह एक लूप-आधारित निर्भरता श्रृंखला का हिस्सा है।

shr rax, 1 समान अहस्ताक्षरित विभाजन करता है: यह 1 uop है, 1c विलंबता के साथ , और प्रति घड़ी 2 चक्र चला सकता है।

तुलना के लिए, 32-बिट डिवीजन तेज है, लेकिन अभी भी भयानक बनाम बदलाव है। idiv r32 9 यूओपीएस, 22-29c विलंबता और हसवेल पर 8-11 सी थ्रूपुट प्रति एक है।

जैसा कि आप gcc -O0 asm आउटपुट ( Godbolt कंपाइलर एक्सप्लोरर ) को देखने से देख सकते हैं, यह केवल शिफ्ट्स निर्देशों का उपयोग करता है -O0 जैसा आपने सोचा था, 64-बिट IDIV का दो बार उपयोग करने पर भी आप जैसा संकलन करते हैं। (जब अनुकूलन, संकलक IDIV के दोनों आउटपुट का उपयोग करते हैं जब स्रोत एक ही ऑपरेंड के साथ एक विभाजन और मापांक करता है, अगर वे IDIV का उपयोग करते हैं)

जीसीसी में पूरी तरह से अनुभवहीन मोड नहीं है; यह हमेशा GIMPLE के माध्यम से बदल जाता है, जिसका अर्थ है कि कुछ "अनुकूलन" को अक्षम नहीं किया जा सकता है । इसमें IDIV से बचने के लिए डिवीजन-बाय-कॉन्स्टेंट और शिफ्ट्स (2 की शक्ति) या एक निश्चित-बिंदु गुणन व्युत्क्रम (2 की गैर-शक्ति) का उपयोग करना शामिल है (उपरोक्त Godbolt लिंक में div_by_13 देखें)।

gcc -Os (आकार के लिए ऑप्टिमाइज़) गैर-पावर ऑफ़-टू डिवीजन के लिए IDIV का उपयोग करता है , दुर्भाग्य से उन मामलों में भी जहां गुणक व्युत्क्रम कोड केवल थोड़ा बड़ा है, लेकिन बहुत तेज़ है।

कंपाइलर की मदद करना

(इस मामले के लिए सारांश: uint64_t n उपयोग करें)

सबसे पहले, यह केवल अनुकूलित संकलक आउटपुट को देखने के लिए दिलचस्प है। ( -O3 )। -O0 गति मूल रूप से अर्थहीन है।

अपने asm आउटपुट को देखें (Godbolt पर, या देखें कि GCC / clang विधानसभा आउटपुट से "शोर" कैसे निकालें? )। जब कंपाइलर पहली बार में इष्टतम कोड नहीं बनाता है: अपने सी / सी ++ स्रोत को इस तरह से लिखना जो कंपाइलर को बेहतर कोड बनाने में मार्गदर्शन करता है, आमतौर पर सबसे अच्छा तरीका है । आपको asm को जानना है, और यह जानना है कि क्या कुशल है, लेकिन आप इस ज्ञान को अप्रत्यक्ष रूप से लागू करते हैं। कंपाइलर भी विचारों का एक अच्छा स्रोत है: कभी-कभी क्लैंग कुछ शांत कर देगा, और आप एक ही काम करने में जीसीसी को हाथ से पकड़ सकते हैं: इस उत्तर को देखें और मैंने नीचे @ वैडरैक के कोड में गैर-अनियंत्रित लूप के साथ क्या किया।

यह दृष्टिकोण पोर्टेबल है, और 20 वर्षों में कुछ भविष्य के कंपाइलर इसे भविष्य के हार्डवेयर (x86 या नहीं) पर कुशल होने के लिए संकलित कर सकते हैं, शायद नए आईएसए एक्सटेंशन या ऑटो-वेक्टरिंग का उपयोग कर रहे हैं। 15 साल पहले से लिखे गए x86-64 asm आमतौर पर Skylake के लिए आमतौर पर ट्यून नहीं किए जाएंगे। उदाहरण के लिए तुलना करें और शाखा मैक्रो-फ्यूजन वापस मौजूद नहीं था। एक माइक्रोआर्किटेक्चर के लिए हाथ से तैयार किए गए एएसएम के लिए अब क्या इष्टतम है जो अन्य वर्तमान और भविष्य के सीपीयू के लिए इष्टतम नहीं हो सकता है। @ Johnfound के जवाब पर टिप्पणियाँ AMD Bulldozer और Intel Haswell के बीच प्रमुख अंतरों पर चर्चा करती हैं, जो इस कोड पर एक बड़ा प्रभाव डालती हैं। लेकिन सिद्धांत रूप में, g++ -O3 -march=bdver3 और g++ -O3 -march=skylake सही काम करेंगे। ( -march=native ।) Or -mtune=... केवल धुन के लिए, बिना निर्देश के उपयोग के बिना कि अन्य CPU समर्थन नहीं कर सकते।

मेरी भावना यह है कि संकलक को यह बताने के लिए कि वर्तमान सीपीयू आपके लिए अच्छा है, भविष्य के संकलक के लिए समस्या नहीं होनी चाहिए। वे उम्मीद कर रहे हैं कि कोड बदलने के तरीके खोजने में वर्तमान संकलक से बेहतर है, और भविष्य के सीपीयू के लिए काम करने का तरीका खोज सकते हैं। भले ही, भविष्य x86 वर्तमान x86 पर कुछ भी अच्छा नहीं होगा, और भविष्य के संकलक आपके सी स्रोत से डेटा आंदोलन की तरह कुछ लागू करते समय किसी भी विशेष-विशिष्ट नुकसान से बचेंगे, अगर यह कुछ बेहतर नहीं दिखता है।

हाथ से लिखा asm अनुकूलक के लिए एक ब्लैक-बॉक्स है, इसलिए जब एक इनपुट एक संकलन-समय स्थिर बनाता है तो निरंतर-प्रसार काम नहीं करता है। अन्य अनुकूलन भी प्रभावित होते हैं। Asm का उपयोग करने से पहले https://gcc.gnu.org/wiki/DontUseInlineAsm पढ़ें। (और MSVC- स्टाइल इनलाइन asm से बचें: इनपुट / आउटपुट को मेमोरी से गुजरना पड़ता है जो ओवरहेड जोड़ता है ।)

इस स्थिति में : आपके n में एक हस्ताक्षरित प्रकार है, और gcc SAR / SHR / ADD अनुक्रम का उपयोग करता है जो सही गोलाई देता है। (IDIV और अंकगणितीय-शिफ्ट "राउंड" को नकारात्मक इनपुट के लिए अलग-अलग रूप से देखें, एसएआर इनस सेट रेफरी मैनुअल प्रविष्टि देखें )। (IDK अगर gcc ने कोशिश की और यह साबित करने में विफल रहा कि n ऋणात्मक नहीं हो सकता है, या क्या है। हस्ताक्षर-अतिप्रवाह अपरिभाषित व्यवहार है, इसलिए इसे करने में सक्षम होना चाहिए।)

आपको uint64_t n उपयोग करना चाहिए था, इसलिए यह सिर्फ SHR कर सकता है। और इसलिए यह उन प्रणालियों के लिए पोर्टेबल है जहां long केवल 32-बिट (जैसे x86-64 विंडोज) है।

BTW, gcc का अनुकूलित asm आउटपुट बहुत अच्छा लगता है ( unsigned long n का उपयोग करके) : इनर लूप इसे main() में बनाता है 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-घटक LEA (3 चक्र)
  • सेमीोव (हसवेल पर 2 चक्र, ब्रॉडवेल या बाद में 1 सी)।

कुल: पुनरावृत्ति प्रति 5 चक्र, विलंबता अड़चन । आउट-ऑफ-ऑर्डर निष्पादन इसके साथ समानांतर में सब कुछ का ख्याल रखता है (सिद्धांत में: मैंने यह देखने के लिए पूर्ण काउंटरों के साथ परीक्षण नहीं किया है कि क्या यह वास्तव में 5c / iter पर चलता है)।

cmov का cmov इनपुट (TEST द्वारा निर्मित) RAX इनपुट (LEA-> MOV) की तुलना में अधिक तेज़ है, इसलिए यह महत्वपूर्ण पथ पर नहीं है।

इसी तरह, CMV का RDI इनपुट बनाने वाला MOV-> SHR महत्वपूर्ण पथ से दूर है, क्योंकि यह LEA से भी तेज है। IvyBridge पर MOV और बाद में शून्य विलंबता (रजिस्टर-नाम बदलने के समय संभाला)। (यह अभी भी पाइप में एक यूओपी, और एक स्लॉट लेता है, इसलिए यह मुफ़्त नहीं है, बस शून्य विलंबता)। LEA dep श्रृंखला में अतिरिक्त MOV अन्य CPU पर अड़चन का हिस्सा है।

Cmp / jne भी महत्वपूर्ण पथ का हिस्सा नहीं है: यह पाश-चालित नहीं है, क्योंकि नियंत्रण आश्रितों को महत्वपूर्ण पथ पर डेटा निर्भरता के विपरीत शाखा भविष्यवाणी + सट्टा निष्पादन के साथ नियंत्रित किया जाता है।

संकलक की पिटाई

जीसीसी ने यहां बहुत अच्छा काम किया। यह add edx, 1 बजाय inc edx का उपयोग करके एक कोड बाइट को बचा सकता है, क्योंकि किसी को भी P4 और इसकी झूठी-निर्भरता के बारे में परवाह नहीं है आंशिक-ध्वज-संशोधित निर्देशों के लिए।

यह सभी MOV निर्देशों को भी सहेज सकता है, और परीक्षण: SHR CF = बिट को स्थानांतरित कर देता है, इसलिए हम test / cmovz बजाय cmovc उपयोग कर सकते हैं।

 ### 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)

एक अन्य चतुर चाल के लिए @ जॉन्फाउंड का जवाब देखें: SHR के ध्वज परिणाम पर शाखा द्वारा सीएमपी को हटा दें और साथ ही इसे CMOV के लिए उपयोग करें: शून्य केवल अगर n 1 (या 0) के साथ शुरू करना था। (मजेदार तथ्य: एसएचआर विद काउंट! = 1 नेहेलम पर या इससे पहले यदि आप झंडा परिणाम पढ़ते हैं तो स्टाल का कारण बनता है । इस तरह से उन्होंने इसे एकल-यूओपी बनाया है। शिफ्ट-बाय -1 विशेष एन्कोडिंग ठीक है, हालांकि।)

MOV से बचना हसवेल पर लेटेंसी के साथ मदद नहीं करता है ( क्या x86 का MOV वास्तव में "फ्री" हो सकता है? मैं इसे क्यों नहीं दोहरा सकता? )। यह इंटेल प्री-आईवीबी, और एएमडी बुलडोजर-परिवार जैसे सीपीयू पर काफी मदद करता है, जहां एमओवी शून्य-विलंबता नहीं है। संकलक के बर्बाद किए गए MOV निर्देश महत्वपूर्ण पथ को प्रभावित करते हैं। BD का जटिल-LEA और CMOV दोनों निम्न विलंबता (क्रमशः 2c और 1c) हैं, इसलिए यह विलंबता का एक बड़ा अंश है। इसके अलावा, थ्रूपुट बाधाएं एक मुद्दा बन जाती हैं, क्योंकि इसमें केवल दो पूर्णांक ALU पाइप हैं। @ जॉनफाउंड के उत्तर को देखें , जहां उनके पास एक एएमडी सीपीयू से परिणाम हैं।

हसवेल पर भी, यह संस्करण कुछ समय की देरी से बचने में थोड़ी मदद कर सकता है, जहां एक गैर-महत्वपूर्ण यूओपी महत्वपूर्ण पथ पर एक से एक निष्पादन पोर्ट चुराता है, 1 चक्र से निष्पादन में देरी करता है। (इसे संसाधन संघर्ष कहा जाता है)। यह एक रजिस्टर भी बचाता है, जो एक interleaved लूप में समानांतर में कई n मान करने में मदद कर सकता है (नीचे देखें)।

LEA की विलंबता इंटेल SnB- परिवार CPU पर, एड्रेसिंग मोड पर निर्भर करती है । 3c के लिए 3 घटकों ( [base+idx+const] , जो दो अलग-अलग जोड़ता है), लेकिन 2 या उससे कम घटकों (एक ऐड) के साथ केवल 1 सी। कुछ CPU (जैसे Core2) एक चक्र में 3-घटक LEA भी करते हैं, लेकिन SnB- परिवार नहीं करता है। इससे भी बदतर, इंटेल SnB- परिवार अक्षांशों को मानकीकृत करता है, इसलिए 2c उप्स नहीं हैं , अन्यथा 3-घटक LEA केवल बुलडोजर की तरह 2c होगा। (3-घटक एलईए एएमडी पर धीमी है, बस उतना नहीं)।

तो lea rcx, [rax + rax*2] / inc rcx केवल 2c विलंबता है, जो कि lea rcx, [rax + rax*2 + 1] से तेज है lea rcx, [rax + rax*2 + 1] , इंटेल एसएलबी-परिवार CPU पर जैसे हैसवेल। ब्रेक-बीडी पर भी, और कोर 2 पर भी बदतर। इसमें एक अतिरिक्त यूओपी खर्च होता है, जो सामान्य तौर पर 1 सी विलंबता को बचाने के लिए इसके लायक नहीं होता है, लेकिन विलंबता यहां की प्रमुख अड़चन है और अतिरिक्त यूओपी थ्रूपुट को संभालने के लिए हैसवेल के पास एक विस्तृत पाइपलाइन है।

ना तो gcc, icc, और ना ही clang (Godbolt पर) SHR के CF आउटपुट का इस्तेमाल किया, हमेशा AND और TEST का उपयोग किया । सिली कंपाइलर। : P वे जटिल मशीनरी के महान टुकड़े हैं, लेकिन एक चतुर मानव अक्सर उन्हें छोटे स्तर की समस्याओं पर हरा सकता है। (इसके बारे में सोचने के लिए हजारों से लाखों गुना अधिक समय दिया जाता है, निश्चित रूप से! कंपाइलर चीजों को करने के लिए हर संभव तरीके की खोज करने के लिए थकाऊ एल्गोरिदम का उपयोग नहीं करते हैं, क्योंकि बहुत सारे इनलाइन कोड का अनुकूलन करते समय बहुत लंबा समय लगेगा, जो कि है वे सबसे अच्छा करते हैं। वे लक्ष्य माइक्रोआर्किटेक्चर में पाइपलाइन का मॉडल नहीं बनाते हैं, कम से कम IACA या अन्य स्थैतिक-विश्लेषण उपकरणों के समान विस्तार में नहीं हैं; वे सिर्फ कुछ IACA उपयोग करते हैं।)

सरल लूप अनियंत्रित करने में मदद नहीं करेगा ; यह लूप लूप-निर्भर निर्भरता श्रृंखला के विलंब पर लूप ओवरहेड / थ्रूपुट पर नहीं होता है। इसका मतलब यह है कि यह हाइपरथ्रेडिंग (या किसी अन्य प्रकार के एसएमटी) के साथ अच्छी तरह से करेगा, क्योंकि सीपीयू के पास दो थ्रेड्स से निर्देशों को हस्तक्षेप करने के लिए बहुत समय है। इसका मतलब होगा कि लूप को main समानांतर करना, लेकिन यह ठीक है क्योंकि प्रत्येक थ्रेड n मानों की एक सीमा की जांच कर सकता है और परिणामस्वरूप परिणामस्वरूप पूर्णांक की एक जोड़ी का उत्पादन कर सकता है।

एक ही धागे के भीतर हाथ से अंतर्क्रिया करना भी व्यवहार्य हो सकता है । हो सकता है कि समानांतर में संख्याओं की एक जोड़ी के लिए अनुक्रम की गणना करें, क्योंकि हर एक केवल एक युगल रजिस्टर लेता है, और वे सभी एक ही max / maxi अपडेट कर सकते हैं। यह अधिक अनुदेश-स्तरीय समानता बनाता है।

ट्रिक यह तय कर रही है कि जब तक n मूल्यों को शुरू करने की एक और जोड़ी प्राप्त करने से पहले सभी n मान 1 तक पहुंच चुके हैं, तब तक इंतजार करना है या क्या बाहर निकलना है और केवल एक के लिए एक नया स्टार्ट पॉइंट प्राप्त करना है जो रजिस्टरों को छूने के बिना, अंतिम स्थिति तक पहुंच गया है अन्य अनुक्रम। संभवत: प्रत्येक श्रृंखला को उपयोगी डेटा पर काम करना सबसे अच्छा है, अन्यथा आपको इसके काउंटर को सशर्त रूप से बढ़ाना होगा।

आप शायद SSE पैक्ड-तुलना वाले सामान के साथ वेक्टर तत्वों के लिए काउंटर को बढ़ाने के लिए ऐसा कर सकते हैं जहां n अभी तक 1 तक नहीं पहुंचा था। और फिर एक SIMD सशर्त-वृद्धि कार्यान्वयन के समान लंबे समय तक विलंबता को छिपाने के लिए, आपको हवा में n मानों के अधिक वैक्टर रखने की आवश्यकता होगी। शायद केवल 256 बी वेक्टर (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 के साथ एक ही तर्क को लागू करने के अलावा, तर्क को सरल बनाने के तरीके की तलाश करें, या अनावश्यक कार्य से बचें। उदाहरण के लिए दृश्यों के लिए सामान्य अंत का पता लगाने के लिए याद रखें। या इससे भी बेहतर, एक बार में 8 अनुगामी बिट्स देखें (gnasher का उत्तर)

@ ईओएफ बताते हैं कि tzcnt (या tzcnt ) का उपयोग एक चरण में कई n/=2 पुनरावृत्तियों को करने के लिए किया जा सकता है। यह शायद SIMD वेक्टरिंग से बेहतर है, क्योंकि कोई SSE या 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 के बिना Intel SnB- पारिवारिक CPU पर चर-गणना की शिफ्ट धीमी है। 3 उफ़, 2 सी विलंबता। (उनका FLAGS पर इनपुट निर्भरता है क्योंकि गिनती = 0 का अर्थ है कि झंडे अनमॉडिफ़ाइड हैं। वे इसे डेटा निर्भरता के रूप में संभालते हैं, और कई यूओपी लेते हैं क्योंकि एक यूओपी में केवल 2 इनपुट हो सकते हैं (पूर्व-एचएसडब्ल्यू / बीडीडब्ल्यू वैसे भी)। यह वह प्रकार है जो x86 के पागल-सीआईएससी डिजाइन के बारे में शिकायत करने वाले लोग उल्लेख कर रहे हैं। यह x86 सीपीयू की तुलना में धीमा बनाता है अगर वे आईएसए को खरोंच से डिजाइन करते थे, तो भी ज्यादातर इसी तरह से। (यानी यह "x86 टैक्स" का एक हिस्सा है जिसकी लागत गति / शक्ति है।) SHRX / SHLX / SARX (BMI2) एक बड़ी जीत (1 uop / 1c विलंबता) है।

यह महत्वपूर्ण मार्ग पर tzcnt (Hasc और बाद में 3c) भी डालता है, इसलिए यह लूप-आधारित निर्भरता श्रृंखला की कुल विलंबता को काफी लंबा कर देता है। यह एक CMOV के लिए या रजिस्टर n>>1 तैयारी के लिए किसी भी आवश्यकता को हटाता है, हालांकि। @ विड्राक का जवाब कई पुनरावृत्तियों के लिए tzcnt / पारी को हटाकर यह सब खत्म कर देता है, जो कि अत्यधिक प्रभावी है (नीचे देखें)।

हम सुरक्षित रूप से BSF या TZCNT उपयोग कर सकते हैं, क्योंकि n उस बिंदु पर कभी भी शून्य नहीं हो सकता है। TZCNT का मशीन कोड CPU पर BSF के रूप में डिकोड करता है जो BMI1 का समर्थन नहीं करता है। (अर्थहीन उपसर्गों की अनदेखी की जाती है, इसलिए REP BSF BSF के रूप में चलता है)।

TZCNT एएमडी सीपीयू पर बीएसएफ की तुलना में बेहतर प्रदर्शन करता है जो इसका समर्थन करते हैं, इसलिए REP BSF का उपयोग करना एक अच्छा विचार हो सकता है, भले ही आप जेडएफ को सेट करने के बारे में परवाह न करें यदि आउटपुट के बजाय इनपुट शून्य है। कुछ कंपाइलर ऐसा करते हैं, जब आप __builtin_ctzll उपयोग यहां तक ​​कि -mno-bmi साथ भी करते हैं।

वे इंटेल सीपीयू पर समान प्रदर्शन करते हैं, इसलिए बस बाइट को बचाएं यदि यह सब मायने रखता है। इंटेल (पूर्व-स्काईलेक) पर TZCNT में अभी भी बीएसएफ की तरह अनपेक्षित व्यवहार का समर्थन करने के लिए बीएसएफ की तरह ही कथित तौर पर केवल आउटपुट ऑपरेंड पर झूठा-निर्भरता है, इनपुट = 0 के साथ बीएसएफ अपने गंतव्य को बिना अनुमति के छोड़ देता है। इसलिए आपको इसके चारों ओर काम करने की आवश्यकता है जब तक कि केवल स्काईलेक के लिए अनुकूलन न हो, इसलिए अतिरिक्त आरईपी बाइट से कुछ भी हासिल नहीं करना है। (इंटेल अक्सर x86 ISA मैनुअल की आवश्यकता के ऊपर और परे जाता है, व्यापक रूप से उपयोग किए जाने वाले कोड को तोड़ने से बचने के लिए जो कुछ ऐसा नहीं होना चाहिए, या जो कि अप्रचलित रूप से अस्वीकृत है। जैसे कि विंडोज 9x का मानना ​​है कि टीएलबी प्रविष्टियों की कोई सट्टा पूर्वनिर्मित नहीं है , जो सुरक्षित था। जब कोड लिखा गया था, उससे पहले इंटेल ने टीएलबी प्रबंधन नियमों को अपडेट किया था ।)

वैसे भी, हैज़वेल पर LZCNT / TZCNT का POPCNT जैसा ही गलत चित्रण है: इस प्रश्नोत्तर को देखें। यही कारण है कि @ Veedrac के कोड के लिए gcc के asm आउटपुट में, आप इसे xor-zeroing के साथ dep श्रृंखला को तोड़ते हुए देखते हैं, यह उस पर TZCNT के गंतव्य के रूप में उपयोग करने के बारे में है, जब यह dst = src का उपयोग नहीं करता है। चूंकि TZCNT / LZCNT / POPCNT कभी भी अपने गंतव्य को अपरिभाषित या अनधिकृत नहीं छोड़ता है, इंटेल CPU पर आउटपुट पर यह गलत निर्भरता विशुद्ध रूप से एक प्रदर्शन बग / सीमा है। संभवत: यह कुछ ट्रांजिस्टर / शक्ति के लायक है जो उन्हें अन्य यूओपी की तरह व्यवहार करता है जो एक ही निष्पादन इकाई में जाते हैं। एकमात्र सॉफ्टवेयर-दृश्यमान अपसाइड एक और माइक्रोआर्किटेक्टुरल सीमा के साथ बातचीत में है: वे हसवेल पर एक इंडेक्सिंग एड्रेसिंग मोड के साथ एक मेमोरी ऑपरेंड को माइक्रो-फ्यूज कर सकते हैं , लेकिन स्काइलेक पर जहां इंटेल ने LZNNT / TZCNT के लिए झूठी निर्भरता को हटा दिया, वे "अन-लेमिनेट" अनुक्रमित पता मोड जबकि POPCNT अभी भी किसी भी एड्र मोड को माइक्रो-फ्यूज कर सकता है।

अन्य उत्तरों से विचारों / कोड में सुधार:

@ Hidefromkgb के उत्तर में एक अच्छा अवलोकन है कि आप एक 3n + 1 के बाद एक सही बदलाव करने में सक्षम होने की गारंटी देते हैं। आप इसे और भी अधिक कुशलता से गणना कर सकते हैं बस चरणों के बीच की जाँच को छोड़कर। उस उत्तर में asm कार्यान्वयन टूट गया है, हालांकि (यह OF पर निर्भर करता है, जो SHRD के बाद एक गिनती> 1 के साथ अपरिभाषित है), और धीमा: ROR rdi,2 SHRD rdi,rdi,2 तुलना में तेज है SHRD rdi,rdi,2 , और दो CMOV निर्देशों का उपयोग कर रहा है महत्वपूर्ण पथ पर एक अतिरिक्त परीक्षण की तुलना में धीमी है जो समानांतर में चल सकता है।

मैंने tidied / बेहतर C (जो कि बेहतर asm का उत्पादन करने के लिए संकलक का मार्गदर्शन करता है) को रखा, और Godbolt पर asm (C के नीचे की टिप्पणियों में) तेजी से परीक्षण करके काम किया: @ Hidefromkgb के उत्तर में लिंक देखें। (इस उत्तर ने बड़े गॉडबॉल्ट URL से 30k char सीमा को मारा, लेकिन शॉर्टलिंक सड़ सकते हैं और वैसे भी goo.gl के लिए बहुत लंबे थे।)

साथ ही एक बार में एक वर्ण लिखने के बजाय एक स्ट्रिंग में बदलने और एक write() बनाने के लिए आउटपुट-प्रिंटिंग में सुधार हुआ। यह संपूर्ण कार्यक्रम को पूर्ण perf stat ./collatz साथ समय पर प्रभाव को कम करता है perf stat ./collatz (प्रदर्शन काउंटरों को रिकॉर्ड करने के लिए), और मैंने गैर-महत्वपूर्ण asm में से कुछ को perf stat ./collatz

@ Veedrac का कोड

मुझे राइट-शिफ्टिंग से एक बहुत छोटा स्पीडअप मिला जितना हमें पता है कि क्या करना है, और लूप को जारी रखने के लिए जाँच करना है। 7.5 के लिए सीमा = 1e8 से नीचे 7.275s, Core2Duo (मेरोम) पर, 16 के अनियंत्रित कारक के साथ।

Godbolt पर कोड + टिप्पणियाँ। इस संस्करण का उपयोग क्लैंग के साथ न करें; यह डिफर-लूप के साथ मूर्खतापूर्ण कुछ करता है। Tmp काउंटर k का उपयोग करना और फिर बाद में count करने के लिए इसे जोड़ना यह बताता है कि क्लैंग क्या करता है, लेकिन यह थोड़ा gcc को नुकसान पहुंचाता है।

टिप्पणियों में चर्चा देखें: बीएमआई 1 (यानी सेलेरॉन / पेंटियम नहीं) के साथ सीपीयू पर वेडरैक का कोड उत्कृष्ट है


यह दावा करना कि C ++ कंपाइलर एक सक्षम असेंबली कोड की तुलना में अधिक इष्टतम कोड का उत्पादन कर सकता है प्रोग्रामर एक बहुत खराब गलती है। और विशेष रूप से इस मामले में। मानव हमेशा कोड को बेहतर बना सकता है जो संकलक कर सकता है, और यह विशेष स्थिति इस दावे का अच्छा चित्रण है।

आपके द्वारा देखा जा रहा समय अंतर इसलिए है क्योंकि प्रश्न में असेंबली कोड आंतरिक छोरों में इष्टतम से बहुत दूर है।

(नीचे का कोड 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

इस कोड को संकलित करने के लिए, FreshLib की आवश्यकता है।

मेरे परीक्षणों में, (1 GHz AMD A4-1200 प्रोसेसर), उपरोक्त कोड प्रश्न से C ++ कोड की तुलना में लगभग चार गुना तेज है (जब -O0 : 430 एमएस बनाम 1900 एमएस से संकलित), और दो बार से अधिक तेजी से (430 एमएस बनाम 830 एमएस) जब सी ++ कोड -O3 साथ संकलित किया जाता है।

दोनों कार्यक्रमों का आउटपुट समान है: अधिकतम अनुक्रम = 525 पर i = 837799।






x86