Code refactoring mechanism for asynchronous code optimization using topological sorting
10157055 ยท 2018-12-18
Assignee
Inventors
Cpc classification
International classification
Abstract
Methods, systems, apparatuses, and computer program products are provided for transforming asynchronous code into more efficient, logically equivalent asynchronous code; Program code is converted into a first syntax tree. A dependency graph is generated from the first syntax tree with each node of the dependency graph corresponding to a code statement and having an assigned weight. Weighted topological sorting of the dependency graph is performed to generate a sorted dependency graph. A second syntax tree is generated from the sorted dependency graph. In another implementation, the program code is transformed into await-relaxed and/or loop-relaxed program code prior to being transformed into the first syntax tree.
Claims
1. A method for transforming asynchronous code into more efficient, logically equivalent asynchronous code, comprising: converting asynchronous program code into a first syntax tree; generating a dependency graph from the first syntax tree with each node of the dependency graph corresponding to a code statement and having an assigned weight; performing weighted topological sorting of the dependency graph to generate a sorted dependency graph, said performing weighted topological sorting including modifying an order of asynchronous code statements in the dependency graph based at least on weights assigned to nodes of the dependency graph; and converting the sorted dependency graph to refactored asynchronous code that is logically equivalent to the asynchronous program code.
2. The method of claim 1, wherein said converting asynchronous program code into a first syntax tree comprises: transforming the asynchronous program code into await-relaxed program code; and converting the await-relaxed program code into the first syntax tree.
3. The method of claim 2, wherein said the transforming the asynchronous program code into await-relaxed program code comprises: converting any awaits on asynchronous method calls in the asynchronous program code to awaits on task variables.
4. The method of claim 1, wherein said converting asynchronous program code into a first syntax tree comprises: transforming the asynchronous program code into loop-relaxed program code; and converting the loop-relaxed program code into the first syntax tree.
5. The method of claim 1, wherein said generating a dependency graph from the first syntax tree with each node of the dependency graph corresponding to a code statement and having an assigned weight comprises: generating a dependency graph by following on variables resulting from each code statement of the first syntax tree; and assigning weights to the nodes of the dependency graph.
6. The method of claim 5, wherein said assigning weights to the nodes of the dependency graph comprises: assigning a first weight to nodes of the dependency graph corresponding to code statements that start asynchronous operations; assigning a second weight to nodes of the dependency graph corresponding to code statements that await; and assigning a third weight to nodes of the dependency graph not assigned the first weight and not assigned the second weight.
7. The method of claim 1, wherein said converting the sorted dependency graph to refactored asynchronous code that is logically equivalent to the asynchronous program code comprises: generating a second syntax tree from the sorted dependency graph; and converting the second syntax tree into the refactored asynchronous code.
8. A computing device, comprising: at least one processor circuit; and at least one memory that stores instructions configured to be executed by the at least one processor circuit, the instructions configured to perform operations for transforming asynchronous code into more efficient, logically equivalent asynchronous code, the operations comprising: converting asynchronous program code into a first syntax tree, generating a dependency graph from the first syntax tree with each node of the dependency graph corresponding to a code statement and having an assigned weight, performing weighted topological sorting of the dependency graph to generate a sorted dependency graph, said performing weighted topological sorting including modifying an order of asynchronous code statements in the dependency graph based at least on weights assigned to nodes of the dependency graph; and converting the sorted dependency graph to refactored asynchronous code that is logically equivalent to the asynchronous program code.
9. The computing device of claim 8, wherein said converting asynchronous program code into a first syntax tree comprises: transforming the asynchronous program code into await-relaxed program code; and converting the await-relaxed program code into the first syntax tree.
10. The computing device of claim 9, wherein said the transforming the asynchronous program code into await-relaxed program code comprises: converting any awaits on asynchronous method calls in the asynchronous program code to awaits on task variables.
11. The computing device of claim 8, wherein said converting asynchronous program code into a first syntax tree comprises: transforming the asynchronous program code into loop-relaxed program code; and converting the loop-relaxed program code into the first syntax tree.
12. The computing device of claim 8, wherein said generating a dependency graph from the first syntax tree with each node of the dependency graph corresponding to a code statement and having an assigned weight comprises: generating a dependency graph by following on variables resulting from each code statement of the first syntax tree; and assigning weights to the nodes of the dependency graph.
13. The computing device of claim 12, wherein said assigning weights to the nodes of the dependency graph comprises: assigning a first weight to nodes of the dependency graph corresponding to code statements that start asynchronous operations; assigning a second weight to nodes of the dependency graph corresponding to code statements that await; and assigning a third weight to nodes of the dependency graph not assigned the first weight and not assigned the second weight.
14. The computing device of claim 8, where said converting the sorted dependency graph to refactored asynchronous code that is logically equivalent to the asynchronous program code comprises: generating a second syntax tree from the sorted dependency graph; and converting the second syntax tree into the refactored asynchronous code.
15. A computing device, comprising: at least one processor circuit; and at least one memory that stores instructions configured to be executed by the at least one processor circuit, the instructions configured to perform operations for transforming asynchronous code into more efficient, logically equivalent asynchronous code, the instructions comprising: a code-to-syntax tree converter configured to convert asynchronous program code into a first syntax tree; a dependency graph generator configured to generate a dependency graph from the first syntax tree with each node of the dependency graph corresponding to a code statement and having an assigned weight; a topological sorter configured to perform weighted topological sorting of the dependency graph to generate a sorted dependency graph, wherein to perform weighted topological sorting, the topological sorter is configured to modify an order of asynchronous code statements in the dependency graph based at least on weights assigned to nodes of the dependency graph; and a graph-to-code converter configured to convert the sorted dependency graph to refactored asynchronous code that is logically equivalent to the asynchronous program code.
16. The computing device of claim 15, wherein the code-to-syntax tree converter includes: an await relaxer configured transform the asynchronous program code into await-relaxed program code; and the code-to-syntax tree converter is configured to convert the await-relaxed program code into the first syntax tree.
17. The computing device of claim 16, wherein the await-relaxer is configured to convert any awaits on asynchronous method calls in the asynchronous program code to awaits on task variables.
18. The computing device of claim 15, wherein the code-to-syntax tree converter includes: a loop-relaxer configured to transform the asynchronous program code into loop-relaxed program code; and the code-to-syntax tree converter is configured to convert the loop-relaxed program code into the first syntax tree.
19. The computing device of claim 15, wherein the dependency graph generator includes: a variable follower configured to generate the dependency graph by following on variables resulting from each code statement of the first syntax tree; and a weight assigner configured to assign weights to the nodes of the dependency graph.
20. The computing device of claim 19, the weight assigner is configured to: assign a first weight to nodes of the dependency graph corresponding to code statements that start asynchronous operations; assign a second weight to nodes of the dependency graph corresponding to code statements that await; and assign a third weight to nodes of the dependency graph not assigned the first weight and not assigned the second weight.
Description
BRIEF DESCRIPTION OF THE DRAWINGS/FIGURES
(1) The accompanying drawings, which are incorporated herein and form a part of the specification, illustrate embodiments of the present application and, together with the description, further serve to explain the principles of the embodiments and to enable a person skilled in the pertinent art to make and use the embodiments.
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16) The features and advantages of the present invention will become more apparent from the detailed description set forth below when taken in conjunction with the drawings, in which like reference characters identify corresponding elements throughout. In the drawings, like reference numbers generally indicate identical, functionally similar, and/or structurally similar elements. The drawing in which an element first appears is indicated by the leftmost digit(s) in the corresponding reference number.
DETAILED DESCRIPTION
I. Introduction
(17) The present specification and accompanying drawings disclose one or more embodiments that incorporate the features of the present invention. The scope of the present invention is not limited to the disclosed embodiments. The disclosed embodiments merely exemplify the present invention, and modified versions of the disclosed embodiments are also encompassed by the present invention. Embodiments of the present invention are defined by the claims appended hereto.
(18) References in the specification to one embodiment, an embodiment, an example embodiment, etc., indicate that the embodiment described may include a particular feature, structure, or characteristic, but every embodiment may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is submitted that it is within the knowledge of one skilled in the art to effect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described.
(19) In the discussion, unless otherwise stated, adjectives such as substantially and about modifying a condition or relationship characteristic of a feature or features of an embodiment of the disclosure, are understood to mean that the condition or characteristic is defined to within tolerances that are acceptable for operation of the embodiment for an application for which it is intended.
(20) Numerous exemplary embodiments are described as follows. It is noted that any section/subsection headings provided herein are not intended to be limiting. Embodiments are described throughout this document, and any type of embodiment may be included under any section/subsection. Furthermore, embodiments disclosed in any section/subsection may be combined with any other embodiments described in the same section/subsection and/or a different section/subsection in any manner.
II. Example Embodiments for Optimizing Queries in Program Code
(21) Many development tools and programming languages enable synchronous and asynchronous programming. A program must wait for a synchronous process/operation to complete before continuing execution. A program does not have to wait for an asynchronous process/operation to complete before continuing execution. As such, asynchronous operations can enable more efficient execution of program code.
(22) A programming language may include keywords that designate operations for asynchronous operation. For instance, in the C# programming language, the async keyword is used to designate an asynchronous method that generates a task as a result, and program execution can continue until the await keyword is encountered. The await keyword is used to retrieve the result of the task when the asynchronous method is eventually complete, and once the result is returned, program execution may continue. Programming languages like Scala, Python, JavaScript, and others may use the keywords async and await in similar or different ways to C#, and/or may use other keywords in any suitable fashion to designate asynchronous code and to indicate tasks to be awaited on.
(23) As such, in asynchronous programming, the position in the program code for the await (or similar) keyword can have a significant impact on how efficiently the program code executes, including altering the running time of the code drastically. The less experienced the developer (also known as programmer or computer programmer), the more likely that developer will develop program code that inefficiently handles asynchronous operations.
(24) According to embodiments, an automated tool is provided that analyzes the developer's code and refactors it without changing the underlying programming logic. This analysis and refactoring can increase the performance of asynchronous operations in the program code, which can relieve performance bottlenecks in many applications.
(25) In an embodiment, the tool performs several steps, including (a), building the relevant data structures, (b) analyzing the code for potential locations for improving asynchronous performance, and (c) refactoring the code. For instance, in (a), each awaited, asynchronous statement may be divided into two logically equal statements, where the first is a statement that returns a task (in C# terminology) and the second statement is the actual wait on that task. In addition, await statements in loop scope code, if any exist, may be observed as a component. Each code statement is decomposed, and a dependency graph is built (e.g., a directed acyclic graph). In (b), each code statement is ranked/weighted. For instance, ranking values from 0 to 2 may be used, where 0 is assigned to code statements that begin an asynchronous command, 1 is assigned to non-asynchronous code statements, and 2 is assigned to awaited code statements. The dependency graph may be topologically sorted, and the weighted-topologically sorted graph can be used find the best place to position the await statements without changing the code logic. The refactoring of code in (c) is optional. If the developer chooses to, the tool may perform the actual code refactoring according to the analysis.
(26) Various techniques may be used for the topological sorting of the dependency graph, including topological sorting with modified-DFS (Depth first search), recursion (which can result in higher memory consumption), or known scheduling algorithms.
(27) Accordingly, embodiments provide a tool that moves await or similar statements in program code in a way that improves the code's efficiency, that finds an efficient ordering by running topological sorting, and that can notify the developer about potential code improvements, while performing the actual refactoring at the developer's option.
(28) Embodiments may be implemented in various ways. For instance,
(29) Asynchronous code optimizer 104 may be implemented independently or included in any system or tool that may be used by a developer to input or process program code, such as a code editor, a code compiler, a code debugger, etc. For instance,
(30) As shown in
(31) Computing device 102 may be one or more of any type of stationary or mobile computing device(s), including a mobile computer or mobile computing device (e.g., a Microsoft Surface device, a personal digital assistant (PDA), a laptop computer, a notebook computer, a tablet computer such as an Apple iPad, a netbook, etc.), a mobile phone, a wearable computing device, or other type of mobile device, or a stationary computing device such as a desktop computer or PC (personal computer).
(32) Code editor 202 may be any proprietary or conventional code editor configured for editing of program code mentioned elsewhere herein or otherwise known (e.g., a code editor of Eclipse, ActiveState Komodo, IntelliJ IDEA, Oracle JDeveloper NetBeans, Codenvy, Xcode, Microsoft Visual Studio, etc.).
(33) A developer may interact with source code editor 202 to enter and modify program code when generating source code for an application. For instance, the developer may interact with a user interface 212 of source code editor 202 to add, modify, or delete program code text such as by typing, by voice input, by selecting suggested code blocks, etc. Accordingly, user interface 212 may include one or more text entry boxes/windows (e.g., code editor window 604 of
(34) For instance, as shown in
(35) As shown in
(36) Compiler 204 may be invoked in any manner, such as by a command line, a graphical user interface, etc. A -full switch, or other switch, may be used when compiler 204 is invoked to perform a full compile. Compiler 204 is configured to receive and compile program code 106 (or program code 108) to generate machine code 222. In particular, compiler 204 is configured to transform program code 106 and/or 108 into machine code 222 in the form of another computer language, typically having a binary form, referred to as machine code or object code. In some cases, compiler 204 may include multiple stages, and may first convert program code 106 into an intermediate form (e.g., an intermediate language), which is subsequently converted into machine code 222.
(37) Compiler 204 may be configured to perform one or more types of optimizations on program code 106 and/or 108 when generating machine code 222. An optimized build results in machine code that is semantically equivalent to machine code generated without optimizations, but is configured in a way that fewer resources are used during execution of the optimized machine code (e.g., less memory, fewer procedure calls, etc.). Examples of optimizations that may be performed include loop optimizations, data-flow optimizations, SSA-based optimizations, code-generator optimizations, functional language optimizations, interprocedural optimizations, and/or further types of optimizations that would be known to persons skilled in the relevant art(s). Many specific types of optimizations exist. For example, inlining may be performed, where a callee function called by a caller function is copied into the body of the caller function. In another example of a specific optimization, common subexpression elimination may be performed, where a single instance of code is used for a quantity that is computed multiple times in source code. When asynchronous code optimizer 104 is used by compiler 204 to process program code 106 for improvements in asynchronous code execution, refactored program code 108 may be generated and used to generate machine code 222 by compiler 204.
(38) Machine code 222 may be included in a file (e.g., an object or .obj file), or may be created/stored in another form, to form an executable program or application. Machine code 222 may optionally be stored in storage 210.
(39) When program code 106 and/or 108 is compiled by compiler 204 for the debug stage of development, debugger tool 206 may receive machine code 222. Debugger tool 206 is configured to run a debugger (or debug, debugging) session on the application represented by machine code 222. In a debugger session, a developer may be enabled to step through the execution of code of machine code 222, while viewing the values of variables, arrays, attributes, and/or outputs (e.g., contents of registers, a GUI, etc.) generated by the execution of machine code 222, including having access to the effects of any debug code/statements entered into program code 106 and/or 108 (and passed to machine code 222 by compiler 204 for purposes of debug). In this manner, a developer may be able to test or troubleshoot (debug) program code 106 and/or 108, making edits to program code 106 and/or 108 using source code editor 202 based on the results of the debugger session. The modified version of program code 106 and/or 108 may be compiled by compiler 204 and received by debugger tool 206 for further debugging. During debug, debugger tool 206 may enable asynchronous code optimizer 104 to suggest asynchronous program code improvements in program code 106 to generate program code 108. Debugger tool 206 may include one or more processors (e.g., a central processing unit (CPU)), physical and/or virtual, that execute(s) machine code 222.
(40) When debugging by debugger tool 206 is complete, and program code 106 and/or 108 is in its final version, compiler 204 may compile program code 106 and/or 108 to generate machine code 222 for the release stage of development. The release version of machine code 222 may be released to be used by users.
(41) Communication interface 208 is configured to transmit program code 106 and/or 108 to remote entities, and/or to communicate other data according to any suitable communication protocol, proprietary or conventional. Further examples of communication interfaces and communication protocols are described in the next section.
(42) Asynchronous code optimizer 104 may be configured in various ways to perform its functions. For instance,
(43) Flowchart 300 begins with step 302. In step 302, program code is transformed into await-relaxed program code. As shown in
(44) In a first illustrative example, code relaxer 402 may parse the following C# program code for asynchronous code statements:
(45) TABLE-US-00001 public class MyProgram { public async SendAllEmails( ) { var emailSender = new EmailSender( ); var recipients = new List<EmailAddress>( ) { new EmailAddress(User1@microsoft.com), new EmailAddress(User2@microsoft.com)| }; var emailContent1 = new MailContent(first mail :)); await emailSender.SendEmail(recipients, emailContent1); var emailContent2 = new MailContent(second mail :)); await emailSender.SendEmail(recipients, emailContent2);
This example program code sends two emails (containing the messages first mail:) and second mail:)) to the email addresses included in the variable recipients (User1@microsoft.com and User2@microsoft.com). In this example, code relaxer 402 may detect the C# keywords of async and await, and may flag the corresponding methods/code statements as being asynchronous code statements, which are repeated below for ease of illustration:
(46) TABLE-US-00002 public async Task SendAllEmails( ) await emailSender.SendEmail(recipients, emailContent1); await emailSender.SendEmail(recipients, emailContent2);
For other programming languages, code relaxer 402 may identify asynchronous code statements using the same or other keywords and/or other identifiers.
(47) In this example, the SendEmail methods send the emails sequentially, the first SendEmail method having to complete (due to the await statement) before the second SendEmail is performed. Thus, if the duration of an email sending is 5 seconds, the total duration of the above program code will be around 10 seconds for the 2 emails.
(48) According to step 302, code relaxer 402 is configured to transform program code into await-relaxed program code. Code relaxer 402 may perform this function in various ways. For instance,
(49) In step 602, any awaits on asynchronous method calls in the program code is/are converted to awaits on task variables. In an embodiment, await-relaxer 502 is configured to convert awaits detected in program code 106 on asynchronous method calls to awaits on task variables (or similar attributes of program code in other programming languages). In this manner, the awaits can be repositioned in the program code to occur later, and thereby defer any awaiting in the program code until later.
(50) In an embodiment, await-relaxer 502 performs step 602 by converting await method calls to awaits on task variables according to the following conversion operation:
(51) await f(x)------>Task<T>y=f(x); await y;
(52) In other words, for a function f(x) preceded by an await keyword (await f(x)), await-relaxer 502 generates a task<T>y statement, by generating a task (e.g., using a var keyword) that assigns the function(x) to the task variable y, and the task variable y is awaited upon rather than the function.
(53) For example, the first await on the SendEmail method shown above is repeated below: await emailSender. SendEmail(recipients, emailContent1);
This await on a method may be converted by await-relaxer 502 to: var mail1=emailSender.SendEmail(recipients, emailContent1); await mail1;
where function f(x) is emailSender.SendEmail(recipients, emailContent1); task variable y is mail1, and task<T> is established by the C# keyword var.
The second await on the SendEmail method shown above may similarly be converted to: var mail2=emailSender.SendEmail(recipients, emailContent2); await mail2;
(54) In this manner, with reference to
(55) In an embodiment, code relaxer 402 may use loop-relaxer 504 to loop-relax program code 414. Note that such loop-relaxing may be performed by loop-relaxer 504 during step 302 of flowchart 300, or may instead be performed later (e.g., during step 306 when a dependency graph is generated). In embodiments where loop-relaxing is performed, code relaxer 402 may operate according to
(56) Loop relaxer 504 performs loop relaxing of program code to avoid having program code loops that include await statements, which result in multiple sequential awaits to be performed, slowing down program code execution.
(57) In a second illustrative example of code relaxing, where loop relaxing is performed, code relaxer 402 may parse the following C# program code for asynchronous code statements:
(58) TABLE-US-00003 public class EmailSender { private IEmailClient m_client; public async Task SendEmail( |IEnumerable<EmailAddress> recipients, MailContent content) { foreach (var recipient in recipients) { await m_client.SendEmail(recipient, content); } }
This program code is an example of the SendEmail method present in the first example program code further above. This second example of program code obtains a collection of recipients and sends email (containing content) to each of them. As shown in this second example, because the developer included the await keyword inside the foreach statement, which identifies a loop, the program code sends the email to each recipient, one at a time, waiting for each email sending to complete before moving onto the next email in the next loop iteration, which can be very time consuming. For instance, if the duration of an email sending is 2 seconds, the total duration of the above program code will be the number of recipients multiplied by 2 seconds.
(59) According to step 702, code relaxer 402 is configured to transform program code into await-relaxed and loop-relaxed program code, with the loop-relaxing performed by loop-relaxer 504. Loop-relaxer 504 may loop-relax program code in various ways, including by operating according to
(60) In step 802, the program code is loop-relaxed by extracting each loop in the program code to a method. In an embodiment, loop-relaxer 504 is configured to loop-relax awaits detected to be included in loops by extracting the loops to methods. In this manner, an await is not conducted during each loop of the loop code.
(61) In particular, to extract a loop to a method, loop-relaxer 504 is configured to analyze dependencies between iterations of the loop to determine whether they are independent. A list/collection of tasks is inserted into the program code prior to the start of the loop, each task in the loop is added to this collection, and after the loop statement completes all loop iterations, an await is performed on all of the collected tasks, such as by a Task.WhenAll keyword (C#) or similar keyword/function.
(62) For example, the foreach loop code portion of the second example program code shown above is repeated below:
(63) TABLE-US-00004 foreach (var recipient in recipients) { await m_client.SendEmail(recipient, content); }
In this example, await-relaxer 502 may first await-relax the await code statement by transforming the await statement to an await on a task variable:
(64) TABLE-US-00005 foreach (var recipient in recipients) { Task task = m_client.SendEmail(recipient, content); await task; }
Then, loop-relaxer 504 extracts the await from the loop as follow
(65) TABLE-US-00006 var tasks = new List<Task>( ); foreach (var recipient in recipients) { tasks.Add(m_client.SendEmail(recipient, content)); } await Task.WhenAll(tasks);
In particular, loop-relaxer 504 extracts the await from the loop by creating a task collection tasks outside the loop, by modifying the task code statement inside the loop with the Add keyword so that the tasks occurring within the loop are added to the collection, and by pulling the await on task (await task;) outside the loop, and converting the await with the Task.WhenAll keyword to an await on all of the tasks of the collection, only completing when all tasks have completed. All of the tasks can be initiated inside the loop without awaiting on each one individually, instead awaiting on the entire collection of tasks outside the loop.
(66) In this manner, with reference to
(67) Note that step 302 of flowchart 300 is optional. In some embodiments, neither await-relaxing nor loop-relaxing of program code are performed, and instead, step 302 is skipped (or is not present) and step 304 of flowchart 300 is performed on program code that is not await-relaxed (and not loop-relaxed). In such an embodiment, code relaxer 402 of
(68) Referring back to flowchart 300 of
(69) First syntax tree 416 generated by code-to-syntax tree converter 404 indicates all of the nodes and interrelationships determined for await-relaxed program code 414.
(70) In step 306 of flowchart 300, a dependency graph is generated from the first syntax tree with each node of the dependency graph corresponding to a code statement and having an assigned weight. In embodiment, dependency graph generator 406 receives first syntax tree 416, and is configured to generate a dependency graph 418 based on first syntax tree 416. In an embodiment, dependency graph 418 is a directed graph of the components of the syntax tree, meaning that dependency graph 418 has nodes and edges, with each node corresponding to a code statement, and each edge directed from one node to another node. Dependency graph generator 406 assigns weights to the nodes of the dependency graph. In an embodiment, dependency graph 418 may be acyclic, such that there is no way to start at a node and loop back to that node again.
(71) Dependency graph generator 406 may be configured to generate dependency graph 418 in various ways. For instance,
(72) In step 1002, a dependency graph is generated by following on variables resulting from each code statement of the first syntax tree. In an embodiment, variable follower 902 is configured to generate an unweighted dependency graph 906 based on first syntax tree 416 by setting each code statement as a node, and following on variables resulting from each code statement (node) of first syntax tree 416. The direction of followed variable from node-to-node provides the direction of the edge between those nodes. Unweighted dependency graph 906 indicates the nodes for each code statement, the edges between nodes, and the directions of the edges.
(73) In step 1004, weights are assigned to the nodes of the dependency graph. In an embodiment, weight assigner 904 receives unweighted dependency graph 906 and assigns a weight to each node of unweighted dependency graph 906 to generate dependency graph 418 (weighted). The weights may have any suitable values, depending on the particular implementation, and may be assigned based on various factors, including the type of operation (e.g., asynchronous or synchronous) performed by the node.
(74) For instance, weight assigner 904 may operate according to
(75) In step 1102, a first weight is assigned to nodes of the dependency graph corresponding to code statements that start asynchronous operations. In an embodiment, weight assigner 904 parses unweighted dependency graph 906 to determine any code statements that begin asynchronous operations. For example, weight assigner 904 may parse unweighted dependency graph 906 for code statements where task variables are assigned to begin an asynchronous operation (which ends in the code with an await keyword). With respect to the first example program code described above, after await-relaxing, the following two code statements assign task variables:
(76) TABLE-US-00007 var mail1 = emailSender.SendEmail(recipients, emailContent1); var mail2 = emailSender.SendEmail(recipients, emailContent2);
Thus, in this first example program code, these two code statements may each be assigned the first weight value by weight assigner 904. In an embodiment, weight assigner 904 may assign a weight of 0 to code statements that start an asynchronous operation, though in other embodiments, any other weight value may be assigned for such an operation.
(77) In step 1104, a second weight is assigned to nodes of the dependency graph corresponding to code statements that await. In an embodiment, weight assigner 904 parses unweighted dependency graph 906 to determine any code statements that correspond to code statements that await. For example, weight assigner 904 may parse unweighted dependency graph 906 for code statements where an await keyword (e.g., in C#, etc.) or analogous keyword is used. With respect to the first example program code described above, after await-relaxing, the following two code statements await (e.g., contain the await keyword):
(78) await mail1;
(79) await mail2;
(80) Thus, in this first example program code, these two code statements may each be assigned the second weight value by weight assigner 904. In an embodiment, weight assigner 904 may assign a weight of 2 to code statements that await, though in other embodiments, any other weight value may be assigned for such an operation.
(81) In step 1106, a third weight is assigned to nodes of the dependency graph not assigned the first weight and not assigned the second weight. In an embodiment, weight assigner 904 parses unweighted dependency graph 906 to determine any code statements that do not start an asynchronous operation and do not await. For example, weight assigner 904 may parse unweighted dependency graph 906 for code statements where no task variables are assigned and no await keywords are used, or weight assigner 904 may merely assign the third weight to any code statements that were not assigned the first or second weights after steps 1102 and 1104. With respect to the first example program code described above, after await-relaxing, the following code statements were not assigned the first or second weights:
(82) TABLE-US-00008 public class MyProgram { public async Task SendAllEmails( ) { var emailSender = new EmailSender( ); var recipients = new List<EmailAddress>( ) { new EmailAddress(User1@microsoft.com), new EmailAddress(User2@microsoft.com) }; var emailContent1 = new MailContent(first mail :)); var emailContent2 = new MailContent(second mail :));
Thus, in this first example program code, these code statements may each be assigned the third weight value by weight assigner 904. In an embodiment, weight assigner 904 may assign a weight of 1 to code statements that neither start asynchronous operations nor await, though in other embodiments, any other weight value may be assigned for such an operation.
(83) In the example of assigning weight values 0-2, the lowest value weight is given to code statements that start asynchronous operations, the highest value weight is given to code statements that await, and the middle value weight is given to code statements that are neither. In this manner, code statements that start asynchronous operations may be prioritized to appear earlier in code, while code statements that await may be positioned later in code.
(84) As described above, dependency graph generator 406 generates dependency graph 418 to indicate nodes corresponding to code statements of first syntax tree 416, directed edges between the nodes that indicate directions of variable flows between nodes, and weights for the nodes.
(85) Note that in the embodiment of
(86) Referring back to
(87) A topological sort or topological ordering performed by topological sorter 408 of a directed graph, such as dependency graph 418, is a linear ordering of its nodes such that for every directed edge uv from node u to node v, u comes before v in the ordering. For instance, the nodes of dependency graph 418 represent code statements to be performed, and the edges represent constraints such that one code statement must be performed before another, providing a valid sequence for the tasks. Any suitable topological sorting algorithm, proprietary or known to persons skilled in the relevant art(s), may be implemented by topological sorter 408. The topological sorting may be implemented using Kahn's algorithm (choosing vertices in the same order as the eventual topological sort), modified-DFS (Depth first search) (looping through each node of dependency graph 418, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since the beginning of the topological sort or the node has no outgoing edges (i.e. a leaf node)), shortest path through a weighted directed acyclic graph, recursion, known scheduling algorithms, and/or any other suitable technique.
(88) In an embodiment, topological sorter 408 takes the weights applied to the nodes of dependency graph 418 during the sorting, ordering lower valued weights earlier and higher value weights later where possible. For instance, with respect to the above example of assigning weight values 0-2, code statements that start asynchronous operations (0 weight) are prioritized to occur earliest, code statements that await (2 weight) are ordered to occur latest where possible, and code statements that are neither of these (1 weight) are neutral. In this manner, the code statements that start asynchronous operations are executed early to give maximal time to complete, and the code statements that await are executed as late as possible to reduce as much as possible the time spent awaiting.
(89) As described above, topological sorter 408 generates sorted dependency graph 420 to indicate a re-ordering (sorting) of the nodes (relative to dependency graph 418) corresponding to code statements of first syntax tree 416, and directed edges between the nodes that indicate directions of variable flows between nodes. Sorted dependency graph 420 represents a sequence of operations (code statements) that naturally can be converted back into a program code (by passing through syntax tree, as in step 310 of flowchart 300).
(90) Referring back to
(91) Accordingly, second syntax tree 422 generated by graph-to-syntax tree converter 410 is a restructuring of sorted dependency graph 420, where the code statement nodes of sorted dependency graph 420 are each converted to one or more code constructs that are each assigned a node, and each node interconnected by branches with other code construct nodes.
(92) In step 312, the second syntax tree is converted into refactored program code. In embodiment, c receives second syntax tree 422, and is configured to generate refactored program code 424 based thereon. Accordingly, syntax tree-to-code converter 412 performs the opposite operation to code-to-syntax tree converter 404. In an embodiment, refactored program code 424 is program code that is logically equivalent to program code 106, but is configured to operate more efficiently with respect to asynchronous code operations.
(93) In particular, refactored program code 424 is an example of refactored program code 108 described above (
(94) Note that step 312 is not performed in all embodiments. In some embodiments, user interface 212 of
(95) With respect to the first illustrative example program code described above, asynchronous code optimizer 104 may generate the following refactored program code:
(96) TABLE-US-00009 public class MyProgram { public async Task SendAllEmails( ) { var emailSender = new EmailSender( ); var recipients = new List<EmailAddress>( ) { new EmailAddress(User1@microsoft.com), new EmailAddress(User2@microsoft.com)| }; var emailContent1 = new MailContent(first mail :)); var mail1 = emailSender.SendEmail(recipients, emailContent1); var emailContent2 = new MailContent(second mail :)); var mail2 = emailSender.SendEmail(recipients, emailContent2); await mail1; await mail2; } }
In this example, as described above with respect to step 302, await relaxer 502 generated task and await code statements to replace both of the original await code statements. Steps 304 and 306 converted the program code to a dependency graph. Additionally, in step 306, weights were assigned to the nodes of the dependency graph, including weights of 0 applied to the task statements (var mail1 and var mail2) and weights of 2 applied to the await statements (await mail1 and await mail2). In step 308, topological sorter 408 sorted the dependency graph, and steps 310 and 312 converted the sorted dependency graph to refactored program code. Due to the sorting of step 308, the two await statements, await mail1 and await mail2 were relocated to the program code end, delaying their execution as much as possible to avoid unnecessary awaiting.
(97) With respect to the second illustrative example program code described above, asynchronous code optimizer 104 may generate the following refactored program code:
(98) TABLE-US-00010 public class EmailSender { private IEmailClient m_client; public async Task SendEmail( |IEnumerable<EmailAddress> recipients, MailContent content) { var tasks = new List<Task>( ); foreach (var recipient in recipients) { tasks.Add(m_client.SendEmail(recipient, content)); } await Task.WhenAll(tasks); } }
In this example, as described above with respect to step 302, await relaxer 502 generated a task and await code statement to replace the original await code statement. Furthermore, according to step 802 (
(99) The optimizations of the first and second illustrative examples of program code described above are summarized and re-detailed with respect to
(100) With respect to the first example program code,
(101)
(102)
(103) Although not illustrated in
(104) With respect to the second example program code,
(105)
(106) At this point or other, loop relaxer 504 may operate on code statement nodes 1502-1510 to loop-relax the code loop present there, as determined by loop relaxer 504 by the foreach statement (represented by node 1504), and by detecting the await keyword within the loop (represented by node 1510). In this example (as shown in code above), loop-relaxer 504 extracts the loop to a method by creating a task collection tasks outside the loop, by modifying the task code statement inside the loop with the Add keyword so that the tasks occurring within the loop are added to the collection, by pulling the await on task (await task;) outside the loop, and converting the await with the Task.WhenAll keyword to an await on all of the tasks of the collection, only completing when all tasks have completed.
(107)
(108) Although not illustrated in
III. Example Mobile and Stationary Device Embodiments
(109) Computing device 102, asynchronous code optimizer 104, compiler 204, development application 200, source code editor 202, compiler 204, debugger tool 206, code relaxer 402, code-to-syntax tree converter 404, dependency graph generator 406, topological sorter 408, graph-to-syntax tree converter 410, syntax tree-to-code converter 412, await-relaxer 502, loop-relaxer 504, variable follower 902, weight assigner 904, flowchart 300, step 602, step 702, step 802, flowchart 1000, and flowchart 1100 may be implemented in hardware, or hardware combined with software and/or firmware. For example, asynchronous code optimizer 104, compiler 204, development application 200, source code editor 202, compiler 204, debugger tool 206, code relaxer 402, code-to-syntax tree converter 404, dependency graph generator 406, topological sorter 408, graph-to-syntax tree converter 410, syntax tree-to-code converter 412, await-relaxer 502, loop-relaxer 504, variable follower 902, weight assigner 904, flowchart 300, step 602, step 702, step 802, flowchart 1000, and/or flowchart 1100 may be implemented as computer program code/instructions configured to be executed in one or more processors and stored in a computer readable storage medium. Alternatively, computing device 102, asynchronous code optimizer 104, compiler 204, development application 200, source code editor 202, compiler 204, debugger tool 206, code relaxer 402, code-to-syntax tree converter 404, dependency graph generator 406, topological sorter 408, graph-to-syntax tree converter 410, syntax tree-to-code converter 412, await-relaxer 502, loop-relaxer 504, variable follower 902, weight assigner 904, flowchart 300, step 602, step 702, step 802, flowchart 1000, and/or flowchart 1100 may be implemented as hardware logic/electrical circuitry.
(110) For instance, in an embodiment, one or more, in any combination, of asynchronous code optimizer 104, compiler 204, development application 200, source code editor 202, compiler 204, debugger tool 206, code relaxer 402, code-to-syntax tree converter 404, dependency graph generator 406, topological sorter 408, graph-to-syntax tree converter 410, syntax tree-to-code converter 412, await-relaxer 502, loop-relaxer 504, variable follower 902, weight assigner 904, flowchart 300, step 602, step 702, step 802, flowchart 1000, and/or flowchart 1100 may be implemented together in a SoC. The SoC may include an integrated circuit chip that includes one or more of a processor (e.g., a central processing unit (CPU), microcontroller, microprocessor, digital signal processor (DSP), etc.), memory, one or more communication interfaces, and/or further circuits, and may optionally execute received program code and/or include embedded firmware to perform functions.
(111)
(112) As shown in
(113) Computing device 1800 also has one or more of the following drives: a hard disk drive 1814 for reading from and writing to a hard disk, a magnetic disk drive 1816 for reading from or writing to a removable magnetic disk 1818, and an optical disk drive 1820 for reading from or writing to a removable optical disk 1822 such as a CD ROM, DVD ROM, or other optical media. Hard disk drive 1814, magnetic disk drive 1816, and optical disk drive 1820 are connected to bus 1806 by a hard disk drive interface 1824, a magnetic disk drive interface 1826, and an optical drive interface 1828, respectively. The drives and their associated computer-readable media provide nonvolatile storage of computer-readable instructions, data structures, program modules and other data for the computer. Although a hard disk, a removable magnetic disk and a removable optical disk are described, other types of hardware-based computer-readable storage media can be used to store data, such as flash memory cards, digital video disks, RAMs, ROMs, and other hardware storage media.
(114) A number of program modules may be stored on the hard disk, magnetic disk, optical disk, ROM, or RAM. These programs include operating system 1830, one or more application programs 1832, other programs 1834, and program data 1836. Application programs 1832 or other programs 1834 may include, for example, computer program logic (e.g., computer program code or instructions) for implementing asynchronous code optimizer 104, compiler 204, development application 200, source code editor 202, compiler 204, debugger tool 206, code relaxer 402, code-to-syntax tree converter 404, dependency graph generator 406, topological sorter 408, graph-to-syntax tree converter 410, syntax tree-to-code converter 412, await-relaxer 502, loop-relaxer 504, variable follower 902, weight assigner 904, flowchart 300, step 602, step 702, step 802, flowchart 1000, and/or flowchart 1100 (including any suitable step of flowcharts 300, 1000, 1100), and/or further embodiments described herein.
(115) A user may enter commands and information into the computing device 1800 through input devices such as keyboard 1838 and pointing device 1840. Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, a touch screen and/or touch pad, a voice recognition system to receive voice input, a gesture recognition system to receive gesture input, or the like. These and other input devices are often connected to processor circuit 1802 through a serial port interface 1842 that is coupled to bus 1806, but may be connected by other interfaces, such as a parallel port, game port, or a universal serial bus (USB).
(116) A display screen 1844 is also connected to bus 1806 via an interface, such as a video adapter 1846. Display screen 1844 may be external to, or incorporated in computing device 1800. Display screen 1844 may display information, as well as being a user interface for receiving user commands and/or other information (e.g., by touch, finger gestures, virtual keyboard, etc.). In addition to display screen 1844, computing device 1800 may include other peripheral output devices (not shown) such as speakers and printers.
(117) Computing device 1800 is connected to a network 1848 (e.g., the Internet) through an adaptor or network interface 1850, a modem 1852, or other means for establishing communications over the network. Modem 1852, which may be internal or external, may be connected to bus 1806 via serial port interface 1842, as shown in
(118) As used herein, the terms computer program medium, computer-readable medium, and computer-readable storage medium are used to refer to physical hardware media such as the hard disk associated with hard disk drive 1814, removable magnetic disk 1818, removable optical disk 1822, other physical hardware media such as RAMs, ROMs, flash memory cards, digital video disks, zip disks, MEMs, nanotechnology-based storage devices, and further types of physical/tangible hardware storage media (including memory 1820 of
(119) As noted above, computer programs and modules (including application programs 1832 and other programs 1834) may be stored on the hard disk, magnetic disk, optical disk, ROM, RAM, or other hardware storage medium. Such computer programs may also be received via network interface 1850, serial port interface 1842, or any other interface type. Such computer programs, when executed or loaded by an application, enable computing device 1800 to implement features of embodiments discussed herein. Accordingly, such computer programs represent controllers of the computing device 1800.
(120) Embodiments are also directed to computer program products comprising computer code or instructions stored on any computer-readable medium. Such computer program products include hard disk drives, optical disk drives, memory device packages, portable memory sticks, memory cards, and other types of physical storage hardware.
IV. Example Embodiments
(121) In an embodiment, a method for transforming asynchronous code into more efficient, logically equivalent asynchronous code comprises: converting program code into a first syntax tree; generating a dependency graph from the first syntax tree with each node of the dependency graph corresponding to a code statement and having an assigned weight; performing weighted topological sorting of the dependency graph to generate a sorted dependency graph; and generating a second syntax tree from the sorted dependency graph.
(122) In an embodiment, the converting program code into a first syntax tree comprises: transforming the program code into await-relaxed program code; and converting the await-relaxed program code into the first syntax tree.
(123) In an embodiment, the transforming the program code into await-relaxed program code comprises: converting any awaits on asynchronous method calls in the program code to awaits on task variables.
(124) In an embodiment, the converting program code into a first syntax tree comprises: transforming the program code into loop-relaxed program code; and converting the loop-relaxed program code into the first syntax tree.
(125) In an embodiment, the generating a dependency graph from the first syntax tree with each node of the dependency graph corresponding to a code statement and having an assigned weight comprises: generating a dependency graph by following on variables resulting from each code statement of the first syntax tree; and assigning weights to the nodes of the dependency graph.
(126) In an embodiment, the assigning weights to the nodes of the dependency graph comprises: assigning a first weight to nodes of the dependency graph corresponding to code statements that start asynchronous operations; assigning a second weight to nodes of the dependency graph corresponding to code statements that await; and assigning a third weight to nodes of the dependency graph not assigned the first weight and not assigned the second weight.
(127) In an embodiment, the method further comprises: converting the second syntax tree into refactored program code.
(128) In another embodiment, a computing device comprises: at least one processor circuit; and at least one memory that stores instructions configured to be executed by the at least one processor circuit, the instructions configured to perform operations for transforming asynchronous code into more efficient, logically equivalent asynchronous code, the operations comprising: converting program code into a first syntax tree, generating a dependency graph from the first syntax tree with each node of the dependency graph corresponding to a code statement and having an assigned weight, performing weighted topological sorting of the dependency graph to generate a sorted dependency graph, and generating a second syntax tree from the sorted dependency graph.
(129) In an embodiment, the converting program code into a first syntax tree comprises: transforming the program code into await-relaxed program code; and converting the await-relaxed program code into the first syntax tree.
(130) In an embodiment, the transforming the program code into await-relaxed program code comprises: converting any awaits on asynchronous method calls in the program code to awaits on task variables.
(131) In an embodiment, the converting program code into a first syntax tree comprises: transforming the program code into loop-relaxed program code; and converting the loop-relaxed program code into the first syntax tree.
(132) In an embodiment, the generating a dependency graph from the first syntax tree with each node of the dependency graph corresponding to a code statement and having an assigned weight comprises: generating a dependency graph by following on variables resulting from each code statement of the first syntax tree; and assigning weights to the nodes of the dependency graph.
(133) In an embodiment, the assigning weights to the nodes of the dependency graph comprises: assigning a first weight to nodes of the dependency graph corresponding to code statements that start asynchronous operations; assigning a second weight to nodes of the dependency graph corresponding to code statements that await; and assigning a third weight to nodes of the dependency graph not assigned the first weight and not assigned the second weight.
(134) In an embodiment, where the instructions are further configured to perform operations comprising: converting the second syntax tree into refactored program code.
(135) In another embodiment, a computing device comprises: at least one processor circuit; and at least one memory that stores instructions configured to be executed by the at least one processor circuit, the instructions configured to perform operations for transforming asynchronous code into more efficient, logically equivalent asynchronous code, the instructions comprising: a code-to-syntax tree converter configured to convert program code into a first syntax tree; a dependency graph generator configured to generate a dependency graph from the first syntax tree with each node of the dependency graph corresponding to a code statement and having an assigned weight; a topological sorter configured to perform weighted topological sorting of the dependency graph to generate a sorted dependency graph; a graph-to-syntax tree converter configured to generate a second syntax tree from the sorted dependency graph; and a syntax tree-to-code converter configured to convert the second syntax tree into refactored program code.
(136) In an embodiment, wherein the instructions further comprise: an await relaxer configured transform the program code into await-relaxed program code; and the code-to-syntax tree converter is configured to convert the await-relaxed program code into the first syntax tree.
(137) In an embodiment, the await-relaxer is configured to convert any awaits on asynchronous method calls in the program code to awaits on task variables.
(138) In an embodiment, wherein the instructions further comprise: a loop-relaxer configured to transform the program code into loop-relaxed program code; and the code-to-syntax tree converter is configured to convert the loop-relaxed program code into the first syntax tree
(139) In an embodiment, the dependency graph generator includes: a variable follower configured to generate the dependency graph by following on variables resulting from each code statement of the first syntax tree; and a weight assigner configured to assign weights to the nodes of the dependency graph.
(140) In an embodiment, the weight assigner is configured to: assign a first weight to nodes of the dependency graph corresponding to code statements that start asynchronous operations; assign a second weight to nodes of the dependency graph corresponding to code statements that await; and assign a third weight to nodes of the dependency graph not assigned the first weight and not assigned the second weight.
V. Conclusion
(141) While various embodiments of the present invention have been described above, it should be understood that they have been presented by way of example only, and not limitation. It will be understood by those skilled in the relevant art(s) that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined in the appended claims. Accordingly, the breadth and scope of the present invention should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.