System and method for batch evaluation programs

• US 9,898,335 B1
• Filed: 05/02/2016
• Issued: 02/20/2018
• Est. Priority Date: 10/22/2012
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Marinelli, III, Eugene E., Namara, Yogy
• Primary Examiner(s): Do, Chat
• Assistant Examiner(s): Wood, William C
• Application Number:
  US15/144,602
• Time in Patent Office: 659 Days
• Field of Search: None
• CPC Class Codes: G06F 2209/484 Precedence
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/547 Remote procedure calls [RPC]; Web services

Abstract

A batching module that prepares a plurality of blocked expressions for batch evaluation. The plurality of blocked expressions comprises a current expression in a particular stack in a blocked state. The batching module divides the plurality of blocked expressions into one or more partitions. For each particular partition of the one or more partitions, a single batch processing call is dispatched to an application server to perform a batch evaluation.

Claims

1. A method comprising:

preparing a plurality of blocked expressions for batch evaluation, wherein the plurality of blocked expressions comprises a current expression in a particular stack;

wherein the particular stack is in a blocked state;

dividing the plurality of blocked expressions into one or more partitions;

wherein each partition of the one or more partitions comprises one or more blocked expressions associated with at least one similar characteristic;

wherein the dividing is based, at least in part, on the at least one similar characteristic;

for each particular partition of the one or more partitions, dispatching a single batch processing call to an application server to perform a batch evaluation of the one or more blocked expressions associated with the at least one similar characteristic;

for each particular partition of the one or more partitions, receiving results from the application server of the batch evaluation of the one or more blocked expressions associated with at least one similar characteristic;

updating the one or more blocked expressions with the results;

transitioning a state of the particular stack to an unblocked state or completed state; and

wherein the method is performed using one or more processors.

2. The method of claim 1, further comprising:

determining that every stack in a plurality of stacks is in a blocked state or a completed state.

3. The method of claim 2, further comprising:

prior to determining that every stack in a plurality of stacks is in a blocked state or completed state, identifying expressions for batch evaluation in one or more stacks of the plurality of stacks that is in an unblocked state;

transitioning a state of each stack of the plurality of stacks that is in an unblocked state to a blocked state.

4. The method of claim 3, wherein identifying expressions for batch evaluation comprises determining whether the expressions have a particular characteristic that is included in a pre-determined list of characteristics that are associated with expressions that should be batch evaluated.

5. The method of claim 4, wherein the pre-determined list of characteristics comprises a particular characteristic of an expression that is evaluated via a database call.

6. The method of claim 4, wherein the pre-determined list of characteristics comprises a particular characteristic of an expression that specifies a plurality of inputs.

7. The method of claim 1, wherein the similar characteristic comprises an attribute and wherein the attribute is one of:

type of an expression, number of inputs specified in the expression, or a type of operation to be performed by the expression.

8. The method of claim 1, wherein the particular stack corresponds to a program subroutine associated with an application program.

9. The method of claim 8, wherein the particular stack comprises a plurality of frames and wherein each frame of the plurality of frames corresponds to a particular evaluation iteration of the program subroutine.

10. A data processing system, comprising:

one or more storage media;

one or more processors coupled to the one or more storage media;

one or more programs stored in the storage media and configured for execution by the one or more processors, the one or more programs comprising instructions which when executed by the one or more processors cause performing;

preparing a plurality of blocked expressions for batch evaluation, wherein the plurality of blocked expressions comprises a current expression in a particular stack;

wherein the particular stack is in a blocked state;

dividing the plurality of blocked expressions into one or more partitions;

wherein each partition of the one or more partitions comprises one or more blocked expressions associated with at least one similar characteristic;

wherein the dividing is based, at least in part, on the at least one similar characteristic;

for each particular partition of the one or more partitions, dispatching a single batch processing call to an application server to perform a batch evaluation of the one or more blocked expressions associated with the at least one similar characteristic;

for each particular partition of the one or more partitions, receiving results from the application server of the batch evaluation of the one or more blocked expressions associated with at least one similar characteristic;

updating the one or more blocked expressions with the results; and

transitioning a state of the particular stack an unblocked state or completed state.

11. The system of claim 10, wherein the instructions further comprise instructions for:

determining that every stack in a plurality of stacks is in a blocked state or a completed state.

12. The system of claim 11, wherein the instructions further comprise instructions for:

prior to determining that every stack in a plurality of stacks is in a blocked state or completed state, identifying expressions for batch evaluation in one or more stacks of the plurality of stacks that is in an unblocked state;

transitioning a state of each stack of the plurality of stacks that is in an unblocked state to a blocked state.

13. The system of claim 12, wherein the instructions for identifying expressions for batch evaluation comprise instructions for determining whether the expressions have a particular characteristic that is included in a pre-determined list of characteristics associated with expressions that should be batch evaluated.

14. The system of claim 13, wherein the pre-determined list of characteristics comprises a particular characteristic of an expression that is evaluated via a database call.

15. The system of claim 13, wherein the pre-determined list of characteristics comprises a particular characteristic of an expression that specifies a plurality of inputs.

16. The system of claim 10, wherein the similar characteristic comprises an attribute wherein the attribute is one of:

type of an expression, number of inputs specified in the expression, or a type of operation to be performed by the expression.

17. The system of claim 10, wherein the particular stack corresponds to a program subroutine associated with an application.

18. The system of claim 17, wherein the particular stack comprises a plurality of frames and wherein each frame of the plurality of frames corresponds to a particular evaluation iteration of the program subroutine.

19. A data processing method comprising:

using a computer, preparing a plurality of blocked expressions that are stored in digital computer memory for batch evaluation, wherein the plurality of blocked expressions comprises a current expression in a particular stack;

wherein the particular stack is in the computer memory and is in a blocked state;

using the computer, dividing the plurality of blocked expressions into one or more partitions in the computer memory;

wherein each partition of the one or more partitions comprises one or more blocked expressions associated with at least one similar characteristic;

wherein the dividing is based, at least in part, on the at least one similar characteristic;

using the computer, for each particular partition of the one or more partitions, dispatching a single batch processing call to an application server computer wherein the single batch processing call is configured to cause the application server computer to perform a batch evaluation of the plurality of blocked expressions that are in that particular partition;

for each particular partition of the one or more partitions, receiving results from the application server of the batch evaluation of the one or more blocked expressions associated with at least one similar characteristic;

updating the one or more blocked expressions with the results; and

transitioning a state the particular stack to an unblocked state or completed state.