avoiding string creation

i think that one of my performance leaks is the permanent creation of internal string object when i display scores etc.
every frame (like g.drawString("myScore "+scoreInt):wink:

now i want to create string objects which persist holding those informations.
=> g.drawString(scoreString)

so a new string has only to be created, when the score changes, not in every repaint.

but i dunno if a stringbuffer could be a better choice. if a stringbuffer is used in drawString, its toString() method is called.
is therefore a new String object created ?

It would seem so yes. Since StringBuffer doesn’t extend String it can’t be used as one so somewhere along the lines a String will be created.

Interesting note in: http://java.sun.com/j2se/1.4.2/docs/api/java/lang/StringBuffer.html that StringBuffers are actually used by the compiler for doing “dfds” + “dsfds” + 5 + bob + “dsfdsf”

Kev

g.drawString("myScore "+scoreInt);

You’d be suprised how much code that actually expands to!

At the 1st level, it simply expands to :-


g.drawString((new StringBuilder().append("myScore").append(scoreInt)).toString());

This obviously involves 4 object creations.

  1. new StringBuilder()
  2. new char [16] (inside StringBuilder constructor)
  3. new String() (inside StringBuilder.toString())
  4. new char [stringLength] (inside String constructor)

However, the object creation realy is only part of the reason for this codes slowness.

Heres the exact path of all the code (WARNING, its fukin HUGE!):-



    //StringBuilder constructor

    public StringBuffer() {
      super(16);
    }


     //AbstractStringBuilder constructor and related member vars.
    char value[];
    AbstractStringBuilder(int capacity) {
        value = new char[capacity];
    }


     //StringBuilder.append(String)

    public StringBuilder append(String str) {
      super.append(str);
        return this;
    }

     //AbstractStringBuilder.append(...)

    public AbstractStringBuilder append(String str) {
      if (str == null) str = "null";
        int len = str.length(); // not worth expanding this, its a trivial 'getter' method.
      if (len == 0) return this;
      int newCount = count + len;
      if (newCount > value.length)
          expandCapacity(newCount); //not worth expanding, it isn't executed
      str.getChars(0, len, value, count); //expanded below 
      count = newCount;
      return this;
    }

     //String.getChars(......)

    public void getChars(int srcBegin, int srcEnd, char dst[], int dstBegin) {
        if (srcBegin < 0) {
            throw new StringIndexOutOfBoundsException(srcBegin);
        }
        if (srcEnd > count) {
            throw new StringIndexOutOfBoundsException(srcEnd);
        }
        if (srcBegin > srcEnd) {
            throw new StringIndexOutOfBoundsException(srcEnd - srcBegin);
        }
        System.arraycopy(value, offset + srcBegin, dst, dstBegin,
             srcEnd - srcBegin);
    }


     // now, the String is appended to the StringBuilder
     // we trace what is needed to append the int.

    //StringBuilder.append(int)

    public StringBuilder append(int i) {
      super.append(i);
        return this;
    }

    public AbstractStringBuilder append(int i) {
        if (i == Integer.MIN_VALUE) {
            append("-2147483648");
            return this;
        }
        int appendedLength = (i < 0) ? stringSizeOfInt(-i) + 1 
                                     : stringSizeOfInt(i); //this method call is expanded below
        int spaceNeeded = count + appendedLength;
        if (spaceNeeded > value.length)
            expandCapacity(spaceNeeded); //not expanded, it won't be called
      Integer.getChars(i, spaceNeeded, value); //expended *further* below
        count = spaceNeeded;
        return this;
    }

    //static member var needed for stringSizeOfInt(int) method

    final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
                                     99999999, 999999999, Integer.MAX_VALUE };

    // stringSizeOfInt(int) called from AbstractStringBuilder.append(int)

    static int stringSizeOfInt(int x) {
        for (int i=0; ; i++)
            if (x <= sizeTable[i])
                return i+1;
    }


    //static member vars of Integer class, needed for Integer.getChars(....)

    final static char [] DigitTens = {
      '0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
      '1', '1', '1', '1', '1', '1', '1', '1', '1', '1',
      '2', '2', '2', '2', '2', '2', '2', '2', '2', '2',
      '3', '3', '3', '3', '3', '3', '3', '3', '3', '3',
      '4', '4', '4', '4', '4', '4', '4', '4', '4', '4',
      '5', '5', '5', '5', '5', '5', '5', '5', '5', '5',
      '6', '6', '6', '6', '6', '6', '6', '6', '6', '6',
      '7', '7', '7', '7', '7', '7', '7', '7', '7', '7',
      '8', '8', '8', '8', '8', '8', '8', '8', '8', '8',
      '9', '9', '9', '9', '9', '9', '9', '9', '9', '9',
      } ; 

    final static char [] DigitOnes = { 
      '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
      '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
      '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
      '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
      '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
      '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
      '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
      '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
      '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
      '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
      } ;

    //Integer.getChars(....) also called from AbstractStringBuilder.append(int)


    static void getChars(int i, int index, char[] buf) {
        int q, r;
        int charPos = index;
        char sign = 0;

        if (i < 0) { 
            sign = '-';
            i = -i;
        }

        // Generate two digits per iteration
        while (i >= 65536) {
            q = i / 100;
        // really: r = i - (q * 100);
            r = i - ((q << 6) + (q << 5) + (q << 2));
            i = q;
            buf [--charPos] = DigitOnes[r];
            buf [--charPos] = DigitTens[r];
        }

        // Fall thru to fast mode for smaller numbers
        // assert(i <= 65536, i);
        for (;;) { 
            q = (i * 52429) >>> (16+3);
            r = i - ((q << 3) + (q << 1));  // r = i-(q*10) ...
            buf [--charPos] = digits [r];
            i = q;
            if (i == 0) break;
        }
        if (sign != 0) {
            buf [--charPos] = sign;
        }
    }

     //we now have the StringBuilder created, and the String + int components added to it.
     //we just have to call toString on it...

     //StringBuilder.toString()

    public String toString() {
        // Create a copy, don't share the array
      return new String(value, 0, count);
    }

     //String constructor

    public String(char value[], int offset, int count) {
        if (offset < 0) {
            throw new StringIndexOutOfBoundsException(offset);
        }
        if (count < 0) {
            throw new StringIndexOutOfBoundsException(count);
        }
        // Note: offset or count might be near -1>>>1.
        if (offset > value.length - count) {
            throw new StringIndexOutOfBoundsException(offset + count);
        }
        char[] v = new char[count];
        System.arraycopy(value, offset, v, 0, count);
        this.offset = 0;
        this.count = count;
        this.value = v;
    }

Don’t you just love OO :smiley:

As for a way to speed it up, you have 2 options :-

  1. use an image font.

Images can generally be blitted faster than a typefaced font can be rasterized, so, while taking more memory, it should be alot faster. (especially with HW acceleration)

  1. If the length (number of characters) of the score is always going to be within a fixed range, you could do something like :-

static final int STRING_MYSCORE_LENGTH = "myScore ".length();

static final int MAX_SCORE_CHARS = 4; //your score will be limited to 4 characters long i.e. 9999

char [] chars = new char[STRING_MYSCORE_LENGTH+MAX_SCORE_CHARS];
{
   "myScore ".getChars(0, STRING_MYSCORE_LENGTH, chars, 0) ; //put the chars from myScore into the char []
    // the indexs used to display the score don't need initialising as they will be updated every loop anyway
}


//then in your draw method


public void drawScore(Graphics g, int score)
{
   //note this is the easy but relatively slow way of converting a decimal number into a sequence of chars
   // there is a faster way that uses multiply rather than divides/mod
   //however it requires huge lookup tables (you can see them in the code I quoted above)

   for(int i = STRING_MYSCORE_LENGTH+MAX_SCORE_CHARS-1; i >= STRING_MYSCORE_LENGTH;i--)
   {
      chars[i] = (char)((score%10) + '0'); //'0' is ascii code 48
      score/=10;
   }

   g.drawString(new String(chars));
}

oehm … did i mention that i just want to print out some scores … ?! ;D

i have to try some of these suggestions later. …

I found the same problem in my game with printing the score was taking way to much of the % of cycles in the profiler. Made a bit of code that would divided up the score into each 0 through 9 reprentation of each tens/hundred/thousands (so on) place and then print the string for that number from an array of strings that held the just the digits 0-9. It works similar to the idea of painting a image of the number for each part of the score, but prints a string instead.


numString[0]="0";
numString[1]="1";
numString[2]="2";
numString[3]="3";
numString[4]="4";
numString[5]="5";
numString[6]="6";
numString[7]="7";
numString[8]="8";
numString[9]="9";

g.drawString ("Score",scorePrint,bottom+3,0);
tempScore=score; 
a=10; 
numPlaces=0; 
for (p=1;p<8;p++) { 
      if (score-a<0) { 
            numPlaces=p; 
            p=9; 
      } 
      a=a*10; 
} 
for (p=1;p<numPlaces;p++) { 
      k=1; 
      a=0;
      for (t=0;t<numPlaces-p;t++) k=k*10;
      a=score/k;
      g.drawString (numString[a],scorePrint2+(p*FONT.stringWidth ("5")),bottom+3,0);
      score=score-(a*k);
}
g.drawString (numString[score],scorePrint2+(p*FONT.stringWidth ("5")),bottom+3,0);
score=tempScore;

I also found that Strings are very memory hungry - so I have also reverted to the use of a set of image based fonts.