Πρόσφατα κυκλοφόρησε μια πρόταση για τον πυρήνα του Linux, στο οποίο προτείνεται να συμπεριληφθεί ένα σύνολο μπαλωμάτων με α βελτιστοποιημένη υλοποίηση της συνάρτησης memchr(). χρησιμοποιείται για την αναζήτηση ενός χαρακτήρα σε έναν πίνακα.
Η συνάρτηση memchr() σαρώνει τα κύρια n byte της περιοχής μνήμης που δείχνει το s για την πρώτη περίπτωση του c. Τόσο το c όσο και τα byte στην περιοχή μνήμης που δείχνει το s ερμηνεύονται ως ανυπόγραφοι χαρακτήρες.
Η πρόταση υποσχέσεις να είσαι πιο γρήγορος για να εντοπίσετε έναν χαρακτήρα μέσα σε ένα μπλοκ μνήμης. Σε δοκιμές προγραμματιστών, η νέα εφαρμογή μπορεί να είναι σχεδόν τέσσερις φορές πιο γρήγορη σε μεγάλες αναζητήσεις
Σε αντίθεση με την προηγούμενη έκδοση, η οποία χρησιμοποιούσε σύγκριση byte-by-byte, η προτεινόμενη υλοποίηση δημιουργείται λαμβάνοντας υπόψη την πλήρη χρήση καταχωρητών CPU 64-bit και 32-bit. Αντί για byte, η σύγκριση γίνεται με τη χρήση λέξεων μηχανής, που επιτρέπει τη σύγκριση τουλάχιστον 4 byte τη φορά.
Αυτή η σειρά patches βελτιστοποίησε το "memchr()" και πρόσθεσε μια μακροεντολή για
"memchr_inv()" ώστε και οι δύο συναρτήσεις να μπορούν να το χρησιμοποιήσουν για να δημιουργήσουν μια μάσκα bit.Η αρχική υλοποίηση του "memchr()" βασίζεται στη σύγκριση byte,
που δεν χρησιμοποιεί πλήρως τον καταχωρητή 64 ή 32 bit στην CPU. Εφαρμόζουμε α
σύγκριση με λέξεις, ώστε τουλάχιστον 4 byte να μπορούν να συγκριθούν με τα ίδια
καιρός. Η βελτιστοποιημένη memchr() είναι σχεδόν 4 φορές ταχύτερη από την αρχική
για μακριές αλυσίδες. Στον πυρήνα Linux, βρίσκουμε ότι το μήκος της συμβολοσειράς
που αναζητείται από το "memchr()" είναι έως και 512 byte στα προγράμματα οδήγησης/misc/lkdtm/heap.c.
Όταν κάνετε αναζήτηση σε μεγάλες χορδές, η νέα έκδοση αποδείχθηκε ότι ήταν περίπου 4 φορές πιο γρήγορη από την παλιά (για παράδειγμα, για συμβολοσειρές 1000 χαρακτήρων). Για μικρές αλυσίδες, η αποτελεσματικότητα της νέας εφαρμογής δεν είναι τόσο σημαντική, αλλά εξακολουθεί να είναι υψηλότερη από την αρχική έκδοση.
Το ενδιαφέρον με τη νέα πρόταση είναι η βελτίωση για μεγάλες αλυσίδες, η οποία βελτιώνει σημαντικά τους χρόνους. Αξίζει να αναφέρουμε ότι στον πυρήνα του Linux, το μέγεθος των συμβολοσειρών που υποβάλλονται σε επεξεργασία σε memchr() φτάνει τα 512 byte. Στις δοκιμές μας, το κέρδος απόδοσης για συμβολοσειρές 512 byte, σε μια κατάσταση όπου ο χαρακτήρας αναζήτησης είναι στο τέλος της χορδής, είναι 20%.
Αξίζει να αναφέρουμε ότι η αρχική έκδοση του memchr() υλοποιείται με την τεχνική σύγκρισης byte-wise, η οποία δεν χρησιμοποιεί πλήρως τους καταχωρητές στην CPU 64-bit ή 32-bit.
Χρησιμοποιούμε σύγκριση ολόκληρων λέξεων έτσι ώστε να μπορούν να συγκριθούν 8 χαρακτήρες ταυτόχρονα στην CPU. Αυτός ο κώδικας βασίζεται στην υλοποίηση του David Light.
Δημιουργούμε δύο αρχεία για να μετρήσουμε την απόδοση του πρώτου αρχείου που περιέχει κατά μέσο όρο 10 χαρακτήρες μπροστά από τον χαρακτήρα προορισμού. Το δεύτερο αρχείο περιέχει τουλάχιστον 1000 χαρακτήρες πριν από το χαρακτήρας στόχος.
Η εφαρμογή του "memchr()" είναι ελαφρώς καλύτερο στην πρώτη δοκιμή και σχεδόν 4 φορές πιο γρήγορο από το πρωτότυπο υλοποίηση στη δεύτερη δοκιμή.
Δοκιμή πυρήνα 5.18 με νέα παραλλαγή "memchr()" για αρχιτεκτονικές 32 bit και 64 bit δεν αποκάλυψε κανένα πρόβλημα.
Τι συμβαίνει εάν το p δεν είναι στοιχισμένο byte 8 (ή 4 σε στόχους 32 bit); Δεν υποστηρίζουν όλοι οι στόχοι μη ευθυγραμμισμένα (αποδοτικά) φορτία, σωστά;
Νομίζω ότι λειτουργεί αν το p δεν είναι ευθυγραμμισμένο 8 ή 4 byte. Ας υποθέσουμε ότι η συμβολοσειρά είναι 10 byte. Ο βρόχος for εδώ θα αναζητήσει τα πρώτα 8 byte. Εάν ο χαρακτήρας προορισμού βρίσκεται στα τελευταία 2 byte, ο δεύτερος βρόχος for θα τον βρει. Λειτουργεί έτσι και σε μηχανές 32-bit.
Το συνολικό κέρδος απόδοσης δεν έχει ακόμη αξιολογηθεί των υποσυστημάτων του πυρήνα κατά τη χρήση της βελτιστοποιημένης παραλλαγής "memchr()", ούτε έχει συζητηθεί εάν θα παρακάμψει την υλοποίηση (η κλήση της συνάρτησης memchr() εμφανίζεται 129 φορές στον κώδικα του πυρήνα, συμπεριλαμβανομένων προγραμμάτων οδήγησης και συστημάτων αρχείων).
Τελικά Εάν ενδιαφέρεστε να μάθετε περισσότερα γι 'αυτό, μπορείτε να ελέγξετε τις λεπτομέρειες Στον ακόλουθο σύνδεσμο.