ארכיון עבור הקטגוריה Java

« לרשומות הקודמות
20 02 2010

חלון מהיר

נכתב על ידי עמרי בנושא Java, אלגוריתמים, קוד פתוח

לפני כמה פוסטים שאלתי את השאלה הבאה:

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

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

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

private static int [][][] buildgrid(byte[][] image, int width, int height, int gridSize)
{
    int grid[][][] = new int[width / gridSize][height / gridSize][];
    // count the number of points in each grid cell
    int numpoints[][] = new int[width / gridSize][height / gridSize];
    for(int x=0;x<width;x++)
    {
        for(int y=0;y<height;y++)
        {
            if (image[x][y] > Byte.MIN_VALUE)
            {
                numpoints[x/gridSize][y/gridSize]++;
            }
        }
    }
   
   
    for(int x=0;x<width;x++)
    {
        for(int y=0;y<height;y++)
        {
            int c = image[x][y];
            if (c > Byte.MIN_VALUE)
            {
                int gy = y/gridSize;
                int gx = x/gridSize;
                int list[] = grid[gx][gy];
                if (list == null)
                {
                        int np = numpoints[gx][gy];
                    list = new int[np * 2];
                    grid[gx][gy] = list;
                    numpoints[gx][gy] = 0;
                }
               
                list[numpoints[gx][gy]++] = x;
                list[numpoints[gx][gy]++] = y;
            }
        }
    }
    return grid;
}

הקוד הבא סופר את המספר הנקודות בתוך החלון שמרכזו (x,y)’ שימו לב שהלולאות עוברות על ארבעה ריבועים בגריד בלבד:

// window boundaries:
int rx1 = x – grid_size/2;
int ry1 = y – grid_size/2;
int rx2 = rx1 + grid_size;
int ry2 = ry1 + grid_size;

// top left grid cell (out of 2×2 group to be checked)
int gx = rx1 / grid_size;
int gy = ry1 / grid_size;

for(int grid_x=gx;grid_x<gx+2 && grid_x >= 0 && grid_x < gwidth;grid_x++)
{
    for(int grid_y=gy;grid_y<gy+2 &&  grid_y >= 0 && grid_y < gheight;grid_y++)
    {
        int list[] = grid[grid_x][grid_y];
        if (list == null) continue;
        for(int i=0;i<list.length/2;i++)
        {
            int jj = i*2;
            int dx = list[jj];
            int dy = list[jj+1];
            if (dx >= rx1 && dx < rx2 && dy >= ry1 && dy < ry2)
            {
                c++;
            }
        }
    }
}

יתכן שאפשר לשפר את הביצועים אם נחלק את הגריד לריבועים יותר קטנים ונכלול ריבועים שלמים שנופלים בתוך החלון בלי לבדוק כל נקודה באופן פרטני, אבל לא ניסיתי.
הביצועים של הפתרון הזה די מטורפים. על Q6600 במהירות 2.4GHZ, עם תמונה בגודל 500X500 פיקסלים וחלון של 20X20, בדיקה של כמה זמן לוקח לספור את הפיקסלים בכל 250,000 החלונות האפשריים לקחה כ160 מילישניות, מה שנותן מהירות בדיקה של מעל 1500 חלונות במילישניה (או יותר ממליון וחצי חלונות בשניה), בלי תלות בגודל התמונה שנבדקת (על תמונה של 1000X1000 המהירות היתה דומה).

האפלט הבאה מדגימה את האלגוריתם. אפשר להוריד אותה מפה. הקוד כלול בתוך הJAR (אפשר לפתוח את הJAR עם תוכנה לפתיחת קבצי ZIP).
בנוסף, האפלט יכולה לרוץ כתוכנית רגילה : java -jar fast_window.jar
אפשר ללחוץ בתוך האפלט כדי לסמן את הנקודות בחלון.


הדפדפן שלך לא תומך בג’אווה, ככה האפלט ניראית (רק שהיא אינטראקטיבית) :


Comments 10 תגובות »

25 01 2010

JNotify 0.92

נכתב על ידי עמרי בנושא Java, לינוקס, קוד פתוח

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

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

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

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

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

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

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

JNotify התעורר.

Comments 13 תגובות »

17 01 2010

חיבור לתהליך ג’אווה מרוחק עם VisualVM למחשב שמוגן על ידי פיירוואל

נכתב על ידי עמרי בנושא Java, קוד פתוח

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

  • jps : מראה תהליכי ג’אווה
  • jstack : מציג את רשימת הת’רדים בתהליך ג’אווה, ומה כל אחד מהם עושה.
  • jmap: מאפשר שמירה לקובץ של תמונת הזכרון (heap dump) של תהליך ג’אווה. אפשר לבחון את הקובץ עם jhat או עם VisualVM.
  • jhat : מאפשר ניתוח קבצי heap dump שנוצרו בעזרת jmap.
  • jconsole : ממשק פשוט שמאפשר בחינה של שימוש הזכרון, שימוש בזמן מעבד ועוד.
  • visualvm: כלי חזק יותר מjconsole, שהחל מעדכון 18 של JDK 1.6.0 מגיע עם הJDK. ויז’ואל VM מאפשר גם ניתוח ביצועים פשוט (cpu and memory profiling).

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

VisualVM

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

על המחשב המרוחק:

1. צרו קובץ permissions.txt שיכיל את זה:

grant {
permission java.security.AllPermission;
};

2. הריצו את jstatd (שמאפשר לתהליכים מרוחקים לקבל רשימה של מכונות ג’אווה שרצות על המכונה ולהתחבר אליהן) :

jstatd -J-Djava.security.policy=permissions.txt

3. הריצו את התוכנית שלהם עם הפרמטר הבא:

java -Dcom.sun.management.jmxremote MainClass

על המחשב המקומי:

1. צרו תעלות SSH לשרת כך:

ssh -D9696 -L1101:localhost:1099 your_server

שימו לב שיש פה שתי ‘תעלות’:

  • תעלת TCP מ1101 אל 1099 בשרת המרוחק. זו תעלה שמאפשרת להתחבר אל הjstatd ישירות.
  • פרוקסי SOCKS5 שמאזין על פורט 9696

2. הפעילו את visualvm עם הפרמטרים הבאים :

visualvm -J-Dnetbeans.system_socks_proxy=localhost:9696 -J-Djava.net.useSystemProxies=true

שאומרים לו להשתמש בפרוקסי SOCKS5 שהקמנו.

3. מתוך VisualVM, הוסיפו לחיבור המקומי חיבור לjstatd בפורט 1101.

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

Comments 2 תגובות »

01 12 2009

Java with authenticated urls

נכתב על ידי עמרי בנושא Java

התקן של HTTP כולל קביעה של שם משתמש וסיסמא ישירות בURL, למשל:

http://user:password@site.com/file.txt

מסיבה לא ברורה, ג’אווה לא מסתדר עם URLים כאלו ונראה שהוא לא מעביר את שם המשתמש והסיסמא לאתר.
הנה פתרון לעניין (עקום אך גנרי) :

Authenticator.setDefault(new Authenticator()
{
    @Override
    protected PasswordAuthentication getPasswordAuthentication()
    {
        URL url = getRequestingURL();
        String userInfo = url.getUserInfo();
        String user;
        String password;
        int i = userInfo.indexOf(‘:’);
        if (i == -1)
        {
            user = userInfo.substring(0);
            password = “”;
        }
        else
        {
            user = userInfo.substring(0, i);
            password = userInfo.substring(i+1);
        }
        PasswordAuthentication ps = new PasswordAuthentication(user, password.toCharArray());
        return ps;
    }
});

עוגיה למי שסביר למה המימוש הסטנדרטי של ג’אווה לא תומך בדבר הטריויאלי הזה.

Comments 4 תגובות »

27 11 2009

protobuf

נכתב על ידי עמרי בנושא Java, קוד פתוח, תכנות

לפני קצת יותר משנה גוגל שחררו ברשיון קוד פתוח פרוייקט בשם Protocol Buffers, ובקיצור protobuf.
protobuf מגדיר שפה להגדרת מבני נתונים (IDL), ויודע לייצר קוד יעיל שקורא וכותב את אותם מבני נתונים בC++, JAVA או פייתון.
יש תמיכה חיצונית לפורמט בשפות נוספות, C#, D, רובי PHP* ועוד.
הדוגמאות שאני אתן יהיו בג’אווה, אבל השתמשתי בו גם עם C++ והוא עובד היטב גם שם.
כל מפתח מגיע מתי שהוא לשלב שבו תוכנית שהוא כותב צריכה להעביר נתונים לתוכנית אחרת (או למופע אחר של עצמה) דרך הרשת, או לשמור נתונים לקובץ כדי לקרוא אותם אחר כך.
מקובל לקודד את הנתונים בתוך הודעות, כשיש הרבה מאוד דרכים לכתוב את ההודעות, ובדרך כלל מדובר בקוד די סיזיפי שחוזר על עצמו וכתיבתו היא די משעממת (בפעם העשירית שעושים משהו כזה).
נניח שאנחנו רוצים להעביר אובייקט שמייצג אימייל על גבי הרשת (ונתעלם רגע מהפרוטוקולים המקובלים להעברת אימיילים).
לאובייקט אימייל שלנו יש שדה של שולח, אחד או יותר שדות של מקבלים, נושא, טקסט, ואפס או יותר קבצים נלווים ואפילו עדיפות.
אפשר לייצג אותו במבנה הלוגי הזה:

package messages;
message Email
{
        enum Priority
        {
                LOW = 1;
                NORMAL = 2;
                HIGH = 3;
        }

        required string from = 1;
        repeated string to = 2;
        required string subject = 3;
        required string message = 5;
        repeated Attachment attch = 4;
        optional Priority priority = 6;
        optional string date = 7;

        message Attachment
        {
                optional string data = 1;
                required string name = 2;
        }
}

מה שיש לנו פה זה הגדרת הודעה תקינה בשפת הIDL של protobuf.
השפה תומכת בהגדרת חבילה (שמתורגמת לpackage בג’אווה ולnamespace בC++), וכן בהגדרות מקוננות של הודעות.
המספרים אחרי כל שורה נקראים טאגים ומשמשים לזיהוי של השדות בפרוטוקול הבינארי, ולכן אחרי שהם נקבעים אי אפשר לשנות אותם.
אפשר לראות שהשפה תומכת בהגדרה של enum, וכן ברשימות של אובייקטים (שיכולים בעצמם להכיל אובייקטים וכן הלאה).
חוץ מטיפוסים שאתם מגדירים, השפה תומכת גם בטיפוסים פנימיים למשל מחרוזת, משתנה בוליאני, מספר ברוחב קבוע (למשל ארבעה בתים), מספר ברוחב משתנה ועוד.
המספרים ברוחב משתנה מקודדים בצורה דומה קצת לקידוד של UTF8, אבל בצורה קצת יותר פשוטה:

הביט השמאלי (MSB) בכל בייט מוגדר כך: 1 אם המספר המועבר כולל בייטים נוספים, או 0 אם זה סוף המספר.
7 הביטים האחרים בכל בייט משמשים להעברת 7 ביטים של המספר עצמו. בצורה כזו, מספרים קטנים מ128 יתפסו בייט אחד בלבד, מספרים קטנים מ65000 בקירוב יתפסו שני בתים וכן הלאה. אם התוכנית שלכם מעבירה מספרים קטנים שיכולים להיות גדולים לעיתים נדירות – הקידוד הזה הוא אידיאלי כי בדרך כלל המספרים לא יתפסו הרבה מקום, בניגוד לקידוד ברוחב קבוע שבו כל מספר תופס למשל ארבעה בתים.

חלק מהטיפוסים הנתמכים בשפה הם ברוחב קבוע, למשל מספרים בנקודה צפה (Floating point) ושלמים שמוגדרים כFIXED, למשל FIXED64 יהיה תמיד 64 ביטים או 8 בתים.
עוד על השפה אפשר לקרוא פה.

את הקובץ שמכיל את הגדרת ההודעות “מקמפלים” עם protoc, שמייצר ממנו קוד בג’אווה C++ או פייתון:

$ protoc messages.proto –java_out src/

הנה דוגמא לקוד ג’אווה שמייצר הודעה, כותב אותה לקובץ, קורא אותה ומדפיס אותה בפורמט טקסטואלי:

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;

import test.Messages.Email;
import test.Messages.Email.Attachment;
import test.Messages.Email.Builder;

class Test
{
    public static void main (String args[]) throws FileNotFoundException, IOException
    {
        Builder b = Email.newBuilder();
        b.addTo(“test@abc.com”);
        b.addTo(“test@loogle.com”);
        b.setFrom(“someone@there.com”);
        Attachment aa = Attachment.newBuilder().setName(“viruts.exe”).build();
        b.addAttch(aa);
        b.setSubject(“A present for you”);
        b.setMessage(“Please open the attached Virus”);
        Email email = b.build();
        System.out.println(email.toString());
        FileOutputStream out = new FileOutputStream(“email.dat”);
        email.writeTo(out);
        out.close();

        System.out.println(Email.parseFrom(new FileInputStream(“email.dat”)));
    }
}

נקמפל ונריץ:

$ javac -cp lib/protobuf-java-2.2.0.jar src/Test.java src/test/Messages.java
$ java -cp lib/protobuf-java-2.2.0.jar:src Test
from: “someone@there.com”
to: “test@abc.com”
to: “test@loogle.com”
subject: “A present for you”
attch {
  name: “viruts.exe”
}
message: “Please open the attached Virus”

אפשר לראות שבמפתיע הפלט הטקסטואלי הוא כמעט קובץ Swush תקני, אני נשבע שלא הסתכלתי עליו כשהגדרתי את Swush :)
זו דוגמא לשימוש בprotobuf בג’אווה, השימוש בC++ בשפות אחרות פשוט בצורה דומה.
כל העניין מאוד קל לשימוש, ואני ממליץ מאוד לכל מי שצריך לכתוב אובייקטים לקובץ או לרשת לבדוק את protobu.
אגב, הקוד המחולל נראה טוב מאוד, כמעט כאילו כתבתם אותו בעצמכם.

* PHP : הספריה לתמיכה בPHP היא pb4php, והיא לא מאוד מוצלחת. למרות שיתכן שבקרוב הפרוייקט יקבל PATCH משמעותי שהופך את הספריה ליותר שמישה (לפחות לצרכים שלי).

Comments 5 תגובות »

01 10 2009

Java singleton – the next generation

נכתב על ידי עמרי בנושא Java

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

public class EmailSender
{
        private static EmailSender s_instance;
       
        private EmailSender(){} // private constructor
       
        public static synchronized EmailSender getInstance()
        {
                if (s_instance == null)
                        s_instance = new EmailSender();
                return s_instance;
        }
       
        public void sendEmail(String recepient, String subject, String text)
        {
                // …
        }
}

כדי להשתמש בסינגלטון ככה:

EmailSender.getInstance().sendEmail(…);

כמה דברים לשים אליהם לב:
* יש בנאי פרטי, כדי למנוע מכל מני גורמים “לא מוסמכים” לאתחל עותק משל עצמם של הסינגלטון.
* הפונקציה getInstance צריכה להיות מסונכרנת כדי למנוע מצב שבו שני ת’רדים שונים ניגשים במקביל לפונקציה וגורמים לאיתחול של שני אובייקטים במקום אחד.

עד כאן, טרויאלי לכל מי שכתב תוכנה בג’אווה.
הפוסט הזה הוא על דרך אלטרנטיבית לכתיבת סינגלטון, והרי היא:

public enum EmailSender
{
        instance;
       
        public void sendEmail(String recepient, String subject, String text)
        {
                // …
        }
}

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

EmailSender.instance.sendEmail(…);

אלגנטי, לא?

Comments 10 תגובות »

30 05 2009

Google Wave

נכתב על ידי עמרי בנושא Java, אינטרנט, קוד פתוח, תכנות

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

וויב

  • אפשרות לפצל שיחה לכמה קווי שיחה בקלות (Threads)
  • צ’אט חי, כמו בימי הבבסים (רואים מה האדם השני מקליד בזמן שהוא מקליד).
  • אפשרות לחבר אדם נוסף לשיחה בדיעבד על ידי הוספה שלו למשתתפים, הוא יוכל לראות את השיחה מההתחלה, כולל באמצעות מצב ניגון שמנגן את השיחה בשבילו צעד אחר צעד כאילו הוא השתתף בה מההתחלה.
  • אפשרות להגביל גישה להודעות למשתתפים מסויימים (מסרים פרטיים)
  • תמיכה בגרור וזרוק כדי להצמיד תמונות (וקבצים באופן כללי) להודעות, נכון לכרגע זה דורש גוגל gears, אבל הכוונה היא לדחוף את היכולת הזו בהצעה לHTML 5.
  • אפשרות לשתול שיחה בקלות בתוך בלוג (Embed), מכיוון שהשיחה מאוכסנת בשרת מרכזי זה לא משנה אם מגיבים מהבלוג אם מתוך Wave, היא תשאר שיחה אחת.
  • כל שיחה יכול להיות בעצם מסמך משותף שכל המשתתפים תורמים לו, בדומה לוויקי, כולל פיצול ואיחוד של גרסאות (Branch and merge), כולל עריכה חיה (כמו הצ’אט החי) על ידי כמה משתתפים במקביל.

הרחבות

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

פרוטוקול

  • ההצלחה של אימייל נובעת מכך שהפרוטוקול פתוח וכל אחד יכול להריץ שרת דואר שידבר עם כל שרת דואר אחד בפרוטוקול SMTP, שמוגדר היטב וברור לכל.
  • וויב יעבוד בצורה דומה. הפרוטוקול יהיה פתוח, ובנוסף גוגל ישחררו את כל הקוד של השרת כדי לאפשר לכל אחד שרוצה להריץ שרת וויב שידבר עם שרתי וויב אחרים בצורה שקופה למשתמשים (כמו Jabber).

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

מחכה בקוצר רוח שהדבר הזה יבשיל, יהיה טעים.

Comments 16 תגובות »

19 05 2009

שימוש חכם בזכרון כדי להאיץ גישה לנתונים

נכתב על ידי עמרי בנושא Java, תכנות

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

SELECT a,b,c FROM TABLE WHERE id IN (….)

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

הרעיון הבא שלי היה לשמור את הנתונים המעניינים על הדיסק בצורה בינרית, ממויינים לפי שדה הid, כאשר הפורמט הוא פשוט רשומה אחרי רשומה.
ברגע שכל הנתונים בקובץ, אפשר לטעון אותו לזכרון פעם אחת, ולבצע עליו חיפוש בינארי זריז כדי למצוא כל רשומה.
רעיון פשוט, אבל המימוש נתקל בכמה קשיים:
נפח הנתונים המעניינים במקרה שלי הוא כ14.4 ג’יגה בייטים, כל רשומה שוקלת 24 בתים, ויש 600 מליון רשומות כאלו.
אין הרבה מחשבים שמסוגלים להעלות כזו כמות של מידע לזכרון, בהתחלה חשבתי שנתונים ישקלו “רק” 12 ג’יגה, ולכן היה ישים לטעון את כולם לזכרון של שרת עם 16GB זכרון, אבל 14.4 ג’יגה זה כבר גבולי מדי.
בעיה נוספת היא שג’אווה, השפה בה אני מממש את העניין – לא תומכת במערכים גדולים מכ2 מילארד איברים (גם לא בJVM של 64 ביט), ולכן מערך הבייטים הגדול ביותר שאני יכול ליצור לא מספיק גדול בשביל להחזיק את הקובץ בזכרון.

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

בבדיקה ביצועים ראשונית יצרתי קובץ מ26 מיליון רשומות, וחיפשתי בתוכו 2 מיליון רשומות. הקצב היה קרוב למיליון רשומות בשניה, מה שאומר שהבעיה נפתרה.

ניצחון.

Comments 16 תגובות »

15 05 2009

midp-build

נכתב על ידי עמרי בנושא Java, קוד פתוח

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

The midp-build system is a generic build system for mobile java applications developed in Eclipse. it uses the Eclipse configuration files (.classpath files) to determine project dependency, build order and build classpath automatically.

it can build any MIDlet with very little configuration.

  • The system supports complex builds with multiple outputs, for example – it’s possible to build for several products, configurations and devices in a single run.
  • The build fully support preprocessing of source code based on symbols that are defined per devices, products and configurations (or almost any combination of those).
  • The build allow fine customization of the properties contained in the JAD for each JAR+JAD pair generated.
  • The build supports signing of generated MIDlets automatically
  • The build supports including classpath resources in the generated JAR(s), and/or copying specific resources
  • The build supports local builds, based on files on the workspace (without changing them in any way).
  • The build fully supports CVS and have some untested support for SVN
  • The build supports multiple build configurations per Eclipse project (see conf.prefix)

Comments תגובה אחת »

25 04 2009

Swush

נכתב על ידי עמרי בנושא Java, קוד פתוח

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

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

ניקח לדוגמא את פיסת הXML הבאה (קוד אמיתי מההגדרות של טומקט):

<ResourceParams name=“UserDatabase”>
      <parameter>
        <name>factory</name>
        <value>org.apache.catalina.users.MemoryUserDatabaseFactory</value>
      </parameter>
      <parameter>
        <name>pathname</name>
        <value>conf/tomcat-users.xml</value>
      </parameter>
    </ResourceParams>

הרבה מלל כדי להגיד שיש דבר כזה UserDatabase, ויש בתוכו שני זוגות Key-value, לא?
אפשר גם לציין את אותו מידע כך:

ResourceParams{
     UserDatabase{
           factory : org.apache.catalina.users.MemoryUserDatabaseFactory
           pathname : conf/tomcat-users.xml
    }
}

יותר קומפקטי ופחות פלצני.
השפה שבה השתמשתי בפעם השניה היא Swush, שפה שהגדרתי ומימשתי בסופ”ש.
Swush (סוו’ש בעברית, נראה לי שאני אדבוק באנגלית), תומכת בהערות בסגנון C/C++ וbash:

// C++ single line comment
/* C multi-
line comment*/
# Bash style comments

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

string1

“another string”

“multi
line
string”

המימוש שלי לSwush הוא בשפת ג’אווה, אבל בהחלט אפשרי שיהיו מימושים בשפות נוספות (בין אם שלי או של אנשים אחרים).
Swush תומך ברשימה פשוטה של מפתח-ערך, למשל:

host : “locahost”
port : 8080

ככה שאפשר בקלות רבה להחליף אותו קבצי properties של ג’אווה.

מבחינת הקוד, השתדלתי שהוא יהיה מה שיותר פשו לשימוש.
אפשר ליצור אובייקט Swush בכמה צורות:

Swush fromFile = new Swush(new File(filename));

Swush fromString = Swush.constructFromString(“swush:rocks”,“UTF-8″);

Swush usingCode = new Swush();
usingCode.add(new Swush(“key”,“value”));
usingCode.add(new Swush(“node”));
usingCode.getChildren(1).add(new Swush(“key2″, “value2″));

אחת הפונקציות המעניינות של המימוש שלי היא פונקציית select, שמחזירה רשימה של צמתים שמתאימים לקריטריות שצויין, לדוגמא – אם יש לנו קובץ Swush כזה:

addressbook
{
        max_size : 30

        item
        {
                phone : 123
                name : “The dude”
                address : “Multi
Line address”
        }

        item
        {
                phone : 3454
                name : “Another dude”
                address : unknown
        }
}

ואנחנו רוצים לגשת לצמתים של הItem, נוכל לעשות משהו כזה:

Swush swush = new Swush(new File(filename));
List<Swush> matchs = swush.select(“addressbook.item”);

הרשימה שחוזרת תכיל את שני הצמתים המתאימים (מסוג item שנמצאים בתוך addressbook).
Swush ממומשת עם Antlr, וההגדרה שלה מאוד פשוטה, אפשר להעביר אותה בכמה דיאגרמות:



Swush משוחררת ברשיון BSD, ואפשר להוריד אותה מפה.

Comments 35 תגובות »

« לרשומות הקודמות
FireStats icon ‏מריץ FireStats‏