Μετροπρόγραμμα σε java τρέχει πιο γρήγορα σε παλαιότερους επεξεργαστές!

[gdp77]

Λοιπόν ζητώ βοήθεια από έμπειρους προγραμματιστές που μπορούν να μου εξηγήσουν το εξής παράδοξο.

 

Έχω φτιάξει ένα απλό προγραμματάκι σε java για να υπολογίζει τον χρόνο που χρειάζεται το σύστημα για να βρει τον εκατοστό χιλιοστό πρώτο αριθμό (100.000). Το παράδοξο είναι ότι προκύπτει ότι όσο "παλαιότερος" ο επεξεργαστής, τόσο πιο γρήγορα τρέχει. Δηλαδή, το τρέχω στον i7 920 @ 4.0GHz και μου βγάζει 44". Αφού έκανα αναβάθμιση, το έτρεξα στον Ryzen 1600 (3.2GHz), ένας επεξεργαστής 7 χρόνια μεταγενέστερος και μου βγάζει 66"!!! Σίγουρα δεν είναι πρόβλημα cpu γιατί σε όλα τα άλλα μετροπρογράμματα έχω 20% καλύτερο single thread performance και 100% multi thread. ( Το εν λόγω πρόγραμμα είναι single thread). Προσπαθώντας να διερευνήσω το θέμα, το στέλνω σε έναν φίλο μου με έναν q9550(core 2 quad @ 3.8GHz) και το βγάζει σε 42", δηλαδή ταχύτερα από όλα τα συστήματα!!!! Στην αρχή σκεφτόμουν ότι πιθανόν να είναι πολύ καλύτεροι οι intel στις modulo πράξεις. Όταν όμως και ο core 2 quad αποδείχτηκε πιο γρήγορος, τότε πραγματικά δεν είχα τι να υποθέσω...

 

Προφανώς κάποιο κομμάτι του κώδικα έχει τεράστιο penalty hit σε καινούρια συστήματα, αλλά ποιο είναι αυτό και γιατί;

 

Ακολουθεί ο κώδικας με σχολιασμό:

 

Spoiler

public class Main {

    public static void main(String[] args) throws InterruptedException {

        int i=3,counter=2, remainder=0; // Η αναζήτηση ξεκινάει από το αριθμό 3 και ο counter είναι ίσος με 2 εφόσον οι αριθμοί 2 και 3 είναι πρώτοι και δεν θα υπολογιστούν
        Long startTime = System.nanoTime(); // Η μεταβλητή startTime μας δίνει τον χρόνο έναρξης της μέτρησης
        while (counter!=100000){            // Βρόχος while μέχρι την εύρεση του εκατοστού χιλιοστού πρώτου αριθμού
            i+=2;                           // αυξάνουμε το i κατά 2, εφόσον οι ζυγοί αριθμοί μετά το 2 ΔΕΝ είναι πρώτοι. Θα ελέγχουμε δηλαδή μόνο τους μονούς
            for (int j=3;j<i/2+2;j+=2){     // Βρόχος for όπου θα διαιρούμε το i (πιαθανός πρώτος) με ΌΛΟΥΣ τους μονούς αριθμούς μέχρι το μισό του (j), εφόσον ένας φυσικός διαιρείται ακριβώς μόνο με τους αριθμούς που είναι μικρότεροι από το μισό του (πλην του ευαυτού του)
                remainder = i%j;            // Η μεταβλητή remainder παίρνει την τιμή του υπόλοιπου της διαίρεσης i/j
                if (remainder==0)           // Αν το remainder είναι 0, τότε βρέθηκε διαιρέτης, άρα ο αριθμός δεν είναι πρώτος, οπότε break
                    break;
            }
            if (remainder!=0) {             // Αν το remainder είναι != 0, τότε ο υπό εξέταση αριθμός είναι πρώτος
                counter += 1;               // Εφόσον βρέθηκε πρώτος αριθμός αυξάνουμε κατά 1 τον counter
                if (counter % 1000 == 0)    // Αν ο counter διαιρείται ακριβώς με 1000, τότε τυπώνουμε τον counter για να έχει γνώση ο χρήστης πόσοι πρώτοι υπολογίστηκαν ανά 1000
                    System.out.println(counter + " πρώτοι αριθμοί υπολογίστηκαν");

            }
        }
        System.out.println("\nΟ εκατοστός χιλιοστός πρώτος αριθμός είναι ο "+i);
        Long endTime = System.nanoTime();       // Παίρνουμε μέτρηση χρόνου στο τέλος της διαδικασίας
        double duration = ((double)endTime-(double)startTime)/1000000000;       // Διαιρούμε με 1.000.000.000 για να μετατρέψουμε τη διαφορά τελικής και αρχίκής μέτρησης σε sec
        System.out.println("Χρόνος υπολογισμού = " +duration + " sec");
    }
}

 

Έχω υλοποιήσει πολύ πιο αποδοτικούς και γρήγορους αλγόριθμους για υπολογισμό πρώτων, απλά για τις ανάγκες πειραματισμών ήθελα να χρησιμοποιήσω αυτόν. Το θέμα είναι γιατί τρέχει πιο γρήγορα σε παλαιότερα μηχανήματα οεο;

[defiant]

Ποια versrion του JRE χρησιμοποιείς? Ίδιο λειτουργικό? Ξέρω ότι το nanoTime σε WindowsXP έχει θέματα.

Πιστεύω γνωρίζεις ότι στην Java ο bytecode μετατρέπεται σε native at runtime καθώς τρέχει δηλαδή με optimisation που κάνει ο JIT.

Λογικά, αν δεν είναι θέμα ακρίβειας του nanotime το οποίο βασίζεται σε os specific timers, κάποιες βελτιώσεις γίνονται στο παλιό σύστημα που δεν τα κάνει στο νέο, το οποίο είναι παράξενο.

Τώρα μόνο με profiling θα το δεις. Βεβαιώσου πρώτα ότι έχεις ακριβώς το ίδιο JRE.

 

Τρέχοντας το στον ίδιο υπολογιστή(core i5 3210M, Windows 10 64bit) έχω διαφορετικά αποτελέσματα ανάλογα του JRE:

 

32bit jdk1.8.0_91: 105 sec

32 bit jdk1.8.0_101: 107 sec

64 bit jdk1.8.0_101: 52 sec

64bit openjdk-1.8.0.141-1:  52 sec

 

[akis_z80]

o 920 είναι πιο γρήγορος σε single thread ???

[gdp77]

Ευχαριστώ για την εμπεριστατωμένη απάντηση. 

 

Λοιπόν στον i7 και στον ryzen οι δοκιμές έγιναν με jdk1.8.0_152 64bit και σε linux και σε windows 10 64 bit με ίδια αποτελέσματα. Δυστυχώς δεν έχω πλέον τον i7 για να δοκιμάσω με άλλα jdk, αλλά στον ryzen δοκίμασα και τα εξής jdk με ίδια αποτελέσματα:

java-8-openjdk-amd64

java-9-oracle / 64bit

jdk1.8.0_152 64bit 

 

Δεν ξέρω με ποιο JDK δοκίμασε ο φίλος μου με τον Q9550, αλλά είναι σίγουρο ότι δουλεύει windows 7 64bit και λογικά δοκίμασε με το jdk 1.8.0

 

Εγώ δηλαδή δεν κατάφερα να πάρω διαφορετικά αποτελέσματα όπως εσύ (δεν δοκίμασα 32bit jdk, αλλά μάλλον δεν έχει νόημα βλέποντας τους χρόνους σου).

 

Να υποθέσω ότι δεν γίνονται optimizations στον κώδικα για ryzen και πρέπει να περιμένω για νέο jdk που να τους υποστηρίζει;

 

Θα δοκιμάσω σήμερα αργότερα να μεταφέρω τον κώδικα σε c# να δω τι αποτελέσματα θα πάρω εκεί. (δοκίμασα ήδη να τρέξω το ίδιο αλγόριθμο σε python με απογοητευτικά αποτελέσματα χεχε)

 

ΥΓ με το nanotime δεν υπήρξε κανένα θέμα ούτε σε linux ούτε σε windows, καθώς μέτρησα χρόνους και με ρολόι χειρός και επαληθεύονταν σε κάθε περίπτωση και σε windows και σε linux.

3 minutes ago, akis_z80 said:

o 920 είναι πιο γρήγορος σε single thread ???

Για τον συγκεκριμένο κώδικα, αποδείχτηκε ο Q9550 πιο γρήγορος....

 

Μάλλον όμως όπως λέει και ο @defiant είναι θέμα jdk

14 hours ago, defiant said:

Τώρα μόνο με profiling θα το δεις.

Δεν ξέρω καν τι είναι αυτό. Κανά link να διαβάσω, για να το ψάξω περαιτέρω; 

[gdp77]

Λοιπόν το έκανα port σε c# και πήρα με τον ryzen αυτούς τους χρόνους:

 

build 32 bit: 2'44" --> ~164sec

build 64 bit 1'05" --> ~ 65 sec

 

Δηλαδή πήρα σε c# ακριβώς ίδιο χρόνο (64bit) με αυτόν που είχα με java. Οπότε καταλήγω ότι  οι ryzen είτε α) έχουν τεράστιο penalty hit με modulus operations ή β) και τo java jdk και ο c# compiler του VS δεν είναι optimized για τη νέα πλατφόρμα. 

 

Αν υπάρχει καμιά άλλη ιδέα, ευχαρίστως να την υλοποιήσω.

[defiant]

πριν 6 ώρες, το μέλος gdp77 έγραψε:

Να υποθέσω ότι δεν γίνονται optimizations στον κώδικα για ryzen και πρέπει να περιμένω για νέο jdk που να τους υποστηρίζει;

 

Αυτό δεν παίζει να γίνει. Είναι θέμα του ryzen.Αν δεις εδώ -> (https://videocardz.com/65825/first-amd-ryzen-7-1700x-benchmarks-are-here)

Είναι ο δεύτερος χειρότερος στο prime number benchmark.

 

Γενικά όλοι οι επεξεργαστές ζορίζονται στο modulus operations. Υπάρχουν μερικοί τρόποι βελτιώσεις αλλά αυτό που ξέρω εγώ είναι μόνο για πολλαπλάσια του 2. Αντί για i % j είναι πιο γρήγορο να κάνεις i & ( j - 1 ).  Στο συγκεκριμένο πρόγραμμα θα τα κάνει χειρότερα επειδή κάνει modulus και με ζυγούς και με περιττούς αριθμούς.

πριν 3 ώρες, το μέλος gdp77 έγραψε:

 

Αν υπάρχει καμιά άλλη ιδέα, ευχαρίστως να την υλοποιήσω.

 

Αν αντί για  for (int j=3;j<i/2+2;j+=2)  το κάνεις for (int j=3;j<Math.sqrt(i);j+=2) θα δεις μεγάλη βελτίωση. 0.5 sec total time σε μένα.

Τωρα αν εννοεις για τον Ryzen δοκιμασε καποιο official prime numbers benchmark.

[gdp77]

Ok το έχω δει αυτό που αναφέρεις για βελτιστοποιημένο mod. Έχω ούτως ή άλλως αλγόριθμο που βρίσκει τους ίδιους πρώτους (100.000) σε 0.3 sec. Απλά ψαχνόμουν με το γιατί είχα τέτοια απόδοση με τον ryzen και μάλλον η απάντηση είναι ότι σε modulus εντολές δέχονται πολύ μεγαλύτερο penalty hit σε σχέση με τους Intel.

 

Sent from my Redmi Note 2 using Tapatalk

 

 

 

[tragikos]

Για την ιστορία σε i7-6700 στα 3,8GHz με Windows 10 και 64bit JDK 1.8.0_144:

Ο εκατοστός χιλιοστός πρώτος αριθμός είναι ο 1299709
Χρόνος υπολογισμού = 36.749157032 sec

Πάντως μία τέτοια εφαρμογή φυσικά επηρεάζεται και από τον χρονισμό της CPU που στον Ryzen είναι χαμηλότερα από τα άλλα που δοκίμασες.

[gdp77]

18 minutes ago, tragikos said:

Για την ιστορία σε i7-6700 στα 3,8GHz με Windows 10 και 64bit JDK 1.8.0_144:

Ο εκατοστός χιλιοστός πρώτος αριθμός είναι ο 1299709
Χρόνος υπολογισμού = 36.749157032 sec

Πάντως μία τέτοια εφαρμογή φυσικά επηρεάζεται και από τον χρονισμό της CPU που στον Ryzen είναι χαμηλότερα από τα άλλα που δοκίμασες.

 

Σίγουρα εφόσον είναι ξεκάθαρα single thread και ipc bound. Όταν κάνω oc θα έχω καλύτερο χρόνο, αλλά σε κάθε περίπτωση προκύπτει ότι οι ryzen έχουν πολύ χειρότερη απόδοση σε modulus σε σχέση με intel.

[gdp77]

Use the force Luke....!

 

Το έκανα multi-threaded (10 threads) και το έριξα στα 11.6 sec :-)