Abstract:
One embodiment of a method for constructing executable code for a component-based application includes receiving a request to compile source code for the component-based application, wherein the request identifies the source code, and wherein the source code comprises a plurality of source code components, each of the source code components implementing a different component of the application, and performing a series of steps for each source code component where the series of steps includes: deriving a signature for the source code component, retrieving a stored signature corresponding to a currently available instance of executable code for the source code component, comparing the derived signature with the stored signature, compiling the source code component into the executable code when the derived signature does not match the stored signature, and obtaining the executable code for the source code component from a repository when the derived signature matches the stored signature.

Description:
REFERENCE TO GOVERNMENT FUNDING 
       [0001]    This invention was made with Government support under Contract No. H98230-07-C-0383, awarded by the United States Department of Defense. The Government has certain rights in this invention. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    The present invention relates generally to component-based code generation, and relates more specifically to an incremental method for constructing component-based applications. 
         [0003]    Component-based applications are applications that are built using a plurality of interconnected functional components or operators. Within this context, a component is a small piece of code that carries out generic operations, such as data transformations, filtering, annotation, classification, de-multiplexing, and splitting. Two components can interact through streams, which carry a potentially infinite quantity of data. The components operate on this data in a predefined manner, possibly according to a specified sequence, to produce some output. 
         [0004]    Typically, each of these components is built in accordance with a two-step process that involves code generation and code compilation. The code generation step consists of generating executable code from the declarative description of the application. Specifically, given a component of a specific class, code generation involves invoking the code generator corresponding to that class and providing it with the proper configuration parameters for the component. The code generator then generates specialized code in a general purpose programming language (e.g., the C or C++ programming language) for the component. The code compilation step consists of compiling the specialized code into object code that is executable on the target platform (e.g., an Intel x86 instruction set architecture-based computer). General purpose build tools are typically used to orchestrate the generation and/or compilation steps. Some examples of such build tools are the “make,” “gnumake,” “nmake,” “jam,” and “ant” tools. 
         [0005]    In some cases, a file that contains the declarative description of a component-based application may change. As a result, some of the components associated with the application may change, necessitating the re-generation of the code for those components. Conventional build tools that rely on timestamp data to determine if code has changed not only re-generate the code for all of the components, but also completely re-compile the re-generated code. Thus, code is re-generated and re-compiled even for components that have not effectively changed (e.g., have not changed the way in which they process data), simply because their timestamps are newer than the object code&#39;s. 
       SUMMARY OF THE INVENTION 
       [0006]    One embodiment of a method for constructing executable code for a component-based application includes receiving a request to compile source code for the component-based application, wherein the request identifies the source code, and wherein the source code comprises a plurality of source code components, each of the source code components implementing a different component of the application, and performing a series of steps for each source code component where the series of steps includes: deriving a signature for the source code component, retrieving a stored signature corresponding to a currently available instance of executable code for the source code component, comparing the derived signature with the stored signature, compiling the source code component into the executable code when the derived signature does not match the stored signature, and obtaining the executable code for the source code component from a repository when the derived signature matches the stored signature. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0007]    So that the manner in which the above recited features of the present invention can be understood in detail, a more particular description of the invention may be had by reference to embodiments, some of which are illustrated in the appended drawings. It is to be noted, however, that the appended drawings illustrate only typical embodiments of this invention and are therefore not to be considered limiting of its scope, for the invention may admit to other equally effective embodiments. 
           [0008]      FIG. 1  is a block diagram illustrating a first exemplary component-based application that may be adapted to benefit from the present invention; 
           [0009]      FIG. 2  is a block diagram illustrating one embodiment of a compiler, according to the present invention; 
           [0010]      FIG. 3  is a flow diagram illustrating one embodiment of a method for generating code for a component based application, according to the present invention; 
           [0011]      FIG. 4  is a block diagram illustrating a second exemplary component-based application that may be adapted to benefit from the present invention; and 
           [0012]      FIG. 5  is a high-level block diagram of the code generation method that is implemented using a general purpose computing device. 
       
    
    
     DETAILED DESCRIPTION 
       [0013]    In one embodiment, the invention is a method and apparatus for incrementally constructing component-based applications. Embodiments of the present invention employ a metadata-based signature technique to avoid unnecessarily re-generating and re-compiling executable component code. In particular, metadata is used to describe the configurations that define each component of an application. A signature is computed from this metadata for each component and maintained in association with the executable code generated for the component in a code repository. At code generation time, the code repository is searched, and, if stored code is found therein that corresponds to the component for which new code is to be generated, the signature corresponding to the stored code is retrieved. If the signature of the stored code differs from a computed signature for the new code, the code for the component is re-generated in accordance with the new code. If the signatures do not differ, the code for the component is not re-generated. 
         [0014]      FIG. 1  is a block diagram illustrating a first exemplary component-based application  100  that may be adapted to benefit from the present invention. In particular, the exemplary component-based application  100  is a stream processing application; however, it is understood that the present invention may be used in substantially any type of component-based application development framework and is not limited to stream processing applications. 
         [0015]    The application  100  comprises a plurality of components or “operators”  102   1 - 102   n  (hereinafter collectively referred to as “operators  102 ”) that are connected to each other by streams. The operators  102  are configured to operate on incoming streaming data  104  and to output a result of the operation (possibly also in stream form) to a database  106 . 
         [0016]    In one embodiment, each of the operators  102  is one of a plurality of possible types, including, but not limited to: Source (e.g., operator  102   1 , which is used to read data from external data sources), Functor (e.g., operators  102   2 ,  102   3 ,  102   6 , and  102   7 , which is used to carry out basic data transformations, such as filtering, on streaming data), Aggregate (e.g., operator  102   4 , which is used to logically group streaming data into summaries), Join (e.g., operator  102   5 , which is used to correlate two streams), and Sink (e.g., operator  102   n , which is used to externalize data). Each of these operators  102  can be configured in a specific way. In other words, each operator  102  is a configurable component with a specific type. Thus, each operator  102  may be referred to as an “operator instance” within the context of the exemplary stream processing application  100 . 
         [0017]    For instance, the exemplary application  100  may be configured to process a stream of financial data, such as a live stock market feed. In such an application, the Source operator  102   1  may read input from the incoming data stream  104  and passes this input on to first and second Functor operators  102   2  and  102   3 . The first Functor operator  102   2  might pass trades and compute volume prices from the input data stream, while the second Functor operator  102   3  might pass stock quotes from the incoming data stream. The trades and volume prices are then passed from the first Functor operator  102   2  to the Aggregate operator  102   4 , which might compute a moving average for each stock ticker or symbol in the incoming data stream. The Aggregate operator  102   4  might then pass the moving average to a third Functor operator  102   6 , which computes the volume-weighted average price (VWAP) of stocks in the incoming data stream. The Join operator  102   5  might receive the stock quotes from the second Functor operator  102   3  and the volume-weighted average price from the third Functor operator  102   6  and compute a bargain index. The Join operator  102   5  might then pass the bargain index to a fourth Functor operator  102   7 , which might drop the messages with a zero-value bargain index before passing the data to the Sink operator  102   n , which then writes the results to the database  106 . 
         [0018]    As discussed above, compiling a stream processing application such as the exemplary application  100  involves generating executable code from the logical description of the application. Given an operator instance of a specific type, code generation involves invoking the corresponding code generator and providing the code generator with the proper configuration parameters. The code generator generates specialized code in a general purpose programming language (e.g., the C or C++ programming language) for the operator instance. The generated code is then compiled into object code that is executable on the target platform. Compilation is generally performed using general purpose build tools, such as the “make” tool. 
         [0019]    For instance, consider the following two exemplary Functor operator instances, represented in a high-level programming language, where two Functor operators are used to generate new streams (TradeFilter and QuoteFilter) by processing the data coming from a primal stream called TradeQuote). These examples, and those shown below, are written in the SPADE programming language, which is described in further detail by Gedik et al. in “SPADE: The System S Declarative Stream Processing Engine,” SIGMOD Conference 2008: 1123-1134. 
         [0000]                                                                            Stream TradeFilter(ticker: String, myvwap:Float, volume:Float)                := Functor(TradeQuote) [ttype=”Trade” &amp; volume&gt;0.0]   (EX. 1)                {myvwap :=price*volume}            Stream QuoteFilter(ticker:String, askprice:Float, asksize:Float)   (EX. 2)                := Functor(TradeQuote) [ttype=”Quote” &amp; askprice&gt;0.0] { }                        
EX. 1 and EX. 2 represent high-level programming language translations of the declarative descriptions for the corresponding Functor operator instances.
 
         [0020]    The two Functor operator instances in EX. 1 and EX. 2 are clearly configured in different ways. Specifically, the schemas of the streams that each of the operator instances are generating are different (i.e., the schema for TradeFilter versus the schema for QuoteFilter). In addition, some of the parameters, such as the filtering conditions (i.e., ttype=“Trade”&amp; volume&gt;0.0 versus ttype=“Quote” &amp; askprice&gt;0.0), are different (i.e., the resulting stream messages they produce are different, and in EX. 1, a new message attribute called myvwap is computed based on the values of attributes of the incoming tuple). Also, the attribute assignments are different. This indicates that the code generator associated with Functor operator instances will generate different code for at least these two Functor operator instances. 
         [0021]      FIG. 2  is a block diagram illustrating one embodiment of a compiler  200 , according to the present invention. Within the context of  FIG. 2 , the entity referred to as the “compiler” performs both code generation and compilation, as discussed in further detail below. The compiler  200  may be implemented, for example, to generate code for components or operator instances of a component-based application, such as the component-based application  100  illustrated in  FIG. 1 . As illustrated, the compiler  200  receives configuration parameters  202  for a proposed operator instance (e.g., stream schemas, filtering predicates, or the like within the context of a stream processing application) and outputs corresponding object code for the proposed operator instance to a target machine  204 . The compiler  200  may be implemented in hardware, software, or a combination of both. The compiler  200  may comprise a plurality of elements, such as a signature comparator, a signature database, and a code generator. One example of a compiler  200  is the SPADE programming language compiler, as adapted according to the present invention. 
         [0022]    As illustrated, the compiler  200  comprises a signature comparison engine  206 , a repository or signature database  208 , a plurality of code generators  210   1 - 210   n  (hereinafter collectively referred to as “code generators  210 ”), and a back end  212 . When the compiler  200  receives configuration parameters  202  for a proposed operator instance of a component-based program, it passes the configuration parameters  202  to the signature comparison processor  206 . As discussed in further detail with respect to  FIG. 3 , the signature comparison processor  206  derives a signature for the proposed operator instance from the configuration parameters  202 . The signature comparison engine  206  then compares the derived signature to a stored signature for a previously generated version of the operator instance. The stored signature is retrieved from the signature database  208 . 
         [0023]    If the signature comparison processor  206  determines, based on the signature comparison, that executable code should be generated for the proposed operator instance, the signature comparison processor  206  passes the configuration parameters  202  to the code generator  210  that corresponds to the type of operator represented by the proposed operator instance (e.g., Source, Functor, Aggregate, Join, Sink, or the like). The code generator  210  generates specialized code in a general purpose programming language for the operator instance and passes the specialized code to the back end compiler (e.g., a C or C++ programming language compiler)  212 . The back end compiler  212  compiles the specialized code into object code that is executable on the target machine  204  and then and provides the object code to the target machine  204 . 
         [0024]      FIG. 3  is a flow diagram illustrating one embodiment of a method  300  for generating code for a component based application, according to the present invention. The method  300  may be implemented, for example, by the signature comparison processor  206  of the compiler  200  illustrated in  FIG. 2 . The method  300  may be implemented, for example, when a component-based application is changed and the compiler is re-run. 
         [0025]    The method  300  is initialized at step  302  and proceeds to step  304 , where the method  300  receives an instruction to re-generate the code for a component-based application. Thus, the instruction requires that code be generated for a proposed version of at least one operator instance in the application, where a current version of the operator instance is present in the current version of the application. 
         [0026]    In step  306 , the method  300  derives a signature for the proposed version of the operator instance. In one embodiment, the signature is an extensible markup language (XML) document that captures the configuration parameters of the proposed version of the operator instance. In this example, the signature represents the configuration parameters that can be used to bind the modifiable aspects of an operator to specific settings. Thus, the signature captures all of the relevant operator parameters that can trigger the generation of different code. For example, within the context of a data stream processing application, the signature for an operator instance might include the stream schema, filtering predicates, join and group-by settings, or the like. In one embodiment, the signature for an operator instance is derived from metadata associated with the operator instance. For instance, the method  300  may extract the configuration parameters from the source code for the operator instance and generate an XML- or a string-based representation of the metadata as the signature. In one embodiment, compile-time evaluatable constant expressions in the metadata are replaced with place holders (e.g., modified configuration parameters) that are loaded at runtime. This metadata captures all of the configuration parameters associated with the operator instance. 
         [0027]    In step  308 , the method  300  retrieves a signature associated with the current version of the operator instance from a code repository. In one embodiment, the code repository maintains a signature for each operator instance associated with an application, along with the generated code for the operator instance. 
         [0028]    In step  310 , the method  300  compares the signatures for the proposed operator instance and the current operator instance to determine whether the signatures match. As discussed above, the signature for an operator instance is derived from metadata that captures all of the configuration parameters associated with the operator instance. Given these configuration parameters, the code generator associated with the operator type can create the appropriate code for the operator instance. Thus, if the metadata for two operator instances is the same, then the generated code for those operator instances (as well as the signatures) are also the same. However, if the metadata for two operator instances is different, then the generated code for those operator instances (as well as the signatures) are also different. In one embodiment, the signatures are compared in full and must match down to the individual bit in order for a match to be found. 
         [0029]    If the method  300  concludes in step  310  that the signatures for the proposed operator instance and the current operator instance do not match, then the method  300  proceeds to step  312  and re-generates the code for the operator instance (i.e., generates the code in accordance with the proposed version of the operator instance). The method  300  then stores the regenerated code and the signature (e.g., in the signature database  208  of  FIG. 2 ) before terminating in step  316 . 
         [0030]    Alternatively if the method  300  concludes in step  310  that the signatures for the proposed operator instance and the current operator instance do match, then the method  300  proceeds to step  314  and determines that code for the operator instance does not need to be re-generated (i.e., the proposed version of the operator instance is the same as the current version of the operator instance) before terminating in step  316 . 
         [0031]    The method  300  thereby avoids the unnecessary re-generation of code for operator instances that do not change from an earlier version of an application. Operator instances that are the same should share the same code. Consider, for example, the following high-level code, which creates thirty-one instances of the program fragments described in EX. 1 and EX. 2: 
         [0000]    
       
         
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                   
               
             
             
               
                 for_begin @day 1 to day 31 # for each day 
               
             
          
           
               
                   
                 stream TradeFilter@day (ticker: String, myvwap:Float, 
               
               
                   
                 volume:Float) 
               
               
                   
                 := Functor(TradeQuote@day) [ttype=”Trade” &amp; volume&gt;0.0] 
               
             
          
           
               
                   
                 {myvwap :=price*volume} 
               
             
          
           
               
                   
                 stream QuoteFilter@day(ticker:String, askprice:Float, asksize:Float) 
               
             
          
           
               
                   
                 := Functor(TradeQuote@day) [ttype=”Quote” &amp; 
               
               
                   
                 askprice&gt;0.0] { } 
               
             
          
           
               
                 for_end 
                 (EX. 3) 
               
               
                   
               
             
          
         
       
     
         [0032]    In accordance with the method  300 , it is advantageous to avoid re-generating code for sixty-two (i.e., thirty-one times two) operator instances in EX. 3, and instead only re-generate code for two operator instances (since the same groups of components will be reused for each of the thirty-one days). 
         [0033]    One notable exception to the method  300  is the case in which the code generator for an operator type has changed (e.g., due to the availability of a new version of the high-level language compiler). In such a case, even if the signatures for the new version of the operator instance and the current version of the operator instance match, the code for the operator instance must still be re-generated. Changes in the code generator can be detected using file timestamps. For example, if the code generator has been modified more recently than the last-generated code, the build tools can re-generate the code without checking the signatures of the operator instances. 
         [0034]    The signature-based technique of the method  300  can also be used to avoid unnecessary re-generation and re-compilation of code when a component-based application contains repeated operators instances. As discussed above, signatures are generated for each operator instance, and the corresponding code generator is called once for each unique signature. Thus, operator instances that share the same signature become instances of the same operator class and share the same code. Sharing code for operator instances can, in turn, significantly reduce compilation times by avoiding unnecessary code generation. 
         [0035]    However, code sharing among operator instances can be too restrictive in some cases because full advantage cannot be taken of the similarity between operator instances. For example, consider the following code excerpt, wherein a small change in the configurations of a large number of Source operators used, in this case, to convert data coming from files into messages to be streamed out, results in excessive code generation: 
         [0000]    
       
         
               
             
               
               
             
               
               
             
               
               
             
           
               
                   
               
             
             
               
                 for_begin @day 1 to day 31 # for each day 
               
             
          
           
               
                   
                 stream TradeFilter@day (ticker: String, myvwap:Float, volume:Float) 
               
             
          
           
               
                   
                 := Source( ) [file://taq_data_+toString(@day), binformat] { } 
               
             
          
           
               
                 for_end 
                 (EX. 4) 
               
               
                   
               
             
          
         
       
     
         [0036]    Specifically, a different programming language (e.g., C or C++ programming language) implementation of the operator instance code is generated for each operator instance. For example, referring to the code excerpt of EX. 4, it is noted that each Source operator reads data from a file specified by a different uniform resource indicator (URI), which, in an implementation based on conventional techniques, would be embedded in the generated code, making the code generated for different instantiations of the operator slightly different. 
         [0037]    Thus, embodiments of the invention further seek to avoid unnecessary code re-generation when the application contains repeated operator instances that differ only in parameter configurations that rely on constants known at compile-time. Compile-time constants in parameter configurations can be converted into arguments to be loaded by the operator instances when the operator instances are initialized at runtime. For instance, the file name in EX. 4 can be converted into an argument of the operator instance by including extra logic in the generated code to extract the file name from arguments of the operator instance. In this way, all of the Source operator instances in EX. 4 can share code, but can be fed different arguments at runtime since the operator processing logic itself remains unchanged. 
         [0038]    In one embodiment, this code sharing technique is applied to operator parameters that are partially constant, as long as the variable (not constant) parameters match for different operator instances. In one embodiment, the compile-time constants are excluded from the operator instance&#39;s signature (discussed above), even though they are part of the operator instance&#39;s metadata, because they trigger re-compilation when a signature comparison is made as illustrated in  FIG. 3 . 
         [0039]    Even when multiple operator instances are exact copies of each other, differences in the connections of the operator instances may result in changes in the generated code. For instance, the connection information may become part of the operator instance configuration. Consider, for example, the following high-level code: 
         [0000]    
       
         
               
               
             
               
               
             
               
               
             
               
               
             
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 stream TradeFilter1 (ticker: String, myvwap:Float, volume:Float) 
               
             
          
           
               
                   
                 := Functor(QuotesA) [ttype=”Trade” &amp; volume&gt;0.0] { } 
               
             
          
           
               
                   
                 stream TradeFilter2 (ticker: String, myvwap:Float, volume:Float) 
               
             
          
           
               
                   
                 := Functor(QuotesA, QuotesB) [ttype=”Trade” &amp; 
               
             
          
           
               
                   
                 volume&gt;0.0] { } 
                 (EX. 5) 
               
               
                   
                   
               
             
          
         
       
     
         [0040]    In EX. 5, the two Functor operator instances are the same, except that the second Functor operator instance has two streams (i.e., QuotesA and QuotesB) connected to its input port, while the first Functor operator instance only has a single stream (i.e., QuotesA) connected to its input port. Similarly, it may be the case that the output streams generated by the two Functor operator instances are connected to a different number of downstream operators. 
         [0041]    Thus, embodiments of the invention further seek to avoid unnecessary code re-generation when the application contains repeated operator instances that differ only in their inter-connection patterns. In one embodiment, this is accomplished by separating the operator code from the container code. A container can host multiple operators and is responsible for establishing the connections between the operators. Similar to operator instances, container instances are also generated automatically. The mapping from the operator graph to the container graph is flexible. 
         [0042]    Also similar to operator instances, signatures can be derived for container instances to avoid unnecessary code regeneration and re-compilation. Thus, one can minimize the re-generation and re-compilation of code by employing different instances of multi-operator hosting containers in the application. It is noted that the container code is generally not as complex as the operator code 
         [0043]      FIG. 4 , for example, is a block diagram illustrating a second exemplary component-based application  400  that may be adapted to benefit from the present invention. As illustrated, the application  400  comprises a plurality of components or operator instances  402   1 - 402   n  (hereinafter collectively referred to as “operator instances  402 ”) interconnected by streams. As also illustrated, these operator instances  402  are hosted by container instances  404 ,  406 , and  408   1 - 408   m  (hereinafter collectively referred to as “container instances  408 ”). Each of the container instances  404 ,  406 , and  408  hosts at least one operator instance  402 . 
         [0044]    In one embodiment, all of the operator instances  402  are configured in the same way and thus share code. Moreover, as illustrated, there are m container instances  408  that are the same in terms of internal connections and operator instances  402  hosted thereby. Within the context of the exemplary application  400 , one would only need to generate code for one of the container instances  408 , and this code could then be shared for all m container instances  408 . 
         [0045]    Embodiments of the invention further seek to avoid unnecessary code re-generation when the application contains repeated container instances that comprise identical operator instances connected in the same manner. In one embodiment, this is accomplished in a manner similar to the solutions previously described herein. Specifically, signatures are derived for each of the container instances, where the signature for a container instance captures the intra-connection topology of the container instance as well as the signatures of the operator instances hosted thereby. In this way, container instances that have the same configuration can share code. 
         [0046]      FIG. 5  is a high-level block diagram of the code generation method that is implemented using a general purpose computing device  500 . In one embodiment, a general purpose computing device  500  comprises a processor  502 , a memory  504 , a code generation module  505  and various input/output (I/O) devices  506  such as a display, a keyboard, a mouse, a stylus, a wireless network access card, and the like. In one embodiment, at least one I/O device is a storage device (e.g., a disk drive, an optical disk drive, a floppy disk drive). It should be understood that the code generation module  505  can be implemented as a physical device or subsystem that is coupled to a processor through a communication channel. 
         [0047]    Alternatively, the code generation module  505  can be represented by one or more software applications (or even a combination of software and hardware, e.g., using Application Specific Integrated Circuits (ASIC)), where the software is loaded from a storage medium (e.g., I/O devices  506 ) and operated by the processor  502  in the memory  504  of the general purpose computing device  500 . Thus, in one embodiment, the code generation module  505  for generating code for component-based applications, as described herein with reference to the preceding figures can be stored on a computer readable storage medium or carrier (e.g., RAM, magnetic or optical drive or diskette, and the like). 
         [0048]    It should be noted that although not explicitly specified, one or more steps of the methods described herein may include a storing, displaying and/or outputting step as required for a particular application. In other words, any data, records, fields, and/or intermediate results discussed in the methods can be stored, displayed, and/or outputted to another device as required for a particular application. Furthermore, steps or blocks in the accompanying figures that recite a determining operation or involve a decision, do not necessarily require that both branches of the determining operation be practiced. In other words, one of the branches of the determining operation can be deemed as an optional step. 
         [0049]    While the foregoing is directed to embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof. Various embodiments presented herein, or portions thereof, may be combined to create further embodiments. Furthermore, terms such as top, side, bottom, front, back, and the like are relative or positional terms and are used with respect to the exemplary embodiments illustrated in the figures, and as such these terms may be interchangeable.