Skip to content

Code Generation

Jump to bottom Edit New page
Paul Rogers edited this page Nov 17, 2016 · 19 revisions

Code Generation

Drill relies heavily on code generation for the data-specific functionality in each operator. For example, the FilterBatch (implements the SQL WHERE clause) generates code for the actual filter condition. Code generation is necessary because Drill works with a large number of data types (over 120 different value vector implementations) and many kinds of expressions. The alternative, an interpreter, would be expensive to maintain (given the large number of value vector types) and slower to execute.

Drill has two major forms of code generation:

  1. The FreeMarker-based code generation done during the build process, and
  2. The JCode-based code generation done at execution time.

This writeup focuses on the second form.

(Code generation seems to follow a pattern established by Hive? Need to research.)

Code Generation Workflow

Drill developers prepare for code generation by:

At runtime, code generation is done as follows:

  • Each operator has a method to generate the query-specific operator implementation class.
  • The code generation (CG) method creates an instance of CodeGenerator using both global and query-specific settings.
  • The CodeGenerator gathers information about the new class including its name with is: org.apache.drill.exec.test.generated.CodeCompiler<TemplateName>Gen<serial-no> where serial-no is a number assigned to each new generated class from a specific template.
  • Creates one or more ClassGenerator "that implement outer and inner classes associated with a particular runtime generated instance."
  • The operator (batch) uses the ClassGenerator to build up the operator-specific bits of the class using information specific to this operator instance (specific columns, expressions and so on.)
  • Code generation is heavily assisted by pre-defined templates and the HolderContainer class that represents a value vector Holder class.
  • The DrillbitContext provides a CodeCompiler utility that generates and compiles the code.
  • The CodeCompiler has an associated [Google Guava 'LocalCache](https://github.com/google/guava/wiki/CachesExplained) that holds the compiled classes. LocalCache` looks up the code, and will call a "loader" object to create the compiled class if it is not found in the cache.
  • If the code does not yet exist, the code is generated as follows.
  • Invokes QueryClassLoader.getClassByteCode to compile the code.
  • Selects the configured compiler (Janino or JDK).
  • The generated code is compiled into byte codes.
  • The compiled code is merged with template code. (Yes, the byte code from the generated class is combined, at the byte code level, with the template class to create a combined class for which there never was any source code. See this blog post and this paper for information.)

Code Generation Components

  • CodeGenerator<T>: generate the Java source code required to complete the implementation of an abstract template. T is the interface that results from compiling and merging the runtime code that is generated.
  • TemplateClassDefinition<T>: Identifies the interface which the code will implement, along with the template code used to (what?). Also provides a serial number for classes generated from this template. The template is created from the interface that the generated code is to implement.
  • SignatureHolder: (Seems to hold information about the class to be generated: methods and so on.)
  • CodeGeneratorMethod: (Describes one method in the generated code: name, return value, arguments, etc.)
  • FunctionImplementationRegistry:
  • OptionManager: A Javascript-like, prototype-based "stack" of options set from various sources (system, query, etc.) (Used to customize code?)
  • MappingSet:
  • GeneratorMapping: Maps the four standard "conceptual" methods (setup, eval, reset, cleanup) to the names of the actual method (if any) in the generated code. Many method use a standard set of mappings defined in ClassGenerator<T>: DEFAULT_SCALAR_MAP and DEFAULT_CONSTANT_MAP.
  • JCodeModel: "CodeModel is a Java library for code generators; it provides a way to generate Java programs."
  • FragmentContext: Provides the getImplementationClass( ) method which uses the DrillbitContext to find the compiler module that generates and compiles the code.
  • CodeCompiler: Mechanism to generate and compile code. Holds the code cache (with a limit of 1000 entries.)
  • ClassGenerator: Generates an a query-specific class from a template.

Code Cache

The code cache is a mapping from CodeGenerator to generated class. The code generator, however, holds onto code with a unique class name. To allow the cache to work, during code generation, CodeGenerator replaces the specific class name with "GenericGenerated", so that the generic version can be used as a key for the code cache.

CodeGenerator computes its hash code based on two attributes: the definition and the generic code. Similarly, the equals( ) method compares these same two attributes.

The code cache is stored in a Google Guava LocalCache.

LocalCache has three very useful features:

  1. It is concurrent. If a new object must be added to the cache, it locks that cache entry, builds the item, and unlocks. This ensures that if two threads ask for the same value, the first one builds it and the second one waits for completion.
  2. It has "build if absent" semantics. (See CodeCompiler.Loader.)
  3. It will expire old entries after a period of time or when the cache size goes above some threshold. The code cache holds up to 1000 entries.

Other notes:

  • LocalCache provides the means to gather statistics for the hit rate, etc. Drill does not currently use this feature.
  • LocalCache provides a callback to remove a class. It would seem that a class must reside in a ClassLoader. Wouldn't we need a removal method to remove an expired class from the class loader?
  • (Note: this is probably wrong) It turns out the this class does not call the standard Object.hash() method, instead calling System.identityHashCode() to get an identity hash code for the object itself. This means that Drill never actually reuses classes and instead generates a new class for each operator. This is because Drill does not set the CacheBuilder.keyEquivalence() object, so that LocalCache

Code Transformations

An unusual aspect of Drill's code generation system is the use of the ASM package to merge Java classes. Byte code manipulation appeared to grow out of the Aspect Oriented Programming community, and appears to be used by projects such as HBase. A good place to start is this tutorial.

The code transformer attempts to do scalar replacement (which also seems to be a feature of the JVM itself.) More information is available in this paper.

Example - ExternalSortBatch, SingleBatchSorter

The SingleBatchSorter interface, template and template definition:

public interface SingleBatchSorter {
  public void setup(FragmentContext context, SelectionVector2 vector2, VectorAccessible incoming) 
              throws SchemaChangeException;
  public void sort(SelectionVector2 vector2);

  public static TemplateClassDefinition<SingleBatchSorter> TEMPLATE_DEFINITION = 
                new TemplateClassDefinition<SingleBatchSorter>(SingleBatchSorter.class, 
                                                               SingleBatchSorterTemplate.class);
}

public abstract class SingleBatchSorterTemplate implements SingleBatchSorter, IndexedSortable{
  ...

  public abstract void doSetup(@Named("context") FragmentContext context,
                               @Named("incoming") VectorAccessible incoming, 
                               @Named("outgoing") RecordBatch outgoing);
  public abstract int doEval(@Named("leftIndex") char leftIndex, 
                             @Named("rightIndex") char rightIndex);
}

The following code in ExternalSortBatch generates the specialized class:

  public SingleBatchSorter createNewSorter(FragmentContext context, VectorAccessible batch)
          throws ClassTransformationException, IOException, SchemaChangeException{
    CodeGenerator<SingleBatchSorter> cg = CodeGenerator.get(SingleBatchSorter.TEMPLATE_DEFINITION, context.getFunctionRegistry(), context.getOptions());
    ClassGenerator<SingleBatchSorter> g = cg.getRoot();

    generateComparisons(g, batch);
    return context.getImplementationClass(cg);
  }

Here, generateComparisons() builds up the specific methods needed to do the comparisons needed to implement the sort.

The particular case compares nullable VarChar fields. Internally, the code generator looks for a function with the template name of compare_to_nulls_high with arguments nullable VarChar. The match is:

  @FunctionTemplate(name = FunctionGenerationHelper.COMPARE_TO_NULLS_HIGH,
                    scope = FunctionTemplate.FunctionScope.SIMPLE,
                    nulls = NullHandling.INTERNAL)
  public static class GCompareVarCharVsVarCharNullHigh implements DrillSimpleFunc {
    @Param VarCharHolder left;
    @Param VarCharHolder right;
    @Output IntHolder out;
    public void setup() {}
    public void eval() {
     outside: {
      out.value = org.apache.drill.exec.expr.fn.impl.ByteFunctionHelpers.compare(
          left.buffer, left.start, left.end, right.buffer, right.start, right.end );
      } // outside
    }
  }

The code generator will "inline" the above code. To do that, it needs to create local variables that correspond to the VarCharHolder parameters.

Code Cache

Drill implements a code cache. The cache holds generated classes. The cache is indexed by the entire body of the generated code. This means that each operator must generate source code, then check if that body of source has already been compiled.

The reason for this approach is that each code generator has a very wide interface: the resulting code is dependent not just on properties of the template and query; but also on properties for the fragment, the query and globally. Thus, the only reliable, known key is the generated source itself rather than the (large number) of parameters used to generate the source.

Scalar Replacement

Applying a bit of "software archeology", it seems that Drill started by providing functions for most tasks using the form still used for UDFs:

  @FunctionTemplate(name = FunctionGenerationHelper.COMPARE_TO_NULLS_HIGH,
                    scope = FunctionTemplate.FunctionScope.SIMPLE,
                    nulls = NullHandling.INTERNAL)
  public static class GCompareNullableVarCharVsVarCharNullHigh implements DrillSimpleFunc {
    @Param NullableVarCharHolder left;
    @Param VarCharHolder right;
    @Output IntHolder out;
    public void setup() {}
    public void eval() {
     outside:
      {
        if ( left.isSet == 0 ) {
          out.value = 1;
          break outside;
        }
      out.value = org.apache.drill.exec.expr.fn.impl.ByteFunctionHelpers.compare(
          left.buffer, left.start, left.end, right.buffer, right.start, right.end );
      } // outside
    }
  }

Because there are a very large number of such functions, they are generated (using Freemarker):

  <#-- Comparison function for sorting and grouping relational operators
       (not for comparison expression operators (=, <, etc.)). -->
  @FunctionTemplate(name = FunctionGenerationHelper.COMPARE_TO_NULLS_HIGH,
                    scope = FunctionTemplate.FunctionScope.SIMPLE,
                    nulls = NullHandling.INTERNAL)
  public static class GCompare${leftType}Vs${rightType}NullHigh implements DrillSimpleFunc {
    @Param ${leftType}Holder left;
    @Param ${rightType}Holder right;
    @Output IntHolder out;
    public void setup() {}
    public void eval() {
      <@compareBlock mode=typeGroup.mode leftType=leftType rightType=rightType
                     output="out.value" nullCompare=true nullComparesHigh=true />
    }
  }

At some point, Drill moved to generating code for these functions instead of calling the (statically generated and compiled) functions. The code generator seems to use the code from the above functions and combines it with generated code to get the source code for the operator-specific bits of the logic:

public class SingleBatchSorterGen7 {
    NullableVarCharVector vv0;
    NullableVarCharVector vv4;
    public int doEval(char leftIndex, char rightIndex)
        throws SchemaChangeException
    {
        {
            NullableVarCharHolder out3 = new NullableVarCharHolder();
            {
                out3 .isSet = vv0 .getAccessor().isSet((leftIndex));
                if (out3 .isSet == 1) {
                    out3 .buffer = vv0 .getBuffer();
                    long startEnd = vv0 .getAccessor().getStartEnd((leftIndex));
                    out3 .start = ((int) startEnd);
                    out3 .end = ((int)(startEnd >> 32));
                }
            }
            ...
            //---- start of eval portion of compare_to_nulls_high function. ----//
            IntHolder out8 = new IntHolder();
            {
                final IntHolder out = new IntHolder();
                NullableVarCharHolder left = out3;
                NullableVarCharHolder right = out7;
                 
GCompareVarCharVsVarChar$GCompareNullableVarCharVsNullableVarCharNullHigh_eval: {
    outside:
    {
        if (left.isSet == 0) {
            if (right.isSet == 0) {
                out.value = 0;
                break outside;
            } else
            {
                out.value = 1;
                break outside;
            }
        } else
        if (right.isSet == 0) {
            out.value = -1;
            break outside;
        }
        out.value = org.apache.drill.exec.expr.fn.impl.ByteFunctionHelpers.compare(
            left.buffer,
            left.start,
            left.end,
            right.buffer,
            right.start,
            right.end
        );
    }
}
 
                out8 = out;
            }
            //---- end of eval portion of compare_to_nulls_high function. ----//
            if (out8 .value!= 0) {
                return out8 .value;
            }
            return  0;
    }
    ...
}

Notice that that source code makes use of temporary objects:

            NullableVarCharHolder out3 = new NullableVarCharHolder();

Scalar replacement is a technique to replace such objects with local scalar variables. Drill uses the ASM library to do the work rather than relying on the JVM to do it. From the decompilation of the final generated code:

    NullableVarCharHolder out3;
    int i = 0; int j = 0; int k = 0; DrillBuf localDrillBuf1 = null;
    ...
   if (i == 0) {
      if (m == 0) {
        i3 = 0;
      }
      else
      {
        i3 = 1;
      }

Here we can see that the NullableVarCharHolder has been removed; replaced by a series of local variables.

Compilation Framework

Background

Java compilation in Java itself is based on the JavaCompiler class. The javax.tools provides a dynamic compilation framework. The IBM article provides a sample app that compiles Java classes from in-memory sources.

Debugging Hints

You can view the generated code in one of three ways:

  • Enable debug logging for AbstractClassCompiler. The generated code is written to the log file. Set the config option drill.exec.compile.debug to true if you want line numbers added to each line.
  • Uncomment the obvious block of code in AbstractClassCompiler to write each generated class to /tmp. This version is handy as it uses the class name to name each file.
  • Pass the following to the command line when starting Drill: -Dorg.codehaus.janino.source_debugging.enable=true -Dorg.codehaus.janino.source_debugging.dir=/tmp. (See this post for more information.) This version writes all files using generic temporary names, making it hard to find the particular file of interest.

You can gain access to the generated class files by uncommenting the obvious lines near line 256 in MergeAdapter.

Add a custom footer
Add a custom sidebar
Clone this wiki locally