Automated expression parallelization
A system is capable of automatically adjusting or reconstructing a baseline expression to generate a parallelized expression. Evaluation of the parallelized expression provide a substantially similar output as the evaluation of the baseline query in more efficient manner. In some implementations, data indicating an expression to be evaluated on a primary thread of the one or more processors is obtained. Elements of the expression are identified. The elements are grouped into a parse tree representation. Elements of the expression are classified as belonging to either a first category that includes elements that are eligible for parallel processing or a second category that includes elements that are not eligible for parallel processing. A particular element that is classified as belonging to the first category is identified and evaluated on a non-primary thread of the one or more processors. The non-primary thread is evaluated in parallel with the primary thread.
1. A method performed by one or more processors of a computing device, the method comprising:
obtaining, by the [A1] computing device, data indicating an expression to be evaluated on a primary thread of the one or more processors, wherein:
the expression is coded in a declarative programming language and references computer-executable elements that are each associated with imperative programming language executed by the one or more processors, and
the computer-executable elements of the expression comprise at least a processor-bound element and an IO-bound element that is classified as being eligible for parallel processing;
grouping, by the computing device and based on the respective classifications of the IO-bound element and the processor-bound element, the computer-executable elements into a parse tree representation, wherein:
the parse tree representation comprises a hierarchal structure of nodes and reflects an assignment of computer-executable elements to nodes of the parse tree representation based on a particular sequence of evaluating the computer-executable elements of the expression,
the IO-bound element is assigned to a first child node of an intermediate node within the parse tree representation, and
the processor-bound element is assigned to a second child node of the intermediate node within the parse tree representation; and
based on the respective assignments of the IO-bound element and the processor-bound element within the parse tree representation, evaluating, by the computing device, the IO-bound element and the processor-bound element on a non-primary thread of the one or more processors that is executed in parallel with the primary thread of the one or more processors, wherein the processor-bound element is evaluated prior to evaluation of the IO-bound element.
2. The method of claim 1 , wherein:
the hierarchal structure of nodes comprises (i) a root node, and (ii) intermediate nodes descending within the hierarchal structure from the root node;
the intermediate nodes comprise one or more intermediate nodes having one or more child nodes descending within the hierarchal structure from the one or more intermediate nodes; and
the method further comprises classifying, by the computing device and sequentially along the hierarchal structure of nodes, individual computer-executable elements of the expression as either elements that are eligible for parallel processing or elements that are not eligible for parallel processing, the classification comprising:
determining, for an intermediate node to which a computer-executable element is assigned, one or more child nodes associated with the intermediate node,
classifying the computer-executable elements assigned to the one or more child nodes,
determining a composite classification for the intermediate node based on classifying the computer-executable elements assigned to the one or more child nodes, and
classifying the computer-executable element assigned to the intermediate node based on the composite classification.
3. The method of claim 1 , further comprising:
reconstructing, by the computing device and based on the parse tree representation, a text segment of the expression to generate a text segment for a transformed expression, the transformed expression specifying evaluation of one or more elements from among the computer-executable elements of the expression on the non-primary thread; and
providing, by the computing device and for output to a client device, data indicating the text segment for the transformed expression.
4. The method of claim 3 , further comprising:
determining, by the computing device, a particular sequence to evaluate the computer-executable elements of the transformed expression based on the grouping of the identified computer-executable elements into the parse tree representation; and
providing, by the computing device and for output to the client device, an instruction specifying the particular sequence to evaluate the computer-executable elements of the transformed expression.
5. The method of claim 3 , wherein:
the text segment for the expression does not include text corresponding to parallelization code; and
the text segment for the transformed expression includes a portion corresponding to parallelization code.
6. The method of claim 5 , wherein the text segment for the expression is specified by a user input provided by a user through a user interface for a developer application that runs on the client device.
7. The method of claim 1 , further comprising:
determining, by the computing device, that evaluation of a computer-executable element assigned to a first child node of a particular intermediate node is not computationally dependent on evaluation of a computer-executable element assigned to a second child of the particular intermediate node; and
in response to determining that evaluation of the computer-executable element assigned to the first child node is not computationally dependent on evaluation of the computer-executable element assigned to the second child node, generating, by the computing device, an instruction that causes the one or more processors to:
evaluate the computer-executable element assigned to the first child node on the primary thread, and
evaluate the computer-executable element assigned to the second child node on the non-primary thread.
8. The method of claim 1 , further comprising:
determining, by the computing device, that evaluation of a computer-executable element assigned to a first child node of a particular intermediate node is computationally dependent on evaluation of a computer-executable element assigned to a second child node of the particular intermediate node;
determining, by the computing device, that evaluation of a computer-executable element assigned to a third child node of the particular intermediate node is not computationally dependent on evaluation of a computer-executable element assigned to the second child of the particular intermediate node; and
in response to determining that evaluation of the computer-executable element assigned to the first child node is computationally dependent on evaluation of a computer-executable element assigned to a second child node, generating, by the computing device, an instruction that, causes the one or more processors to:
evaluate the computer-executable element assigned to the third child node on the primary thread,
evaluate the computer-executable element assigned to the second child node on the non-primary thread, and
based on evaluating the computer-executable element assigned to the second child node, evaluate the computer-executable element assigned to the first child node on the non-primary thread.
9. A system comprising:
one or more computers; and
one or more storage devices storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising:
obtaining, by a computing device, data indicating an expression to be evaluated on a primary thread of one or more processors of the computing device, wherein:
the expression is coded in a declarative programming language and references computer-executable elements that are each associated with imperative programming language executed by the one or more processors, and
the computer-executable elements of the expression comprise at least a processor-bound element and an IO-bound element that is classified as being eligible for parallel processing;
grouping, by the computing device and based on the respective classifications of the IO-bound element and the processor-bound element, the computer-executable elements into a parse tree representation, wherein:
the parse tree representation comprises a hierarchal structure of nodes and reflects an assignment of computer-executable elements to nodes of the parse tree representation based on a particular sequence of evaluating the computer-executable elements of the expression,
the IO-bound element is assigned to a first child node of an intermediate node within the parse tree representation, and
the processor-bound element is assigned to a second child node of the intermediate node within the parse tree representation; and
based on the respective assignments of the IO-bound element and the processor-bound element within the parse tree representation, evaluating, by the computing device, the IO-bound element and the processor-bound element on a non-primary thread of the one or more processors that is executed in parallel with the primary thread of the one or more processors, wherein the processor-bound element is evaluated prior to evaluation of the IO-bound element.
10. The system of claim 9 , wherein:
the hierarchal structure of nodes comprises (i) a root node, and (ii) intermediate nodes descending within the hierarchal structure from the root node;
the intermediate nodes comprise one or more intermediate nodes having one or more child nodes descending within the hierarchal structure from the one or more intermediate nodes; and
wherein the operations further comprise classifying, sequentially along the hierarchal structure of nodes, individual computer-executable elements of the expression as either elements that are eligible for parallel processing or elements that are not eligible for parallel processing, the classification comprising:
determining, for an intermediate node to which a computer-executable element is assigned, one or more child nodes associated with the intermediate node,
classifying the computer-executable elements assigned to the one or more child nodes,
determining a composite classification for the intermediate node based on classifying the computer-executable elements assigned to the one or more child nodes, and
classifying the computer-executable element assigned to the intermediate node based on the composite classification.
11. The system of claim 9 , wherein the operations further comprise:
reconstructing, based on the parse tree representation, a text segment of the expression to generate a text segment for a transformed expression, the transformed expression specifying evaluation of one or more computer-executable elements from among the computer-executable elements of the expression on the non-primary thread; and
providing data indicating the text segment for the transformed expression for output to a client device.
12. A non-transitory computer-readable storage device encoded with computer program instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:
obtaining, by a computing device, data indicating an expression to be evaluated on a primary thread of one or more processors of the computing device, wherein:
the expression is coded in a declarative programming language and references computer-executable elements that are each associated with imperative programming language executed by the one or more processors, and
the computer-executable elements of the expression comprise at least a processor-bound element and an IO-bound element that is classified as being eligible for parallel processing;
grouping, by the computing device and based on the respective classifications of the IO-bound element and the processor-bound element, the computer-executable elements into a parse tree representation, wherein:
the parse tree representation comprises a hierarchal structure of nodes and reflects an assignment of computer-executable elements to nodes of the parse tree representation based on a particular sequence of evaluating the computer-executable elements of the expression,
the IO-bound element is assigned to a first child node of an intermediate node within the parse tree representation, and
the processor-bound element is assigned to a second child node of the intermediate node within the parse tree representation; and
based on the respective assignments of the IO-bound element and the processor-bound element within the parse tree representation, evaluating, by the computing device, the IO-bound element and the processor-bound element on a non-primary thread of the one or more processors that is executed in parallel with the primary thread of the one or more processors, wherein the processor-bound element is evaluated prior to evaluation of the IO-bound element.
13. The device of claim 12 , wherein:
the hierarchal structure of nodes comprises (i) a root node, and (ii) intermediate nodes descending within the hierarchal structure from the root node;
the intermediate nodes comprise one or more intermediate nodes having one or more child nodes descending within the hierarchal structure from the one or more intermediate nodes; and
wherein the operations further comprise classifying, sequentially along the hierarchal structure of nodes, individual computer-executable elements of the expression as either elements that are eligible for parallel processing or elements that are not eligible for parallel processing, the classification comprising:
determining, for an intermediate node to which a computer-executable element is assigned, one or more child nodes associated with the intermediate node,
classifying the computer-executable elements assigned to the one or more child nodes,
determining a composite classification for the intermediate node based on classifying the computer-executable elements assigned to the one or more child nodes, and
classifying the computer-executable element assigned to the intermediate node based on the composite classification.
14. The device of claim 12 , wherein the operations further comprise:
reconstructing, based on the parse tree representation, a text segment of the expression to generate a text segment for a transformed expression, the transformed expression specifying evaluation of one or more computer-executable elements from among the computer-executable elements of the expression on the non-primary thread; and
providing data indicating the text segment for the transformed expression for output to a client device.
15. The device of claim 14 , wherein the operations further comprise:
determining a particular sequence to evaluate the computer-executable elements of the transformed expression based on the grouping of the identified computer-executable elements into the parse tree representation; and
providing, for output to the client device, an instruction specifying the particular sequence to evaluate the computer-executable elements of the transformed expression.