मुझे दुनिया का सबसे तेज़ कार्यान्वयन कहां मिल सकता है?

Question

मैं यूएस-एन लोकेल, एएससीआईआई, और गैर-वैज्ञानिक नोटेशन के लिए अनुकूलित आईए 32 पर एक बेहद तेज़ एटॉफ() कार्यान्वयन की तलाश में हूं। विंडोज़ मल्टीथ्रेडेड सीआरटी यहां खराब तरीके से गिरती है क्योंकि यह प्रत्येक कॉल पर लोकल परिवर्तनों के लिए isdigit() पर जांच करता है। हमारा वर्तमान सर्वोत्तम पार्ल + टीसीएल के कार्यान्वयन के सर्वोत्तम से लिया गया है, और परिमाण के क्रम से msvcrt.dll के आउटफॉर्म को आउटपुट करता है। मैं बेहतर करना चाहता हूं, लेकिन विचारों से बाहर हूं। बीसीडी से संबंधित x86 निर्देश वादा करने लगते थे, लेकिन मैं इसे perl/tcl सी कोड से बेहतर प्रदर्शन नहीं कर सका। क्या कोई सोर्स वहां से सबसे अच्छा लिंक जोड़ सकता है? गैर x86 असेंबली आधारित समाधान भी स्वागत है।

स्पष्टीकरण प्रारंभिक जवाब पर आधारित: ~ 2 ULP की

अशुद्धियों इस आवेदन के लिए ठीक हैं।
परिवर्तित होने की संख्या छोटे बैचों में नेटवर्क पर एसीआईआई संदेशों में पहुंच जाएगी और हमारे आवेदन को सबसे कम विलंबता में परिवर्तित करने की आवश्यकता है।

Answer 1

आपकी सटीकता आवश्यकता क्या है? यदि आपको वास्तव में इसे "सही" की आवश्यकता है (हमेशा निर्दिष्ट दशमलव पर निकटतम फ़्लोटिंग-पॉइंट मान प्राप्त होता है), तो संभवतः मानक लाइब्रेरी संस्करणों को हरा करना मुश्किल होगा (स्थानीय समर्थन को हटाने के अलावा, जो आपने पहले ही किया है), क्योंकि इसके लिए मनमाने ढंग से सटीक अंकगणित करने की आवश्यकता है। यदि आप एक उल या दो त्रुटि (और उपनिवेशों के लिए उससे अधिक) को सहन करने के इच्छुक हैं, तो क्रूजर द्वारा प्रस्तावित दृष्टिकोण का प्रकार काम कर सकता है और तेजी से हो सकता है, लेकिन यह निश्चित रूप से < 0.5ulp आउटपुट का उत्पादन नहीं करेगा। आप पूर्णांक और fractional भागों को अलग से गणना करने के लिए बेहतर सटीकता-वार करेंगे, और अंत में अंश की गणना करें (उदाहरण के लिए 12345.6789 के लिए, इसे 123 * + 7789/10000.0 के रूप में गणना करें, बजाय 6 * .1 + 7 * .01 + 8 * .001 + 9 * 0.0001) 0.1 एक तर्कहीन बाइनरी अंश है और त्रुटि 0.1^एन की गणना के रूप में तेज़ी से जमा हो जाएगी। यह आपको फ्लोट के बजाए पूर्णांक के साथ गणित के अधिकांश भाग करने देता है।

बीसीडी निर्देशों को हार्डवेयर में (आईआईआरसी) 286 के बाद लागू नहीं किया गया है, और आजकल माइक्रोक्रोड किए गए हैं। वे विशेष रूप से उच्च प्रदर्शन होने की संभावना नहीं है।

Answer 2

मुझे याद है कि हमारे पास एक विनफॉर्म एप्लिकेशन था जो कुछ डेटा इंटरचेंज फ़ाइलों को पार्स करते समय धीरे-धीरे प्रदर्शन करता था, और हमने सभी को सोचा था कि यह डीबी सर्वर थ्रैशिंग था, लेकिन हमारे स्मार्ट बॉस को वास्तव में पता चला कि बाधा उस कॉल में थी जो कनवर्ट कर रही थी पार्स किए गए तार decimals में!

स्ट्रिंग में प्रत्येक अंक (वर्ण) के लिए लूप करना सबसे सरल है, कुल चलते रहें, कुल 10 से गुणा करें और फिर अगले अंक का मान जोड़ें। जब तक आप स्ट्रिंग के अंत तक नहीं पहुंच जाते हैं या आप एक बिंदु का सामना करते हैं तब तक ऐसा करते रहें। यदि आप एक बिंदु का सामना करते हैं, तो पूरे नंबर भाग को आंशिक भाग से अलग करें, फिर एक गुणक है जो प्रत्येक अंक के लिए 10 से स्वयं को विभाजित करता है। जैसे ही आप जाते हैं उन्हें जोड़ते रहें।

उदाहरण: 123,456

कुल = 0 चल रहा है, को जोड़ने 1 (अब यह है 1) कुल = 1 * 10 = 10, जोड़ने 2 (अब यह 12) चल चल कुल = 12 * 10 = 120, 3 जोड़ें (अब यह 123 है) एक डॉट का सामना करना पड़ा, आंशिक भाग गुणक = 0.1 के लिए तैयार करें, 4 से गुणा करें, 0.4 प्राप्त करें, कुल चलाने के लिए जोड़ें, 123.4 गुणक = 0.1/10 = 0.01 बनाता है, 5 से गुणा करें, 0.05 प्राप्त करें कुल मिलाकर, 123.45 मल्टीप्लर = 0.01/10 = 0.001, 6 से गुणा करें, 0.006 प्राप्त करें, कुल चलाने के लिए जोड़ें, 123.456

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

Answer 3

क्या आपने GPU को यह काम करने में विचार किया है? यदि आप स्ट्रिंग को जीपीयू मेमोरी में लोड कर सकते हैं और इसे सब कुछ संसाधित कर सकते हैं तो आपको एक अच्छा एल्गोरिदम मिल सकता है जो आपके प्रोसेसर की तुलना में काफी तेज होगा।

वैकल्पिक रूप से, इसे एक एफपीजीए में करें - एफपीजीए पीसीआई-ई बोर्ड हैं जिनका उपयोग आप मनमाने ढंग से coprocessors बनाने के लिए कर सकते हैं। स्मृति के भाग पर एफपीजीए को इंगित करने के लिए डीएमए का उपयोग करें जिसमें स्ट्रिंग्स की सरणी शामिल है, जिसे आप कनवर्ट करना चाहते हैं और इसे परिवर्तित किए गए मानों को पीछे छोड़कर उनके माध्यम से चलो।

क्या आपने क्वाड कोर प्रोसेसर देखा है? इनमें से अधिकांश मामले में असली टोंटी स्मृति पहुँच वैसे भी है ...

-Adam

Answer 4

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

• यह केवल एकल परिशुद्धता नाव का समर्थन करता है,
• और #INF, आदि जैसे किसी विशेष मूल्यों को स्कैन नहीं करता ...

__forceinline bool float_scan(const wchar_t* wcs, float* val) 
{ 
int hdr=0; 
while (wcs[hdr]==L' ') 
    hdr++; 

int cur=hdr; 

bool negative=false; 
bool has_sign=false; 

if (wcs[cur]==L'+' || wcs[cur]==L'-') 
{ 
    if (wcs[cur]==L'-') 
     negative=true; 
    has_sign=true; 
    cur++; 
} 
else 
    has_sign=false; 

int quot_digs=0; 
int frac_digs=0; 

bool full=false; 

wchar_t period=0; 
int binexp=0; 
int decexp=0; 
unsigned long value=0; 

while (wcs[cur]>=L'0' && wcs[cur]<=L'9') 
{ 
    if (!full) 
    { 
     if (value>=0x19999999 && wcs[cur]-L'0'>5 || value>0x19999999) 
     { 
      full=true; 
      decexp++; 
     } 
     else 
      value=value*10+wcs[cur]-L'0'; 
    } 
    else 
     decexp++; 

    quot_digs++; 
    cur++; 
} 

if (wcs[cur]==L'.' || wcs[cur]==L',') 
{ 
    period=wcs[cur]; 
    cur++; 

    while (wcs[cur]>=L'0' && wcs[cur]<=L'9') 
    { 
     if (!full) 
     { 
      if (value>=0x19999999 && wcs[cur]-L'0'>5 || value>0x19999999) 
       full=true; 
      else 
      { 
       decexp--; 
       value=value*10+wcs[cur]-L'0'; 
      } 
     } 

     frac_digs++; 
     cur++; 
    } 
} 

if (!quot_digs && !frac_digs) 
    return false; 

wchar_t exp_char=0; 

int decexp2=0; // explicit exponent 
bool exp_negative=false; 
bool has_expsign=false; 
int exp_digs=0; 

// even if value is 0, we still need to eat exponent chars 
if (wcs[cur]==L'e' || wcs[cur]==L'E') 
{ 
    exp_char=wcs[cur]; 
    cur++; 

    if (wcs[cur]==L'+' || wcs[cur]==L'-') 
    { 
     has_expsign=true; 
     if (wcs[cur]=='-') 
      exp_negative=true; 
     cur++; 
    } 

    while (wcs[cur]>=L'0' && wcs[cur]<=L'9') 
    { 
     if (decexp2>=0x19999999) 
      return false; 
     decexp2=10*decexp2+wcs[cur]-L'0'; 
     exp_digs++; 
     cur++; 
    } 

    if (exp_negative) 
     decexp-=decexp2; 
    else 
     decexp+=decexp2; 
} 

// end of wcs scan, cur contains value's tail 

if (value) 
{ 
    while (value<=0x19999999) 
    { 
     decexp--; 
     value=value*10; 
    } 

    if (decexp) 
    { 
     // ensure 1bit space for mul by something lower than 2.0 
     if (value&0x80000000) 
     { 
      value>>=1; 
      binexp++; 
     } 

     if (decexp>308 || decexp<-307) 
      return false; 

     // convert exp from 10 to 2 (using FPU) 
     int E; 
     double v=pow(10.0,decexp); 
     double m=frexp(v,&E); 
     m=2.0*m; 
     E--; 
     value=(unsigned long)floor(value*m); 

     binexp+=E; 
    } 

    binexp+=23; // rebase exponent to 23bits of mantisa 


    // so the value is: +/- VALUE * pow(2,BINEXP); 
    // (normalize manthisa to 24bits, update exponent) 
    while (value&0xFE000000) 
    { 
     value>>=1; 
     binexp++; 
    } 
    if (value&0x01000000) 
    { 
     if (value&1) 
      value++; 
     value>>=1; 
     binexp++; 
     if (value&0x01000000) 
     { 
      value>>=1; 
      binexp++; 
     } 
    } 

    while (!(value&0x00800000)) 
    { 
     value<<=1; 
     binexp--; 
    } 

    if (binexp<-127) 
    { 
     // underflow 
     value=0; 
     binexp=-127; 
    } 
    else 
    if (binexp>128) 
     return false; 

    //exclude "implicit 1" 
    value&=0x007FFFFF; 

    // encode exponent 
    unsigned long exponent=(binexp+127)<<23; 
    value |= exponent; 
} 

// encode sign 
unsigned long sign=negative<<31; 
value |= sign; 

if (val) 
{ 
    *(unsigned long*)val=value; 
} 

return true; 
} 

Answer 5

यह कार्यान्वयन मैंने अपने डेस्कटॉप पर 'एटॉफ' के रूप में तेजी से कोडिंग को दो बार समाप्त कर दिया। यह मेरे सिस्टम के मानक gnu 'atof' के साथ 4 सेकंड की तुलना में, 2 सेकंड में 1024 * 1024 * 39 संख्या इनपुट को परिवर्तित करता है। (सेटअप समय सहित और स्मृति प्राप्त करना और वह सब कुछ)।

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

https://github.com/matiu2/yajp

आप के लिए दिलचस्प फ़ाइलें हैं:

:

https://github.com/matiu2/yajp/blob/master/tests/test_number.cpp

https://github.com/matiu2/yajp/blob/master/number.hpp

इसके अलावा, आप राज्य मशीन है कि रूपांतरण करता है में रुचि हो सकती

Answer 6

ऐसा लगता है कि आप (हाथ से) एक राज्य मशीन के लिए कितनी मात्रा में निर्माण करना चाहते हैं जहां प्रत्येक राज्य एनएच इनपुट अंक या एक्सपोनेंट अंक को संभालता है; इस राज्य मशीन को पेड़ की तरह आकार दिया जाएगा (कोई लूप नहीं!)। लक्ष्य जहां भी संभव हो पूर्णांक अंकगणित करना है, और (स्पष्ट रूप से) राज्यों में असाइनमेंट, स्टोर्स और बाद में ऐसे मूल्यों के परीक्षण/परीक्षण से बचने के लिए राज्य चरों ("अग्रणी शून्य", "स्थिति 3 पर दशमलव बिंदु") को याद रखने के लिए है। । केवल इनपुट वर्णों पर सादे पुराने "अगर" कथन के साथ राज्य मशीन को कार्यान्वित करें (इसलिए आपका पेड़ घोंसला वाले आईएसएस का सेट हो जाता है)। इनलाइन बफर वर्णों तक पहुंचता है; आप धीमा करने के लिए getchar पर फ़ंक्शन कॉल नहीं करना चाहते हैं।

अग्रणी शून्य बस दबाया जा सकता है; हास्यास्पद रूप से लंबे समय तक शून्य अनुक्रमों को संभालने के लिए आपको यहां एक लूप की आवश्यकता हो सकती है। पहले nonzero अंक को संचयक शून्य या दस से गुणा किए बिना एकत्र किया जा सकता है। पहले 4-9 nonzero अंक (16 बिट या 32 बिट्स पूर्णांक के लिए) पूर्णांक दस के साथ पूर्णांक गुणा के साथ एकत्र किया जा सकता है (अधिकांश कंपलरों द्वारा कुछ बदलावों और जोड़ों में परिवर्तित)। [शीर्ष पर: शून्य अंकों को किसी भी काम की आवश्यकता नहीं होती है जब तक कि एक गैर-शून्य अंक नहीं मिलता है और फिर एन अनुक्रमिक शून्य के लिए 10^एन गुणा आवश्यक है; आप इसे सब राज्य मशीन में तार कर सकते हैं]। आपकी मशीन के शब्द आकार के आधार पर पहले 4-9 के बाद अंक 32 या 64 बिट गुणों का उपयोग करके एकत्र किए जा सकते हैं। चूंकि आपको सटीकता की परवाह नहीं है, इसलिए आप 32 या 64 बिट्स के लायक होने के बाद अंकों को अनदेखा कर सकते हैं; मुझे लगता है कि जब आप इन नंबरों के साथ वास्तव में अपने आवेदन के साथ वास्तव में क्या करते हैं, तो आप वास्तव में कुछ निश्चित संख्या में nonzero अंक प्राप्त कर सकते हैं जब आप वास्तव में रोक सकते हैं। अंक स्ट्रिंग में पाया गया दशमलव बिंदु बस राज्य मशीन पेड़ में एक शाखा का कारण बनता है। वह शाखा बिंदु के निहित स्थान को जानता है और इसलिए बाद में दस की शक्ति द्वारा उचित तरीके से कैसे स्केल किया जाए। प्रयास के साथ, यदि आप इस कोड के आकार को पसंद नहीं करते हैं तो आप कुछ राज्य मशीन उप-पेड़ों को गठबंधन करने में सक्षम हो सकते हैं।

[शीर्ष पर: पूर्णांक और fractional भागों को अलग (छोटे) पूर्णांक के रूप में रखें। इसके लिए पूर्णांक और अंश भागों को गठबंधन करने के लिए अंत में अतिरिक्त फ़्लोटिंग पॉइंट ऑपरेशन की आवश्यकता होगी, शायद इसके लायक नहीं है]।

[शीर्ष पर: अंक जोड़े के लिए 2 वर्णों को 16 बिट मान में एकत्र करें, 16 बिट मान देखें। यह मेमोरी एक्सेस के लिए व्यापार में रजिस्टरों में गुणा करने से बचाता है, शायद आधुनिक मशीनों पर जीत नहीं]।

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

[शीर्ष पर: आप ptr++ की लागत से बच सकते हैं यदि आप जानते हैं कि संख्या के लिए वर्ण एक बफर में रैखिक रूप से संग्रहीत हैं और बफर सीमा पार नहीं करते हैं। एक वृक्ष शाखा के साथ केटी राज्य में, आप केटी चरित्र को *(start+k) के रूप में एक्सेस कर सकते हैं। एक अच्छा कंपाइलर आमतौर पर एड्रेसिंग मोड में अनुक्रमित ऑफसेट में "... + के" को छुपा सकता है।]

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

मैंने उपर्युक्त लागू नहीं किया है। मैंने लूप के साथ इसके संस्करणों को लागू किया है, वे बहुत तेज़ हैं।