optimization σε C

[defacer]

Δεν καταλαβαίνω τι νόημα έχει να λες "παιδιά πώς θα κάνω optimize την πίεση στα ελαστικά για μεγαλύτερη απόδοση, αλλά τη μηχανή δε θέλω να την πειράξω".

 

Αλλά το βασικότερο όλων: απ' ότι βλέπω προσπαθείς να κάνεις "optimization by intuition". Ξέχασέ το και μη προσπαθείς καν. Αν ήσουν expert (εννοείται βαθειά γνώση του ARM που στοχεύεις όπως και του compiler) θα είχες μια μη-μηδαμινή πιθανότητα (εννοώ, πολύ μικρή αλλά ποτέ δεν ξέρεις) να κάνεις κάτι σωστό. Τώρα δεν έχεις απολύτως καμία.

 

https://en.wikipedia.org/wiki/Program_optimization#Quotes

[παπι]

gon1332 έχεις δίκιο, δεν είχα διαπιστώσει οτι και το i θα αλλάζει μέσα στην επανάληψη

Το optimization γίνεται για ένα προσομοιωτή επεξεργαστή ARM, δεν ξέρω τι δυανατότητες έχει ο compiler του.

και τον κώδικα ανάγνωσης εικόνας τον πήραμε έτοιμο από την σχολή, προτιμώ να τον αφήσω έτσι όπως είναι

Σας ευχαριστώ όλους για τις απαντήσεις σας, gon1332 το post σου για το optimization ήταν πολύ ενδιαφέρον

Unrolling κανεις οταν στο λουπ εχεις πραγματα που τρεχουν πιο γρηγορα απο τα read της μνημης. Το fgetc σιγουρα θελει πολυ χρονο σε σχεση με το read στη μνημη, αρα και το unrolling που κανεις, δεν εχει κανα effect. Μια fread θα σου δωσει αρκετα μεγαλο μπουστ σε σχεση με αυτο που εχεις.

 

Αν να το θες ετσι, οκ. Απλα να ξερεις, πως αυτο δειχνει πως ξερεις τι ειναι το unrolling αλλα δεν ξερεις που να το βαλεις.

[gon1332]

Μεγάλες αλήθειες:

 

"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified"

Donald Knuth

 

"Bottlenecks occur in surprising places, so don't try to second guess and put in a speed hack until you have proven that's where the bottleneck is."

Rob Pike

 

και μία ακόμη που θυμήθηκα (δε θυμάμαι ποιος το είχε πει) πάει κάπως έτσι:

"The biggest optimization is to make the code work correctly."

Όπως λένε και οι σοφοί...

 

PROFILING

[M2000]

Σε συστήματα με πολυεπεξεργασία όπως τα σύγχρονα το πόσο γρήγορα τρέχει κάτι εξαρτάται και από (μαζί με άλλα δηλαδή που δεν γράφω και ίσως δεν τα γνωρίζω):

1) από το τι άλλο τρέχει!

2) αν χρειάζεται να τραβάει η CPU μνήμη έξω από την CACHE (π.χ. η δυαδική αναζήτηση μπορεί να χειροτερέψει σε σχέση με την σειριακή αν έχουμε τέτοιο ζήτημα)

3) από το πότε ανανεώνει την οθόνη. Αυτό το είδα στην Vb6. Αν αφήσεις το σύστημα να ανανεώνει την οθόνη την έβαψες! Κάθε εγγραφή στην οθόνη προκαλεί "απαίτηση" για ανανέωση. Πως θα αποφασίσεις πότε πρέπει να γίνει η ανανέωση; Αν γίνει για κάθε εγγραφή τότε ο χρόνος ανανέωσης είναι χαμένος για τη εφαρμογή! Κάποιος θα υποστηρίξει ίσως ότι γίνεται αυτόματα! Ασφαλώς. Και για το λόγο αυτό σέρνονται οι εφαρμογές! Μόλις μάθεις το τρόπο αλλάζουν τα πράγματα!

[gon1332]

Σε συστήματα με πολυεπεξεργασία όπως τα σύγχρονα το πόσο γρήγορα τρέχει κάτι εξαρτάται και από (μαζί με άλλα δηλαδή που δεν γράφω και ίσως δεν τα γνωρίζω):

1) από το τι άλλο τρέχει!

2) αν χρειάζεται να τραβάει η CPU μνήμη έξω από την CACHE (π.χ. η δυαδική αναζήτηση μπορεί να χειροτερέψει σε σχέση με την σειριακή αν έχουμε τέτοιο ζήτημα)

3) από το πότε ανανεώνει την οθόνη. Αυτό το είδα στην Vb6. Αν αφήσεις το σύστημα να ανανεώνει την οθόνη την έβαψες! Κάθε εγγραφή στην οθόνη προκαλεί "απαίτηση" για ανανέωση. Πως θα αποφασίσεις πότε πρέπει να γίνει η ανανέωση; Αν γίνει για κάθε εγγραφή τότε ο χρόνος ανανέωσης είναι χαμένος για τη εφαρμογή! Κάποιος θα υποστηρίξει ίσως ότι γίνεται αυτόματα! Ασφαλώς. Και για το λόγο αυτό σέρνονται οι εφαρμογές! Μόλις μάθεις το τρόπο αλλάζουν τα πράγματα!

 

1) Το λειτουργικό τι κάνει;

2) Η δυαδική σε σχέση με σειριακή; Δε νομίζω να έχεις τόσο μεγάλο effect στις caches που να σε κάνει να αλλάξεις τόσο πολύ αλγόριθμο. Και πάλι όμως. Στη δυαδική πας και κόβεις τον αρχικό σε μισά κομμάτια κ.ο.κ. Κάθε νέο κομμάτι που θα πάρεις θα είναι στην cache, πράγμα που σημαίνει πως και τα υποψήφια μέσα σε αυτό θα είναι (αναλόγως και το cache line). Οπότε όχι. Οι τεράστιοι μονοδιάστατοι (οι οποίοι θα δημιουργούσαν κάποια misses αν επιλέγονταν το δεξιό κομμάτι) μικραίνουν γρήγορα (κόβεις διά δύο). Αν θυμηθώ θα το μετρήσω αύριο και θα σου πω (με perf). Το πρώτο πράγμα που κοιτάμε είναι η αρχιτεκτονική του συστήματος, ύστερα οι αλγόριθμοι και μετά τα υπόλοιπα.

3) Όσο για αυτό δε ξέρω. Δεν έχω ασχοληθεί με τέτοιες εφαρμογές (GUI κλπ). Αλλά πιστεύω πως εξαρτάται από το framework που θα χρησιμοποιήσεις. Αυτό πολύ πιθανόν να χρησιμοποιείς καμμιά openGL πχ από κάτω. Θέμα υλοποίησης που δε μας νοιάζει είναι αυτό. Μπορεί να λέω και βλακείες.

[M2000]

Στο 1...Πραγματικά με τα Virtual Box έχει πολύ πλάκα η κατάσταση..διότι τρέχει το έλα να δεις..ποιος μοιράζει τι...Στο δικό μου μηχάνημα τρέχουν 64bit ubuntu με 32 Bit 7 και Xp ταυτόχρονα (καμία φορά τα έχω και τα δυο windows όχι πάντα, αλλά μπορεί τα ubuntu να φτιάχνουν κανένα βίντεο...εκτός από το να παίζουν μουσική, και μάλιστα ίσως τραβάνε βίντεο αυτό που παίζει στα windows...Έχω λοιπόν μετρήσει με δικά μου benchmark την απόδοση συγκεκριμένων προγραμμάτων. Υπάρχει φυσικά καθυστέρηση!

Στο ερώτημά σου το λειτουργικό ότι θέλουμε κάνει..όχι ότι θέλει!

 

Στο 2 (εδώ το διάβασα...δεν μου ήρθε έμπνευση)

https://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues

Δες παραπάνω ότι σε ορισμένες περιπτώσεις δεν ισχύει ότι η δυαδική είναι γρηγορότερη από τη σειριακή!

 

 

Στο 3...δεν έχω χρησιμοποιήσει framework, το έχω φτιάξει!

[gon1332]

1) Δεν-καταλαβαίνω-τι-λες. Προφανώς και θα κάνει ό,τι του πούμε σε επίπεδο χρήστη. Σε επίπεδο scheduling όμως ποιος έχει το λόγο;

2) Μέγεθος πίνακα από `1<<27` long longs ή αλλιώς 1GB. Ταξινομημένος και για τις δύο περιπτώσεις. Σύγκριση μόνο των μεθόδων για απομόνωση συμπεριφοράς cache. Και για να έχει νόημα όλο αυτό, ψάχνω για ένα στοιχείο, το οποίο δεν υπάρχει (χείριστη περίπτωση) και είναι το μεγαλύτερο όλων, ώστε να επιλέγει η δυαδική δεξιότερα κομμάτια, κι έτσι να έχω μεγαλύτερη πιθανότητα cache miss.

 

Ακολουθεί spoiler:

Αυτός ο μεγάλος αριθμός δεν επηρεάζει καθόλου το τελικό αποτέλεσμα (σε σχέση με κάποιον μικρό που δεν υπάρχει στον πίνακα), λόγω γρήγορης σύγκλισης φαντάζομαι, που θα αναφέρω παρακάτω.

 

 

 

Χαρακτηριστικά επεξεργαστή (3 GB RAM):

 

 

➜  ~  lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
Thread(s) per core:    2
Core(s) per socket:    4
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 42
Stepping:              7
CPU MHz:               800.000
BogoMIPS:              3990.95
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              6144K
NUMA node0 CPU(s):     0-7
 

 

 

 

Επίσης τρέχω 10 φορές την κάθε μέθοδο και ο χρόνος που βλέπετε είναι ο τελικός χρόνος διά 10:

 

 

➜  ~  gcc -Wall -Wextra -std=c99 -O3 -DBIN_SEARCH -o search_algorithms search_algorithms.c
➜  ~  ./search_algorithms                                                                 
BINARY SEARCH:
	found = no
	time  = 3.000000e-07 sec
➜  ~  gcc -Wall -Wextra -std=c99 -O3 -DLIN_SEARCH -o search_algorithms search_algorithms.c
➜  ~  ./search_algorithms                                                                 
LINEAR SEARCH:
	found = no
	time  = 1.196509e-01 sec

 

 

 

Ορίστε και τα αποτελέσματα από linux performance counters:

 

 

➜  ~  perf stat -e L1-dcache-loads -e L1-dcache-load-misses -e LLC-loads -e LLC-load-misses -e dTLB-load-misses -e branch-loads -e branch-load-misses ./search_algorithms
LINEAR SEARCH:
	found = no
	time  = 1.228673e-01 sec

 Performance counter stats for './search_algorithms':

       14872874106 L1-dcache-loads                                              [66,67%]
         490484640 L1-dcache-load-misses     #    3,30% of all L1-dcache hits   [66,67%]
         221232104 LLC-loads                                                    [66,66%]
   <not supported> LLC-load-misses         
           3349793 dTLB-load-misses                                             [66,72%]
       17402742146 branch-loads                                                 [66,70%]
          25101251 branch-load-misses                                           [66,63%]

      11,996357670 seconds time elapsed

➜  ~  perf stat -e L1-dcache-loads -e L1-dcache-load-misses -e LLC-loads -e LLC-load-misses -e dTLB-load-misses -e branch-loads -e branch-load-misses ./search_algorithms
BINARY SEARCH:
	found = no
	time  = 2.000000e-07 sec

 Performance counter stats for './search_algorithms':

       13670545228 L1-dcache-loads                                              [66,68%]
         328981846 L1-dcache-load-misses     #    2,41% of all L1-dcache hits   [66,63%]
          36624119 LLC-loads                                                    [66,68%]
   <not supported> LLC-load-misses         
           2168134 dTLB-load-misses                                             [66,71%]
       14806737801 branch-loads                                                 [66,65%]
          25126602 branch-load-misses                                           [66,68%]

      10,706313165 seconds time elapsed

 

 

 

Φαίνεται να έχεις περισσότερα L1 misses στο linear. Πολύ χοντρικά αυτό το εξηγώ γιατί όπως προείπα, με τη δυαδική αναζήτηση, το πρόβλημα μικραίνει γρήγορα (η γρήγορη σύγκλιση που έλεγα), οπότε και δεν είναι τόσο εκτεθειμένο στο έλεος των περιορισμών των caches. Παρατήρησε πόσο λιγότερα L3 loads (LLC) έχεις στο binary search. Πολύ καλή τοπικότητα. Θα ήταν πολύ ενδιαφέρον να μπορούσαμε να δούμε πόσα L3 cache misses θα είχαμε. Δηλαδή πόσες φορές θα έπρεπε να πληρώσουμε το penalty να φέρουμε δεδομένα από τη DRAM.

 

Ορίστε και ο κώδικας που τέσταρα. Πιστεύω δεν έκανα καμμιά πατάτα. Ελέγξτε μία κι εσείς. Επίσης θα δείτε πως δεν έχει και πολύ νόημα η κλήση της qsort (λόγω της αρχικοποίησης που κάνω). Δε μας πειράζει βέβαια.

 

ΚΩΔΙΚΑΣ σε τιμή ευκαιρίας!!!

 

 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <unistd.h> // ssize_t

#define SIZE        (1 << 27)
#define BENCH_SIZE  (10UL)

#define ITEM (SIZE+1)  // The array consists only of positive numbers

void *array_alloc     (size_t type_size, size_t quantity);
void  array_free      (long long *array);
void  array_init      (long long *array, size_t size);
void  array_print     (const long long *array, size_t size);
bool  array_lin_search(const long long *array, size_t size, long long item);
bool  array_bin_search(const long long *array, size_t size, long long item);

int compare(const void *a, const void *
{
    return *(int*)a - *(int*)b;
}

int main(void)
{
    long long *array = array_alloc(sizeof(long long), SIZE);

    array_init(array, SIZE);

    // We only care about the performance of each algorithm without the sorting
    // overhead. It for sure is important, but not in our case, in which we
    // want to observe cache behaviour.
    qsort(array, SIZE, sizeof(long long), compare);

    bool found;

#ifdef BIN_SEARCH
    /* BINARY SEARCH */
    clock_t start = clock();
    for (size_t i = 0; i < BENCH_SIZE; i++)
        found = array_bin_search(array, SIZE, ITEM);
    clock_t end = clock();

    printf("BINARY SEARCH:\n");
    printf("\tfound = %s\n", found ? "yes" : "no");
    printf("\ttime  = %e sec\n", (((double) end - start) / CLOCKS_PER_SEC) / BENCH_SIZE);
#else
    /* LINEAR SEARCH */
    clock_t start = clock();
    for (size_t i = 0; i < BENCH_SIZE; i++)
        found = array_lin_search(array, SIZE, ITEM);
    clock_t end = clock();

    printf("LINEAR SEARCH:\n");
    printf("\tfound = %s\n", found ? "yes" : "no");
    printf("\ttime  = %e sec\n", (((double) end - start) / CLOCKS_PER_SEC) / BENCH_SIZE);
#endif

    array_free(array);

    return 0;
}

void *array_alloc(size_t type_size, size_t quantity)
{
    long long *array = malloc(quantity * type_size);
    if (!array) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }
    return array;
}

void array_free(long long *array)
{
    free(array);
}

void array_init(long long *array, size_t size)
{
    for (size_t i = 0; i < size; i++) {
        //srand(i);
        array[i] = i; //- (rand() % (i + 1));
    }
}

void array_print(const long long *array, size_t size)
{
    for (size_t i = 0; i < size; i++)
        printf("%Ld ", array[i]);
    putchar('\n');
}

bool array_lin_search(const long long *array, size_t size, long long item)
{
    size_t i;
    for (i = 0; (i < size) && (array[i] != item); i++) {
        ;
    }
    return i != size;
}

bool array_bin_search(const long long *array, size_t size, long long item)
{
    ssize_t imin = 0;
    ssize_t imax = size - 1;

    while (imin <= imax) {

        ssize_t imid = imin + ((imax - imin) / 2);

        if      (array[imid] > item) imax = imid - 1;
        else if (array[imid] < item) imin = imid + 1;
        else    return true;
    }

    return false;
}
 

 

 

 

Compile κάνετε έτσι:

 

 

# Binary search
gcc -Wall -Wextra -std=c99 -O3 -DBIN_SEARCH -o search_algorithms search_algorithms.c

# Linear search
gcc -Wall -Wextra -std=c99 -O3 -LBIN_SEARCH -o search_algorithms search_algorithms.c 

 

 

 

3) Στα λόγια μου έρχεσαι. Μιλούσα για χρήστες GUI frameworks. Όχι για δημιουργούς, προφανώς.

 

 

EDIT: Όποιος μπορέσει ας ελέγξει και μέση περίπτωση. Μπορεί να το κάνω κι εγώ αν δεν έχει δείξει κάποιος κάτι. Ως μέση περίπτωση θεωρείται να έχεις log_2(N)-1 searches.

 

EDIT: Επίσης, αν κάποιος έχει χρόνο ας υλοποιήσει και το external searching (δηλαδή να βρίσκονται οι πίνακες στο δίσκο) ώστε να δούμε κι αυτό που λέει ο Μ2000.

Επεξ/σία 23 Δεκεμβρίου 2015 από gon1332

[παπι]

Tl;dr

 

Like επειδή βλέπω κώδικας. Κάτι το οποίο είναι υπό εξαφάνιση στο παρών νήμα.

[M2000]

Εντυπωσιάστηκα...Πάντως δεν πάω κόντρα με αυτούς που γράφουν τα Wiki (δεν ξέρουμε ποιοι είναι και πόσο ατάκα μας ξεφτιλίζουν)...

Για τους αλγόριθμους δεν τους τσεκάρω τώρα, διότι δεν ξέρουμε τι γίνεται σε πραγματική κατάσταση, εδώ έχεις κάνει αναζήτηση όπως να είναι ...Αν η σειριακή ζήταγε το έκτο στοιχείο θα το είχε βρει...πριν αλλάξει η δυαδική "σελίδα"..

 

Στο κείμενο πάντως στο wiki λέει ότι όταν το άνοιγμα πέσει κάτω από 16 πάμε σε σειριακή! Πάντως για φαντάσου να έχεις ένα δίσκο και να πηδάς από κομμάτι σε κομμάτι για να δεις ένα νούμερο! Η πράξη από τη θεωρία διαφέρει..πολλές φορές!

 

 

(δεν εξηγώ το 1 που δεν κατανοείς, απλά σκέψου πόσοι εξωτερικοί παράγοντες...αλλάζουν το σχέδιο του λειτουργικού και πόσες επιλογές έχει ο TaskManager).

 

Δες εδώ μια πραγματική κατάσταση:

Site: Εδώ είχα δημοσιεύσει μαζί με αλγόριθμους άλλων και έναν δικό μου που έπαιρνε τα βιβλία της βίβλου και σε 1.3 δευτερόλεπτα έβγαζε 792367 λέξεις με μοναδικές 13231 και το πόσες φορές η κάθε μια. Και αυτό γίνεται με ταυτόχρονη δυαδική αναζήτηση και ταξινόμηση και χωρίς να μετακινηθούν οι λέξεις, ούτε για τη σύγκριση! (ασφαλώς το έχω βάλει στην Μ2000, ανοίγεις τον διορθωτή πετάς ένα κείμενο ας πούμε 30000 γραμμές και με ένα πάτημα του F9 σου λέει πόσες λέξεις έχει! (μέσα από την γλώσσα μπορείς να πάρεις και τις μοναδικές λέξεις).

 

δοκίμασα 30641 γραμμές vb στο διορθωτή της Μ2000. Με το πάτημα του κουμπιού παίρνεις το αποτέλεσμα...100300 λέξεις (δεν μετράει αριθμούς ή σύμβολα).

[gon1332]

Δεν πήγα κόντρα κανέναν από Wiki. Απλά δοκίμασα κάτι γρήγορα για να δω συμπεριφορά σε caches. Η δυαδική φαίνεται να κερδίζει κι εκεί (έστω και για λίγο) - δες L1 & L3 misses. Όπως έγραψα στο edit, αυτό που λέει στο wiki θα μπορούσαμε να το δούμε καλύτερα αν κάποιος έκανε τις αναζητήσεις σε πίνακες που βρίσκονται στο δίσκο. Εκεί το wiki αναφέρει πως θα είχαμε πιθανόν πρόβλημα στα πρώτα "κοψίματα", όπου θα συμβούν κάποια page faults, επειδή δε μπορούν να χωρέσουν αρκετά μεγάλα κομμάτια του πίνακα ώστε να καλύψουμε δεξιότερες επιλογές (λογικό μου ακούγεται).

 

Μετά για πίνακες 64 στοιχείων και κάτω που λέει δοκίμασε εσύ να μετρήσεις και να συγκρίνεις και πες μας τι βλέπεις. Πάρε τον κώδικα που έδωσα και άλλαξε απλά πάνω πάνω το SIZE. Αν βλέπεις ότι η γραμμική αναζήτηση υπερνικά τη δυαδική, τότε μάλλον έχεις ξεμείνει με μηχάνημα που έχει κανένα pentium 3 ξέρω 'γω. Αν το τρέξεις σε VM, τότε δώσε επίσης και configuration των cores αν γίνεται (Caches, TLB).

 

Επίσης μπορείς να γράψεις ένα πρόγραμμα για να συγκρίνεις (single threaded) τις αναζητήσεις που να διαβάζει πίνακες από δίσκο και να αναφέρεις χρόνους (αν γίνεται όχι σε VB - δε βγάζω άκρη | Άντε και σε M2000 αν δε μπορείς σε κάποια C-like ή python-ruby); Να μη μείνουμε στη φαντασία. Όχι τίποτα άλλο.

 

Όσο για το λειτουργικό που έλεγες.. Έχω την εντύπωση πως θες να μου εξηγήσεις πως όσες πιο πολλές διεργασίες ανοίγουμε, τόσο πιο πολύ αργούν να εξυπηρετηθούν. No shit Sherlock. Όταν λες αλλάζουν το σχέδιο του λειτουργικού; Γιατί δε μου εξηγείς; Δεν είμαι χαζός, θα καταλάβω. Μήπως μιλάς για το preemption; Και πάλι αυτό, το λειτουργικό το καθορίζει. (Καλά εντάξει, μπορείς να παίξεις κι εσύ με τις προτεραιότητες αλλάζοντας το nice στο linux), αλλά που το πας;

[M2000]

Δεν είσαι χαζός, αυτό είναι το βέβαιο, αλλά βιάζεσαι να βγάλεις συμπεράσματα, ειδικά εκείνα που γενικεύουν.

Τις σκέψεις σου για την χρήση της cache και όλων των τρικ των επεξεργαστών...(αν το δεις σε βάθος το θέμα, ακόμα και η γλώσσα μηχανής δεν είναι το τελικό επίπεδο, υπάρχει και ο μικροκώδικας κάτω από αυτήν και εκεί κάθε εταιρεία παραγωγής cpu κάνει τα δικά της κόλπα, πάντα στο πνεύμα το εμπορικό, δηλαδή με δόσεις ανά εκδόσεις..) τις θέτεις πάνω στο πλαίσιο έχω ένα μηχάνημα σύγχρονο και δοκιμάζω ένα πρόγραμμα. Εγώ αναφέρομαι στο έχω ένα περιβάλλον που γίνεται χαμός, πιθανόν να είναι εικονικό, και έχουμε το προς έλεγχο πρόγραμμα. Κάποιες βελτιστοποιήσεις στο κώδικα, όπως λέγαμε κάποτε ότι το να ξοδεύεις μνήμη κερδίζεις σε ταχύτητα...πχ αν έχεις πίνακα ημιτόνων πιο γρήγορα βρίσκεις ημίτονα, τώρα λόγω διευθέτησης της cache, αλλά και των μεγάλων απαιτήσεων σε μνήμη, δες βίντεο, ίσως είναι ακατάλληλες.

Ασφαλώς όταν θες να δεις το ζήτημα του optimization κάνεις παραδοχές. Αλλά το απόλυτο θα ήταν ένα λειτουργικό με μια εφαρμογή μόνο. Τότε οι συνθήκες είναι ελεγμένες και πάντα επαναλαμβανόμενες.

 

Κάνε ένα απλό τεστ. Δες πόσο χρόνο κάνει το πρόγραμμά σου αν τρέχει δέκα φορές...ταυτόχρονα, και φυσικά μείωσε το πίνακα στα 100MB.

Τα τεστ γίνονται με επαναλήψεις,τη μεγαλύτερη και τη μικρότερη στις τιμές τις αφαιρούμε, και μετά βγάζουμε μέσο όρο. Έστω αριθμός επαναλήψεων 1002. Θα παίξει για μια φορά και για δέκα ταυτόχρονα. Το ερώτημα είναι ... οι δέκα ταυτόχρονα θέλουν επακριβώς δεκαπλάσια χρόνο ή παραπάνω...

Μετά αξιολογούμε το αποτέλεσμα.

Δες το λοιπόν και τα λέμε.

[gon1332]

Δεν είσαι χαζός, αυτό είναι το βέβαιο, αλλά βιάζεσαι να βγάλεις συμπεράσματα, ειδικά εκείνα που γενικεύουν.

Τις σκέψεις σου για την χρήση της cache και όλων των τρικ των επεξεργαστών...(αν το δεις σε βάθος το θέμα, ακόμα και η γλώσσα μηχανής δεν είναι το τελικό επίπεδο, υπάρχει και ο μικροκώδικας κάτω από αυτήν και εκεί κάθε εταιρεία παραγωγής cpu κάνει τα δικά της κόλπα, πάντα στο πνεύμα το εμπορικό, δηλαδή με δόσεις ανά εκδόσεις..) τις θέτεις πάνω στο πλαίσιο έχω ένα μηχάνημα σύγχρονο και δοκιμάζω ένα πρόγραμμα. Εγώ αναφέρομαι στο έχω ένα περιβάλλον που γίνεται χαμός, πιθανόν να είναι εικονικό, και έχουμε το προς έλεγχο πρόγραμμα. Κάποιες βελτιστοποιήσεις στο κώδικα, όπως λέγαμε κάποτε ότι το να ξοδεύεις μνήμη κερδίζεις σε ταχύτητα...πχ αν έχεις πίνακα ημιτόνων πιο γρήγορα βρίσκεις ημίτονα, τώρα λόγω διευθέτησης της cache, αλλά και των μεγάλων απαιτήσεων σε μνήμη, δες βίντεο, ίσως είναι ακατάλληλες.

Ασφαλώς όταν θες να δεις το ζήτημα του optimization κάνεις παραδοχές. Αλλά το απόλυτο θα ήταν ένα λειτουργικό με μια εφαρμογή μόνο. Τότε οι συνθήκες είναι ελεγμένες και πάντα επαναλαμβανόμενες.

 

Κάνε ένα απλό τεστ. Δες πόσο χρόνο κάνει το πρόγραμμά σου αν τρέχει δέκα φορές...ταυτόχρονα, και φυσικά μείωσε το πίνακα στα 100MB.

Τα τεστ γίνονται με επαναλήψεις,τη μεγαλύτερη και τη μικρότερη στις τιμές τις αφαιρούμε, και μετά βγάζουμε μέσο όρο. Έστω αριθμός επαναλήψεων 1002. Θα παίξει για μια φορά και για δέκα ταυτόχρονα. Το ερώτημα είναι ... οι δέκα ταυτόχρονα θέλουν επακριβώς δεκαπλάσια χρόνο ή παραπάνω...

Μετά αξιολογούμε το αποτέλεσμα.

Δες το λοιπόν και τα λέμε.

 

Προφανώς και όταν πάμε να βελτιστοποιήσουμε κάτι, πάμε πρώτα και κάνουμε profiling. Οπότε βασιζόμαστε σε γεγονότα. Και το perf που χρησιμοποιήσα εγώ, είναι κάτι γρήγορο. Αν ήταν να μετρήσω σωστά θα το έκανα χρησιμοποιώντας το vtune (αν κι εδώ ξέρω τι μου δημιουργεί το πρόβλημα) ας πούμε ή αν είχα χρόνο θα χρησιμοποιούσα το PAPI για να μετρήσω συγκεκριμένα τα σημεία που θέλω. Όπως και να το κάνουμε ο κανόνας είναι (στις περισσότερες περιπτώσεις), ότι ξεκινάμε με τον καλύτερο αλγόριθμο, ανά περίπτωση (παραλληλισμός ή όχι). Έτσι, έχουμε βελτιστοποιήσει το πρόβλημά μας χωρίς καν να ασχοληθούμε με το σύστημα που είμαστε. Μέτα έρχονται όλα τα άλλα.

 

Εσύ μου λες (νομίζω κατάλαβα τι μου λες), ότι ένας μεγάλος παράγοντας στην απόδοση του προγράμματος είναι το λειτουργικό που τρέχουμε και το φόρτο που έχει σε διαφορετικές χρονικές στιγμές. Αυτό όμως δεν είναι στο χέρι του προγραμματιστή εφαρμογών. Δε μπορεί να πείσει το λειτουργικό να τρέχει μόνο αυτή τη διεργασία (το είχα ψάξει παλιότερα ) και είναι απολύτως λογικό αυτό. Στο τεστ που μου είπες να δοκιμάσω, ξέρω πως η κάθε διεργασία θα κάνει περισσότερο χρόνο να τελειώσει αν τρέχουν πολλές μαζί. Σε αυτή την περόπτωση όμως, εκτός από το χρόνο εκτέλεσης θες και την τυπική απόκλιση. Αν είναι τρελή, τότε πρέπει να βρεις τι φταίει. Στην περίπτωσή μας ξέρω πως θα φταίει το γεγονός ότι το τρέχω πολλές φορές μαζί κι έτσι ο χρόνος είναι στο έλεος του μηχανισμού δρομολόγισης του λειτουργικού. Δεν είναι όμως θέμα του αλγορίθμου. Οπότε το ερώτημά μου είναι το εξής: Τι μετράς εσύ όταν θες να βρεις απόδοση ενός προγράμματος; Έχει νόημα να τρέχω πολλές φορές την εφαρμογή παράλληλα για να βγάλω συμπεράσματα για την ίδια;

[M2000]

Άλλο πράγμα να μετράς θεωρητικά και να το θεωρείς μέτρηση σε Κ.Σ. (κανονικές συνθήκες) και άλλο σε Π.Σ. (πραγματικές συνθήκες).

Δηλαδή το πρόβλημα που έθεσα δεν θα μας πείσει ποιος αλγόριθμος είναι σε Κ.Σ. πιο γρήγορος. Αυτό μας το λέει και η πολυπλοκότητα, το μέγεθος εισόδου, και ότι αν δεν ψάχνουμε τα πρώτα στοιχεία τότε το πιθανότερο είναι να κερδίσει η δυαδική αναζήτηση. Πρόσεξες..το πιθανότερο. Σε πραγματική συνθήκη αν ζητάμε πάντα τα πρώτα στοιχεία...τότε η σειριακή θα πετάει! Η πραγματική συνθήκη βάζει και το στήσιμο μέσα της εισόδου. 

Στο πρόβλημα όμως θέλω να δω αν υπάρχει μποτιλιάρισμα με την εναλλαγή διαδικασιών και την χρήση της cache. Διότι η cache δεν είναι αγκαζέ σε κάθε διαδικασία. Αν υπάρχουν περισσότερες τότε περιορίζεται ή μπορεί να χάνεται εντελώς! Να έχουμε δηλαδή άμεση ροή από τη μνήμη (ή πρακτικά άμεση). Έτσι ενώ ο αλγόριθμος έχει σε Κ.Σ τα εύσημα...σε Π.Σ να έχει θέμα. Ασφαλώς οι Κ.Σ. είναι κάτι που στηρίζεται σε παραδοχές. (χωρίς να πολιτικολογώ...εκεί πάνω προγραμματιστικά μπορεί να παίχτηκε η αστοχία του συστήματος εκλογών της ΝΔ). Μόλις πάμε σε πραγματικές συνθήκες έχουμε την αντίληψη του τι συμβαίνει στη πράξη! Πως τα δεδομένα κάνουν σαλάτα το σύστημα. Εγώ το έθεσα και πιο προχωρημένα. Π.χ. ότι τρέχει το σύστημα σε VM. οπότε ο επεξεργαστής και η Cache του έχει γίνει σαλάτα...(εγώ έχω εξαπύρηνο τον FX 6100 αλλά δεν λέει τίποτα αυτό, μέτριος είναι, και όλα τα όρια ξεπερνιούνται).

Στο βασικό ερώτημα...τι μετράμε για την απόδοση..η απάντηση δεν είναι ...το βάζω σε ένα τοπ μηχάνημα και βγάζω το χρόνο με ένα πακέτο δεδομένων...αλλά το ελέγχω σε ένα χώρο εργασίας. Ακόμα και στη βιομηχανία τίποτα δεν αγοράζεται -μηχανισμός, μηχανή, εξοπλισμός- χωρίς Test Run, δηλαδή να τρέξει σε συνθήκες εργασίας. Τότε μπορείς να έχεις την σωστή μέτρηση (και πάλι όχι για ώρες/φάσεις αιχμής).

 

Έτσι για να επανέλθουμε....Optimization σε C καλύτερο από μεταγλωττιστή μπορεί να γίνει αν γνωρίζουμε τις συνθήκες που θα τρέξει το πρόγραμμα!

Το "σαλάτα" που "κοπανάω" εδώ είναι ο κατακερματισμός της cache

[gon1332]

Οι caches γίνονται invalidate με κάθε context switch (αναλόγως και το σύστημα πάντα). Οπότε έχω την εντύπωση πως πάνω κάτω τα ίδια αποτελέσματα θα είχαμε και σε Π.Σ.. Βέβαια αυτό θέλει έλεγχο. Από την άλλη τα αποτελέσματα εξαρτώνται καθαρά από το ίδιο το λειτουργικό. Καταλαβαίνω τί θέλεις να πεις. Απλά όλη αυτή η διαδικασία δε ξέρω κατά πόσο ακολουθείται για εφαρμογές desktop. Ας πούμε εσύ έφτιαξες την M2000. Τι έκανες για να διασφαλίσεις ότι θα δουλέψει τουλάχιστον ανεκτά σε ένα σύστημα που έχει φτάσει στα όριά του από μεγάλος πλήθος διεργασιών;

 

Αυτό που ξέρω, είναι ότι όταν είναι να βελτιστοποιήσεις μία εφαρμογή (HPC) και είναι να την τρέξεις σε κάποιο super-computer, σε ενδιαφέρει πάρα πολύ να γνωρίζεις την αρχιτεκτονική του τάδε συστήματος. Θα το πληρώσεις για να τρέξεις κάτι πάνω του. Θα τρέξει μόνο η εφαρμογή σου και τίποτα άλλο και θες να το αξιοποιήσεις στο έπακρο, ώστε να τελειώσεις και πιο νωρίς.

 

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

 

Δεν είμαι και πολύ γνώστης του τί συμβαίνει γενικά από εδώ και πέρα, οπότε κάνω αρκετές υποθέσεις.

[M2000]

Στη γλώσσα Μ2000 έχω βάλει την Αναλυτής που λαμβάνει μια ένδειξη από ένα ρολόι των Windows (που το έχει γι΄αυτήν την δουλειά) και μετά από μια εντολή π.χ. ένα οποιοδήποτε μικρο loop διαβάζω την Φόρτος (που δίνει τιμή σε nanosecond). Δηλαδή το εργαλείο το δίνω στον προγραμματιστή.

Στο περιβάλλον της γλώσσας έχω βάλει πολλά! Ένα για παράδειγμα είναι να αποκλείσω το WindowsGhosting στο πρόγραμμα που ρίχνει το λειτουργικό αν "πάρει γραμμή" ότι μαζεύονται μηνύματα...και δεν επεξεργάζονται!

(Αυτό γίνεται γιατί επεμβαίνω στο μήνυμα του Repaint για να έχω δικές μου ανανεώσεις στις φόρμες)

Αν βλέπεις μήνυμα "Αυτή η εφαρμογή δεν ανταποκρίνεται" και είναι δική σου και ξέρεις ότι κάνει κάποια επεξεργασία...τότε θες το φάρμακο που το καταργεί (έκανα καιρό να το βρω..στα Xp δεν υπήρχε τέτοιο θέμα αλλά την έχουν την ρουτίνα στο User32)

Private Declare Sub DisableProcessWindowsGhosting Lib "user32" ()

 

Για να μην γράφω πολλά, έχω τρια επίπεδα ταχύτητας σε σχέση με το πως ελέγχεται το τρέξιμο του κώδικα! (εξ ορισμού είναι το μεσαίο). Επιπλέον η γλώσσα χρησιμοποιεί το Kernel για να ενεργοποιεί ένα εσωτερικό Threading pool (φτιαγμένο με πρόγραμμα) και έτσι πετυχαίνει η γλώσσα σε ένα πραγματικό Thread να τρέχει νήματα του κώδικά της! Αν λοιπόν κάποιος χρησιμοποιεί νήματα στη Μ2000 τότε ο κώδικας μπορεί να έχει πολλά κενά...που δεν κάνει τίποτα! Και φαίνεται στο CPU % πόσο φόρτο πιάνει.Δες όμως ότι έτσι έχουμε μια ασύγχρονη λειτουργία. Εδώ η βελτιστοποίηση δεν έχει να κάνει με την ταχύτητα αλλά με το σπάσιμο των διεργασιών για πιο ομαλά αποτελέσματα. Σε περίπτωση που ο χρόνος δεν βγαίνει για κάθε νήμα, τότε κλέβει από τα άλλα! Πως γίνεται όμως να μην "εξαφανίσει" τα άλλα; Εδώ έχω απάντηση αλλά για άλλη συζήτηση!

 

Ο επόμενος βαθμός "πολυεπεξεργασίας" είναι να αναταλλάσουν δεδομένα εφαρμογές σε Μ2000 μέσω σωληνώσεων και "ειδικών" νημάτων που λαμβάνουν ασύγχρονα δεδομένα. Εδώ οι χρόνοι και τα δεδομένα που διαβιβάζονται έχουν άλλους περιορισμούς! Οπότε αν κάποιος θέλει να είναι συνεπής πρέπει να ρυθμίσει επί τόπου (το πότε είναι "περασμένος" ο χρόνος, timeout error)

Όλα αυτά δεν έχουν σχέση με την Cache γιατί για την M2000 αυτό είναι υπερβολικό για να το κοιτάξει!

 

Όμως η βελτιστοιποίηση και εδώ είναι το ζουμί δεν είναι κυρίως σε επίπεδο αλγορίθμου. Στο προγραμματισμό δεν είναι το ζουμί στον αλγόριθμο αλλά στις επιλογές..από τη μεταβλητή μέχρι τη ρύθμιση του περιβάλλοντος που θα τρέξει το πρόγραμμα! Δεν γίνεσαι μηχανικός αυτοκινήτων με μια μηχανή που δείχνει ότι δουλεύει για ένα λεπτό! Στη πράξη τι κάνει;

 

Π.χ. όταν θες να διαχειριστείς ένα κείμενο 10000 παραγράφων θα το βάλεις σε ένα αλφαριθμητικό; Όχι γιατί για κάθε εισαγωγή θα έχεις θέμα μετακίνησης. Θα το σπάσεις σε παραγράφους! Αυτή είναι η πρώτη επιλογή για βελτιστοποίηση! Είδες πουθενά κώδικα; Ο κώδικας θα έρθει μετά..Πρώτα οι επιλογές!