System and method for stack-based batch evaluation of program instructions

A batching module that inspects call stacks within a stack evaluator to identify current expressions that can be evaluated in batch with other expressions. If such expressions are identified, the corresponding stacks are blocked from further processing and a batch processing request for processing the expressions is transmitted to the application server. The application server processes the expressions in batch and generates a value for each of the expressions. The blocked stacks are then populated with the values for the expressions.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present disclosure relates generally to data access and analysis and, more specifically, to a system and method for evaluating programs in batch.

2. Description of the Related Art

Software applications, such as financial analysis applications, allow users to create and interact with large software data objects. Such data objects organize data relevant to the software application and provide methods that allow operations to be performed on the data. In some situations, the operations are performed on a large set of data and require high processing power as well as high bandwidth access to a database.

Typically, for the efficient processing of such operations, the bulk of the processing occurs on a server that is external to the computing device that executes the software application. In operation, the software application transmits calls associated with the operations to be performed on the data, and the calls are processed on the server. The results of the processing are then transmitted back to the software application for presentation to the user.

One drawback to such an implementation is that the server receives and processes one call per operation to be performed. In situations where operations are performed on an extremely large set of data, serving a large amount of calls can slow down the server and, in some cases, crash the server. Such a scenario is extremely undesirable because the server is extremely slow and in some cases entirely unusable, thereby affecting the overall user experience.

As the foregoing illustrates, what is needed in the art is a mechanism for efficiently managing and processing a large volume of calls to be processed on a server.

SUMMARY OF THE INVENTION

One embodiment of the invention is computer-implemented method for evaluating a program instruction within the stack evaluator. The method includes the steps of generating a call frame associated with the program instruction within a call stack, wherein the call frame includes a first expression specified by the program instruction, generating a child frame associated with the first expression within the call stack, receiving a modification to the child frame that sets the value of the first expression within the child frame, and processing the call frame based at least in part on the value of the first expression within the child frame.

Advantageously, because a single batch processing request is transmitted to the application server for a group of similar expressions, the number of processing requests received by the application server is reduced. As a result, the application server is not burdened with a large amount of requests at any given time. Therefore, the overall processing efficiency of the application server is increased and the overall processing latency of the application server is reduced.

DESCRIPTION OF EXAMPLE EMBODIMENTS

FIG. 1illustrates a system100that enables an application to be processed in batch-mode. As shown, the system100includes a application102, service logic104, an application server106and a data store108.

The application102is a software program that allows a user to create, analyze and interact with workflows having one or more documents. A document is typically composed of several data objects, each having a particular type and function. The data objects that could make up a document are described in greater detail below. A user, via a programming interface, can typically write program routines that interact with the data objects to generate the results or analysis needed. Again, some examples of such instructions are described below.

The service logic104is an infrastructure layer that, among other things, allows the application102to communicate with the application server106. In one embodiment, the service logic104includes a messaging service (not shown) that allows the application102and the application server106to communicate asynchronously via messages. The service logic104includes a stack evaluator118and a batching module120. The stack evaluator118is an infrastructure module that manages the stack-based evaluation of program routines associated with the application102. Each program routine is associated with a call stack that includes multiple frames, each frame storing information about a particular portion of the program routine. The batching module120allows for the batch processing on the application server106of program routines being evaluated within the stack evaluator118. The functions of the stack evaluator118and the batching module120is described in greater detail below in conjunction withFIGS. 2A-6B.

The application server106includes logical elements such as input receiving logic110, an object model112, evaluation logic114and data store access logic116. The application server106may be implemented as a special-purpose computer system having the logical elements shown inFIG. 1. In one embodiment, the logical elements comprise program instructions stored on one or more machine-readable storage media. Alternatively, the logical elements may be implemented in hardware, firmware, or a combination thereof.

The input receiving logic110receives inputs from different applications executing within the system100, such as the application102, via the service logic104. Inputs include, but are not limited to, processing requests, data access/storage requests and expression evaluation requests. The input receiving logic110transmits requests received from the different applications to logical elements within the application server106that are configured to process those requests.

The object model112is a model that specifies a universe of data objects, relationships between the data objects, higher-order data objects generated based on one or more zero-order data objects in the universe, higher-order data objects generated based on other higher-order data objects, and auxiliary entities related to the universe of data objects. The data objects may be created by users via data object creation mechanisms exposed in different applications, such as the application102. In one embodiment, the object model112includes only references to the data objects and data related to those data objects is stored within the data store108. Persons skilled in the art would understand that any other data objects can be included in the object model112.

The evaluation logic114receives expression evaluation requests from applications, such as the application102, via the input receiving logic and evaluates the expressions specified in those requests. An expression typically includes a reference to one or more data objects included in the object model112and specifies one or more operations to be performed on those data objects. The evaluation logic114, when processing a particular expression, may create, modify, delete and store data objects that are associated with the universe of data objects included in the object model112. In addition, the evaluation logic112transmits the results of processing the particular expression to the application that transmitted the expression evaluation request.

In an embodiment, application server106comprises data store access logic116. Data store access logic116may comprise a set of program instructions which, when executed by one or more processors, are operable to access and retrieve data from data store108. For example, data store access logic116may be a database client or an Open Database Connectivity (ODBC) client that supports calls to a database server that manages data store108. Data store108may be any type of structured storage for storing data including, but not limited to, relational or object-oriented databases, data warehouses, directories, data files, and any other structured data storage.

FIG. 2Aillustrates a more detailed view of the stack evaluator118ofFIG. 1, according to one embodiment of the invention. As shown, the stack evaluator118includes multiple stacks202.

The stack evaluator118generates a stack202corresponding to each program subroutine (referred to herein as a “subroutine”) associated with the application102. Typically, a subroutine includes multiple instructions, where each instruction includes one or more expressions to be evaluated. As discussed above, an expression may include an argument, a parameter and/or a metric, as described above. When evaluating a particular instruction, the stack evaluator118generates a different frame for each expression within that instruction. For example, an array frame is generated for each argument of an instruction and a call frame is generated for performing a specified operation on the arguments that were evaluated in the array frame(s).

FIG. 2Billustrates a more detailed view of a stack202ofFIG. 2A, according to one embodiment of the invention. As shown, the stack202includes a frames portion206, a value portion208and an expression portion210.

The frames portion206includes multiple frames204, where each frame204corresponds to a particular evaluation iteration of the subroutine corresponding to the stack202. When a particular frame is ready for evaluation, the stack202transitions to an “evaluation state.” During evaluation, the expressions within the current frame are first extracted and pushed into the expression array210, such as exp214. The value of the expressions are then evaluated and pushed into the value array208. If an expression being evaluated is nested, the evaluation of the expression in the current frame204generates one or more new frames204that are evaluated before evaluating the current frame. Once the evaluation of each frame in the stack202is completed, the stack202transitions to a “completed state.”

FIG. 3illustrates a more detailed view of the batching module120ofFIG. 1, according to one embodiment of the invention. As shown, the batching module120includes an inspection engine302, a blocking engine304and an unblocking engine.

The batching module120monitors the execution of program subroutines within the stack evaluator118to identify program subroutines that can be processed within the application server106in batch. More specifically, for each stack202, the inspection engine302analyzes a current expression within a frame204of the stack202to determine whether the evaluation of the expression should be evaluated in batch with other similar expressions.

To determine whether a particular expression should be evaluated in batch with other similar expressions, the inspection engine302first determines the type of the expression. An expression may be an economic index, an instrument, a metric, an input object, an output object, a parameter, a time series, a higher-order-object, or any higher-order object in the object model. Based on the type of expression, the inspection engine302then determines whether the type of the expression falls within a pre-determined category of expressions that should be processed in batch with other expressions of the same type or a similar type. For example, an expression that includes a metric for which the evaluation involves a database access or a model access should be processed in batch with other expressions that include metrics for which the evaluation involves database accesses or model accesses.

As another example, consider the following program instruction: return this.close+this.open, where “this” refers to a time series. There are multiple expressions within the program instruction, such as “this.close,” “+,” and “this.open.” In one scenario, the program instruction may be evaluated multiple times, each evaluation generating a different stack202. In such a scenario, the inspection engine302may identify the expressions “this.close” and “this.open” as expressions that should be evaluated in batch with similar expressions. Therefore, for each stack202, the corresponding “this.close” expression is evaluated in batch with the “this.close” expressions in the remaining stacks202. Similarly, for each stack202, the corresponding “this.open” expression is evaluated in batch with the “this.open” expressions in the remaining stacks202.

For a particular stack202, once the inspection engine302determines that the current expression should be evaluated in batch with other similar expressions, the blocking engine304blocks the processing of the current expression and the stack202, in general. At this instant, the stack202transitions to a “blocked state.” Therefore, at any given point, a stack202is either in an evaluation state, a blocked state or a completed state. When all the stacks202are either in a blocked state or a completed state, the blocking engine304prepares the current expressions in each of the blocked stacks202(referred to herein as the “blocked expressions”) for evaluation on the application server106in batch. The blocking engine304divides the blocked expressions into partitions, where blocked expressions in a particular partition are each associated with at least one similar characteristic. For example, each blocked expression in a particular partition may need a database call to be executed by the application server106.

Once the blocked expressions are divided into partitions, the blocking engine304dispatches, per partition, a single call to the application server106for evaluating all of the expressions in that partition. The application server106evaluates the expression in a manner described above in conjunction withFIG. 1. The application server106transmits the results associated with each expression in a partition to the unblocking engine306. For each result associated with a particular expression, the unblocking engine306updates the stack202corresponding to the expression to store the result. The updated stack202is then unblocked and the frames204within the stack202continue to be processed.

The inspection engine302continues to inspect the stacks202to identify expressions that can be evaluated in batch. In turn, the blocking engine304continues to block stacks202and dispatch calls for evaluating similar expressions in batch until each of the stacks202is in a completed state. In such a manner, similar expressions from different stacks202are processed in batch within the application server106, thus increasing the efficiency of the overall system.

FIG. 4is an exemplary system within which the application102ofFIG. 1could execute, according to one embodiment of the invention. As shown, the system400includes a system memory402, an external memory404, a central processing unit (CPU)406, an input device410and an display device412.

The system memory402includes the application102previously described herein. The system memory402is a memory space, usually a random access memory (RAM), that temporarily stores software programs running within the system400at any given time. The CPU406executes a sequence of stored instructions associated with and/or transmitted from the various elements in the computer system400. The external memory404is a storage device, e.g. a hard disk, for storing data associated with the application102. The input device410is an end-user controlled input device, e.g. a mouse or keyboard, that allows a user to manipulate various aspects of the application102. The display device412may be a cathode-ray tube (CRT), a liquid crystal display (LCD) or any other type of display device.

FIGS. 5A and 5Bset forth a flow diagram of method steps for evaluating a program instruction within the stack evaluator, according to one embodiment of the invention. Although the method steps are described in conjunction with the system forFIG. 1-4, persons skilled in the art will understand that any system configured to perform the method steps, in any order, is within the scope of the invention.

The method500begins at step501, where the stack evaluator118generates a stack202corresponding to a program subroutine associated with the application102that is being evaluated. At step502, the stack evaluator118generates a call frame associated with a particular program instruction included in the program subroutine. As discussed above, each program instruction within a program subroutine includes one or more expressions to be evaluated. An expression may be an argument, a parameter and/or a metric, as described above. Therefore, the call frame associated with the particular program instruction includes the one or more expressions to be evaluated.

At step504, the stack evaluator118generates a different child frame for evaluating each expression within that instruction. For example, an array frame is generated for each argument of an instruction. At step506, the stack evaluator118transitions the stack202to an evaluation state. At step508, the stack evaluator118begins the evaluation of an expression included in a next child frame to be evaluated (referred to herein as the “current frame”). An expression is evaluated either within the stack evaluator118itself or needs to be processed within the application server106as described above in conjunction withFIG. 1.

At step510, the stack evaluator118receives a request from the inspection engine302to inspect the current frame. As described above, each time a new frame is being evaluated, the inspection engine analyzes a current expression that is to be evaluated within the frame to determine whether the evaluation of the expression should be executed in batch with other similar expressions. The process of inspection and batch execution is described in detail with respect toFIGS. 6A and 6B.

At step512, the stack evaluator118determines whether the stack202is in a blocked state. As discussed above and described in greater detail with respect toFIGS. 6A and 6B, for a particular stack202, if the inspection engine302determines that the current expression should be evaluated in batch with other similar expressions, then the blocking engine304blocks the processing of the current expression and the stack202, in general. If, at step512, the stack evaluator118determines that the stack202is in a blocked state, then the method500proceeds to step514, where the stack evaluator118waits until the stack202is unblocked by the unblocking engine306. However, if, at step512, the stack evaluator118determines that the stack202is not in a blocked state, then the method500proceeds to step516, where the stack evaluator118completes the evaluation of the expression in the current frame.

At step518, the stack evaluator118determines whether any child frames were generated at step504are still not evaluated. If so, then the method proceeds to step508previously described herein. If the stack evaluator118determines that all the child frames were generated at step504have been evaluated, then the method500proceeds to step520. At step520, the stack evaluator118determines whether the call frame that was generated at step502has been evaluated.

If, at step520, the stack evaluator118determines that the call frame that was generated at step502has not been evaluated, then the method500proceeds to step522. At step522, the stack evaluator118begins the evaluation of the call frame based on the expressions that were evaluated via the child frames. The method then proceeds to step510previously described herein.

If, however, at step520, the stack evaluator118determines that the call frame that was generated at step502has already been evaluated, then the method500proceeds to step524. At step524, the stack evaluator118transitions the state of the stack202to the completed state. The method500then ends.

As discussed above, the application102is associated with one or more program subroutines and each program subroutine includes multiple program instructions. Persons skilled in the art would recognize that the stack evaluator118executes the method steps described with respect toFIGS. 5A and 5Bfor each program instruction included in each program subroutine associated with the application102, as discussed above.

FIGS. 6A and 6Bset forth a flow diagram of method steps for processing related program instructions in batches, according to one embodiment of the invention. Although the method steps are described in conjunction with the system forFIG. 1-4, persons skilled in the art will understand that any system configured to perform the method steps, in any order, is within the scope of the invention.

The method600begins at step602, where the inspection engine302, for each stack202, inspects an expression within the stack202that is to be evaluated. At step604, the inspection engine302, based on the inspection, identifies one or more expressions included in the unblocked stacks that should be batch processed. As previously described, the inspections engine302identifies such expressions based on a type of the expression, the number of inputs specified in the expression, the type of operation to be performed, etc.

At step606, the blocking engine304blocks the processing of the expressions identified at step604and the stacks202that include those expressions. In one embodiment, the blocking engine304transitions the state of each of the stacks202to a blocked state. At step608, the blocking engine304determines whether all the stacks are in a blocked or completed state. If, at step608, at least one stack is not in a blocked or completed state, then the method600returns to step602. If, however, at step608, all the stacks are in a blocked or completed state, then the method600proceeds to step610.

At step610, the blocking engine304divides the expressions included in the blocked stacks into partitions, where expressions in a particular partition are each associated with at least one similar characteristic. For example, each blocked expression in a particular partition may be a database call to be executed by the application server106. At step612, once the blocked expressions are divided into partitions, the blocking engine304dispatches, for each partition, a single call to the application server106for evaluating each of the expressions in that partition in batch. The application server106evaluates the expression in a manner described above in conjunction withFIG. 1.

At step614, the unblocking engine306receives, for each partition, the results for each expression in the partition. At step616, for each received result, the unblocking engine306updates the stack202corresponding to the expression for which the result was generated to store the result. At step618, the unblocking engine306unblocks each of the updated stacks202, which then continue to be processed.

Advantageously, because a single batch processing request is transmitted to the application server for a group of similar expressions, the number of processing requests received by the application server is reduced. As a result, the application server is not burdened with a large amount of requests at any given time. Therefore, the overall processing efficiency of the application server is increased and the overall processing latency of the application server is reduced.

Another embodiment of the invention may be implemented as a program product deployed for use over a network. In such an embodiment, the program product may be accessed via a web browser.