מחשבות, מחשבים, ושאר דברי בלע

IP2C היא ספריה קטנה למציאת קוד המדינה אליה שייכת כתובת IP.
הספרייה מכילה נכון לכרגע מימוש בPHP ובג'אווה, וכוללת ומבוססת על המרת הנתונים לקובץ בינארי קומפקטי שמתוכנן לחיפוש מהיר.
בסיס נתונים של נתוני IP למדינה זה דבר די גדול, בסיס הנתונים החינמי של WHI שמגיע כקובץ CSV מכיל כ77000 טוחי כתובות (הטווח מכתובת X לכתובת Y שייך למדינה C) ובסיסי נתונים אחרים הם הרבה יותר גדולים.
כשרוצים לחפש בדבר כזה יש כמה אפשרויות:
1. העלאת הנתונים לטבלא לבסיס הנתונים ושימוש בבסיס הנתונים לחיפוש.
2. המרה של קובץ הCSV לקובץ בינארי חסכוני ואז חיפוש בקובץ. על הדרך הזו המשך הפוסט מדבר.

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

שורה בקובץ הCSV המקורי מכילה תחילת טווח, סוף טווח, ומידע לגבי הטווח - כמו קוד ISO של המדינה והשם שלה. שורה לדוגמא:
"201620312","201674095","US","USA","UNITED STATES"

נניח שאנחנו שומרים את הנתונים האלו לקובץ בצורה הזו:
לכל מדינה:
4 בתים: תחילת טווח.
4 בתים: סוף טווח.
2 בתים קודISO
X בתים שם מדינה.

יש פה בעיה, כי שם המדינה הוא לא באורך ידוע, מה שלא מאפשר גישה ישירה לנתונים (כדי להגיע לשורה X צריך לסרוק את כל השורות שלפניה).
פתרון חלופי הוא לחלק את הקובץ לשני תחומים כדלקמן:
חלק ראשון בקובץ, לכל מדינה:
4 בתים: תחילת טווח.
4 בתים: סוף טווח.
2 בתים קודISO
4 בתים ההיסט של שם המדינה בתוך הקובץ
חלק שני בקובץ, לכל מדינה:
X בתים: שם המדינה.

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

נניח שאלו הנתונים שלנו:
1. 1 עד 10 : ישראל
2. 10 עד 20: הודו
3. 20 עד 22: סין
4. 25 עד 30: ארצות הברית

אפשר לשים לב שלמעט המעבר מסין לארצות הברית טווח n תמיד מתחיל איפה שטווח n-1 נגמר.
ככה זה גם במציאות, כמעט תמיד אין חורים בין הטווחים.
זה מאפשר לנו ליעל את צורת השמירה: פשוט נשמור רק את תחילת הטווח של כל שורה, ונשתמש בתחילת הטווח של השורה הבאה בתור סמן לסוף הטווח.
אבל אני שומע את הצעקות: אבל מה עם סין? היא תקבל עוד שלוש כתובות!
הפתרון הפשוט למדי הוא להוסיף שורת סרק אחרי סין, שסוגרת את הטווח שלה:
1. 1 : ישראל
2. 10: הודו
3. 20 : סין
4. 22: אף אחד
4. 25 : ארצות הברית
…
חסכנו בממוצע 4 בתים מתוך 14, שזה כשלושים אחוז מנפח הנתונים, בלי לאבד שום דבר.
כמובן שהאלגוריתם של החיפוש יצטרך להתחשב בשורות ששייכות ל"אף אחד", מה שיסבך אותו, אבל זה שווה את המחיר.

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

למעשה הקובץ שIP2C מייצרת אפילו יותר חסכוני מזה, החלק הראשון של הקובץ מכיל שורות בצורת:
IP התחלה: 4 בתים.
קוד מדינה: 2 בתים.

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

גישה לנתונים

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

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

קובץ ממופה זכרון
קובץ ממופה זכרון (Memory mapped file) לוקח את הטוב משני העולמות. מצד אחד לא טוענים את כל הקובץ לזכרון, מצד שני המהירות קרובה למהירות חיפוש בזכרון.
PHP לא תומך בזה, אבל ג'אווה כן - וקיבלתי תוצאות יפות למדי עם זה.
היתרונות הם שכמו בחיפוש ישירות על הקובץ, לא טוענים את כל הקובץ לזכרון בהתחלה ולכן החיפוש הראשון יהיה מהיר בערך כמו החיפוש הראשון בחיפוש ישיר על הקובץ, אבל החיפושים הבאים יתקרבו למהירות חיפוש בזכרון. החיסרון העיקרי הוא שלא כל הפלטפורמות תומכות בזה.
מימוש: Java בלבד.

זכרון משותף
זכרון משותף (Shared memory) היא עוד גישה. הפעם הקובץ נטען פעם אחת ויחידה לזכרון, ונשאר שם. הגישה הזו מנטרלת את הבעיה המרכזית של PHP עם הגישה של טעינת הקובץ לזכרון (שצריך לטעון אותו כל פעם מחדש), אבל עדיין סובלת מהבעיה של צריכת זכרון גבוהה (למעשה הבעיה מחריפה גם הזכרון יהיה בשימוש גם אם אף אחד לא רוצה לבצע חיפוש במשך שבוע).
גם PHP וגם Java תומכים בזכרון משותף, אבל לא בדקתי את הביצועים של מימוש כזה.
מימוש: לא ממומש.

IP2C משוחררת ברשיון GPL2, והיא קלה מאוד לשימוש.

בשעה טובה, שחררתי את FireStats 1.3.0-beta.
בין השינויים המשמעותיים בגרסא:

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

ועוד.

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

נתקלתי:
מרטין פואלר בהרצאה קצרה ומעניינת על שפות תחום (Domain Specific Languages : DSL).

לפני יותר משלוש שנים פתחתי פרוייקט בשם JWebcam בסורס-פורג'.
הפרוייקט היה הנסיון הראשון שלי לכתוב פרוייקט קוד פתוח, והיה מערכת שרת/לקוח להזרמת וידאו ממצלמת רשת.
התחלתי לפתח אותו אחרי שלא הייתי מרוצה מהאלטרנטיבות שהיו בזמנו.
הפרייקט היה נחמד, וכלל פונקציות נחמדות כמו זיהוי תנועה, הזרמת וידאו על גבי HTTP ויכולת לתמוך בכמה מצלמות שמשדרות לאותו שרת.
וברגע שעברתי לעבודה על לינוקס הפסקתי סופית את הפיתוח שלו, כי לא היה לי מספיק זמן לברר מה השינויים שאני צריך לעשות כדי לשאוב נתונים מהמצלמה תחת לינוקס.
לפני כשבוע פנה אלי schwarzer_peter שרצה להחיות את הפרוייקט; הוא התחיל לפתח משהו דומה וכשהוא ניסה לרשום אותו בסורס-פורג' - כנראה תחת אותו שם, הוא גילה שתפסתי את השם.
אחרי קצת אימייל-פונג החלטנו שהוא יקבל הרשאות מנהל ומנדט לעשות ככל העולה על רוחו, ושאני אייעץ ואעזור לו להתממשק אל הקוד שכבר כתבתי.
הוא פתח בלוג וורדפרס חביב לפרוייקט, ונראה שהוא עובד די במרץ.
כיף לראות שאחרי שלוש שנים מישהו מוצא שימוש לקוד שכתבתי ושהפרוייקט מתעורר.

בחיפושי אחרי ווידג'ט לוח שנה שישמש לבחירת תאריכים בFireStats נתקלתי בדבר החמוד להפליא הזה.
מדובר ברכיב לוח שנה שכתוב בג'אווה-סקריפט, שמאפשר בחירת תאריכים נוחה ומגניבה.
הרכיב גמיש מאוד, מתאים לכל הדפדפנים הפופלריים, מתורגם למספר שפות וקל מאוד להטמעה בתור פופ-אפ או ישירות בתוך הדף.
בנוסף, הוא ברשיון נוח (LGPL).

הנה תמונה (התעצלתי לשלב את הדבר האמיתי):

מבחן אישיות נחמד למתכנתים.
אני יצאתי:

Doer.
You are very quick at getting tasks done. You believe the outcome is the most important part of a task and the faster you can reach that outcome the better. After all, time is money

High level.
The world is made up of objects and components, you should create your programs in the same way.

Solo situation.
The best way to program is by yourself. There’s no communication problems, you know every part of the code allowing you to write the best programs possible.

Conservative programmer.
The less code you write, the less chance there is of it containing a bug. You write short and to the point code that gets the job done efficiently.

היסטורית, מפתחי PHP תמיד היו מקופחים.
בזמן שמפתחים לשפות אחרות נהנו מסביבות פיתוח מתקדמות, עם יכולות דיבאג (נקודות עצירה, בדיקת ערכי משתנים בזמן ריצה ועוד), השלמת קוד תלויית הקשר ועוד, הרוב המכריע של מפתחי הPHP השתמשו בעורכי טקסט פשוטים יחסית (ואני לא מזלזל בVIM ובEmacs).
את FireStats התחלתי לפתח כאשר לא ידעתי כמעט כלום על PHP, ובוודאי שלא ידעתי על סביבות הפיתוח המומלצות לפיתוח בPHP, כך שהתחלתי את הפיתוח בשימוש בVIM ישירות על שרת הפיתוח שלי (המחשב בסלון), והייתי מרוצה מהתוצאות.
לפני מספר חודשים נתקלתי בMylar, שאיפשר לי התממשקות נוחה למערכת ניהול הבאגים של FireStats, שעובדת על trac.
החלטתי שזה שווה את המאמץ של המעבר, והתחלתי לחפש פתרון PHP לEclipse.
בהתחלה מצאתי את PHPEclipse, פלאגין שעובד די טוב, אבל כמה באגים עיצבנו אותי, ושמתי לב שהפרוייקט די רדום, אז נטשתי אותו לטובת PDT שמפותח כתוסף רשמי של פלטפורמת Eclipse, בעיקר על ידי מפתחים של Zend.

PDT נמצא כרגע במצב די טוב, יש כמה באגים קטנים אבל הפרוייקט חי ומשחרר גרסאות חדשות כל כמה חדשים.
ההשלמה האוטומטית עובדת יפה מאוד, גם בהקשר של PHP, גם בהקשר של HTML ואפילו בהקשר של CSS וJavaScript.
בנוסף, במאמץ קטן יחסית ניתן לאפשר דיבוג באמצעות xdebug מתוך Eclipse (!), ממש סוף הדרך.

עבודה עם PDT:

דיבאג עם PDT:

בונוס למגיב הראשון שיספר מה עושה הפונקציה fs_sum_search_tree.

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

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

הטקסט שלמעלה הוא טקסט בשפה של קבצי Properties בג'אווה.
לא קשה לכתוב קוד בסיסי שמפענח אותו (נעזוב לרגע את זה שלא צריך לכתוב כזה כי המחלקה Properties יודעת לקרוא את זה):

פשוט מספיק, נכון?
אבל השפה מכילה גם הערות, שאפשר שאפשר לציין באמצעות סימן #. כל מה שאחרי ה# מוגדר כהערה.
הקוד הקודם לא מתמודד עם זה - ולמרות שזה לא מסובך במיוחד להוסיף את זה, זה טיפה יותר קשה ממה שזה נראה במבט ראשון כי יש כל מני מקרים:
* האם ההערה היא בתחילת השורה? (מתעלמים מכל השורה).
* האם ההערה היא בסוף השורה? (השורה מכילה זוג ערכים וגם הערה).
עוד דבר אפשרי הוא לשבור שורה באמצע:

פה יש רק ערך אחד לפי החוקים של השפה.

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

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

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

בגדול, יש חלוקה כזו:
חלק ראשון הוא המנתח הלקסיקלי, שמקבל זרם תווים, ומוציא זרם של לקסמות, הידועים גם כאסימונים (Tokens). האסימונים מוגדרים באמצעות ביטויים רגולריים (שפה דומה לשפה שמשמשת את grep).
חלק שני הוא המנתח התחבירי, שמקבל זרם של אסימונים מהמנתח הלקסיקלי, ומוציא עץ תחביר אבסטרקטי (Abstract syntax tree).
יש כלים שיודעים לקבל הגדות לקסיקליות ותחבירות, ולייצר מזה בצורה אוטומטית קוד שיודע לפענח קלט בשםה הנתונה. למעשה, הטכניקה המקובלת לכתיבת קומפיילרים כבר עשרות שנים מתבססת על כלים אוטומטיים כאלו.
את הPreprocessor של אנטנה כתבתי תוך שימוש בantlr, שהוא כלי כזה שכתוב בג'אווה, אבל יודע לייצר קוד במגוון שפות, ובקורס קומפילציה שאני לוקח כרגע בפתוחה לומדים להשתמש בכלים הקלאסיים - flex וbison.
לדעתי antlr הרבה יותר סימפטי לעבודה.

אם תהיה דרישה אני ארחיב עוד בנושא.

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

בעיית רשת מוזרה מספר 1:

BattleField 2142, משחק רשת מרובה משתתפים עובד היטב, עד שיום בהיר אחד הוא מפסיק לראות שרתים ברשת.
פניתי לתמיכה של EA, שהציעו להסיר ולהתקין מחדש, תוך מחיקה של כל רמז לספריות נוספות שהמשחק שומר (במילים אחרון, אין להם מושג והם יורים באפלה).
עקבתי אחרי ההוראות, וכמובן שהבעיה לא נפתרה.
בצר לי, הורדתי את WireShark (לשעבר Ethereal), שהוא Network sniffer רב עוצמה, והפעלתי אותו לפני ההפעלה של המשחק.

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

בעית רשת מוזרה מספר 2:

Call of duty 2, עוד משחק רשת משובח, עובד היטב ברשת המשרדית, עד שיום בהיר אחד הוא מפסיק לראות שרתים אחרים.
במילים אחרות, עמרי לא יכול להצטרף לשרתי המשחק ברשת, ונאלץ לעבוד בעבודה.
לאחר הטחת האשמות סרק ברשת, בסוויץ' במערכת הפעלה ובאלוהים, הפעלתי את WireShark על שני מחשבים, אחד בו אין בעיה, וזה שלי.
לאחר שהפעלתי את המשחק בשניהם, בחנתי את תעבורת הרשת, וגיליתי את הדבר הבא:
המשחק שולח בBroadcast פקטת UDP לכל הרשת כשהוא מחפש שרתים, והשרתים אמורים לענות לו ולמסור לו מידע על עצמם. (כדי לשלוח Broadcast צריך לשלוח את הפקטה לכתובת 255.255.255.255).
עד פה הכל טוב, רק שראיתי משהו מוזר במחשב שלי. במקום לצאת מכתובת הIP הרגילה שלי הוא יצא מכתובת IP אחרת, שבכלל לא נראית כאילו היא ברשת הפנימית שלנו.
מסתבר שהכתובת הנ"ל (192.168.40.1) שייכת למתאם רשת וירטואלי של VMWare, ומסיבה עלומה המשחק שלח את חבילת הUDP כאשר הכתובת של המתאם היא כתובת המקור של החבילה. השרת ניסה לענות, אבל מכיוון שהכתובת לא ברשת לא קיבלתי את התשובה.
אחרי ביטול של מתאמי הרשת של VMWare הבעיה נפתרה.

בעיית רשת מוזרה מספר 3:

תוכנה שאנחנו מפתחים בעבודה מקבלת זרם של חבילות UDP משרת.
התוכנה עובדת טוב מול שרת אחד, ומאוד לאט מול שרת שני, שני השרתים מריצים את אותה תוכנה בדיוק.
הפעלה של WireShark על השרת והמכונה שמריצה את הלקוח מראה שהשרת שולח את החבילות בקצב הנכון, והחבילות מגיעות למכונת היעד באותו קצב, ובכל זאת לאפליקציית הלקוח החבילות מגיעות מאוד לאט.
הלקוח רץ על WTK, שהוא אמולטור של סביבות ג'אווה של פלאפונים. לWTK יש כלי Profiling פנימי, שמאפשר להגיד איפה האפליקציה משחיתה את זמנה.
הפעלתי את הפרופיילר, והסתבר שהיא משחיתה את מיטב זמנה בפונקציית מערכת בשם getHostByName.
תפקידה של הפונקציה הזו הוא בעצם לקבל כתובת שמית ולהמיר אותה לכתובת IP מספרית, במילים אחרות - לקרוא לDNS.
מסיבה לא ברורה הפונקציה לקחה הרבה זמן, ומסיבה לא ברורה היא נקראה עבוד כל חבילת UDP שהגיעה לאמולטור (באג באמולטור לדעתי, אבל שיהיה).
לחלונות יש קובץ בשם hosts בספריית החלונות, שדומה מאוד לאותו קובץ במערכות יוניקס (זה מראה על הקשר בין חלונות ליוניקסים), הקובץ משמש להוספה ידנית של רשומות לDNS המקומי.
ברגע שהוספתי את כתובת הIP של השרת לקובץ ההוסטים הבעיה נפתרה.

עד כאן פינתנו, בעיות רשת מוזרות.