Tag Archives: optimization

Antara Roy Suryo dan Donald Knuth

Siapa yang tidak kenal Roy Suryo? Meski banyak dihujat orang, ‘ahli’ telematika (dan ‘-tika -tika’ yang lain) yang satu ini pasti sudah tidak asing lagi di telinga orang Indonesia. Apalagi kalau mereka sering mengakses internet. Yeah, you’re included. After all, you read this blog post, right?

Dan siapa pula yang tidak kenal dengan Donald Knuth? Meskipun lebih asing di telinga orang Indonesia, orang yang satu ini punya masterpiece yang jauh lebih melegenda, yaitu TeX – sebuah perangkat lunak untuk penulisan publikasi – dan The Art of Computer Programming – seri buku tentang pemrograman komputer yang masih belum juga selesai -.

Lalu mengapa saya membandingkan kedua tokoh ini? Keduanya punya lahan olahan yang berbeda, umurnya berbeda puluhan tahun, khalayaknya berbeda, kharismanya berbeda, dan seterusnya dan seterusnya.

Pada penulisan artikel-artikel saya terdahulu saya menyinggung tentang optimasi pada program. Dan bisa ditebak, ada satu kutipan yang sering diambil orang kalau berbicara tentang optimasi:

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil

Kalau boleh saya terjemahkan bebas:

Kita harus melupakan, katakanlah sekitar 97% dari efisiensi yang hasilnya kecil: optimisasi prematur adalah akar dari segala kejahatan

Para pemerhati Roy Suryo selalu dengan setia mendengarkan perkataan Roy Suryo dan menangkap semua titik koma kesalahan dari sang pakar ini. Salah satunya, konon kabarnya, Roy Suryo pernah berkata bahwa “68% data di Friendster itu palsu“.

Bisa mulai terlihat kemana arah tulisan saya?

Ada dua nilai prosentase yang terlihat di sini: 97% dan 68%. Darimana keduanya? Yang jelas, cukup banyak yang mempertanyakan nilai 68%. Tapi saya nyaris tidak menemukan mereka yang mempertanyakan nilai 97% dari Pak Knuth.

Penasaran dengan ini akhirnya saya pun bertanya pada publik: I’m curious how Knuth came up with 97%. Could someone please share something about this?

Bisa ditebak, karena traffic ke website saya sedikit, tidak ada yang menjawab pertanyaan ini. Masih penasaran dengan pertanyaan ini akhirnya saya pun bertanya ke forum yang lebih besar: StackOverflow.

Jawabannya bisa ditebak… semua orang tidak tahu.

Jadi sebenarnya, antara Roy Suryo dan Donald Knuth ada persamaan yang bisa kita tarik. Bahkan kalau saya mau jujur, pernyataan Knuth jauh lebih fatal karena ditulis dalam sebuah paper yang masih dibaca sampai saat ini. Alasannya, yang meskipun bukan satu-satunya, mendasari jawaban mengapa goto statemen harus dihapus dari bahasa pemrograman. Sedangkan pernyataan Roy Suryo, sejauh yang saya tahu, hanya pernyataan informal yang diucapkan secara lisan dan akibat paling buruknya pun hanya membuat geger belantika internet Indonesia.

Mengapa itu bisa terjadi? Apa kita orang Indonesia terlalu berlebihan dalam menyikapi pernyataan Roy Suryo? Bisa dilihat dalam jawaban atas pertanyaan saya di StackOverflow bahwa pembuatan angka statistik bahkan dalam sebuah research paper bisa dimaklumi oleh banyak orang. Semua orang tahu kalau statistik itu adalah kebohongan yang paling besar. “There are three kinds of lies: lies, damned lies, and statistics.” Komik Dilbert ini menarik.

Atau jangan-jangan pondasi keilmuan kita ini sebenarnya masih banyak yang dibangun di atas prinsip-prinsip subjektif seseorang?

Atau karena kita masih menilai pernyataan seseorang dari pandangan kita terhadap orang tersebut? Kalau orang itu buruk, maka semua omongannya jadi buruk? Kalau orang itu hebat, maka semua omongannya jadi hebat?

Tambahan: mungkin malah Roy Suryo benar dengan pernyataannya bahwa blog hanya trend sesaat. Buktinya, trend saat ini kan twitter 😛

Jangan diambil hati, tulisan ini cuman guyonan karena kesel pertanyaannya tentang 97% diabaikan dan juga jangan diartikan saya pengagum Roy Suryo, aduh jangan deh. Plis, bitte, mohon, dengat sangat…

.

Java Tips: Optimizing your Map loop

Quite often, a program needs to go through all elements of a Map. Unfortunately, like a Set, a Map doesn’t have index in the data structure so you can’t just get a key of certain index or a value of certain index.

The most common practice used to iterate all elements in a Map is to get the key set and then based on the key, we can retrieve the value. The template we use for such case is something like this:

for (String k : m.keySet()) {
    Integer v = m.get(k);
   // do something with the key and value
}

This works of course, but based on quick observation, this should be not that efficient because we have to retrieve value using key for every step. It would be much better to get the key and value as a pair in the beginning. This is unfortunately less obvious and less used. The template would be something like this (of course, we need to change the generic type as properly):

for (Entry<String, Integer> e : m.entrySet()) {
    Integer v = e.getValue();
    // do something with the key and value
}

Now let’s make some tests. I use this template for the test and changing the backing object, number of iteration, and the method to get the key and value from the map (of course it’s not that real, because we only use the value and ignore the key, in which case we can use values() for better performance).

public static void main(String[] args) {
	java.util.Map<String, Integer> m = new TreeMap<String, Integer>();
	for (int i = 0; i < 500000; i++) {
		m.put(i + "", i);
	}

	List<Integer> l = new ArrayList<Integer>();

	long st = System.currentTimeMillis();

	for (String string : m.keySet()) {
		l.add(m.get(string));
	}

	System.out.println(System.currentTimeMillis() - st);
}

From my tests, I observe that the performance of the first template depends on the backing object. If we are using HashMap, the performance is less or more the same as the second template. If we are using Hashtable, the performance of the first template is about 1.5 times worse as the second template and if we are using TreeMap, the performance of the first template is more than 5 times worse as the second template. This proved my original hypotheses and we as developers should try to change our instinct to use the second template every time we encounter such problem.

UPDATE: I redo the test using nanotime and it’s just confirming my original observation.

Java Tips: Memory Optimization for String

String is a unique object in Java. The Java Specification explains several unique properties of String in Java. We might already know some of them. First, String is unique because it can be created without new keyword, like example below.

String s = "new String";

I have to mention that you can still create String object using new keyword, like this:

String s = new String("new String");

Does both statement “exactly equals”? Well, most of you also know that this is not true. The first example will try to reuse the same object whenever possible (and is correct because String is immutable) while the second will force the creation of new String object. Consider this example:

System.out.println("b" == "b");
System.out.println(new String("b") == new String("b"));

The result of first example is “true” while the second one will give “false”.

I almost certain that experienced programmer will never create String using new in normal use. But sometime, we are forced to use that. One case that I can think of is when you parse an XML file using SAX parser.

public class Reader extends DefaultHandler {

    private List<String> listString = new ArrayList<String>();

    public void characters(char[] ch, int start, int length) throws SAXException {

        String content = new String(ch, start, length);
        listString.add(content);

    }
}

This example works correctly but is not efficient. Once you have a document like this:

<test>
    <string>String</string>
    <string>String</string>
    <string>String</string>
    <string>String</string>
    <string>String</string>
    <string>String</string>
    <string>String</string>
    <string>String</string>
    <string>String</string>
    <string>String</string>
</test>

Try to profile your application, force garbage collection and you will still have ten String objects left in the memory.

Fortunately, Java has provided a method to avoid such case. You can use String.intern() to force the application to use the same String object whenever possible. For above example, you can change the code to something like this:

public class Reader extends DefaultHandler {

    private List<String> listString = new ArrayList<String>();

    public void characters(char[] ch, int start, int length) throws SAXException {

        String content = new String(ch, start, length).intern();
        listString.add(content);

    }
}

Now, re-profile the application, force garbage collection, and you will only have one String left in the memory. You can save a lot of memory if you can make sure that there is only one instance of String with certain value in your JVM.

This method also has nice side effect. If you do a lot of String equality comparison in the application, a same String object run faster. To explain this, we can read the source code of String:

...
public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = count;
        if (n == anotherString.count) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = offset;
            int j = anotherString.offset;
            while (n-- != 0) {
                if (v1[i++] != v2[j++])
                    return false;
            }
            return true;
        }
    }
    return false;
}
...

If the object is same, then the method will be immediately after this line if (this == anObject). This is very fast and will save a lot of process time if your application do this operations a lot of time.