जावा में गुणा करने और विभाजित करने से तेजी से बिट्स को स्थानांतरित कर रहा है? नेट?

Question

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

Answer 1

अधिकांश कंपाइलर आज संचालन को स्थानांतरित करने के लिए दो-शक्तियों द्वारा गुणा या विभाजित करने से अधिक कुछ करेंगे। ऑप्टिमाइज़ करते समय, कई कंपाइलर एक संकलन समय स्थिरता के साथ एक गुणा या विभाजन को अनुकूलित कर सकते हैं, भले ही यह 2 की शक्ति न हो। प्रायः एक गुणा या विभाजन को बदलावों और जोड़ों की एक श्रृंखला में विघटित किया जा सकता है, और यदि संचालन की श्रृंखला तेजी से हो जाएगी गुणा या विभाजन से, संकलक इसका उपयोग करेंगे।

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

• http://www.hackersdelight.org/

भी देखें एक चर्चा:

Henry Warren's book, Hacker's Delight, इस विषय पर जानकारी का खजाना है, जो भी साथी वेबसाइट पर काफी अच्छी तरह से कवर किया जाता है है :

• Reading assembly code

वैसे भी, यह सभी कंपाइलर को माइक्रो-ऑप्टिमाइज़ेशन के कठिन विवरणों का ख्याल रखने की अनुमति देने के लिए उबलता है। अपने स्वयं के बदलावों को संकलक से बाहर करने के बाद से सालों रहे हैं।

Answer 2

आप लगभग निश्चित रूप से शिफ्ट ऑपरेशन के लिए दो गुणा ऑप्टिकल ऑप्टिमाइज़ेशन पर निर्भर कर सकते हैं। यह पहला अनुकूलन है कि कंपाइलर निर्माण के छात्र सीखेंगे। :)

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

Answer 3

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

Answer 4

मुझे आश्चर्य है क्योंकि मैंने अभी इस कोड को लिखा है और महसूस किया है कि एक द्वारा स्थानांतरित करना वास्तव में 2 से गुणा करने से धीमा है!

(संपादित करें: माइकल मायर्स 'सुझाव के बाद बह निकला को रोकने के लिए कोड बदल गया है, लेकिन परिणाम एक ही हैं यहाँ क्या गलत है?)

import java.util.Date; 

public class Test { 
    public static void main(String[] args) { 
     Date before = new Date(); 
     for (int j = 1; j < 50000000; j++) { 
      int a = 1 ; 
      for (int i = 0; i< 10; i++){ 
       a *=2; 
      } 
     } 
     Date after = new Date(); 
     System.out.println("Multiplying " + (after.getTime()-before.getTime()) + " milliseconds"); 
     before = new Date(); 
     for (int j = 1; j < 50000000; j++) { 
      int a = 1 ; 
      for (int i = 0; i< 10; i++){ 
       a = a << 1; 
      } 
     } 
     after = new Date(); 
     System.out.println("Shifting " + (after.getTime()-before.getTime()) + " milliseconds"); 
    } 
} 

परिणाम हैं:

गुणा 639 मिलीसेकेंड
718 मिलीसेकेंड

Answer 5

शिफ्टिंग मैं पूछना होगा "क्या एक क्या आप ऐसा कर रहे हैं इससे कोई फर्क नहीं पड़ता? "। पहले पठनीयता और रखरखाव के लिए अपना कोड तैयार करें। संभावित गुणा करने वाले छंदों को मानक गुणा करने की संभावना एक प्रदर्शन अंतर को बहुत कम कर देगी।

Answer 6

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

Answer 7

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

आप कभी भी किसी को यह नहीं सुनेंगे कि "मेरा आवेदन बहुत धीमा था, फिर मैंने x * 2 को x << 1 के साथ यादृच्छिक रूप से बदलना शुरू कर दिया और सब ठीक हो गया!" प्रदर्शन की समस्याएं आमतौर पर परिमाण कम काम के क्रम को करने का तरीका ढूंढकर हल की जाती हैं, न कि एक ही काम को 1% तेज करने का तरीका ढूंढकर।

Answer 8

इन मामलों में मनुष्य गलत हैं।

99% जब वे दूसरे (और भविष्य के सभी) कंपाइलर्स का अनुमान लगाने का प्रयास करते हैं।
99.9% जब वे एक ही समय में आधुनिक (और सभी भविष्य) जेआईटी अनुमान लगाते हैं।
99.9 99% जब वे दूसरे अनुमानित आधुनिक (और भविष्य के) CPU अनुकूलन का अनुमान लगाते हैं।

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

Answer 9

यह हार्डवेयर निर्भर है। अगर हम माइक्रो नियंत्रक या i386 बात कर रहे हैं, तो स्थानांतरण तेजी से हो सकता है, लेकिन कई उत्तर राज्य के रूप में, आपका कंपाइलर आमतौर पर आपके लिए अनुकूलन करेगा।

आधुनिक (पेंटियम प्रो और उससे परे) हार्डवेयर पर पाइपलाइनिंग यह पूरी तरह से अप्रासंगिक बनाती है और पीटा पथ से भटकने का मतलब है कि आमतौर पर आप लाभ प्राप्त करने के मुकाबले बहुत अधिक अनुकूलन खो देते हैं।

माइक्रो अनुकूलन न केवल आपके समय का अपशिष्ट है, बल्कि उन्हें सही होने में भी बहुत मुश्किल है।

Answer 10

मैंने परीक्षण किए गए कंप्यूटरों पर, पूर्ण ऑपरेशन 4 से 10 गुना धीमी अन्य परिचालनों की तुलना में धीमे हैं।

जब कंपाइलर 2 के गुणकों द्वारा डिवीजनों को प्रतिस्थापित कर सकते हैं और आपको कोई फर्क नहीं पड़ता है, तो 2 के गुणकों द्वारा डिवीजन काफी धीमे नहीं होते हैं।

उदाहरण के लिए, मेरे पास 255 तक कई सारे डिवीजनों के साथ एक (ग्राफिक्स) प्रोग्राम है। असल में मेरी गणना है:

r = (((top.R - bottom.R) * alpha + (bottom.R * 255)) * 0x8081) >> 23; 

मैं सुनिश्चित कर सकते हैं कि यह मेरे पिछले गणना की तुलना में बहुत तेजी से होता है:

r = ((top.R - bottom.R) * alpha + (bottom.R * 255))/255; 

इसलिए कोई, compilers अनुकूलन के सभी गुर नहीं कर सकते।

Answer 11

ध्यान दें कि स्थानांतरण और विभाजन (जावा में, निश्चित रूप से) नकारात्मक, विषम संख्याओं के लिए अलग-अलग परिणाम देगा।

int a = -7; 
System.out.println("Shift: "+(a >> 1)); 
System.out.println("Div: "+(a/2)); 

प्रिंटों:

Shift: -4 
Div: -3 

के बाद से जावा किसी भी अहस्ताक्षरित संख्या इस अनुकूलन करने के लिए यह एक जावा के लिए संभव वास्तव में नहीं है नहीं है।

Answer 12

यह Savvas Dalkitsis से किए गए बेंचमार्क का विश्लेषण है। हालांकि इस परीक्षण जाँच करता है बिट पर गुणन की गति स्थानांतरण, इस्तेमाल किया मूल्यों, ही नहीं हैं सी # जो मूल्यों को प्रदर्शित करता है) में नीचे दिए गए कोड की जाँच

for (int i = 0, j = 1, k = 1; i < 10; i++) 
{ 
    j = j * 2; 
    k <<= 2; 
    Console.WriteLine("{0} {1}", j, k); 
} 

मूल्यों सी # में दिखाया गया है साथ Savvas Dalkitsis उदाहरण के बराबर कोड होगा

public static void Main(String[] args) 
    { 
     for (int i = 0, j = 1, k = 1; i < 10; i++) 
     { 
      j = j * 2; k <<= 2; 
      Console.WriteLine("{0} {1}", j, k); 
     } 
     Console.WriteLine("-----------------------------------------------"); 


     DateTime before = DateTime.Now; 
     for (int j = 1; j < 500000000; j++) 
     { 
      int a = 1; 
      for (int i = 0; i < 10; i++) a *= 2; 
     } 
     DateTime after = DateTime.Now; 

     Console.WriteLine("Multiplying " + (after - before).ToString() + " milliseconds"); 

     before = DateTime.Now; 
     for (int j = 1; j < 500000000; j++) 
     { 
      int a = 1; 
      for (int i = 0; i < 10; i++) a = a << 1; 
     } 
     after = DateTime.Now; 
     Console.WriteLine("Shifting " + (after - before).ToString() + " milliseconds"); 
     Console.ReadKey(); 
    } 

Answer 13

हो this microbenchmark के परिणामों के अनुसार, स्थानांतरण विभाजित (Oracle जावा 1.7.0_72) के रूप में दो बार के रूप में तेजी से है।