ibessonov commented on code in PR #6316: URL: https://github.com/apache/ignite-3/pull/6316#discussion_r2236766499
########## modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/comparator/JitComparatorGenerator.java: ########## @@ -0,0 +1,661 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.internal.storage.pagememory.index.sorted.comparator; + +import static com.facebook.presto.bytecode.control.SwitchStatement.switchBuilder; +import static com.facebook.presto.bytecode.expression.BytecodeExpressions.add; +import static com.facebook.presto.bytecode.expression.BytecodeExpressions.bitwiseAnd; +import static com.facebook.presto.bytecode.expression.BytecodeExpressions.bitwiseOr; +import static com.facebook.presto.bytecode.expression.BytecodeExpressions.constantInt; +import static com.facebook.presto.bytecode.expression.BytecodeExpressions.equal; +import static com.facebook.presto.bytecode.expression.BytecodeExpressions.invokeStatic; +import static com.facebook.presto.bytecode.expression.BytecodeExpressions.notEqual; +import static com.facebook.presto.bytecode.instruction.JumpInstruction.jump; +import static org.apache.ignite.internal.binarytuple.BinaryTupleParser.shortValue; +import static org.apache.ignite.internal.lang.IgniteStringFormatter.format; + +import com.facebook.presto.bytecode.Access; +import com.facebook.presto.bytecode.BytecodeBlock; +import com.facebook.presto.bytecode.ClassDefinition; +import com.facebook.presto.bytecode.ClassGenerator; +import com.facebook.presto.bytecode.MethodDefinition; +import com.facebook.presto.bytecode.Parameter; +import com.facebook.presto.bytecode.ParameterizedType; +import com.facebook.presto.bytecode.Scope; +import com.facebook.presto.bytecode.Variable; +import com.facebook.presto.bytecode.control.IfStatement; +import com.facebook.presto.bytecode.control.SwitchStatement.SwitchBuilder; +import com.facebook.presto.bytecode.expression.BytecodeExpression; +import com.facebook.presto.bytecode.instruction.LabelNode; +import com.facebook.presto.bytecode.instruction.VariableInstruction.LoadVariableInstruction; +import java.lang.reflect.Method; +import java.math.BigDecimal; +import java.math.BigInteger; +import java.nio.file.Path; +import java.time.LocalDate; +import java.time.LocalDateTime; +import java.time.LocalTime; +import java.time.chrono.ChronoLocalDate; +import java.time.chrono.ChronoLocalDateTime; +import java.util.EnumSet; +import java.util.List; +import java.util.concurrent.atomic.AtomicInteger; +import org.apache.ignite.internal.binarytuple.BinaryTupleCommon; +import org.apache.ignite.internal.binarytuple.BinaryTupleFormatException; +import org.apache.ignite.internal.binarytuple.BinaryTupleParser; +import org.apache.ignite.internal.binarytuple.BinaryTupleReader; +import org.apache.ignite.internal.binarytuple.ByteBufferAccessor; +import org.apache.ignite.internal.catalog.descriptors.CatalogColumnCollation; +import org.apache.ignite.internal.lang.IgniteInternalException; +import org.apache.ignite.internal.schema.BinaryTupleComparatorUtils; +import org.apache.ignite.internal.schema.UnsafeByteBufferAccessor; +import org.apache.ignite.internal.type.NativeType; +import org.apache.ignite.internal.util.GridUnsafe; +import org.apache.ignite.lang.ErrorGroups.Common; + +/** + * Generator for implementation of {@link JitComparator} using bytecode generation. + */ +public class JitComparatorGenerator { + /** + * Class generator. Please use {@link ClassGenerator#dumpClassFilesTo(Path)} for debugging or investigations. + */ + private static final ClassGenerator CLASS_GENERATOR = ClassGenerator.classGenerator(JitComparatorGenerator.class.getClassLoader()); + + // Methods of BinaryTupleParser. + private static final Method PARSER_BYTE_VALUE; + private static final Method PARSER_SHORT_VALUE; + private static final Method PARSER_INT_VALUE; + private static final Method PARSER_LONG_VALUE; + private static final Method PARSER_FLOAT_VALUE; + private static final Method PARSER_DOUBLE_VALUE; + private static final Method PARSER_DATE_VALUE; + private static final Method PARSER_TIME_VALUE; + private static final Method PARSER_DATETIME_VALUE; + + // "compare" methods of primitive types. + private static final Method BYTE_COMPARE; + private static final Method SHORT_COMPARE; + private static final Method INT_COMPARE; + private static final Method LONG_COMPARE; + private static final Method FLOAT_COMPARE; + private static final Method DOUBLE_COMPARE; + + // Methods of BinaryTupleComparatorUtils. + private static final Method UTILS_TIMESTAMP_COMPARE; + private static final Method UTILS_UUID_COMPARE; + private static final Method UTILS_STRING_COMPARE; + private static final Method UTILS_BYTES_COMPARE; + + // "compareBigDecimal" from this class. + private static final Method DECIMAL_COMPARE; + + // "compareTo" methods of LocalDate, LocalTime, and LocalDateTime. + private static final Method DATE_COMPARE_TO; + private static final Method TIME_COMPARE_TO; + private static final Method DATETIME_COMPARE_TO; + + static { + try { + PARSER_BYTE_VALUE = BinaryTupleParser.class.getDeclaredMethod("byteValue", ByteBufferAccessor.class, int.class, int.class); + PARSER_SHORT_VALUE = BinaryTupleParser.class.getDeclaredMethod("shortValue", ByteBufferAccessor.class, int.class, int.class); + PARSER_INT_VALUE = BinaryTupleParser.class.getDeclaredMethod("intValue", ByteBufferAccessor.class, int.class, int.class); + PARSER_LONG_VALUE = BinaryTupleParser.class.getDeclaredMethod("longValue", ByteBufferAccessor.class, int.class, int.class); + PARSER_FLOAT_VALUE = BinaryTupleParser.class.getDeclaredMethod("floatValue", ByteBufferAccessor.class, int.class, int.class); + PARSER_DOUBLE_VALUE = BinaryTupleParser.class.getDeclaredMethod("doubleValue", ByteBufferAccessor.class, int.class, int.class); + PARSER_DATE_VALUE = BinaryTupleParser.class.getDeclaredMethod("dateValue", ByteBufferAccessor.class, int.class, int.class); + PARSER_TIME_VALUE = BinaryTupleParser.class.getDeclaredMethod("timeValue", ByteBufferAccessor.class, int.class, int.class); + PARSER_DATETIME_VALUE = BinaryTupleParser.class.getDeclaredMethod( + "dateTimeValue", ByteBufferAccessor.class, int.class, int.class + ); + + BYTE_COMPARE = Byte.class.getDeclaredMethod("compare", byte.class, byte.class); + SHORT_COMPARE = Short.class.getDeclaredMethod("compare", short.class, short.class); + INT_COMPARE = Integer.class.getDeclaredMethod("compare", int.class, int.class); + LONG_COMPARE = Long.class.getDeclaredMethod("compare", long.class, long.class); + FLOAT_COMPARE = Float.class.getDeclaredMethod("compare", float.class, float.class); + DOUBLE_COMPARE = Double.class.getDeclaredMethod("compare", double.class, double.class); + + UTILS_TIMESTAMP_COMPARE = BinaryTupleComparatorUtils.class.getDeclaredMethod( + "compareAsTimestamp", ByteBufferAccessor.class, int.class, int.class, ByteBufferAccessor.class, int.class, int.class + ); + UTILS_UUID_COMPARE = BinaryTupleComparatorUtils.class.getDeclaredMethod( + "compareAsUuid", ByteBufferAccessor.class, int.class, ByteBufferAccessor.class, int.class + ); + UTILS_STRING_COMPARE = BinaryTupleComparatorUtils.class.getDeclaredMethod( + "compareAsString", ByteBufferAccessor.class, int.class, int.class, ByteBufferAccessor.class, int.class, int.class + ); + UTILS_BYTES_COMPARE = BinaryTupleComparatorUtils.class.getDeclaredMethod( + "compareAsBytes", ByteBufferAccessor.class, int.class, int.class, ByteBufferAccessor.class, int.class, int.class + ); + + DECIMAL_COMPARE = JitComparatorGenerator.class.getDeclaredMethod( + "compareBigDecimal", + UnsafeByteBufferAccessor.class, int.class, int.class, UnsafeByteBufferAccessor.class, int.class, int.class + ); + + DATE_COMPARE_TO = LocalDate.class.getDeclaredMethod("compareTo", ChronoLocalDate.class); + TIME_COMPARE_TO = LocalTime.class.getDeclaredMethod("compareTo", LocalTime.class); + DATETIME_COMPARE_TO = LocalDateTime.class.getDeclaredMethod("compareTo", ChronoLocalDateTime.class); + } catch (NoSuchMethodException e) { + throw new ExceptionInInitializerError(e); + } + } + + /** Counter for generating class names. */ + private static final AtomicInteger CLASS_NAME_COUNTER = new AtomicInteger(); + + /** + * Creates an instance of {@link JitComparator} using bytecode generation. + * + * @param columnCollations List of column collations. + * @param columnTypes List of column types. + * @param nullableFlags List of nullability flags for each column. + */ + public static JitComparator createComparator( + List<CatalogColumnCollation> columnCollations, + List<NativeType> columnTypes, + List<Boolean> nullableFlags + ) { + int maxEntrySizeLog = maxEntrySizeLog(columnTypes); + + // Name "org/apache/ignite/internal/storage/pagememory/index/sorted/comparator/JitComparatorGenerator&&<idx>" is used for generated + // classes. + ClassDefinition classDefinition = new ClassDefinition( + EnumSet.of(Access.PUBLIC, Access.FINAL), + JitComparator.class.getName().replace('.', '/') + "$$" + CLASS_NAME_COUNTER.getAndIncrement(), + ParameterizedType.type(Object.class), + ParameterizedType.type(JitComparator.class) + ); + + // The implementation of the "JitComparator#compare" method. + MethodDefinition compare = classDefinition.declareMethod( + EnumSet.of(Access.PUBLIC, Access.FINAL), + "compare", + ParameterizedType.type(int.class), + Parameter.arg("outerAccessor", UnsafeByteBufferAccessor.class), + Parameter.arg("outerSize", int.class), + Parameter.arg("innerAccessor", UnsafeByteBufferAccessor.class), + Parameter.arg("innerSize", int.class) + ); + compare.declareAnnotation(Override.class); + + Scope scope = compare.getScope(); + BytecodeBlock body = compare.getBody(); + + // Method parameters. + Variable outerAccessor = scope.getVariable("outerAccessor"); + Variable innerAccessor = scope.getVariable("innerAccessor"); + Variable outerSize = scope.getVariable("outerSize"); + Variable innerSize = scope.getVariable("innerSize"); + + // Variables for entry sizes. If the "maxEntrySizeLog" is "0", then these variables will left unused, because we know their value at + // compile time (it's always zero). + Variable outerEntrySize = scope.declareVariable(int.class, "outerEntrySize"); + Variable innerEntrySize = scope.declareVariable(int.class, "innerEntrySize"); + + if (maxEntrySizeLog != 0) { + // If entry size can be more than 1, then we read it from headers of tuples like this: + // int outerFlag = outerAccessor.get(0) & BinaryTupleCommon.VARSIZE_MASK; + // int outerEntrySize = 1 << outerFlag; + Variable outerFlag = scope.declareVariable(byte.class, "outerFlag"); + Variable innerFlag = scope.declareVariable(byte.class, "innerFlag"); + + body.append(outerFlag.set(outerAccessor.invoke("get", byte.class, constantInt(0)))); + body.append(innerFlag.set(innerAccessor.invoke("get", byte.class, constantInt(0)))); + + body.append(outerEntrySize.set(bitwiseAnd(outerFlag.cast(int.class), constantInt(BinaryTupleCommon.VARSIZE_MASK)))); + body.append(innerEntrySize.set(bitwiseAnd(innerFlag.cast(int.class), constantInt(BinaryTupleCommon.VARSIZE_MASK)))); + } + + // Here we generate all possible combinations of comparators for all possible entry sizes. These methods will look like this + // int innerCompareXY(UnsafeByteBufferAccessor outerAccessor, int outerSize, UnsafeByteBufferAccessor innerAccessor, int innerSize) + // where X and Y are entry sizes in bytes (1, 2, or 4), for "outer" and "inner" tuples respectively. + MethodDefinition[][] innerCompareMethods = new MethodDefinition[3][3]; + for (int i = 0; i <= maxEntrySizeLog; i++) { + for (int j = 0; j <= maxEntrySizeLog; j++) { + innerCompareMethods[i][j] = innerCompare(classDefinition, columnCollations, columnTypes, nullableFlags, 1 << i, 1 << j); + } + } + + // "compare" method implementation will either look like this: + // return innerCompare11(outerAccessor, outerSize, innerAccessor, innerSize); + // if "maxEntrySize" is zero, or like the comment in "else" branch. + if (maxEntrySizeLog == 0) { + body.append(invokeStatic(innerCompareMethods[0][0], outerAccessor, outerSize, innerAccessor, innerSize).ret()); + } else { + // Alternative representation will look like this (entrySize is either 0, 1 or 2): + // switch (outerEntrySize) { + // case 0: + // switch (innerEntrySize) { + // case 0: + // return innerCompare11(outerAccessor, outerSize, innerAccessor, innerSize); + // case 1: + // return innerCompare12(outerAccessor, outerSize, innerAccessor, innerSize); + // case 2: + // return innerCompare14(outerAccessor, outerSize, innerAccessor, innerSize); + // default: + // return 0; + // } + // case 1: + // switch (innerEntrySize) { + // ... + // } + // "case 2" can be missing if "maxEntrySizeLog" is equal to "1". + SwitchBuilder outerSwitchBuilder = switchBuilder() + .expression(outerEntrySize) + .defaultCase(constantInt(0).ret()); + + for (int i = 0; i <= maxEntrySizeLog; i++) { + SwitchBuilder innerSwitchBuilder = switchBuilder() + .expression(innerEntrySize) + .defaultCase(constantInt(0).ret()); + + for (int j = 0; j <= maxEntrySizeLog; j++) { + MethodDefinition innerCompare = innerCompareMethods[i][j]; + + innerSwitchBuilder.addCase(j, invokeStatic(innerCompare, outerAccessor, outerSize, innerAccessor, innerSize).ret()); + } + + outerSwitchBuilder.addCase(i, innerSwitchBuilder.build()); + } + + body.append(outerSwitchBuilder.build()); + } + + // Final "return 0" statement. + body.append(constantInt(0).ret()); + + // Add default constructor. + MethodDefinition constructor = classDefinition.declareConstructor(EnumSet.of(Access.PUBLIC)); + constructor.getBody() + .append(new LoadVariableInstruction(constructor.getThis())) + .invokeConstructor(Object.class) + .ret(); + + Class<?> clazz = CLASS_GENERATOR.defineClass(classDefinition, Object.class); + try { + return (JitComparator) clazz.getDeclaredConstructor().newInstance(); + } catch (Exception e) { + throw new IgniteInternalException(Common.INTERNAL_ERR, e); + } + } + + /** + * Determines how large the offset value has to be in the worst case for the given column types. + * Returns {@code 0} if {@code 1} byte is enough. + * Returns {@code 1} if {@code 2} bytes are enough. + * Returns {@code 2} otherwise. + * + * @param columnTypes List of column types. + */ + private static int maxEntrySizeLog(List<NativeType> columnTypes) { + if (columnTypes.stream().allMatch(NativeType::fixedLength)) { + int maxFixedSize = columnTypes.stream().mapToInt(NativeType::sizeInBytes).sum(); + if (maxFixedSize < 0x100) { + return 0; + } else if (maxFixedSize < 0x10000) { + return 1; + } else { + return 2; + } + } else { + return 2; + } + } + + /** + * Returns a comparator method, for which both entry sizes are known at compile time. + */ + private static MethodDefinition innerCompare( + ClassDefinition classDefinition, + List<CatalogColumnCollation> columnCollations, + List<NativeType> columnTypes, + List<Boolean> nullableFlags, + int outerEntrySizeConstant, + int innerEntrySizeConstant + ) { + MethodDefinition innerCompare = classDefinition.declareMethod( + EnumSet.of(Access.PRIVATE, Access.STATIC), + "innerCompare" + outerEntrySizeConstant + innerEntrySizeConstant, + ParameterizedType.type(int.class), + Parameter.arg("outerAccessor", UnsafeByteBufferAccessor.class), + Parameter.arg("outerSize", int.class), + Parameter.arg("innerAccessor", UnsafeByteBufferAccessor.class), + Parameter.arg("innerSize", int.class) + ); + + BytecodeBlock body = innerCompare.getBody(); + Scope scope = innerCompare.getScope(); + + Variable outerAccessor = scope.getVariable("outerAccessor"); + Variable innerAccessor = scope.getVariable("innerAccessor"); + Variable outerSize = scope.getVariable("outerSize"); + Variable innerSize = scope.getVariable("innerSize"); + + Variable outerEntryBaseStart = scope.declareVariable(int.class, "outerEntryBaseStart"); + Variable innerEntryBaseStart = scope.declareVariable(int.class, "innerEntryBaseStart"); + + // Here we do exactly the same thing that "BinaryTupleComparator.compare" does, but types and offsets are inlined, and the loop is + // unrolled. Please use that method as a reference for understanding this code. + int columnsSize = columnTypes.size(); + body.append(outerEntryBaseStart.set(constantInt(BinaryTupleCommon.HEADER_SIZE + outerEntrySizeConstant * columnsSize))); + body.append(innerEntryBaseStart.set(constantInt(BinaryTupleCommon.HEADER_SIZE + innerEntrySizeConstant * columnsSize))); + + Variable cmp = scope.declareVariable(int.class, "cmp"); + + Variable outerEntryBaseEnd = scope.declareVariable(int.class, "outerEntryBaseEnd"); + Variable innerEntryBaseEnd = scope.declareVariable(int.class, "innerEntryBaseEnd"); + Variable outerInNull = scope.declareVariable(boolean.class, "outerInNull"); + Variable innerInNull = scope.declareVariable(boolean.class, "innerInNull"); + for (int i = 0; i < columnsSize; i++) { + // Last iteration doesn't need to use "cmp" variable, we can return comparison results directly. + boolean lastIteration = i == columnsSize - 1; + LabelNode endOfBlockLabel = new LabelNode(); + + if (lastIteration) { + body.append(outerEntryBaseEnd.set(outerSize)); + body.append(innerEntryBaseEnd.set(innerSize)); + } else { + body.append(outerEntryBaseEnd.set(add( + constantInt(BinaryTupleCommon.HEADER_SIZE + outerEntrySizeConstant * columnsSize), + getOffset(outerAccessor, outerEntrySizeConstant, i) + ))); + body.append(innerEntryBaseEnd.set(add( + constantInt(BinaryTupleCommon.HEADER_SIZE + innerEntrySizeConstant * columnsSize), + getOffset(innerAccessor, innerEntrySizeConstant, i) + ))); + } + + CatalogColumnCollation collation = columnCollations.get(i); + NativeType columnType = columnTypes.get(i); + + // Nullability check. + if (nullableFlags.get(i)) { + body.append(outerInNull.set(equal(outerEntryBaseStart, outerEntryBaseEnd))); + body.append(innerInNull.set(equal(innerEntryBaseStart, innerEntryBaseEnd))); + + body.append(new IfStatement() + .condition(bitwiseAnd(outerInNull, innerInNull)) + .ifTrue(lastIteration ? constantInt(0).ret() : jump(endOfBlockLabel)) + .ifFalse(new IfStatement() + .condition(bitwiseOr(outerInNull, innerInNull)) Review Comment: It is a logical OR. Java treats booleans as integers in its bytecode -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: notifications-unsubscr...@ignite.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org
