Re: inlining and string concatenation

[Bryce McKinlay <bryce at albatross dot co dot nz>]

Per Bothner wrote:

> What you can do for numbers is stack-allocate a work buffer
> guaranteed to be big enough.  I.e. the algorithm is:
> (1) Stack-allocate an array with an element (a pointer plus one bit)
> for each operand.
> (2) Evaluate each operand in order.  If the operand is an object,
> leave a pointer to the resulting String in the array of (1).  If the
> operand is a primitive, stack-allocate a work buffer guaranteed to
> be big enough, leaving a pointer to the buffer in (1).

That sounds like it would be a very fast implementation, but it would take
some effort to implement. Integer, Double, etc would have to be modified so
that they can toString() into a generic char[] buffer.

The solution I had in mind certainly wouldn't be as good as this, but it is a
lot simpler and still a big improvement over the existing implementation
(which tends to waste a lot of memory, since wasted buffer bytes from the
StringBuffer are never released until the resulting string gets collected).
It also seems to be significantly faster when Strings (as opposed to
primitives and Objects) are being concatenated, and when the total length of
the strings being concatenated is longer than 16.

The only non-trivial change required for this implementation is for the
compiler to figure out how many items need to be concatenated prior to
calling the constructor.

I've attached my implementation, along with a simple test/timer case.

Results:

$ gij --ms=64M StringConcat 1
FastStringConcatenator: 2259ms elapsed. (heap used = 26620K)

$ gij --ms=64M StringConcat 2
Concatenation operator: 4387ms elapsed. (heap used = 40516K)

regards

  [ bryce ]

package gnu.gcj.lang;

public class FastStringConcatenator
{
  private String[] strings;
  private int i = 0;
  private int strings_count;

  public FastStringConcatenator(int stringcount)
  {
    strings_count = stringcount;
    strings = new String[stringcount];
  }
  
  public FastStringConcatenator append (boolean bool)
  {
    strings[i++] = (bool ? "true" : "false");
    return this;
  }
  
  public FastStringConcatenator append(char cval)
  {
    strings[i++] = String.valueOf (cval);
    return this;
  }

  public FastStringConcatenator append (int inum)
  {
    strings[i++] = Integer.toString (inum);
    return this;
  }

  public FastStringConcatenator append (long lnum)
  {
    strings[i++] = Long.toString (lnum);
    return this;
  }

  public FastStringConcatenator append (float fnum)
  {
    strings[i++] = Float.toString (fnum);
    return this;
  }

  public FastStringConcatenator append (double dnum)
  {
    strings[i++] = Double.toString (dnum);
    return this;
  }

  public FastStringConcatenator append (Object obj)
  {
    strings[i++] = obj.toString();
    return this;
  }

  public FastStringConcatenator append (String str)
  {
    strings[i++] = str;
    return this;
  }

/*
  public FastStringConcatenator append (FastStringConcatenator str)
  {
  
  }
*/
  
  public native String toString();
  
}
// -*- c++ -*-

#include <gnu/gcj/lang/FastStringConcatenator.h>
#include <gcj/cni.h>

jstring
gnu::gcj::lang::FastStringConcatenator::toString ()
{
  jint length = 0;
  for (int i=0; i < strings_count; i++)
    length += elements (strings)[i]->length ();
    
  jstring result = JvAllocString (length);
  jchar *ptr = JvGetStringChars (result);
  
  for (int i=0; i < strings_count; i++)
    {
      jstring str = elements (strings)[i];
      jint strlen = str->length ();
      if (strlen > 1)
        {
	  memcpy (ptr, JvGetStringChars (str), strlen * sizeof(jchar)); 
	  ptr += strlen;
	}            
      else if (strlen == 1)
        *ptr++ = *JvGetStringChars (str);
    }
  
  return result;
}
import gnu.gcj.lang.FastStringConcatenator;

public class StringConcat
{
  static final int ITERATIONS = 100000;
  static String s1 = "It is not";
  static String s2 = "the";
  static String s3 = "spoon";
  static String s4 = "that bends";
  static String s5 = "it is only yourself.";

  static double d1 = 99.631;
  static int i = 50;
  static byte b = 3;
  
  static String[] strings = new String[ITERATIONS];

  public static void main(String args[])
  {
    int i = 0;
    if (args.length > 0)
     i = Integer.parseInt(args[0]);
     
    switch (i)
    {
      case 1:
        fast();
	break;
      case 2:      
        builtin();
	break;
      case 3:
        sbuffer();
	break;
      case 4:
        fastnum();
	break;
      case 5:
        sbuffernum();
	break;
      default:
        while (true)
	  {
	    fast(); builtin(); sbuffer();
	  }
    }	

    System.out.println(strings[1]);    
  }
  
  static StringBuffer sb;
  static FastStringConcatenator fsc;

  static void fastnum()
  {
    System.out.print("FSC numbers: ");
    start();
    for (int i=0; i < ITERATIONS; i++)
      {
	fsc = new FastStringConcatenator(5);
        fsc.append(d1).append(" ").append(i).append("->").append(b);
	strings[i] = fsc.toString();
      }
    finish();
  }

  static void sbuffernum()
  {
    System.out.print("Sbuffer numbers: ");
    start();
    for (int i=0; i < ITERATIONS; i++)
      {
	sb = new StringBuffer();
	sb.append(d1).append(" ").append(i).append("->").append(b);
	strings[i] = sb.toString();
      }
    finish();
  }

  static void fast()
  {
    System.out.print("FastStringConcatenator: ");
    start();
    for (int i=0; i < ITERATIONS; i++)
      {
	fsc = new FastStringConcatenator(9);
	fsc.append(s1).append(" ").append(s2).append(" ").append(s3);
	fsc.append(" ").append(s4).append(", ").append(s5);
	strings[i] = fsc.toString();
      }
    finish();
  }

  static void builtin()
  {
    System.out.print("Concatenation operator: ");
    start();
    for (int i=0; i < ITERATIONS; i++)
      {
        strings[i] = s1 + " " + s2 + " " + s3 + " " + s4 + ", " + s5;
      }
    finish();
  }

  static void sbuffer() 
  {
    System.out.print("StringBuffer: ");
    start();
    for (int i=0; i < ITERATIONS; i++)
      {
	sb = new StringBuffer();
	sb.append(s1).append(" ").append(s2).append(" ").append(s3);
	sb.append(" ").append(s4).append(", ").append(s5);
	strings[i] = sb.toString();
      }
    finish();
  }  
  
  static long start_time;  
  
  public static void start()
  {
    start_time = System.currentTimeMillis();
  }

  public static void finish()
  {
    Runtime r = Runtime.getRuntime();
    long used_mem = r.totalMemory() - r.freeMemory();
    long elapsed = System.currentTimeMillis() - start_time;
    System.out.print (elapsed + "ms elapsed.");
    System.out.println (" (heap used = " + used_mem / 1024 + "K)");
  }
  

}