לאחרונה שוחררה הצעה עבור ליבת לינוקס, שבו מוצע לכלול סט של טלאים עם a יישום אופטימלי של הפונקציה memchr() משמש לחיפוש דמות במערך.
הפונקציה memchr() סורקת את n הבתים המובילים של אזור הזיכרון שעליו מצביע s עבור המופע הראשון של c. גם c וגם הבתים באזור הזיכרון שעליהם מצביע s מתפרשים כתווים ללא סימנים.
ההצעה הבטחות להיות מהיר יותר כדי לאתר דמות בתוך בלוק זיכרון. במבחני מפתחים, ההטמעה החדשה יכולה להיות מהירה כמעט פי ארבעה בחיפושים גדולים
בניגוד לגרסה הקודמת, שהשתמשה בהשוואה בתים-בתים, היישום המוצע נוצר בהתחשב בשימוש המלא של אוגרי מעבד של 64 סיביות ו-32 סיביות. במקום בתים, ההשוואה נעשית באמצעות מילות מכונה, המאפשרות השוואה של לפחות 4 בתים בכל פעם.
סדרת תיקונים זו עשתה אופטימיזציה של "memchr()" והוסיפה מאקרו עבור
"memchr_inv()" כך ששתי הפונקציות יכולות להשתמש בו כדי ליצור מסכת סיביות.היישום המקורי של "memchr()" מבוסס על השוואת בתים,
אשר אינו משתמש במלואו ברישום 64 או 32 סיביות במעבד. אנו מיישמים א
השוואה לפי מילים כך שניתן להשוות לפחות 4 בתים לאותו דבר
מזג אוויר. ה-memchr() הממוטב מהיר כמעט פי 4 מהמקור
לשרשראות ארוכות. ב-Linux Kernel, אנו מוצאים את אורך המחרוזת
חיפוש על ידי "memchr()" הוא עד 512 בתים ב-drivers/misc/lkdtm/heap.c.
כאשר מחפשים על מיתרים גדולים, הגרסה החדשה התבררה כמהירה פי 4 מזו הישנה (לדוגמה, עבור מחרוזות של 1000 תווים). עבור רשתות קטנות, היעילות של ההטמעה החדשה אינה כה משמעותית, אך היא עדיין גבוהה מהגרסה המקורית.
המעניין בהצעה החדשה הוא השיפור לרשתות הגדולות, שמשפר את הזמנים בצורה ניכרת. ראוי להזכיר כי בקרנל לינוקס, גודל המחרוזות המעובדות ב-memchr() מגיע ל-512 בתים. בבדיקות שלנו, הביצועים צוברים עבור מחרוזות של 512 בתים, במצב שבו תו החיפוש נמצא בסוף המחרוזת, זה 20%.
ראוי להזכיר כי הגרסה המקורית של memchr() מיושמת בטכניקת ההשוואה לפי בתים, שאינה משתמשת במלואה ברגיסטרים במעבד 64 סיביות או 32 סיביות.
אנו משתמשים בהשוואת מילים שלמות כך שניתן להשוות 8 תווים בו זמנית במעבד. קוד זה מבוסס על היישום של David Light.
אנו יוצרים שני קבצים כדי למדוד את הביצועים של הקובץ הראשון שמכיל בממוצע 10 תווים לפני תו היעד. הקובץ השני מכיל לפחות 1000 תווים לפני ה- דמות המטרה.
היישום שלנו של "memchr()" הוא מעט טוב יותר במבחן הראשון וכמעט פי 4 מהר יותר מהמקורי יישום במבחן השני.
בדיקת Kernel 5.18 עם גרסת "memchr()" חדשה עבור ארכיטקטורות של 32 סיביות ו-64 סיביות לא חשף בעיות.
מה קורה אם p אינו מיושר בתים של 8 (או 4 ב-32 סיביות)? לא כל היעדים תומכים בעומסים לא מיושרים (יעילים), נכון?
אני חושב שזה עובד אם p אינו מיושר ל-8 או 4 בתים. נניח שהמחרוזת היא 10 בתים. לולאת ה-for כאן תחפש את 8 הבתים הראשונים. אם תו היעד נמצא ב-2 הבתים האחרונים, השני for loop ימצא אותו. זה עובד ככה גם במכונות 32 סיביות.
רווח ביצועים כולל טרם הוערך של תת-מערכות הליבה בעת שימוש בווריאציה הממוטבת "memchr()", וגם לא נדון אם לעקוף את היישום (קריאה לפונקציה memchr() מתרחשת 129 פעמים בקוד הליבה, כולל מנהלי התקנים ומערכות קבצים).
בסופו של דבר אם אתה מעוניין לדעת יותר על כך, אתה יכול לבדוק את הפרטים בקישור הבא.