String concatenation tweaks
Remi Forax
forax at univ-mlv.fr
Tue May 26 13:31:59 UTC 2015
On 05/25/2015 09:01 PM, Aleksey Shipilev wrote:
> On 05/24/2015 06:33 PM, Remi Forax wrote:
>> Here is my version (see at the end of this message).
> Thanks! Merged it into the patchset with minor polish:
> http://cr.openjdk.java.net/~shade/scratch/string-concat-indy/
>
> The performance is interesting. It seems to break OptimizeStringConcat,
> and so it's a performance win only on non-optimized chains, like
> string_string_long. The allocation pressure is slightly higher as well,
> seems to be because int[] from the collector is not scalarized.
I wonder if the two things are not related, fail to unroll -> creation
of int[] -> non constant value for the StringBuilder constructor ->
break of OptimizeStringConcat optimization.
Here is a new patch that do the unrolling by hand with a nifty trick to
avoid to create an overload for each arities of sum, i'm not very pround
of it because it creates an artificial performance cliff if there is
more than 8 parameters but at least it will confirm or not my theory.
>
> You may want to tune it more, JMH benchmarks are here:
> http://cr.openjdk.java.net/~shade/scratch/string-concat-indy/indy-concat-bench.tar.gz
>
> ...and -prof perfasm, -prof perfnorm, and -prof gc are your friends.
>
> Thanks,
> -Aleksey
regards,
Rémi
>
/*
* Copyright (c) 2012, 2015, Oracle and/or its affiliates. All rights
reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License
version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
package java.lang.invoke;
import jdk.internal.org.objectweb.asm.ClassWriter;
import jdk.internal.org.objectweb.asm.Label;
import jdk.internal.org.objectweb.asm.MethodVisitor;
import jdk.internal.org.objectweb.asm.Opcodes;
import opto_string_concat.StringConcatTestFactory;
import sun.misc.Unsafe;
import sun.security.action.GetPropertyAction;
import java.lang.invoke.MethodHandles.Lookup;
import java.security.AccessController;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.PropertyPermission;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.UnaryOperator;
import java.util.stream.IntStream;
import static jdk.internal.org.objectweb.asm.Opcodes.*;
/**
* Generates the String concatenation stub.
*
* @author Aleksey Shipilev
*/
public class StringConcatFactory {
private static final Strategy STRATEGY;
private static final boolean DEBUG;
private static final ProxyClassesDumper DUMPER;
static {
{
final String key = "java.lang.invoke.stringConcat";
String str = AccessController.doPrivileged(
new GetPropertyAction(key), null,
new PropertyPermission(key, "read"));
STRATEGY = (str == null) ? Strategy.INNER_SIZED :
Strategy.valueOf(str);
}
{
final String key = "java.lang.invoke.stringConcat.debug";
String str = AccessController.doPrivileged(
new GetPropertyAction(key), null,
new PropertyPermission(key, "read"));
DEBUG = (str != null);
}
{
final String key = "java.lang.invoke.stringConcat.dumpClasses";
String str = AccessController.doPrivileged(
new GetPropertyAction(key), null,
new PropertyPermission(key , "read"));
DUMPER = (str == null) ? null :
ProxyClassesDumper.getInstance(str);
}
}
private enum Strategy {
NAIVE_MH_FILTER,
NAIVE_MH_FILTER_SIZED,
INNER,
INNER_SIZED,
FULL_MH
}
private static final Map<MethodType, CallSite> CACHE = new
ConcurrentHashMap<MethodType, CallSite>();
/**
* Bootstrap method for javac-generated concat call.
*
* @param caller caller context
* @param name ignored
* @param args method arguments, in order
* @return a callsite with actual method to concatenate strings
* @throws Exception if something goes wrong
*/
public static CallSite stringConcat(MethodHandles.Lookup caller,
String name, MethodType args) throws Exception {
if (DEBUG) {
System.out.print("StringConcatFactory ");
System.out.print(STRATEGY);
System.out.print(" is here for ");
System.out.print(args);
System.out.print(" ");
}
CallSite cs = CACHE.get(args);
if (cs != null) {
if (DEBUG) {
System.out.println(" <CACHED!>");
}
} else {
cs = generate(caller, args);
CACHE.put(args, cs);
if (DEBUG) {
System.out.println();
}
}
return cs;
}
private static CallSite generate(MethodHandles.Lookup caller,
MethodType args) throws Exception {
switch (STRATEGY) {
case NAIVE_MH_FILTER:
return mhFiltered(caller, args, false);
case NAIVE_MH_FILTER_SIZED:
return mhFiltered(caller, args, true);
case INNER:
return innerClass(caller, args, false);
case INNER_SIZED:
return innerClass(caller, args, true);
case FULL_MH:
return mhFull(caller, args);
default:
throw new IllegalStateException("Not implemented yet: "
+ STRATEGY);
}
}
/* ------------------------------------ Method handler adapters
strategy ------------------------------------ */
private static CallSite mhFiltered(MethodHandles.Lookup caller,
MethodType args, boolean sized) throws Exception {
MethodHandle resultString = caller.findStatic(
StringConcatFactory.class,
(sized ? "concatNaiveSized" : "concatNaive"),
MethodType.methodType(String.class, String[].class));
MethodHandle adapted = resultString.asCollector(String[].class,
args.parameterCount());
// Adapt arguments, if needed: call String.valueOf on them.
Class<?>[] params = args.parameterArray();
for (int p = 0; p < params.length; p++) {
if (params[p] != String.class) {
MethodHandle valueOf = caller.findStatic(
String.class,
"valueOf",
MethodType.methodType(String.class, params[p]));
adapted = MethodHandles.filterArgument(adapted, p,
valueOf);
}
}
return new ConstantCallSite(adapted);
}
/**
* Naive concatenation.
* Argument conversion was already handled by the caller.
*
* @param args strings to concatenate
* @return concatenated string
*/
public static String concatNaive(String[] args) {
StringBuilder sb = new StringBuilder();
for (String s : args) {
sb.append(s);
}
return sb.toString();
}
/**
* Naive concatenation + pre-sized StringBuilder
* Argument conversion was already handled by the caller.
*
* @param args strings to concatenate
* @return concatenated string
*/
public static String concatNaiveSized(String[] args) {
int len = 0;
for (String s : args) {
len += s.length();
}
StringBuilder sb = new StringBuilder(len);
for (String s : args) {
sb.append(s);
}
return sb.toString();
}
/* ---------------------------------------- Inner class strategy
-------------------------------------------- */
static final Unsafe UNSAFE = Unsafe.getUnsafe();
static final int CLASSFILE_VERSION = 52;
static final String JAVA_LANG_OBJECT = "java/lang/Object";
static final String NAME_FACTORY = "concat";
static final String CLASS_NAME = "java/lang/String$Concat";
static final String NAME_CTOR = "<init>";
static final String CLASS_STRING_BUILDER = "java/lang/StringBuilder";
static final String CLASS_STRING = "java/lang/String";
static final String SIG_TO_STRING = "()Ljava/lang/String;";
private static CallSite innerClass(MethodHandles.Lookup caller,
MethodType args, boolean sized) {
Class<?> targetClass = caller.lookupClass();
ClassWriter cw = new ClassWriter(ClassWriter.COMPUTE_MAXS +
ClassWriter.COMPUTE_FRAMES);
cw.visit(CLASSFILE_VERSION,
ACC_SUPER + ACC_FINAL + ACC_SYNTHETIC,
CLASS_NAME,
null,
JAVA_LANG_OBJECT,
null
);
MethodVisitor mv = cw.visitMethod(
ACC_PUBLIC + ACC_STATIC + ACC_FINAL,
NAME_FACTORY,
args.toMethodDescriptorString(),
null,
null);
mv.visitAnnotation("Ljava/lang/invoke/ForceInline;", true);
mv.visitCode();
Class<?>[] arr = args.parameterArray();
// In sized mode, it makes sense to make StringBuilder append
chains look
// familiar to OptimizeStringConcat. Therefore, we need to do
null-checks
// early.
if (sized) {
int off = 0;
for (Class<?> cl : arr) {
if (cl == String.class) {
Label l0 = new Label();
mv.visitIntInsn(ALOAD, off);
mv.visitJumpInsn(IFNONNULL, l0);
mv.visitLdcInsn("null");
mv.visitIntInsn(ASTORE, off);
mv.visitLabel(l0);
}
off += getParameterSize(cl);
}
}
// Prepare StringBuilder instance
mv.visitTypeInsn(NEW, CLASS_STRING_BUILDER);
mv.visitInsn(DUP);
if (sized) {
// Walk through the arguments, and try to estimate the
final length
int add = 0;
mv.visitInsn(ICONST_0);
int off = 0;
for (Class<?> cl : arr) {
// TODO: For anything other than Strings and
primitives, it makes sense to call String.valueOf first.
if (cl == String.class) {
mv.visitIntInsn(ALOAD, off);
mv.visitMethodInsn(
INVOKEVIRTUAL,
CLASS_STRING,
"length",
"()I",
false
);
mv.visitInsn(IADD);
} else if (cl.isPrimitive()) {
// TODO: Consider a more accurate estimate for
primitives.
add += 16;
}
off += getParameterSize(cl);
}
if (add > 0) {
iconst(mv, add);
mv.visitInsn(IADD);
}
mv.visitMethodInsn(
INVOKESPECIAL,
CLASS_STRING_BUILDER,
NAME_CTOR,
"(I)V",
false
);
} else {
mv.visitMethodInsn(
INVOKESPECIAL,
CLASS_STRING_BUILDER,
NAME_CTOR,
"()V", false
);
}
int off = 0;
for (Class<?> cl : arr) {
mv.visitVarInsn(getLoadOpcode(cl), off);
off += getParameterSize(cl);
mv.visitMethodInsn(
INVOKEVIRTUAL,
CLASS_STRING_BUILDER,
"append",
getDesc(cl),
false
);
}
mv.visitMethodInsn(
INVOKEVIRTUAL,
CLASS_STRING_BUILDER,
"toString",
SIG_TO_STRING,
false
);
mv.visitInsn(ARETURN);
mv.visitMaxs(-1, -1);
mv.visitEnd();
cw.visitEnd();
final byte[] classBytes = cw.toByteArray();
final Class<?> innerClass =
UNSAFE.defineAnonymousClass(targetClass, classBytes, null);
if (DUMPER != null) {
DUMPER.dumpClass(args.toString() + ".class", classBytes);
}
try {
UNSAFE.ensureClassInitialized(innerClass);
return new ConstantCallSite(
MethodHandles.Lookup.IMPL_LOOKUP
.findStatic(innerClass, NAME_FACTORY, args));
}
catch (ReflectiveOperationException e) {
throw new IllegalStateException("Exception finding
constructor", e);
}
}
private static String getDesc(Class<?> cl) {
if (cl.isPrimitive()) {
if (cl == Integer.TYPE) {
return "(I)Ljava/lang/StringBuilder;";
} else if (cl == Boolean.TYPE) {
return "(Z)Ljava/lang/StringBuilder;";
} else if (cl == Byte.TYPE) {
return "(B)Ljava/lang/StringBuilder;";
} else if (cl == Character.TYPE) {
return "(C)Ljava/lang/StringBuilder;";
} else if (cl == Short.TYPE) {
return "(S)Ljava/lang/StringBuilder;";
} else if (cl == Double.TYPE) {
return "(D)Ljava/lang/StringBuilder;";
} else if (cl == Float.TYPE) {
return "(F)Ljava/lang/StringBuilder;";
} else if (cl == Long.TYPE) {
return "(J)Ljava/lang/StringBuilder;";
} else {
throw new IllegalStateException();
}
} else if (cl == String.class) {
return "(Ljava/lang/String;)Ljava/lang/StringBuilder;";
} else if (cl == StringBuffer.class) {
return "(Ljava/util/StringBuffer;)Ljava/lang/StringBuilder;";
} else if (cl == CharSequence.class) {
return "(Ljava/lang/CharSequence;)Ljava/lang/StringBuilder;";
} else if (cl == char[].class) {
return "([C)Ljava/lang/StringBuilder;";
} else {
return "(Ljava/lang/Object;)Ljava/lang/StringBuilder;";
}
}
/**
* The following method is copied from
* org.objectweb.asm.commons.InstructionAdapter. Part of ASM: a
very small
* and fast Java bytecode manipulation framework.
* Copyright (c) 2000-2005 INRIA, France Telecom All rights reserved.
*/
private static void iconst(MethodVisitor mv, final int cst) {
if (cst >= -1 && cst <= 5) {
mv.visitInsn(Opcodes.ICONST_0 + cst);
} else if (cst >= Byte.MIN_VALUE && cst <= Byte.MAX_VALUE) {
mv.visitIntInsn(Opcodes.BIPUSH, cst);
} else if (cst >= Short.MIN_VALUE && cst <= Short.MAX_VALUE) {
mv.visitIntInsn(Opcodes.SIPUSH, cst);
} else {
mv.visitLdcInsn(cst);
}
}
private static int getLoadOpcode(Class<?> c) {
if (c == Void.TYPE) {
throw new InternalError("Unexpected void type of load opcode");
}
return ILOAD + getOpcodeOffset(c);
}
private static int getOpcodeOffset(Class<?> c) {
if (c.isPrimitive()) {
if (c == Long.TYPE) {
return 1;
} else if (c == Float.TYPE) {
return 2;
} else if (c == Double.TYPE) {
return 3;
}
return 0;
} else {
return 4;
}
}
private static int getParameterSize(Class<?> c) {
if (c == Void.TYPE) {
return 0;
} else if (c == Long.TYPE || c == Double.TYPE) {
return 2;
}
return 1;
}
/* ------------------------------- Full Method handler adapters
strategy ------------------------------------ */
private static CallSite mhFull(MethodHandles.Lookup caller,
MethodType args) throws Exception {
return new ConstantCallSite(createMH(caller, args));
}
private static MethodHandle createMH(MethodHandles.Lookup lookup,
MethodType methodType) throws NoSuchMethodException,
IllegalAccessException {
// filter: String -> nullmask + identity
// primitive -> do nothing
// Object -> nullmask + Object.toString
// adder: String -> String.length
// primitive drop and initial += 16
int parameterCount = methodType.parameterCount();
MethodHandle[] filters = new MethodHandle[parameterCount];
ArrayList<MethodHandle> lengthers = new ArrayList<>(parameterCount);
ArrayList<Class<?>> appendTypeList = new ArrayList<>(parameterCount);
UnaryOperator<MethodHandle> dropperOp = UnaryOperator.identity();
int initial = 0;
for(int i = 0; i < parameterCount; i++) {
Class<?> type = methodType.parameterType(i);
filters[i] = filter(lookup, type);
Class<?> appendType; // either a primitive or String
if (type.isPrimitive()) {
appendType = type;
initial += 16; // TODO: Consider a more accurate estimate
for primitives.
UnaryOperator<MethodHandle> _dropperOp = dropperOp;
int _i = i;
dropperOp = mh ->
MethodHandles.dropArguments(_dropperOp.apply(mh), _i, type);
} else {
appendType = String.class;
lengthers.add(STRING_LENGTH);
}
appendTypeList.add(appendType);
}
MethodHandle builder =
MethodHandles.dropArguments(MethodHandles.identity(StringBuilder.class),
1, appendTypeList);
for(int i = parameterCount; --i>=0; ) { // in reverse because
calls to append() are composed in reverse too
Class<?> appendType = appendTypeList.get(i);
MethodHandle appender = appender(appendType);
if (i != 0) {
appender = MethodHandles.dropArguments(appender, 1,
appendTypeList.subList(0, i));
}
builder = MethodHandles.foldArguments(builder, appender);
}
MethodHandle sum;
if (lengthers.size() <= SUM_UNROLLED_COUNT) {
sum = MethodHandles.insertArguments(SUM_UNROLLED, 1,
IntStream.range(0, SUM_UNROLLED_COUNT - lengthers.size()).mapToObj(__ ->
0).toArray());
} else {
sum = SUM.asCollector(int[].class, lengthers.size());
}
MethodHandle adder = MethodHandles.insertArguments(sum, 0, initial);
adder = MethodHandles.filterArguments(adder, 0,
lengthers.toArray(new MethodHandle[lengthers.size()]));
adder = dropperOp.apply(adder);
MethodHandle newBuilder = MethodHandles.filterReturnValue(adder,
NEW_STRING_BUILDER);
MethodHandle target = MethodHandles.foldArguments(builder,
newBuilder);
target = MethodHandles.filterArguments(target, 0, filters);
return MethodHandles.filterReturnValue(target, BUILDER_TO_STRING);
}
private static MethodHandle appender(Class<?> appendType) throws
NoSuchMethodException, IllegalAccessException {
//TODO: cache these method handles !
MethodHandle appender =
MethodHandles.publicLookup().findVirtual(StringBuilder.class, "append",
MethodType.methodType(StringBuilder.class, appendType));
return appender.asType(MethodType.methodType(void.class,
StringBuilder.class, appendType)); // should return void
}
private static MethodHandle filter(MethodHandles.Lookup lookup,
Class<?> type) throws NoSuchMethodException, IllegalAccessException {
if (type.isPrimitive()) {
return null; // identity filter
}
MethodHandle op;
if (type == String.class) {
op = MethodHandles.identity(type);
} else {
op = lookup.findVirtual(type, "toString",
MethodType.methodType(String.class)); // try de-virtualize if possible
}
return MethodHandles.guardWithTest(
IS_NULL.asType(MethodType.methodType(boolean.class, type)),
NULL_STRING.asType(MethodType.methodType(String.class, type)),
op);
}
// called by a method handle
private static boolean isNull(Object s) {
return s == null;
}
// called by a method handle
private static int sumUnrolled(int initial, int v0, int v1, int v2,
int v3, int v4, int v5, int v6, int v7) {
return initial + v0 + v1 + v2 + v3 + v4 + v5 + v6 + v7;
}
// called by a method handle
private static int sum(int initial, int[] vs) {
int sum = initial; // this loop is not unrolled by the JIT :(
for(int v: vs) {
sum += v;
}
return sum;
}
private static final int SUM_UNROLLED_COUNT = 8;
private static final MethodHandle NULL_STRING, NEW_STRING_BUILDER,
STRING_LENGTH, BUILDER_TO_STRING,
IS_NULL, SUM, SUM_UNROLLED;
static {
NULL_STRING =
MethodHandles.dropArguments(MethodHandles.constant(String.class,
"null"), 0, Object.class);
Lookup publicLookup = MethodHandles.publicLookup();
try {
NEW_STRING_BUILDER =
publicLookup.findConstructor(StringBuilder.class,
MethodType.methodType(void.class, int.class));
STRING_LENGTH = publicLookup.findVirtual(String.class, "length",
MethodType.methodType(int.class));
BUILDER_TO_STRING =
publicLookup.findVirtual(StringBuilder.class, "toString",
MethodType.methodType(String.class));
IS_NULL =
MethodHandles.lookup().findStatic(StringConcatTestFactory.class, "isNull",
MethodType.methodType(boolean.class, Object.class));
SUM =
MethodHandles.lookup().findStatic(StringConcatTestFactory.class, "sum",
MethodType.methodType(int.class, int.class, int[].class));
SUM_UNROLLED =
MethodHandles.lookup().findStatic(StringConcatTestFactory.class,
"sumUnrolled",
MethodType.methodType(int.class, int.class, int.class,
int.class, int.class, int.class, int.class, int.class, int.class,
int.class));
} catch (NoSuchMethodException | IllegalAccessException e) {
throw new AssertionError(e);
}
}
}
More information about the compiler-dev
mailing list