CODEWITHSUNDEEP
javaandroid
Arthur
Arthur

Reputation: 1548

Java: Avoiding StringBuilder.toString() to create new String by using custom class

In an Android game, I have a cycle that runs about 15 million times where I permutate word fragments and check the results against a dictionary. I notice a lot of GC calls and my main suspect is StringBuilder.toString() which always creates a new String.

I'm only moderately experienced in Java and not sure how to avoid this allocation and pass the internal char array somehow to contains() directly without any allocation or copying.

Simplified pseudo-code fragment that describes my problem:

static HashSet<String>dictionary;       // loaded from text file
String[7] wordParts = new String[7];    // pre-filled from player data
StringBuilder sb = new StringBuilder(20);

for (i=15 million times) {
    sb.setLength(0);
    for (j=2-7 times) {
       sb.append(wordParts[j]);
    }
    if (dictionary.contains(sb.toString()) {
        processValidWord();
    }
}

Upvotes: 2

Views: 779

Answers (2)

Arthur
Arthur

Reputation: 1548

Using Pablo's suggestion:

static HashSet<DictionaryItem>dictionary;       // loaded from text file
String[7] wordParts = new String[7];            // pre-filled from player data
DictionaryItem di = new DictionaryItem();

for (i=15 million times) {
   di.setEmpty();
   for (j=2-7 times) {
      di.append(wordParts[j]);
   }
   if (dictionary.contains(di) {
       processValidWord();
   }
}

Stealing from the String and StringBuilder, but building the hash code on the fly for this special application:

public class DictionaryItem {
    int hashCode;
    int length;
    char[] chars = new char[15];

    public DictionaryItem(String initialValue) {
        this();
        append(initialValue);
    }

    public DictionaryItem() {
        setEmpty();
    }

    public void setEmpty() {
        hashCode = 0;
        length = 0;
    }

    public void append(String s) {
        for (int i=0;i<s.length();i++) {
            chars[length++] = s.charAt(i);
            hashCode = 31*hashCode + s.charAt(i);
        }
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o instanceof DictionaryItem) {
            DictionaryItem di = (DictionaryItem)o;
            if (di.length == length) {
                int i = length-1;
                while (i >= 0) {
                    if (di.chars[i] != chars[i]) {
                        return false;
                    }
                    i--;
                }
                return true;
            }
        }
        return false;
    }

    @Override
    public int hashCode() {
        return hashCode;
    }

    @Override
    public String toString() {
        return new String(chars, 0, length);
    }
}

No allocations now during search, toString() is used only rarely to display results to the user.

Upvotes: 0

Alessio
Alessio

Reputation: 2068

As far as I know, in Java7 they changed the internal implementation of the String class, removing the char[] to be shared between different Strings (with an offset value indicating the first char in that string and a length of that string).

Check here http://java-performance.info/changes-to-string-java-1-7-0_06/

Upvotes: 2

Related Questions