הנה חידה נחמדה:
N אנשים עומדים במעגל וכל איש שני מוצא להורג, האחרון שנשאר ניצל. באיזה מיקום איש יצטרך לעמוד כדי להינצל?
בעיית יוספוס עבור n=7, האיש השביעי ניצל.
קרא עוד
-
עמודים
-
קטגוריות
-
ארכיון
קישורים
-
רססים
-
מטא
בעיית יוספוס
Cache, Multithreading וקצת על הפרוטוקול MESI
בעולם ה-multithreading, את רובינו מדאיגה העובדה שצריך לסנכרן גישה למשתנה שמשותף למספר טרדים, ושסנכרון זה הוא די יקר לפעמים. אך מה לגבי משתנים שאינם נופלים על אותה הכתובת, האם צריך לסנכרן את הגישה אליהם? התשובה היא שהמפתחים אינם צריכים לעשות זאת, אבל החומרה כן. אם אנחנו מעוניינים לכתוב קוד שמנצל את כוח החישוב של מחשבי multi-core באופן מקסימלי עלינו להבין מה קורה מאחורי הקלעים.
הסתכל על הקוד הבא:
struct Widget
{
int x, y;
} w;
const int k = 100000;
//thread 1
void t1()
{
for(int i=0; i < k; ++i)
++w.x;
}
// thread 2
void t2()
{
for(int i=0; i < k; ++i)
++w.y;
}
נאמר שיצרנו שני טרדים t1,t2 על סביבת multi-core. כל אחד מהטרדים מעדכן משתנה אחר. הכתובת של w.x שונה מהכתובת של w.y, לכן אין צורך בסנכרון.
האם אתה יכול למצוא בעיות במימוש המולטיטרדי הנ"ל?
קרא עוד
האם כאשר רמת האבסטרקצייה גדלה הביצועיים יורדים?
טיעון נפוץ הוא שככל שאנחנו עולים ברמת האבסטרקציה של התוכנית, כך הביצועיים של התוכנית נעשים נמוכים יותר. בפוסט הזה תופתעו לגלות שלטיעון זה ישנם הסתייגויות.
ביצעתי השוואת ביצועיים בין הפונקציה qsort שבספריה cstdlib של c לבין הפונקציה sort של ++C מ-STL:
qsort:
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int main()
{
const int k = 100000000;
int* values = new int[k];
for(int i=0; i< k; i++) values[i] = i;
// measure the time
boost::progress_timer t;
qsort(values, k, sizeof(int), compare);
}
std::sort:
struct MyCompare
{
int operator()(int a, int b) { return a < b; }
};
int main()
{
const int k = 100000000;
int* values = new int[k];
for(int i=0; i< k; i++) values[i] = i;
// measure the time
boost::progress_timer t;
std::sort(values, values+k, MyCompare());
}
כיצד ניפטר מאובייקטים זמניים?
במקרים מסוימים ניתן לסלק אובייקטים זמניים ועל ידי כך לשפר את הביצועיים של התוכנית שלנו.
נאמר שיש לנו מחלקה A:
class A
{
private:
int member;
public:
A(int x=0): member(x) { cout << "Constructor" << endl; }
~A() { cout << "Destructor" << endl; }
A(const A& a) { cout << "Copy constructor" << endl; }
friend const A getObj(int);
};
const A getObj(int x)
{
A a;
a.member = x;
return a;
}
למה הפרויקט שלי מתקמפל כל כך לאט?
זמן קומפילציה ארוך במיוחד תמיד היווה בעיה עבור פרוייקטים בקנה מידה גדול ב++C. הבעיה של זמני קומפילציה ארוכים בדרך כלל נובעת מהעובדה שב++C שינויים בחלק ה-private של מחלקה מסוימת יגרום לקומפילציה מחדש של כל הקבצים שמשתמשים במחלקה הזו.
נאמר שיש לנו קובץ header בשם A.h
// A.h:
class A
{
private:
int x;
int y;
void f() { ... }
public:
void g() { f(); }
};
והפרויקט שלנו משתמש בצורה אינטיסיבית במחלקה A, כלומר אנחנו מכלילים את הקובץ A.h בקבצים רבים בפרויקט. כל שינוי בקובץ A.h יגרום לקמפול מחדש של כל הקבצים בפרויקט שביצעו לו include#, מה שמעניין הוא למה שתתבצע קומפילציה מחדש אם אנחנו משנים את החלק ה-private? שהרי ללקוח אין גישה אליו בכלל.
קרא עוד
היזהר מאופרטורי המרה אוטומטיים!
לפעמים זה יכול להיות מסוכן עבורנו להעמיס אופרטור המרה, ויכול לגרום לקוד להתקמפל כשהוא לא אמור להתקמפל.
דוגמא טובה לכך היא std::string, למה ל-std::string אין אופרטור המרה אוטומטי ל-*const char? זה נראה לגיטימי מאוד תחילה, עד שכותבים את הקוד הבא:
string s1, s2; s2 = s1 - s2; // oops I meant s1 + s2
אופס! טעיתי בסדר הפרמטרים.
לפעמים קורה שממשק מסוים מבקש מאיתנו מספר ערכים מאותו הטיפוס, ואנחנו מעבירים את הערכים בסדר ההפוך שלהם, פשוט בשגגה:
class Person
{
private:
int age_, height_;
public:
Person(int age, int height): age_(age), height_(height)
{}
};
זה נורא קל לטעות בסדר הפרמטרים כאשר מפעילים את הקונסטרקטור:
Person p(152, 50); // oops I meant Person p(50,152)
מה ניתן לעשות כדי למנוע ממצבים כאלו לקרות?
קרא עוד
מבוא קצרצר ל-Boost.
כל מתכנת C++ מנוסה שמחפש אפשרויות שונות להתקדמות ולשיפור הקוד נתקל בסופו של דבר בBoost.
Boost היא אחת הספריות הענקיות ביותר שנכתבו ב++C שכוללת פיצ'רים שונים להקלת התכנות וייעולו.
ספריות שונות בBOOST נכנסו לTR1 וככל הנראה יועברו לC++0x.
בפוסט זה אציג טעימה קטנה מBoost על מנת לעורר את חושיכם לנסות את הספריה המדהימה הזו.
הספריה מכילה עשרות "תת-ספריות" הנוגעות בנושאים כמו threading, networking, metaprogramming, serialization, smart pointers, lambda statements, ועוד המון אחרים.
בפוסט זה אסקור חלק מהנושאים שהצגתי לעיל.
כך תצמצם את גודל המבנה שלך
מהו גודל המבנה הבא:
struct Person
{
short age;
int salary;
short height;
};
אם אמרת 8 – טעית. למען האמת, זה תלוי. אם הקומפיילר לא מבצע יישור(alignment) על המבנה אז גודלו אכן כזה, אך אם כן, אז גודלו יהיה 12, פי 1.5 מסכום כל גדלי המשתנים שלו. אך אי ביצוע יישור לא תמיד משתלם(עלול לעלות בגישה איטית למשתני המבנה או בשגיאות), נראה כיצד לצמצם את גודל המבנה כשהוא מיושר.
קרא עוד
דע את הקרביים של <vector<bool!
ל-<vector<bool מימוש די שונה משאר המכולות של STL והוא עלול "לשבור" קוד ג'נרי, משום ש-<vector<bool למעשה לא עונה על כל האלמנטים של מכולת STL לפי הסטנדרט.
אם ננסה לקמפל את הקוד הבא:
vector<bool> v; v.push_back(true); bool* p= &v[0];
להפתעתנו נקבל שגיאת קומפילציה שלא ניתן להמיר את הערך ש[v[0& מחזיר לערך מטיפוס *bool. מה שנראה די תמוה מכיוון אנחנו מתעסקים עם וקטור של בוליאנים. השגיאה שהתקבלה ב:Visual Studio 2008
error C2440: 'initializing' : cannot convert from 'std::_Vb_reference<_Alloc>' to 'bool *'