Κώδικας C για ταξινόμηση απλά συνδεδεμένης λίστας με αλλαγή των pointers

[dop]

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

 

Με μία λέξη: εμπειρία. Δεν υπάρχει από όσο ξέρω ένας οδηγός βελτιστοποίησης για τα πάντα. Ένας έμπειρος προγραμματιστής μπορεί να σου γράψει κώδικα που είναι βελτιστοποιημένο για κάποια δεδομένη αρχιτεκτονική ή/και εφαρμογή. Αυτός ο κώδικας δεν είναι απαραίτητα αυτός με το μικρότερο memory footprint.

 

Εν τέλει είναι πόσο καλά ταιριάζει ο κώδικας σε αυτό που κάνεις. Το να σώσεις 1Μbyte πχ σε ένα σύγχρονο σύστημα δεν είναι και τόσο σημαντικό.

[MitsakosGR]

Εν τέλει είναι πόσο καλά ταιριάζει ο κώδικας σε αυτό που κάνεις. Το να σώσεις 1Μbyte πχ σε ένα σύγχρονο σύστημα δεν είναι και τόσο σημαντικό.

 

Εξαρτάται αυτό, γιατί αν ανοίξει πολλές φορές τότε έχεις τεράστιο πρόβλημα ακόμα και για MB...

Αλλά γενικά στην ερώτηση για το ποιό "πρέπει" να χρησιμοποιήσεις είναι αυτό που βολεύει την εφαρμογή που φτιάχνεις...

[Evgenios1]

Νομιζω οτι δεν ειναι και τοσο σοβαρο προβλημα το αν θα εχεις καποια mb overhead. Το προβλημα ειναι στην προσβαση της μνημη, ναι μεν εχουμε 2-4 gb ram και 2,7-3,7 ghz cpu αλλα εχουμε και ενα πολυ αργο bus.

Πχ στην εν λογου εφαρμογη (node list) για να πας απο το πρωτο αντικειμενο μεχρι το τελευταιο θα εχεις ενα οverhead στο χρονο εκτελεση πανω απο 5.000-10.000% (αν δε κανω λαθος το memory bus ειναι 100-300mhz)

 

Αρα οτι οταν εχομε το διλημμα περισσοτερα request στη μνημη vs περισσοτερο χωρο στη μνημη, νομιζω οτι το δευτερω ειναι καλυτερο.

[dop]

Όσον αφορά τη μνήμη, την καλύτερη ταχύτητα την έχεις ελαχιστοποιώντας τα cache misses, είτε είναι L1, L2, L3 ή TLB.

 

Το πρόβλημα είναι στο access pattern της μνήμης. Οι λίστες είναι οι χειρότερες σε αυτό, καθώς το allocation συνήθως δεν είναι συνεχόμενο (εξαρτάται από τον allocator), με αποτέλεσμα να αυξάνονται τα cache misses.

 

Από την άλλη, μειώνουν κατά πολύ το contention καθώς σπάνια δύο threads ακουμπούν την ίδια μνήμη αλλά και το false sharing.

 

Οπότε είναι αποκλειστικά θέμα της εφαρμογής αν είναι πιο γρήγορο/αργό.