כשהקצאות הזיכרון משנות

ב־יום רביעי, 10 באוגוסט 2011, מאת ארתיום; פורסם תחת: תכנה חופשית, לינוקס, תכנה ומחשבים, CppCMS, C++‎‏; ‏16 תגובות

יש הרבה צווארי בקבוק ביישומי רשת. רבים מהם נובעים מארכיטקטורת היישום, קריאות מערכת הפעלה ועוד.

אבל בשלב מסוים יישום רשת יעיל מגיע לנקודה בה הקצאות זיכרון מתחילות להשפיע בצורה משמעותית, בפרט זה נוגע לכל הקשור לעבודה עם מחרוזות.

ב־C++‎ יש מחרוזת הטובה הישנה: std::string. אבל יש לה מגבלה אחת: היא דורשת הקצאה של חתיכת זיכרון. זה נכון לכל מחרוזות בכל השפות ובכל הכלים גם אם הם immutable ומשתמשות ב-reference counting - עדין יש צורך להקצות זיכרון לאותה החתיכה.

בואו ניקח לדוגמה יישום פשוט שמאתר מקום כלשהו בעץ המשתמש במפתחות std::string המבוסס על std::map. הוא מקבל כפרמטר מחרוזת כמו ‎/foo/bar/124‎ ומחלץ ממנה את המפתחות foo ו־bar כחלקים במסלול, יישום בסגנון xpath.‏

אז עבור פונקציה:

void find_path(std::string const &str);

הקריאה

find_path("/foo/bar/123");

תצטרך ליצור שלוש מחרוזות:

  • /foo/bar/123
  • foo
  • bar

כך או אחרת עבור שולש מחרוזות האלה נצטרך להקצות שלוש חתיכות זיכרון, גם אם המחרוזות שלנו משתמשות ב-reference counting או הן immutable.

אז כיצד CppCMS מתמודד עם הבעיה הזו:

  1. קיימת מחלקה מיוחדת cppcms::string_key שמחזיקה מתוכה את ה־std::string הישן והטוב. אבל בנוסף, ניתן ליצור את אותה המחלקה באופן מפורש מזוג מצביעים מטיפוס char const *‎, כך שהיא שומרת רק הצבעה לטקסט ולא מעתיקה אותו.

    כמובן, שבמקרה הזה, המשתמש הוא האחראי לכך שהמצביעים יישארו תקפים כל עוד משתמשים באובייקט הזה.

  2. עכשיו נשנה את הפונקציה find_path קלות ונוסיף לה עוד גרסה:

    void find_path(char const *str);
    void find_path(std::string const &str);
    

    עכשיו, נשתמש רק במחרוזות שלא "מחזיקות בעלות על התוכן" ובכך נוכל ליצור מחרוזת מקורית ותת־מחרוזות foo ו־bar בלי להקצות זיכרון בכלל.

כמובן, זה הקו הכללי, אבל יש עוד הרבה טריקים מעניינים נוספים שמאפשרים למנוע או להוריד את כמות ההקצאות זיכרון כמו שימוש ב־pool שמוקצה פעם אחת ומשוחרר בסוף בבת אחת, שימוש במחסנית עבור קטעים קטנים ועוד.

CppCMS החל מגרסה 0.99.9 ששוחררה היום, אימץ את הטכניקה הזו בצורה רחבה ואפשר, במקרים מסוימים, להכפיל את ביצועים המערכת כולה.

כמובן, כשמשתמשים בטריקים האלה צריך להיות זהיר במיוחד גבי ניהול זיכרון ידני. אלא אם, קטע קוד רץ הרבה פעמים או כבר זיהיתם קטע מסוים כצוואר בקבוק, תשתמשו במחרוזת הרגילה. בסופו של דבר, הקצאה של זיכרון היום זה תהליך יחסית מהיר, אם לא מנצלים אותו לרעה.

תגובות

ik, ב־10/08/11 15:38

זו בדיוק הסיבה למה AnsiSting בפסקל עבר ל Reference Counting לפני למעלה מעשור כבר (לדעתי ב97-8).

ב reference counting מאפשר לקבל מחרוזת ריקה עם גודל 0, ולהגדיל אותה עד למקסימם זיכרון שהמערכת הפעלה מסוגלת להקצות עבורה (לפחות במימוש של פסקל).

פעם אבל היתה מגבלה "מכנית" של 64 קיי, בגלל שחשבו ש32 ביט זה המקסימום, מזל ששינו את התפיסה הזו.

בקיצור במילים אחרות, אתה בדרך הנכונה. בסוף תשנה את התחביר למשהו קריא, תספק כלים מאוד דומים ל RTL ויהיה אפשר להגיד אתה מתכנת פסקל בשפת ++C :P

נתראה בAP לוויכוח הבא שלנו :)

ארתיום, ב־10/08/11 15:47

עידו, אני חושב שאתה תצטרך לקרוא את הכתבה שוב :-)

הנקודה ש-Reference Counting לא יעזור לך במקרה הזה, לצורך העניין std::string של libstdc++‎ הוא כן reference-counting אבל עדיין לא פותר את הבעיה.

אגב, היום ב־C++‎ דווקא יורדים מ-Reference Counting ואפילו נדמה ש־C++0x יאסור את זה. היום עוברים לשימוש ב-Small String Optimization כאשר המחרוזת מכילה 16 בתים במקום שלא דורשים הקצאה ורק אם המחרוזת גדלה יותר מידי אז מקצים זיכרון. שזה ד"א היה מאוד משפר את הביצועים במקרה הפרטי שדיברתי עליו. כי באמת ברוב המקרים יש מחרוזות קצרות. (אם כי בסוף זה עדיין לא יהיה מהיר כמו שאני עשיתי)

נתראה ב־AP

ik, ב־10/08/11 17:02

האתחול זיכרון של AnsiStrig הוא דינאמי, אבל אני יכול להשפיע עליו עם SetLength למשל, ולהגיד לו אורך קבוע והוא לא ישתנה במהלך הריצה אלא אם תאפס אותו שוב עם SetLength (או אם הזיכרון בראש שלי לא מתפקד טוב).

יש לך בפסקל מודרני כיום 5 סוגי מחרוזות סה"כ, ואתה תמיד יכול ליצור בעצמך עוד (רק אז גם לנהל אותם לבד, כמו שאתה עושה עם PChar שהוא אחד מהחמישה).

ליבוביץ, ב־10/08/11 17:09

שווה לשים לב למחלקה StringPiece בפרוייקט re2

עדיף לעבוד איתה מאשר עם מצביע לדעתי.

ארתיום, ב־10/08/11 20:17

שווה לשים לב למחלקה StringPiece

המחלקה שלי עושה יותר. שים לב היא מאפשרת ליצור מחרוזת ללא בעלות וגם עם בעלות.

ליבוביץ, ב־11/08/11 10:56

רגע, אם יש לך כבר מחלקה כזו, למה יש לך פונקציה שמקבלת char*? תמיד תמיד תקבל מחלקה בטוחה ולא char*, עם שימוש חכם בinline הקוד הבינארי יראה כמעט אותו דבר ולא יהיה הבדל בביצועים.

ליבוביץ, ב־11/08/11 10:57

אופס, תחליף את char בchar*

ארתיום, ב־11/08/11 11:25

תמיד תמיד תקבל מחלקה בטוחה ולא char*

ממש לא. ואני אסביר למה גם איטרטורים כמו std::string::iterator בפועל לא בטוחים יותר מ־‎char*‎ מסיבה פשוטה שלמטה זה עדיין אותו מצביע ואם אתה תפנה ל־str.begin()+100 כאשר מחרוזת שלך קטנה התוכנה תעוף בדיוק כמו עם מצביע ל־char.

הקוד הזה נועד לאופטימיזציות לא בטוחות (כמו ה־stringpice) שסומכות על המשתמש, לכן זה בהחלט נוכן להשתמש במצביע כאן.

ליבוביץ, ב־14/08/11 08:49

ההבדל בין פונקציה שמקבלת איטרטור למצביע (הרי כל התכנון של איטרטורים הוא שיהיה אפשר להעביר לפונ' שמקבלת אותו מצביע ישן של סי ממש), הוא שאם הפונקציה מקבלת איטרטור, היא יכולה לעבוד מהר בדיוק כמו מצביע, אבל, היא יכולה גם לבדוק את עצמה, לשלם מחיר מסויים, ולוודא שלא תקבל התנהגות בלתי מוגדרת.

אם אתה מקבל מצביע - אתה חייב לא לבדוק את עצמך.

אני עדיין לא מבין למה פונ' שלך צריכה לקבל מצביע, ולא את המחלקה הבטוחה שלך. הרי המחלקה הבטוחה שלך מכילה מצביע ואת גודל המחרוזת, לא? אז למעשה ההפסד היחיד שלך בהעברת המחלקה על פני העברת המצביע הוא שהעברת עוד משתנה אחד במחסנית. זה מה שיעשה את ההבדל?

אתה שואל מה הרווח? הרווח הוא, שאם בכל זאת התוכנית שלך מתנהגת מוזר, אתה יכול להוסיף בדיקה ב-stringPiece שמונעת ממך להגיע למקומות לא רצויים - ואם אתה מעביר מצביע - לא.

תוכל לתת לי דוגמא של אופטימיזציה שאי-אפשר לעשות כשמעבירים StringPiece ואפשר לעשות כשמעבירים מצביע?

ארתיום, ב־14/08/11 10:09

תסתכל בפונקציה הבאה

הכל נעשה בצורה בטוחה, אבל עדיין, אני בתור משתמש רוצה לאפשר ליצור חתיכת טקסט מתוכן שרירותי שכל הדרישה שלי ממנו זה שיהיה לי טווח charים רציף המוגדר ע"י שני מצביעים.

אני כן עובד עם מחלקות בטוחות כך שאני יכול ליצור string_key מתוך std::string או מתוך מחרוזת C, אבל אני כן רוצה חופש לעשות מה שבא לי.

ליבוביץ, ב־14/08/11 16:25

אולי אני איטי אבל עדיין לא הבנתי. למה במקרה של הפונקציה שלך, אי אפשר היה שfind תקבל אך ורק StringPiece, ומשתמש שרוצה לתת לה char* יתכבד וייצור StringPiece חדש מרצף ה-char* שיש לו, וייתן לה את ה-StringPiece שיצר.

כך עדיין יש לך חופש לטפל בchar* אם חלילה אתה מקבל מחרוזות של C, אבל באופן כללי הפונ' שלך מקבלות רק StringPiece.

ארתיום, ב־14/08/11 16:50

אני לא רואה בעיה עם char*.

בנוסף, במקרה הפרטי ההוא החיפוש הוא על תו ולא מחרוזת שלמה. אבל אם הייתי רוצה לחפש תת מחרוזת אז כן הייתי מעביר בדיוק כמו ב־std::string או char* או string_key

ליבוביץ, ב־14/08/11 17:19

הבעיה עם char* היא שהוא לא בטוח. אם אתה מקבל StringPiece (או המקבילה שלך, זה לא משנה), אתה יכול אם אתה רוצה, לוודא שאתה לא נוגע באיזור שלא מיועד לך. המחיר - די נמוך. אתה חייב להעביר לפונ' עוד int אחד שאומר לה את אורך המחרוזת.

לכן נראה לי שטוב, באופן כללי, להמנע מלקבל char* ולקבל במקום אך ורק StringPiece. ככה אתה מפחית את הסיכויים להתנהגות בלתי צפויה של התוכנה.

מה אם אתה לא יכול להרשות לעצמך לבדוק אם אתה חורג מגבולות המחרוזת בגלל בעיות ביצועים? בקטעים הקריטיים תוכל תמיד להסיר את הקוד שבודק ומוודא שלא חרגת, ואז התוכנה תתנהג בדיוק כאילו העברת לה char*. זה אחד הדברים שאני יותר אוהב בC++ - שלם רק על מה שאתה משתמש.

בשפה Go יש רעיון מאד דומה. כשאתה פונה למערך, ברירת המחדל היא לבדוק אם האינדקס חוקי. והיה אם יש לך בעיות ביצועים - קמפל את אותו קוד עם -B והבדיקות תעלמנה.

ארתיום, ב־14/08/11 17:40

הבעיה עם char* היא שהוא לא בטוח.

מה לא בטוח? לא בטוח שהוא מסתיים ב־0? לא בטוח שהוא לא 0.

תראה, לפונקציה שמקבלת char* יש דרישה שהמשתמש צריך לענות עליה.

עכשיו אני אספר לך מתי char * מאוד נוח:

כשאתה כותב:

find("/foo/bar");

אתה לא רוצה להקצות זיכרון כי בסה"כ מדובר במחרוזת סטטית קבועה.

אני לא חושב שלפסול char* בגלל שיש במקרים בהם אפשר לעשות שימוש לא נאות, זה דבר חכם.

ד"א אחד הדברים ש-StringPice לא עושה זה להיות הבעלים של זיכרון. כך למשל ברירת מחדש זה לעתיק זיכרון - גישה בטוחה, אבל אם אתה רוצה לייעל את משתמש בפונקציות שמתחילות ב-unowned.

ליבוביץ, ב־14/08/11 22:56

הנקודה שהעלת נכונה. אפשר לטפל בזה עם implicit conversions, שכמובן ישתמש רק במחסנית, אבל לא בטוח שזה רעיון טוב, יש ל-implicits חסרונות משלהם.

אני מסכים שאם אתה מגביל את השימוש של char* למחרוזות סטטיות הוא בטוח. העניין הוא, שברגע שאתה מקצה char[] עושה עליו מניפולציות ואז נותן מצביע לתחילת המערך, אתה עלול לטעות, ולשכוח למשל לשים את ה'\0' בסוף, ואז התוצאות לא ידועות. אם אתה מתכוון לשנות משהו רק ב-foo בתוך המחרוזת foobar, אז אתה עלול להתבלבל ולשנות גם את ה-bar.

בקוד שלך אין באגים? זו עדיין בעיה, כי מישהו אחר או ספריה שתשתמש בה עלולה לשנות לך חלקים במחרוזת שלא נתת לה, ולמצוא את השגיאה הזו זה לא נחמד.

אם תתן StringPiece אתה יודע (או יכול לדעת) בוודאות שהפונקציה לא תיגע במה שלא נתת לה נקודה. והמחיר? כמעט אפס.

אני חושב שהבטחה שהלקוח של הפונקציה יגע רק בחתיכה מסויימת של המחרוזת מגבירה את הביטחון של המפתח.

ארתיום, ב־15/08/11 09:15

אם אתה מתכוון לשנות משהו רק ב-foo בתוך המחרוזת foobar, אז אתה עלול להתבלבל ולשנות גם את ה-bar.

כי מישהו אחר או ספריה שתשתמש בה עלולה לשנות לך חלקים במחרוזת שלא נתת לה, ולמצוא את השגיאה הזו זה לא נחמד.

שים לב, אני מקבל את המצביעים אך ורק כ־const אני מעולם לא

אגב, אני כמעט לא משתמש ב־string_key בממשק, הוא נועד לטיפול פנימי כי למשתמש הסופי שסביר להניח לא מומחה ב־C++‎ לא צריך להתעסק בדברים האלה.

הייעוד שדיברתי עליו הוא פנימי ולא נראה לעין. למעשה מרבית השינויים שעשיתי לא שינו את ממשק המשתמש (רק הרחיבו אותו קלות)

שוב, אין כאן שחור לבן, ולצורך העניין במקרים מסויים אני כן עובד עם מחרוזות C ועם הקצאה שלהם ב-pool מיוחד לצורך הייעול, אבל זה סיפור אחר לגמרי שאינו גלוי למשתמש.

הוסף תגובה:

 
 כתובת דוא"ל לא תוצג
 

ניתן לכתוב תגובות עם שימוש בתחביר Markdown.

חובה לאפשר JavaScript כדי להגיב.

דפים

נושאים