reserve ו- map

[the new L]

reserve ו- map

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

 

[the new L]

וקצת יותר הסבר

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

 

[cyberia2ooo]

אתה לא צריך

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

 

[the new L]

אבל אני עדיין

צריך להגיד ל allocator שיעשה reserve, ובשביל זה צריך להוסיף ל map פונקציה

 

[the new L]

האמת שכבר מצאתי

את get_allocator

 

[the new L]

בעצם לא

הוא סתם מחזיר לי allocator מאותו הסוג

 

[the new L]

למישהו יש

רעיון? אני מתחיל לחשוב שאין דרך יפה לעשות את זה, פשוט כי ה map לא נותן לך שום גישה ישירה ל allocator שהוא משתמש בו. אם לא תהייה ברירה אני אאלץ ללכת על פיתרון של הגדרת מחלקת singleton שתהווה את ה pool של הזיכרון, וכל ה Allocator-ים שלי ידברו עם המחלקה הזאת. אולם הפיתרון צריך לעבוד טוב בסביבה Multi-threaded וזה יגרור בהכרח שגישה ל Map-ים שונים ב Thread-ים שונים בו זמנית תהייה חייבת להיות מוגנת ב Mutex וזה כבר הופך את זה ל overhead לא קטן ולאסון רציני... אני בכלל מתקשה להבין למה המימוש ה-stl-י (לפחות ב VC) מבצע העתקות של הAllocator-ים מידי פעם (עבודה קצרה עם map הראתה לי שהיו שתי קריאות ל Constuctor של ה Allocator), מה שהיה מסבך אפילו את העניין של עבודה עם pool מקומי ל Allocator אם הייתי יכול לעשות את זה. ועוד שאלה שאני אחזור עליה לסיכום: למה אין פונקציית reserve בכל ה Container-ים של stl?

 

[אמיר ט]

השערה

ב containerים כמו vector ו list אתה יכול לעשות reserve כי ה key שלך הוא משהו שה reserve יכול לקבוע, כלומר אתה תעשה reserve של 1000, אין בעיה להקצות 1000 איברים ואח"כ לגשת אליהם לפי האינדקס (key בעצם) שלהם. ב map אתה הרי מגדיר מה הkey שלך, ויש לו השפעה מאד גדולה עם המיקום של כל אובייקט אצלך ב map. אני חותר לזה שאם תחשוב על reserve ל map מאד מהר תראה שאתה צריך לתת מפתח לכל ערך שאתה מכניס, כאן אתה נתקל באחת משני בעיות : א. אתה סתם מייצר מפתחות (נגיד 1 עד 1000) אבל אז המפה שלך ממויינת לפי המפתחות האלה, וברגע שתשנה את ה key זה יגרור אחריו שינוי עצום של כל מבנה האובייקטים ב map שלך, הרי באחורי ה map יושב עץ שחור אדום - תחשוב איזה שינויים יהיו ב map שלך אם תשנה את ה key של מה שהיה 1 לנגיד 1001 (שהוא ה key האמיתי שלך), יהיו לך המון שינוים שיצטרכו להתבצע כדי שהעץ יהיה מסודר שוב נכון. ב. אתה יכול להכניס את המפתחות האמיתיים, אבל אם יש לך אותם מה בעצם עשית כאן ? בקיצור אם אתה מחפש דרך לייעל את זה ולדאוג שלא יהיה חסר זיכרון, תעשה לך איזה list או vector של אובייקטים מהסוג שיכנסו לmap - אותם תקצה בתחילת התוכנית. ואז בכל הכנסה, תקח אובייקט (אחד שלא השתמשת בו עדיין) מה list שלך תתן לו את הנתונים האמיתיים, ותכניס אותו לmap (שיכיל מצביעים לאובייקטים שלך). ככה גם תקצה הכל מראש, גם ה map יעבוד על פוינטרים וההקצאות יהיו קלות. אני מקווה שהבהרתי את עצמי, אני אמנם לא סגור במאה אחוז שכל מה שאמרתי נכון אבל בכל זמן כתיבת ההודעה לא מצאתי פגם בתאוריה שלי

 

[the new L]

זה בהחלט

רעיון לא רע, אם כי כמובן לא מושלם (הקצאה כפולה של pointer-ים, וגם עצם זה שצריך לעבוד פה עם pointer-ים...) בכל מקרה, שלחתי מייל ל Stroustrup בנושא, נראה מה יהיה לו להגיד.

 

[אמיר ט]

תראה...

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

 

[the new L]

זה לא יהרוג

ה4 בתים עצמם, אבל אם לצורך העניין אני מכניס ל map 100,000 אובייקטים, אז זה לקרוא 200,000 פעם ל new במקום פעם אחת...

 

[אמיר ט]

תעשה הפרדה חשובה

בין יעילות מקום ליעילות זמן : אם אתה מחפש יעילות מקום בלבד אז כמובן שגם 4 בתים מיותרים פר אובייקט זה הרבה. אם אתה מחפש יעילות זמן בלבד אז תחשוב שאת 100000 הקריאות הראשונות ל new אותה עושה על התחלת התוכנית שלך, לפני העיבוד האמיתי ולכן התוכנית מהירה לפחות כמו אותה תוכנית עם רק קריאה אחת לnew. אם אתה מחפש יעילות מקום וזמן, אז זה גם פתרון דיי טוב, אין הרבה זיכרון עודף (סה"כ 4 בתים פר אובייקט), והזמן שתחסוך בהקצאות אמיתיות הוא עצום.

 

[אמיר ט]

רגע רגע רגע

עכשיו קראתי שוב את ההודעה שלך ולפי מה שאני רואה לא הבנת למה אני מתכוון. אני אתן לך דוגמא למימוש של הרעיון שלי :

int main() { int currentObject = 0; vector< MyObj > ObjectPool; ObjectPool.reserve( 1000 ); map< MyKeyType, MyObj* > myMap; ... ... ... //here is the "working" part of the program, //these lines will be called for each insertion MyObj* insertObj = ObjectPool[ currentObject ]; insertObj.setSomeParam( someParam ); insertObj.setAnotehrParam( anotherParam ); myMap[ myInsertKey ] = insertObj; ++currentObject; }​

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

 

[annefan]

הבעיה היא ביצועים

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

 

[אמיר ט]

אמת...

זה בדיוק מה שהסברתי מקודם.

 

[annefan]

סליחה

אני לא יודע לקרוא בשעה כזו. (והלחש של בנות-גשרית מזכיר לי נשכחות...)