Wednesday, May 6, 2015

Re: GWT vs js performance: Collections and Strings

Have you done any testing with JsArray or JsArrayOf ? 

Le mardi 5 mai 2015 14:34:46 UTC+2, Vassilis Virvilis a écrit :
Hi,

At some point in time I needed to handle lzw compressing/uncompressing in the client so I found https://gist.github.com/revolunet/843889

Later on I rewrite the LZW in java.

So I did. I benchmarked the difference and the new implementation was way slower when compressing. GWT/java is actually better when uncompressing.

I changed the java collections to javascript collections JsMap, and JsList and the difference was greatly reduced but not enough to be able to scrap the js implementation.

My guess any remaining gains are hidden in the StringBuilder but I may by wrong.

                                    Chrome                      Firefox                   IE
Js                                  544/61                       626/78               795/171
Java                              750/48                       1702/48              2401/468
JavaJsCollections          785/38                       1398/38             1877/351

The numbers are compressing/uncompressing
1000 iterations with a random string multiplied 10 times

I am using a single permutation with collapse-all. Can this be the culprit?

Any idea what to change in order to increase the performance in the java code?

Here is the code


package com.biovista.lib.gwt.client;

import com.google.gwt.core.client.JavaScriptObject;

public class Util {
    private static final char DICT_SIZE = 256;

    public static class JsMap<T> extends JavaScriptObject {
        protected JsMap() {
        }

        public final native void put(String key, T value) /*-{
            this[key] = value;
        }-*/;

        public final native boolean containsKey(String key) /*-{
            return (key in this);
        }-*/;

        public final native T get(String key) /*-{
            return this[key];
        }-*/;

        public static JsMap createInstance() {
            return (JsMap) createObject();
        }
    }

    public static class JsList<T> extends JavaScriptObject {
        protected JsList() {
        }

        public final native void add(T value) /*-{
            this.push(value);
        }-*/;

        public final native int size() /*-{
            return this.length;
        }-*/;

        public final native T get(char index) /*-{
            return this[index];
        }-*/;

        public static JsList createInstance() {
            return (JsList) createArray();
        }
    }

    public static String compressLZW(String text) {
        // Build the dictionary.
        // final Map<String, Character> map = new HashMap<String, Character>(
        // DICT_SIZE);
        final JsMap<Character> map = JsMap.createInstance();
        for (char i = 0; i < DICT_SIZE; i++) {
            map.put("" + i, i);
        }

        char dict_size = DICT_SIZE;

        String w = "";
        final StringBuilder result = new StringBuilder();
        for (char c : text.toCharArray()) {
            final String wc = w + c;
            if (map.containsKey(wc))
                w = wc;
            else {
                result.append(map.get(w));
                // Add wc to the dictionary.
                map.put(wc, dict_size++);
                w = "" + c;
            }
        }

        // Output the code for w.
        if (!w.equals(""))
            result.append(map.get(w));

        return result.toString();
    }

    /** uncompress a string. */
    public static String uncompressLZW(String compressed_text) {
        // Build the dictionary.
        // final List<String> rmap = new ArrayList<String>(DICT_SIZE);
        final JsList<String> rmap = JsList.createInstance();
        for (char i = 0; i < DICT_SIZE; i++) {
            rmap.add("" + i);
        }
        final char[] compressed = compressed_text.toCharArray();

        String w = "" + compressed[0];
        final StringBuilder result = new StringBuilder(w);
        for (int i = 1; i < compressed.length; i++) {
            final char k = compressed[i];
            final String entry = k < rmap.size() ? rmap.get(k) : w
                    + w.charAt(0);
            result.append(entry);
            // Add w+entry[0] to the dictionary.
            rmap.add(w + entry.charAt(0));
            w = entry;
        }
        return result.toString();
    }

    // LZW-compress a string
    public static native String lzwCompress(String s) /*-{
        var dict = {};
        var data = (s + "").split("");
        var out = [];
        var currChar;
        var phrase = data[0];
        var code = 256;
        for (var i = 1; i < data.length; i++) {
            currChar = data[i];
            if (dict[phrase + currChar] != null) {
                phrase += currChar;
            } else {
                out.push(phrase.length > 1 ? dict[phrase] : phrase
                        .charCodeAt(0));
                dict[phrase + currChar] = code;
                code++;
                phrase = currChar;
            }
        }
        out.push(phrase.length > 1 ? dict[phrase] : phrase.charCodeAt(0));
        for (var i = 0; i < out.length; i++) {
            out[i] = String.fromCharCode(out[i]);
        }
        return out.join("");
    }-*/;

    // Decompress an LZW-encoded string
    public static native String lzwDecompress(String s) /*-{
        var dict = {};
        var data = (s + "").split("");
        var currChar = data[0];
        var oldPhrase = currChar;
        var out = [ currChar ];
        var code = 256;
        var phrase;
        for (var i = 1; i < data.length; i++) {
            var currCode = data[i].charCodeAt(0);
            if (currCode < 256) {
                phrase = data[i];
            } else {
                phrase = dict[currCode] ? dict[currCode]
                        : (oldPhrase + currChar);
            }
            out.push(phrase);
            currChar = phrase.charAt(0);
            dict[code] = oldPhrase + currChar;
            code++;
            oldPhrase = phrase;
        }
        return out.join("");
    }-*/;

    public static void benchmark() {
        final int N = 1000;
        final int M = 10;
        final String test1 = "opaopaopaopa236747862348 hfjsgfhjsd g4782q65 87324658764 8 37g fj hdshfjdhjsb hjsgfbhjgb hjdf sjjhsgd 87345y 783256 8736 8573587 68327563";
        String test = "";
        for (int i = 0; i < M; i++) {
            test += test1;
        }

        // log.info("old compress " + lzwCompress(test));
        // log.info("new compress " + compressLZW(test));
        // log.info("old uncompress " + lzwDecompress(lzwCompress(test)));
        // log.info("new uncompress " + uncompressLZW(compressLZW(test)));
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            lzwCompress(test);
        }
        long t2 = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            compressLZW(test);
        }
        long t3 = System.currentTimeMillis();
        log.info("Compressing: old " + (t2 - t1) + " vs new " + (t3 - t2));

        final String test_c = compressLZW(test);
        t1 = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            lzwDecompress(test_c);
        }
        t2 = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            uncompressLZW(test_c);
        }
        t3 = System.currentTimeMillis();
        log.info("UnCompressing: old " + (t2 - t1) + " vs new " + (t3 - t2));

        if (!(lzwDecompress(lzwCompress(test)).equals(test))) {
            log.error("old failure");
        }

        if (!(uncompressLZW(compressLZW(test)).equals(test))) {
            log.error("new failure");
        }
    }
}


--
Vassilis Virvilis

--
You received this message because you are subscribed to the Google Groups "Google Web Toolkit" group.
To unsubscribe from this group and stop receiving emails from it, send an email to google-web-toolkit+unsubscribe@googlegroups.com.
To post to this group, send email to google-web-toolkit@googlegroups.com.
Visit this group at http://groups.google.com/group/google-web-toolkit.
For more options, visit https://groups.google.com/d/optout.

No comments:

Post a Comment