Overview
Partial evaluation is an optimization technique where a program is specialized with respect to some of its input data. GraalVM's Truffle framework uses partial evaluation extensively to optimize dynamically-typed languages by specializing code based on observed types and values.
Key Concepts
- Specialization: Generating optimized code for specific input patterns
- Assumptions: Runtime checks that validate optimization assumptions
- Polymorphism: Handling multiple types efficiently through specialization
- Deoptimization: Falling back to interpreter when assumptions fail
Basic Partial Evaluation with Truffle
1. Simple Calculator with Specialization
import com.oracle.truffle.api.*;
import com.oracle.truffle.api.dsl.*;
import com.oracle.truffle.api.nodes.*;
import com.oracle.truffle.api.frame.*;
@NodeChild(value = "left", type = ExpressionNode.class)
@NodeChild(value = "right", type = ExpressionNode.class)
public abstract class AddNode extends ExpressionNode {
@Specialization(rewriteOn = ArithmeticException.class)
protected int addInt(int left, int right) {
return Math.addExact(left, right);
}
@Specialization
protected double addDouble(double left, double right) {
return left + right;
}
@Specialization
protected long addLong(long left, long right) {
return left + right;
}
@Fallback
protected Object addGeneric(Object left, Object right) {
// Fallback to generic addition
if (left instanceof Number && right instanceof Number) {
return ((Number) left).doubleValue() + ((Number) right).doubleValue();
}
throw new UnsupportedOperationException("Cannot add " + left + " and " + right);
}
}
public abstract class ExpressionNode extends Node {
public abstract Object execute(VirtualFrame frame);
}
2. Specialized Arithmetic Operations
import com.oracle.truffle.api.dsl.*;
import com.oracle.truffle.api.CompilerDirectives.*;
@NodeChildren({
@NodeChild("left"),
@NodeChild("right")
})
public abstract class ArithmeticNode extends ExpressionNode {
public static ArithmeticNode create(ExpressionNode left, ExpressionNode right, String operator) {
switch (operator) {
case "+": return AddNodeGen.create(left, right);
case "-": return SubtractNodeGen.create(left, right);
case "*": return MultiplyNodeGen.create(left, right);
case "/": return DivideNodeGen.create(left, right);
default: throw new IllegalArgumentException("Unknown operator: " + operator);
}
}
}
@GenerateNodeFactory
abstract class AddNode extends ArithmeticNode {
@Specialization(guards = {"isInt(left)", "isInt(right)"})
protected int addInt(int left, int right) {
return left + right;
}
@Specialization(guards = {"isDouble(left)", "isDouble(right)"})
protected double addDouble(double left, double right) {
return left + right;
}
@Specialization(guards = {"isString(left)", "isString(right)"})
protected String addString(String left, String right) {
return left + right;
}
@Specialization
protected Object addGeneric(Object left, Object right) {
CompilerDirectives.transferToInterpreter();
if (left instanceof Number && right instanceof Number) {
return ((Number) left).doubleValue() + ((Number) right).doubleValue();
}
return left.toString() + right.toString();
}
protected static boolean isInt(Object value) {
return value instanceof Integer;
}
protected static boolean isDouble(Object value) {
return value instanceof Double;
}
protected static boolean isString(Object value) {
return value instanceof String;
}
}
abstract class SubtractNode extends ArithmeticNode {
@Specialization(guards = {"isInt(left)", "isInt(right)"})
protected int subtractInt(int left, int right) {
return left - right;
}
@Specialization(guards = {"isDouble(left)", "isDouble(right)"})
protected double subtractDouble(double left, double right) {
return left - right;
}
@Specialization
protected double subtractGeneric(Object left, Object right) {
CompilerDirectives.transferToInterpreter();
if (left instanceof Number && right instanceof Number) {
return ((Number) left).doubleValue() - ((Number) right).doubleValue();
}
throw new UnsupportedOperationException("Cannot subtract " + left + " and " + right);
}
protected static boolean isInt(Object value) {
return value instanceof Integer;
}
protected static boolean isDouble(Object value) {
return value instanceof Double;
}
}
Advanced Partial Evaluation Patterns
1. Polymorphic Dispatch with Caching
import com.oracle.truffle.api.dsl.*;
import com.oracle.truffle.api.nodes.*;
import com.oracle.truffle.api.CompilerDirectives.*;
import com.oracle.truffle.api.CompilerDirectives.CompilationFinal;
public class PolymorphicDispatchExample {
public static class MethodCache {
private final String methodName;
@CompilationFinal private volatile int cachedType;
@CompilationFinal private volatile Object cachedTarget;
@CompilationFinal private volatile DispatchNode cachedNode;
public MethodCache(String methodName) {
this.methodName = methodName;
}
public Object execute(Object receiver, Object[] arguments) {
DispatchNode node = this.cachedNode;
if (node != null && node.canDispatch(receiver)) {
return node.execute(receiver, arguments);
}
return slowPath(receiver, arguments);
}
@TruffleBoundary
private Object slowPath(Object receiver, Object[] arguments) {
CompilerDirectives.transferToInterpreterAndInvalidate();
// Create specialized node based on receiver type
DispatchNode newNode;
if (receiver instanceof String) {
newNode = new StringDispatchNode(methodName);
} else if (receiver instanceof Integer) {
newNode = new IntegerDispatchNode(methodName);
} else if (receiver instanceof Double) {
newNode = new DoubleDispatchNode(methodName);
} else {
newNode = new GenericDispatchNode(methodName);
}
// Update cache
this.cachedNode = newNode;
return newNode.execute(receiver, arguments);
}
}
abstract static class DispatchNode extends Node {
protected final String methodName;
public DispatchNode(String methodName) {
this.methodName = methodName;
}
public abstract boolean canDispatch(Object receiver);
public abstract Object execute(Object receiver, Object[] arguments);
}
static class StringDispatchNode extends DispatchNode {
public StringDispatchNode(String methodName) {
super(methodName);
}
@Override
public boolean canDispatch(Object receiver) {
return receiver instanceof String;
}
@Override
public Object execute(Object receiver, Object[] arguments) {
String str = (String) receiver;
switch (methodName) {
case "length":
return str.length();
case "toUpperCase":
return str.toUpperCase();
case "toLowerCase":
return str.toLowerCase();
default:
throw new UnsupportedOperationException("Unknown method: " + methodName);
}
}
}
static class IntegerDispatchNode extends DispatchNode {
public IntegerDispatchNode(String methodName) {
super(methodName);
}
@Override
public boolean canDispatch(Object receiver) {
return receiver instanceof Integer;
}
@Override
public Object execute(Object receiver, Object[] arguments) {
Integer integer = (Integer) receiver;
switch (methodName) {
case "doubleValue":
return integer.doubleValue();
case "floatValue":
return integer.floatValue();
default:
throw new UnsupportedOperationException("Unknown method: " + methodName);
}
}
}
static class GenericDispatchNode extends DispatchNode {
public GenericDispatchNode(String methodName) {
super(methodName);
}
@Override
public boolean canDispatch(Object receiver) {
return true; // Always applicable
}
@Override
@TruffleBoundary
public Object execute(Object receiver, Object[] arguments) {
// Reflection-based fallback
try {
java.lang.reflect.Method method = receiver.getClass().getMethod(methodName);
return method.invoke(receiver);
} catch (Exception e) {
throw new RuntimeException("Method not found: " + methodName, e);
}
}
}
}
2. Specialized Data Structure Access
import com.oracle.truffle.api.dsl.*;
import com.oracle.truffle.api.CompilerDirectives.*;
import com.oracle.truffle.api.CompilerDirectives.CompilationFinal;
public class SpecializedDataStructures {
@GenerateNodeFactory
abstract static class ArrayAccessNode extends ExpressionNode {
@Specialization(guards = {"array.isIntArray()", "isIntIndex(index)"})
protected int readIntArray(SpecializedArray array, int index) {
return array.getInt(index);
}
@Specialization(guards = {"array.isDoubleArray()", "isIntIndex(index)"})
protected double readDoubleArray(SpecializedArray array, int index) {
return array.getDouble(index);
}
@Specialization(guards = {"array.isObjectArray()", "isIntIndex(index)"})
protected Object readObjectArray(SpecializedArray array, int index) {
return array.getObject(index);
}
@Specialization(guards = "isIntIndex(index)")
protected Object readGenericArray(SpecializedArray array, int index) {
CompilerDirectives.transferToInterpreter();
return array.getGeneric(index);
}
protected static boolean isIntIndex(Object index) {
return index instanceof Integer;
}
}
static class SpecializedArray {
private final Object storage;
private final Class<?> componentType;
@CompilationFinal private boolean intArray;
@CompilationFinal private boolean doubleArray;
@CompilationFinal private boolean objectArray;
public SpecializedArray(Class<?> componentType, int size) {
this.componentType = componentType;
if (componentType == int.class) {
this.storage = new int[size];
this.intArray = true;
} else if (componentType == double.class) {
this.storage = new double[size];
this.doubleArray = true;
} else {
this.storage = new Object[size];
this.objectArray = true;
}
}
public boolean isIntArray() {
return intArray;
}
public boolean isDoubleArray() {
return doubleArray;
}
public boolean isObjectArray() {
return objectArray;
}
public int getInt(int index) {
if (intArray) {
return ((int[]) storage)[index];
}
throw new ClassCastException("Not an int array");
}
public double getDouble(int index) {
if (doubleArray) {
return ((double[]) storage)[index];
}
throw new ClassCastException("Not a double array");
}
public Object getObject(int index) {
if (objectArray) {
return ((Object[]) storage)[index];
}
throw new ClassCastException("Not an object array");
}
@TruffleBoundary
public Object getGeneric(int index) {
if (intArray) return getInt(index);
if (doubleArray) return getDouble(index);
if (objectArray) return getObject(index);
throw new IllegalStateException("Unknown array type");
}
public void setInt(int index, int value) {
if (intArray) {
((int[]) storage)[index] = value;
return;
}
throw new ClassCastException("Not an int array");
}
}
@GenerateNodeFactory
abstract static class ArrayStoreNode extends ExpressionNode {
@Specialization(guards = {"array.isIntArray()", "isIntIndex(index)", "isIntValue(value)"})
protected void storeIntArray(SpecializedArray array, int index, int value) {
array.setInt(index, value);
}
@Specialization(guards = {"array.isDoubleArray()", "isIntIndex(index)", "isDoubleValue(value)"})
protected void storeDoubleArray(SpecializedArray array, int index, double value) {
// Implementation for double array
}
@Specialization(guards = {"array.isObjectArray()", "isIntIndex(index)"})
protected void storeObjectArray(SpecializedArray array, int index, Object value) {
// Implementation for object array
}
@Specialization(guards = "isIntIndex(index)")
protected void storeGenericArray(SpecializedArray array, int index, Object value) {
CompilerDirectives.transferToInterpreter();
// Generic storage implementation
}
protected static boolean isIntIndex(Object index) {
return index instanceof Integer;
}
protected static boolean isIntValue(Object value) {
return value instanceof Integer;
}
protected static boolean isDoubleValue(Object value) {
return value instanceof Double;
}
}
}
Partial Evaluation with Assumptions
1. Monomorphic and Polymorphic Inline Caches
import com.oracle.truffle.api.*;
import com.oracle.truffle.api.CompilerDirectives.*;
import com.oracle.truffle.api.CompilerDirectives.CompilationFinal;
import com.oracle.truffle.api.utilities.*;
public class InlineCacheExample {
public static class PropertyAccessNode extends Node {
private final String propertyName;
@CompilationFinal private Assumption monomorphicAssumption;
@CompilationFinal private Class<?> cachedClass;
@CompilationFinal private Object cachedValue;
private final CyclicAssumption stability;
public PropertyAccessNode(String propertyName) {
this.propertyName = propertyName;
this.stability = new CyclicAssumption(propertyName);
this.monomorphicAssumption = stability.getAssumption();
}
public Object execute(Object object) {
// Monomorphic case: same class as before
if (monomorphicAssumption.isValid() && object.getClass() == cachedClass) {
return cachedValue;
}
return slowPath(object);
}
@TruffleBoundary
private Object slowPath(Object object) {
CompilerDirectives.transferToInterpreterAndInvalidate();
// Lookup property value
Object value = lookupProperty(object, propertyName);
// Update cache if still monomorphic
if (monomorphicAssumption.isValid()) {
if (cachedClass == null) {
// First time - initialize cache
cachedClass = object.getClass();
cachedValue = value;
} else if (cachedClass != object.getClass()) {
// Became polymorphic - invalidate assumption
monomorphicAssumption.invalidate();
monomorphicAssumption = NeverValidAssumption.INSTANCE;
}
}
return value;
}
private Object lookupProperty(Object object, String propertyName) {
// Simplified property lookup
try {
java.lang.reflect.Field field = object.getClass().getField(propertyName);
return field.get(object);
} catch (Exception e) {
throw new RuntimeException("Property not found: " + propertyName, e);
}
}
}
public static class PolymorphicInlineCache extends Node {
private final String methodName;
private final int maxSize;
@CompilationFinal(dimensions = 1) private Class<?>[] cachedClasses;
@CompilationFinal(dimensions = 1) private Object[] cachedValues;
@CompilationFinal private int cacheSize;
public PolymorphicInlineCache(String methodName, int maxSize) {
this.methodName = methodName;
this.maxSize = maxSize;
this.cachedClasses = new Class<?>[maxSize];
this.cachedValues = new Object[maxSize];
this.cacheSize = 0;
}
public Object execute(Object receiver) {
Class<?> receiverClass = receiver.getClass();
// Check cache
for (int i = 0; i < cacheSize; i++) {
if (cachedClasses[i] == receiverClass) {
return cachedValues[i];
}
}
return slowPath(receiver, receiverClass);
}
@TruffleBoundary
private Object slowPath(Object receiver, Class<?> receiverClass) {
CompilerDirectives.transferToInterpreterAndInvalidate();
// Compute value
Object value = computeValue(receiver);
// Update cache if there's space
if (cacheSize < maxSize) {
cachedClasses[cacheSize] = receiverClass;
cachedValues[cacheSize] = value;
cacheSize++;
}
return value;
}
private Object computeValue(Object receiver) {
// Simplified value computation
try {
java.lang.reflect.Method method = receiver.getClass().getMethod(methodName);
return method.invoke(receiver);
} catch (Exception e) {
throw new RuntimeException("Method not found: " + methodName, e);
}
}
}
}
2. Type Specialization with Guards
import com.oracle.truffle.api.dsl.*;
import com.oracle.truffle.api.CompilerDirectives.*;
import com.oracle.truffle.api.CompilerDirectives.CompilationFinal;
public class TypeSpecializationExample {
public static class TypeProfile {
@CompilationFinal private Class<?> primaryType;
@CompilationFinal private Class<?> secondaryType;
@CompilationFinal private boolean isMonomorphic;
@CompilationFinal private boolean isPolymorphic;
@CompilationFinal private boolean isMegamorphic;
private int primaryCount;
private int secondaryCount;
private int otherCount;
public TypeProfile() {
this.isMonomorphic = true;
}
public void recordType(Class<?> type) {
if (primaryType == null) {
primaryType = type;
primaryCount = 1;
} else if (primaryType == type) {
primaryCount++;
} else if (secondaryType == null) {
secondaryType = type;
secondaryCount = 1;
updatePolymorphism();
} else if (secondaryType == type) {
secondaryCount++;
updatePolymorphism();
} else {
otherCount++;
if (otherCount > 5) {
CompilerDirectives.transferToInterpreterAndInvalidate();
isMegamorphic = true;
isPolymorphic = false;
isMonomorphic = false;
}
}
}
private void updatePolymorphism() {
if (primaryCount + secondaryCount > 10) {
CompilerDirectives.transferToInterpreterAndInvalidate();
if (primaryCount > secondaryCount * 2) {
isMonomorphic = true;
isPolymorphic = false;
} else {
isPolymorphic = true;
isMonomorphic = false;
}
}
}
public boolean isMonomorphic() { return isMonomorphic; }
public boolean isPolymorphic() { return isPolymorphic; }
public boolean isMegamorphic() { return isMegamorphic; }
public Class<?> getPrimaryType() { return primaryType; }
public Class<?> getSecondaryType() { return secondaryType; }
}
@GenerateNodeFactory
abstract static class TypeSpecializedNode extends ExpressionNode {
protected final TypeProfile profile = new TypeProfile();
@Specialization(guards = "isMonomorphicInt()")
protected int monomorphicInt(Object value) {
return (Integer) value;
}
@Specialization(guards = "isMonomorphicDouble()")
protected double monomorphicDouble(Object value) {
return (Double) value;
}
@Specialization(guards = "isPolymorphicNumeric()")
protected double polymorphicNumeric(Object value) {
profile.recordType(value.getClass());
return ((Number) value).doubleValue();
}
@Specialization
protected Object generic(Object value) {
profile.recordType(value.getClass());
CompilerDirectives.transferToInterpreter();
return value;
}
protected boolean isMonomorphicInt() {
return profile.isMonomorphic() && profile.getPrimaryType() == Integer.class;
}
protected boolean isMonomorphicDouble() {
return profile.isMonomorphic() && profile.getPrimaryType() == Double.class;
}
protected boolean isPolymorphicNumeric() {
return profile.isPolymorphic() &&
(profile.getPrimaryType() == Integer.class || profile.getPrimaryType() == Double.class) &&
(profile.getSecondaryType() == Integer.class || profile.getSecondaryType() == Double.class);
}
}
}
Practical Use Cases
1. JSON Parser with Partial Evaluation
import com.oracle.truffle.api.dsl.*;
import com.oracle.truffle.api.CompilerDirectives.*;
import com.oracle.truffle.api.nodes.Node;
public class JSONParserExample {
public static class JSONParser {
private final String input;
private int position;
public JSONParser(String input) {
this.input = input;
this.position = 0;
}
public Object parse() {
return parseValue();
}
private Object parseValue() {
skipWhitespace();
char c = input.charAt(position);
if (c == '"') return parseString();
if (c == '{') return parseObject();
if (c == '[') return parseArray();
if (c == 't' || c == 'f') return parseBoolean();
if (c == 'n') return parseNull();
if (Character.isDigit(c) || c == '-') return parseNumber();
throw new JSONParseException("Unexpected character: " + c);
}
private String parseString() {
// String parsing implementation
return "";
}
private Object parseObject() {
// Object parsing implementation
return new Object();
}
private Object parseArray() {
// Array parsing implementation
return new Object[0];
}
private boolean parseBoolean() {
// Boolean parsing implementation
return false;
}
private Object parseNull() {
// Null parsing implementation
return null;
}
private Object parseNumber() {
// Number parsing implementation
return 0;
}
private void skipWhitespace() {
// Whitespace skipping implementation
}
}
@GenerateNodeFactory
abstract static class JSONParseNode extends Node {
@Specialization(guards = "isStringLiteral(input, position)")
protected String parseString(String input, int position) {
// Specialized string parsing
return parseStringLiteral(input, position);
}
@Specialization(guards = "isNumberLiteral(input, position)")
protected Object parseNumber(String input, int position) {
// Specialized number parsing
return parseNumberLiteral(input, position);
}
@Specialization(guards = "isObjectLiteral(input, position)")
protected Object parseObject(String input, int position) {
// Specialized object parsing
return parseObjectLiteral(input, position);
}
@Specialization(guards = "isArrayLiteral(input, position)")
protected Object parseArray(String input, int position) {
// Specialized array parsing
return parseArrayLiteral(input, position);
}
@Specialization
protected Object parseGeneric(String input, int position) {
CompilerDirectives.transferToInterpreter();
// Generic parsing fallback
return new JSONParser(input.substring(position)).parse();
}
protected static boolean isStringLiteral(String input, int position) {
return position < input.length() && input.charAt(position) == '"';
}
protected static boolean isNumberLiteral(String input, int position) {
if (position >= input.length()) return false;
char c = input.charAt(position);
return Character.isDigit(c) || c == '-';
}
protected static boolean isObjectLiteral(String input, int position) {
return position < input.length() && input.charAt(position) == '{';
}
protected static boolean isArrayLiteral(String input, int position) {
return position < input.length() && input.charAt(position) == '[';
}
private String parseStringLiteral(String input, int position) {
// Implementation for string literal parsing
return "";
}
private Object parseNumberLiteral(String input, int position) {
// Implementation for number literal parsing
return 0;
}
private Object parseObjectLiteral(String input, int position) {
// Implementation for object literal parsing
return new Object();
}
private Object parseArrayLiteral(String input, int position) {
// Implementation for array literal parsing
return new Object[0];
}
}
public static class JSONParseException extends RuntimeException {
public JSONParseException(String message) {
super(message);
}
}
}
2. Database Query Optimizer
import com.oracle.truffle.api.dsl.*;
import com.oracle.truffle.api.CompilerDirectives.*;
import com.oracle.truffle.api.CompilerDirectives.CompilationFinal;
import java.util.*;
public class DatabaseQueryOptimization {
public static class QueryPlan {
private final List<QueryNode> nodes = new ArrayList<>();
public void addNode(QueryNode node) {
nodes.add(node);
}
public Object execute(Map<String, Object> context) {
Object result = null;
for (QueryNode node : nodes) {
result = node.execute(context);
}
return result;
}
}
public abstract static class QueryNode extends Node {
public abstract Object execute(Map<String, Object> context);
}
@GenerateNodeFactory
abstract static class FilterNode extends QueryNode {
@Child private QueryNode source;
@Child private ExpressionNode predicate;
public FilterNode(QueryNode source, ExpressionNode predicate) {
this.source = source;
this.predicate = predicate;
}
@Specialization(guards = "isConstantPredicate()")
protected Object executeConstant(Map<String, Object> context) {
Object sourceResult = source.execute(context);
Boolean predicateResult = (Boolean) predicate.execute(context);
return predicateResult ? sourceResult : null;
}
@Specialization
protected Object executeDynamic(Map<String, Object> context) {
Object sourceResult = source.execute(context);
Boolean predicateResult = (Boolean) predicate.execute(context);
return predicateResult ? sourceResult : null;
}
protected boolean isConstantPredicate() {
return predicate instanceof ConstantExpressionNode;
}
}
@GenerateNodeFactory
abstract static class ProjectionNode extends QueryNode {
@Child private QueryNode source;
private final List<String> columns;
public ProjectionNode(QueryNode source, List<String> columns) {
this.source = source;
this.columns = columns;
}
@Specialization(guards = "isSingleColumn()")
protected Object executeSingleColumn(Map<String, Object> context) {
Object sourceResult = source.execute(context);
if (sourceResult instanceof Map) {
return ((Map<?, ?>) sourceResult).get(columns.get(0));
}
return sourceResult;
}
@Specialization
protected Object executeMultiColumn(Map<String, Object> context) {
Object sourceResult = source.execute(context);
if (sourceResult instanceof Map) {
Map<String, Object> result = new HashMap<>();
for (String column : columns) {
result.put(column, ((Map<?, ?>) sourceResult).get(column));
}
return result;
}
return sourceResult;
}
protected boolean isSingleColumn() {
return columns.size() == 1;
}
}
abstract static class ExpressionNode extends Node {
public abstract Object execute(Map<String, Object> context);
}
static class ConstantExpressionNode extends ExpressionNode {
private final Object value;
public ConstantExpressionNode(Object value) {
this.value = value;
}
@Override
public Object execute(Map<String, Object> context) {
return value;
}
}
@GenerateNodeFactory
abstract static class ComparisonNode extends ExpressionNode {
@Child private ExpressionNode left;
@Child private ExpressionNode right;
public ComparisonNode(ExpressionNode left, ExpressionNode right) {
this.left = left;
this.right = right;
}
@Specialization(guards = {"isInt(leftResult)", "isInt(rightResult)"})
protected boolean compareInts(Object leftResult, Object rightResult) {
return ((Integer) leftResult).compareTo((Integer) rightResult) > 0;
}
@Specialization(guards = {"isDouble(leftResult)", "isDouble(rightResult)"})
protected boolean compareDoubles(Object leftResult, Object rightResult) {
return ((Double) leftResult).compareTo((Double) rightResult) > 0;
}
@Specialization
protected boolean compareGeneric(Object leftResult, Object rightResult) {
CompilerDirectives.transferToInterpreter();
if (leftResult instanceof Comparable && rightResult instanceof Comparable) {
return ((Comparable) leftResult).compareTo(rightResult) > 0;
}
return false;
}
@Override
public Object execute(Map<String, Object> context) {
Object leftResult = left.execute(context);
Object rightResult = right.execute(context);
return compare(leftResult, rightResult);
}
protected boolean compare(Object left, Object right) {
// Default implementation
return false;
}
protected static boolean isInt(Object value) {
return value instanceof Integer;
}
protected static boolean isDouble(Object value) {
return value instanceof Double;
}
}
}
Performance Optimization Techniques
1. Loop Specialization and Unrolling
import com.oracle.truffle.api.dsl.*;
import com.oracle.truffle.api.CompilerDirectives.*;
import com.oracle.truffle.api.loop.*;
public class LoopOptimization {
@GenerateNodeFactory
abstract static class SpecializedLoopNode extends Node {
@Specialization(guards = {"isIntArray(array)", "isSmallArray(array)"})
protected int smallIntArrayLoop(Object array, LoopBody body) {
int[] intArray = (int[]) array;
int sum = 0;
for (int i = 0; i < intArray.length; i++) {
sum += body.execute(intArray[i]);
}
return sum;
}
@Specialization(guards = "isIntArray(array)")
protected int largeIntArrayLoop(Object array, LoopBody body) {
int[] intArray = (int[]) array;
int sum = 0;
for (int value : intArray) {
sum += body.execute(value);
}
return sum;
}
@Specialization(guards = "isDoubleArray(array)")
protected double doubleArrayLoop(Object array, LoopBody body) {
double[] doubleArray = (double[]) array;
double sum = 0;
for (double value : doubleArray) {
sum += body.execute(value);
}
return sum;
}
@Specialization
protected Object genericLoop(Object array, LoopBody body) {
CompilerDirectives.transferToInterpreter();
Object[] objectArray = (Object[]) array;
Object result = null;
for (Object value : objectArray) {
result = body.execute(value);
}
return result;
}
protected static boolean isIntArray(Object array) {
return array instanceof int[];
}
protected static boolean isDoubleArray(Object array) {
return array instanceof double[];
}
protected static boolean isSmallArray(Object array) {
if (array instanceof int[]) {
return ((int[]) array).length <= 10;
}
return false;
}
}
@FunctionalInterface
interface LoopBody {
Object execute(Object value);
}
public static class CountedLoopNode extends Node {
private final int iterations;
@CompilationFinal private boolean unrolled;
public CountedLoopNode(int iterations) {
this.iterations = iterations;
this.unrolled = iterations <= 8; // Unroll small loops
}
public void execute(Runnable body) {
if (unrolled) {
executeUnrolled(body);
} else {
executeNormal(body);
}
}
private void executeUnrolled(Runnable body) {
// Manually unroll the loop
switch (iterations) {
case 8: body.run();
case 7: body.run();
case 6: body.run();
case 5: body.run();
case 4: body.run();
case 3: body.run();
case 2: body.run();
case 1: body.run();
}
}
private void executeNormal(Runnable body) {
for (int i = 0; i < iterations; i++) {
body.run();
}
}
}
}
Best Practices for Partial Evaluation
- Use Specializations Wisely: Create specializations for common cases
- Minimize Transfers to Interpreter: Use
@TruffleBoundaryfor complex operations - Use Guards Effectively: Guards should be cheap and meaningful
- Profile Dynamically: Use type profiles and runtime feedback
- Handle Deoptimization Gracefully: Ensure code works correctly after deoptimization
- Cache Expensive Operations: Use compilation-final fields for caching
- Balance Specialization and Generality: Don't over-specialize for rare cases
Partial evaluation in GraalVM enables high-performance execution of dynamic languages by specializing code based on runtime observations. The key is to identify hot paths and create specialized versions that can be aggressively optimized by the Graal compiler.