Initial StringBulder allocation estimates

[Roedy Green]

I put in a little bit of code like this to see how good I was at
estimating the initial size for StringBuilder size allocation.

I was embarrassed to discover I badly underestimated in every single
case. That meant StringBuilder had to pause in the middle of each
string constructed to double the buffer size, then garbage collect
twice as many objects as it need have done.

You might use this code to check out how good you are at estimating.


/**
* Used to fine tune initial StringBuilder size estimates. Insert
a call to checkEstimate just before toString.
*
* @param sb the StringBuilder to check.
* @param initSize initial size the StringBuilder was allocated.
*/
static void checkEstimate( StringBuilder sb, int initSize )
{
final int size = sb.length();
if ( size > initSize )
{
Throwable t = new Throwable();
StackTraceElement[] es = t.getStackTrace();
StackTraceElement e = es[ 1 ];
err.println( "at " + e.getClassName()
+ "." + e.getMethodName()
+ " line:" + e.getLineNumber() );
err.println( "StringBuffer initially sized too small " +
initSize + " to contain " + size + " without autogrowing." );
}
else
{
if ( size + 100 < initSize )
{
Throwable t = new Throwable();
StackTraceElement[] es = t.getStackTrace();
StackTraceElement e = es[ 1 ];
err.println( "at " + e.getClassName()
+ "." + e.getMethodName()
+ " line:" + e.getLineNumber() );
err.println( "StringBuffer initially sized needlessly
large " + initSize + " to contain contain " + size );
}
}
}

 

[Kevin McMurtrie]

I put in a little bit of code like this to see how good I was at
estimating the initial size for StringBuilder size allocation.

I was embarrassed to discover I badly underestimated in every single
case. That meant StringBuilder had to pause in the middle of each
string constructed to double the buffer size, then garbage collect
twice as many objects as it need have done.

You might use this code to check out how good you are at estimating.


/**
* Used to fine tune initial StringBuilder size estimates. Insert
a call to checkEstimate just before toString.
*
* @param sb the StringBuilder to check.
* @param initSize initial size the StringBuilder was allocated.
*/
static void checkEstimate( StringBuilder sb, int initSize )
{
final int size = sb.length();
if ( size > initSize )
{
Throwable t = new Throwable();
StackTraceElement[] es = t.getStackTrace();
StackTraceElement e = es[ 1 ];
err.println( "at " + e.getClassName()
+ "." + e.getMethodName()
+ " line:" + e.getLineNumber() );
err.println( "StringBuffer initially sized too small " +
initSize + " to contain " + size + " without autogrowing." );
}
else
{
if ( size + 100 < initSize )
{
Throwable t = new Throwable();
StackTraceElement[] es = t.getStackTrace();
StackTraceElement e = es[ 1 ];
err.println( "at " + e.getClassName()
+ "." + e.getMethodName()
+ " line:" + e.getLineNumber() );
err.println( "StringBuffer initially sized needlessly
large " + initSize + " to contain contain " + size );
}
}
}

Or put a breakpoint on AbstractStringBuilder.expandCapacity().

 

[Roedy Green]

/**
* Used to fine tune initial StringBuilder size estimates. Insert
a call to checkEstimate just before toString.
*

I have posted a somewhat improved version at
http://mindprod.com/jgloss/stringbuilder.html

Getting the code so it generates no warnings is pretty quick. The key
to it is sorting the warning messages, so you can see what sort of
typical sizes of result there are at a glance.

I have a huge amounts of code that basically uses StringBuilder to
build strings that are then cascaded to build even bigger strings.

I grossly overestimated by ability to by eye generate a good estimate.
This little optimisation doubles my RAM efficiency

 

[Mike Schilling]

On Sat, 19 Jul 2008 18:33:35 GMT, Roedy Green
quoted
someone who said :


I have posted a somewhat improved version at
http://mindprod.com/jgloss/stringbuilder.html

Getting the code so it generates no warnings is pretty quick. The
key
to it is sorting the warning messages, so you can see what sort of
typical sizes of result there are at a glance.

I have a huge amounts of code that basically uses StringBuilder to
build strings that are then cascaded to build even bigger strings.

I grossly overestimated by ability to by eye generate a good
estimate.
This little optimisation doubles my RAM efficiency

When you measure things like elapsed time or CPU usage in the entire
application, how much difference does it make?

 

[Roedy Green]

When you measure things like elapsed time or CPU usage in the entire
application, how much difference does it make?

I stupidly did not benchmark before the changes.

 

[Tom Anderson]

I stupidly did not benchmark before the changes.

No, but you have the old version in source control, right?

Right?

tom

 

[Mark Space]

No, but you have the old version in source control, right?

Right?

Source code controls are for wimps! Real men just fill their VW bus
with back-up tapes!

 

[Roedy Green]

No, but you have the old version in source control, right?

OK, I suppose I could revive it. I suspect my code will improve much
more than average, so it would let you know if there is any hope of
sufficient improvement to justify the optimisation.

 

[Roedy Green]

No, but you have the old version in source control, right?

I used this method to optimise the initial sizes of the StringBuilders
used in the static macros program that expands the macros used to
generate the mindprod.com website. It does a great many StringBuilder.
appends, though it also does a fair bit of i/o as well, since it has
to read each file in the website. Here are the results:

Effect of StringBuilder Optimising
Time Before Optimising Time After Optimising % improvement
Sun 27.5 sec 24 sec 13%
Jet 25 sec 22.5 sec 10%

 

[Mike Schilling]

On Tue, 22 Jul 2008 17:46:21 +0100, Tom Anderson
who
said :



I used this method to optimise the initial sizes of the
StringBuilders
used in the static macros program that expands the macros used to
generate the mindprod.com website. It does a great many
StringBuilder.
appends, though it also does a fair bit of i/o as well, since it has
to read each file in the website. Here are the results:

Effect of StringBuilder Optimising
Time Before Optimising Time After Optimising % improvement
Sun 27.5 sec 24 sec 13%
Jet 25 sec 22.5 sec 10%

That is quite significant indeed. Thanks.

 

[Tom Anderson]

That is quite significant indeed. Thanks.

Yes, thanks. This is interesting stuff.

Roedy, how did you do the analysis? You showed us the routine which
detects wrong-sized buffers, but where do you call it from? Every time you
to a StringBuffer.toString()?

I'm wondering if a more convenient way would be to hack the StringBuffer
class itself. You can get the source code from the JDK, modify it, then
use -Xbootclasspath/p to get it loaded in place of the normal
StringBuffer.

You could alter the class to remember its initial size, then to log its
initial size and final number of characters in its toString, along with a
bit of stack trace to see where it's being used.

You could do other stuff too, like counting the number of times toString
gets called, then having a finalizer which looks at the number, and if
it's zero, logs the fact that the buffer was never toStringed. You could
probably think of other things to check too.

Er, and in the above, s/StringBuffer/StringBuilder/, as appropriate.

tom

 

[Roedy Green]

Roedy, how did you do the analysis? You showed us the routine which
detects wrong-sized buffers, but where do you call it from? Every time you
to a StringBuffer.toString()?

I inserted a call just prior to StringBuffer.toString. This generated
output any time the actual size was outside my estimated range. I
then typically adjusted the range and the initial size. In a few
cases I put in code to precalculate the precise size such as this:

/**
* Display macro name and parms on error.
*
* @return parms as a human-readable string.
*/
private String showParms()
{
// macroName and parms may be null.
if ( macroName == null )
{
macroName = "?";
}

// get exact estimate of size of string we will build.
int estSize = " <!-- macro ".length()
+ macroName.length()
+ "\n".length();

if ( parms != null )
{
for ( String parm : parms )
{
estSize += " {".length() + parm.length() +
"}\n".length();
}
}
estSize += " -->".length();

final StringBuilder sb = new StringBuilder( estSize );

sb.append( " <!-- macro " );
sb.append( macroName );
sb.append( '\n' );
if ( parms != null )
{
for ( String parm : parms )
{
sb.append( " {" );
sb.append( parm );
sb.append( "}\n" );
}
}
sb.append( " -->" );
Tools.checkStringBuilderEstimate( sb, estSize, estSize );
return sb.toString();
}