Δυναμικά Οριζόμενοι Πίνακες σε C

[dop]

Ναι, αλλά εδώ εκμεταλεύεσαι το γεγονός ότι προσπελάζεις συνέχεια τα ίδια δεδομένα. Δες και το τελευταίο μήνυμά μου. Άλλωστε δεν έχει νόημα να κάνεις προσπέλαση μόνον 1 στοιχείο από έναν πίνακα N στοιχείων - ιδανικά, θα πρέπει να τα προσπελάσεις όλα (και ιδανικά με τυχαίο τρόπο).

 

Επιπλέον, αυτό που μας νοιάζει είναι ο σχετικός χρόνος και όχι ο απόλυτος (όπως και σε όλα τα benchmarks). Μπορείς να καταλάβεις πιο σακουλάκι είναι πιο βαρύ, κοιτώντας την ζυγαριά - εσύ δεν έχεις αλλάξει, άρα όταν η ζυγαριά δείχνει μεγαλύτερο βάρος, τότε αυτό το σακουλάκι είναι πιο βαρύ.

 

Ο gcc δεν προϋπολογίζει θέσεις - είναι τυχαίες αυτές και δεν μπορεί να ξέρει το αποτέλεσμα της rand(). Αυτό που κάνει είναι να πετά τις άχρηστες συνεχείς και ίδιες αναθέσεις (ανέφερα παραπάνω "έχω τυχαίες προσπελάσεις για να αναγκάσω τον compiler να μην αρχίσει τα loop unrollings και να μην ψάχνει για κάποιο access pattern").

[alkisg]

Επειδή αυτή τη στιγμή δεν έχω πρόσβαση σε Linux/gcc, αν θες κάνε μια δοκιμή,

a = a + a[dim-i]

οπότε να προσπελαύνονται όλα τα στοιχεία.

 

Δοκίμασε με

1) No optimization

2) Full optimization

3) Full optimization με τα πάντα να είναι δηλωμένα ως volatile

 

> Ο gcc δεν προϋπολογίζει θέσεις

Στο δικό σου παράδειγμα με τις random προφανώς δεν προϋπολογίζει, πέρα από τη διεύθυνση των δεικτών.

Στο δικό μου προϋπολογίζει, γι' αυτό και η τεράστια διαφορά στην περίπτωση με full optimization/no volatile, αφού τα r1 c1 r2 c2 είναι const. Αλλά ο προϋπολογισμός αυτός είναι που κάνει το παράδειγμα μη ενδεικτικό.

 

Στα benchmarks συνήθως μετράμε καταρχάς μόνο το κομμάτι που ισχυριζόμαστε ότι επιταχύναμε. Όταν έχεις μια επιτάχυνση της τάξης του 112% στην προσπέλαση των arrays, είναι προφανές ότι σε ένα μεγάλο πρόγραμμα δε θα δεις σχεδόν καμία επιτάχυνση, εκτός κι αν πρόκειται για μαθηματικό πρόγραμμα που ασχολείται μόνο με πίνακες. Δηλαδή αν υποθέσουμε ότι τελικά έχω δίκιο και όντως υπάρχει επιτάχυνση στους πίνακες, σε συνηθισμένα προγράμματα (που δε χρησιμοποιούν πίνακες αλλά λίστες από objects, maps κτλ) θα βλέπουμε επιταχύνσεις του στυλ 100.01%, οι οποίες προφανώς είναι ανάξιες λόγου...

[dop]

Άλλαξα τον τρόπο προσπέλασης και τον έκανα:

>
 size_t i1 = i%dim;
 size_t i2 = (i-dim)%dim;
 a[i1][i2] = a[i1][i2] + a[i2][i1];

 

Τα αποτελέσματα: με full optimization (-O3) ο b είναι και πάλι ταχύτερος. Χωρίς optimization ανάλογα με τα κέφια - πότε ο ένας, πότε ο άλλος, με μικρή διαφορά μεταξύ τους. Το volatile δεν άλλαξε κάτι - και μεταξύ μας δεν θα έπρεπε σε αυτήν την περίπτωση.

 

Από όσο βλέπω, το speedup (αν υπάρχει) στα variable length C99 arrays είναι ελάχιστο - και συμβαίνει σπάνια. Ακόμα και το data locality δεν βοηθά πολλές φορές. Επιπλέον, δεν μπορεί να ξεπεράσει κάποιο μέγεθος.

 

Προσωπικά, ίσως και να χρησιμοποιούσα variable length arrays αν επρόκειτο για κάποια μικρή συνάρτηση και μικρά arrays, αν το να κάνω όλη την διαδικασία της malloc() την έβρισκα τόσο βαρετή. Ειδάλλως, πραγματικά δεν αξίζει.

[alkisg]

Το δοκίμασα και σε Visual Studio... χωρίς optimization είναι στα ίδια, 110% πιο γρήγορη η C99, ενώ με optimization ο b τρόπος είναι ταχύτερος.

 

Οπότε όντως δεν αξίζει, οι compilers κάνουν καλή δουλειά με τους pointers. Κι εκτός από αυτά που είπες, το Visual Studio δεν δέχεται καν το dim να είναι μεταβλητή, απαιτεί να είναι σταθερά (δεν ξέρω αν παρέβλεψα κάποιο compiler switch - δεν το πολυέψαξα...).

 

Υ.Γ. με volatile στο b εγώ είδα διαφορά... Υποθέτω ότι στον παραγόμενο assembly κώδικα διαβάζει κάθε φορά τον pointer, ενώ χωρίς volatile τον κρατάει σε register.

[dop]

Το Visual Studio δεν είναι C99 compliant (και ούτε πρόκειται να γίνει από όσο λένε στην MS).

 

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