एक लूप को उलट क्यों करता है इसे धीमा कर देता है?

Question

मैं निम्नलिखित कोड है कि सरणी में बिट्स के एक परिपत्र बदलाव करता है:

private static void method1(byte[] bytes) { 
    byte previousByte = bytes[0]; 
    bytes[0] = (byte) (((bytes[0] & 0xff) >> 1) | ((bytes[bytes.length - 1] & 0xff) << 7)); 
    for (int i = 1; i < bytes.length; i++) { 
     byte tmp = bytes[i]; 
     bytes[i] = (byte) (((bytes[i] & 0xff) >> 1) | ((previousByte & 0xff) << 7)); 
     previousByte = tmp; 
    } 
} 

फिर मैंने सोचा कि यह इस तरह पीछे की ओर जाने के लिए आसान और अधिक पठनीय है:

private static void method2(byte[] bytes) { 
    byte lastByte = bytes[bytes.length-1]; 
    for (int i = bytes.length-1; i > 0; i--) { 
     bytes[i] = (byte) (((bytes[i] & 0xff) >> 1) | ((bytes[i-1] & 0xff) << 7)); 
    } 
    bytes[0] = (byte) (((bytes[0] & 0xff) >> 1) | ((lastByte & 0xff) << 7)); 
} 

लेकिन मैंने देखा है कि दूसरा (विधि 2) पहले की तुलना में धीमा है (विधि 1)! मैंने अंतर देखा क्योंकि मैं हजारों बार विधि को बुला रहा हूं। तो मुझे यकीन है कि बनाने के लिए एक परीक्षण किया था और यहां प्रत्येक विधि बुला के 20 परीक्षण से औसत परिणाम है 3000 बार (और बाइट की संख्या 1 लाख है):

method1 average : 4s 572ms 
method2 average : 5s 630ms 

तो मेरे सवाल है: क्यों पहला है दूसरे की तुलना में एक तेज?

यहाँ यकीन है कि मैं कुछ मेरे परीक्षण के साथ गलत नहीं कर रहा हूँ बनाने के लिए परीक्षण कोड है:

import java.math.BigInteger; 

public class BitShiftTests { 

public static void main(String[] args) { 

    int numOfTests = 20; 
    int numberOfShifts = 3000; 
    byte[] numbers = new byte[1000000]; 
    for (int i = 0; i < numbers.length; i++) { 
     numbers[i] = (byte) (i % 255); 
    } 

    System.out.println("Testing method1..."); 
    BigInteger method1Sum = new BigInteger("00000000", 2); 
    for (int i = 1; i <= numOfTests; i++) { 
     long total = 0L; 
     for (int j = 0; j < numberOfShifts; j++) { 
      long startTime = System.nanoTime(); 
      method1(numbers); 
      long endTime = System.nanoTime(); 
      total = total + (endTime - startTime); 
     } 
     method1Sum = method1Sum.add(new BigInteger(Long.toString(total), 10)); 
     System.out.println(String.format("%-2d: %s", i, getTime(total))); 
    } 

    System.out.println("Testing method2..."); 
    BigInteger method2Sum = new BigInteger("00000000", 2); 
    for (int i = 1; i <= numOfTests; i++) { 
     long total = 0L; 
     for (int j = 0; j < numberOfShifts; j++) { 
      long startTime = System.nanoTime(); 
      method2(numbers); 
      long endTime = System.nanoTime(); 
      total = total + (endTime - startTime); 
     } 
     method2Sum = method2Sum.add(new BigInteger(Long.toString(total), 10)); 
     System.out.println(String.format("%-2d: %s", i, getTime(total))); 
    } 

    System.out.println("method1 average : " + getTime(method1Sum.longValue()/numOfTests)); 
    System.out.println("method2 average : " + getTime(method2Sum.longValue()/numOfTests)); 
} 

private static void method1(byte[] bytes) { 
    byte previousByte = bytes[0]; 
    bytes[0] = (byte) (((bytes[0] & 0xff) >> 1) | ((bytes[bytes.length - 1] & 0xff) << 7)); 
    for (int i = 1; i < bytes.length; i++) { 
     byte tmp = bytes[i]; 
     bytes[i] = (byte) (((bytes[i] & 0xff) >> 1) | ((previousByte & 0xff) << 7)); 
     previousByte = tmp; 
    } 
} 

private static void method2(byte[] bytes) { 
    byte lastByte = bytes[bytes.length-1]; 
    for (int i = bytes.length-1; i > 0; i--) { 
     bytes[i] = (byte) (((bytes[i] & 0xff) >> 1) | ((bytes[i-1] & 0xff) << 7)); 
    } 
    bytes[0] = (byte) (((bytes[0] & 0xff) >> 1) | ((lastByte & 0xff) << 7)); 
} 

private static String getTime(long nanoSecs) { 

    int minutes = (int) (nanoSecs/60000000000.0); 
    int seconds = (int) (nanoSecs/1000000000.0) - (minutes * 60); 
    int millisecs = (int) (((nanoSecs/1000000000.0) - (seconds + minutes * 60)) * 1000); 
    int nanosecs = (int) nanoSecs - (millisecs * 1000000000); 

    if (minutes == 0 && seconds == 0 && millisecs == 0) { 
    return nanosecs + "ns"; 
    } 

    if (minutes == 0 && seconds == 0) { 
    return millisecs + "ms"; 
    } 

    if (minutes == 0 && millisecs == 0) { 
    return seconds + "s"; 
    } 

    if (seconds == 0 && millisecs == 0) { 
    return minutes + "min"; 
    } 

    if (minutes == 0) { 
    return seconds + "s " + millisecs + "ms"; 
    } 

    if (seconds == 0) { 
    return minutes + "min " + millisecs + "ms"; 
    } 

    if (millisecs == 0) { 
    return minutes + "min " + seconds + "s"; 
    } 

    return minutes + "min " + seconds + "s " + millisecs + "ms"; 
} 
} 

अद्यतन:

कारण है मैं 2 अलग सूचकांक तक पहुँचने कर रहा हूँ की तरह लग रहा दूसरी विधि में प्रत्येक पाश में, जबकि मैं पहली विधि में केवल 1 अनुक्रमणिका तक पहुंच रहा था। तो लूप को उलटाने के साथ इसका कोई लेना-देना नहीं है।

धन्यवाद @ rm5248 और @Ben, अगर मैं कर सकता हूं तो मैं आपके दोनों उत्तरों का चयन करूंगा, लेकिन मैंने पहले को चुना था।

Answer 1

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

संदर्भ के लिए, मेरी कार्यान्वयन है (मुझे लगता है कि यह एक ही बात करता है, लेकिन यह नहीं हो सकता):

private static void method2(byte[] bytes) { 
    byte prevByte = bytes[bytes.length-1]; 
    for (int i = bytes.length-1; i > 0; i--) { 
     byte tmp = bytes[i]; 
     bytes[i] = (byte) (((bytes[i] & 0xff) >> 1) | ((prevByte & 0xff) << 7)); 
     prevByte = tmp; 
    } 
    bytes[0] = (byte) (((bytes[0] & 0xff) >> 1) | ((bytes[bytes.length-1] & 0xff) << 7)); 
} 

यहाँ थे औसत बार है कि मुझे मिल गया:

method1 average : 6s 555ms 
method2 average : 6s 726ms 

Answer 2

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

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

इसके अलावा, आपका पहला पाश केवल सरणी से एक मान पढ़ता है, और दूसरा एक अस्थायी स्थानीय चर से पढ़ता है जिसे अपग्रेड किया जाएगा। दूसरा संस्करण सरणी से दो अलग-अलग तत्व पढ़ता है।

निश्चित रूप से पता लगाने के लिए, आपको दोनों मामलों के लिए जेआईटी द्वारा उत्पादित मशीन कोड के अलग-अलग हिस्सों को देखना चाहिए।