In certain embodiments, execution traces for a program definition of an application are accessed. Probability information for components of the program definition is computed based at least in part upon the execution traces. Program definition slices are determined based at least in part upon the probability information. The program definition slices comprises a baseline slice and at least one supplemental slice. The baseline slice is communicated to a client in response to a request for the application. At least one supplemental slice is communicated to the client to allow the patching of the baseline slice with the at least one supplemental slice to recreate at least a portion of the program definition.

BACKGROUND

A website may have a complex interactive web application. The application may be downloaded to a client to run inside of a web browser. In certain situations, while pages and images of the website are downloading, resources to support the application are also downloading. The downloads may compete for limited bandwidth, yielding a delayed startup time for the application and the website.

DESCRIPTION OF EXAMPLE EMBODIMENTS

A website may include a complex interactive web application. The application may be downloaded to a client to run inside of a web browser. In certain situations, while pages and images of the website are downloading, other resources to support the application are also downloading. The downloads may compete for limited bandwidth, which may result in a delayed startup time for the application and the website.

In certain situations, an application may be manually refactored in order to be modularly loaded. Manually refactoring an application may require considerable upfront planning and preparation. Moreover, if the application is changed, more manual refactoring may be needed. Accordingly, manual refactoring may be cumbersome.

Certain embodiments may provide efficient downloading of a web application. In the embodiments, a program definition of the application may be divided into program definition slices. The program definition slices may include a baseline slice and one or more supplemental slices. In some cases, the baseline slice includes mandatory program components, and a supplemental slice includes optional program components. The baseline slice may be communicated to a client in response to a request for the application. The supplemental slices may be delivered after the baseline slice, which may allow for efficient delivery of the application. Downloaded slices may be patched together to recreate at least a portion of the program definition.

Certain embodiments may obtain execution traces to determine the program definition slices. In the embodiments, an instrumented program definition of the program definition may be prepared. The instrumented program definition includes instructions for reporting execution traces and may be communicated to a client to obtain execution traces from the client.

Certain embodiments may determine the program definition slices from probability information obtained from the execution traces. In the embodiments, program definition slices that optimize a feature, such as minimize a penalty, may be selected. In certain cases, a penalty may take into account the costs of downloading program components of slices and/or dependency probabilities that the components might require execution of another component of another slice, such as a slice that might not have been downloaded. The probability may be determined from the execution traces.

FIG. 1illustrates an example of a system that performs usage-based program slicing. In the illustrated example, system10includes a repository20, a computer system22, and clients24(e.g.,24a,b). In certain cases, repository20may store program definitions36of applications. Computer system22may prepare and send an instrumented program definition38to client24ain order to obtain execution traces41of program definition36. Computer system22may then use traces41to divide program definition36into slices42, which may be provided to client24bto efficiently download the application.

Repository20may comprise one or more memories (described in more detail below) and may be a source code repository that stores program definitions36. A program definition36of an application may include instructions for a computer to carry out particular tasks. A program definition36may have any suitable format, for example, structured binary object (such as compiled Java or .Net class) or interpretable source code (such as JavaScript). A program definition36may be retrieved from repository20or production endpoint35. Production endpoint35is described in more detail below.

A program component may be any suitable portion of program definition36, for example, a program module. Examples of program components include a function definition, a class definition, and a module definition. A function definition may be a routine that applies across applications. A class definition may be a template for an object. A module definition may define a component of a program.

Computer system22may include one or more computers (described in more detail below). Computer system22includes an instrumenting compiler30, an instrumented endpoint32, a slicing compiler34, and a production endpoint35. Instrumenting compiler30and/or instrumented endpoint32may be used to obtain execution traces41that indicate if and/or when program components have been executed. In certain embodiments, instrumenting compiler30prepares an instrumented program definition38that instructs a client24ato send execution traces41, and instrumented endpoint32provides instrumented program definition38to client24a.

In certain embodiments, an execution trace41may include a component identifier, timing information, and/or a client identifier. A component identifier identifies a program component, and may be used to identify a component that is executed. A component identifier may be determined from a label that is inserted at a point (such as an entry or exit point) of the component. Timing information indicates the time of a state change, such as the time when a component was executed. In certain embodiments, the timing information indicates an elapsed time between the start of the execution of program definition38to the time when a component was executed. Timing information may be expressed in any suitable manner. For example, the timing information may be given as two timestamps from which the elapsed time can be calculated, such as an initial timestamp of the start of the execution of program definition38and a subsequent timestamp of the time when a component was executed. As another example, the timing information may be given as a stopwatch time that provides the elapsed time. Client identifier identifies client24athat provides execution traces41. Computer system22may use an identifier (such as a client or session identifier) to correlate execution traces41of client24ato a single instance.

Instrumenting compiler30may prepare instrumented program definition38in any suitable manner. In certain embodiments, instrumenting compiler30determines points (such as entry and exit points) of program components where tracing logic39can be inserted. A point may indicate any suitable part of a program component. For example, an entry point may indicate the start of the program component, and an exit point may indicate the end of the program component. In certain embodiments, entry and exit points may represent synchronous transitions (such as a direct function call) and/or asynchronous transitions (such as an asynchronous callback or continuation).

Points may be determined by, for example, parsing program definition36. For example, instrumenting compiler30may parse a JavaScript program definition to find globally named functions and/or anonymous lambda functions defined inline. As another example, instrumenting compiler30may inspect text strings of the program definition36to identify and parse functions that may be dynamically evaluated.

Tracing logic39inserted at a point of a component may initiate reporting of execution of the component when the component is executed. Tracing logic39may include a library function that creates execution trace41. In certain embodiments, tracing logic39for asynchronous transitions may capture the invocation call stack to trace execution paths that are discontinuous in time. The call stack may be captured when the asynchronous callback is established, and the call may be wrapped to restore the call stack prior to resuming execution.

In certain embodiments, instrumenting compiler30may insert labels identifying the program components at the points, which may allow the tracing logic39to report the particular program component that is executed. Any suitable label may be used. For example, the label may be based on a module and/or function name, or may be dynamically generated.

In certain embodiments, instrumenting compiler30may insert a callback routine40into instrumented program definition38. Callback routine40instructs client24ato submit execution traces41to computer system22. For example, an asynchronous callback routine40may execute subsequent to the loading of program definition38. The asynchronous callback routine40may establish an Hypertext Transfer Protocol (HTTP) connection to computer system22. The connection may be used to post the execution traces41back to computer system22.

Callback routine40may report execution traces41back to computer system22in any suitable manner. For example, traces41may be sent after obtaining a certain time interval of traces41. An another example, execution traces41may piggyback existing application messages. Program definition38may wait for the next application call after execution traces41are ready and attach traces41to the application responses.

Instrumented endpoint32delivers instrumented program definition38to client24ato allow client24ato report execution traces41to computer system22, such as to end point32. Instrumented endpoint32may be hosted by a server (such as an HTTP server) to deliver instrumented program definition38to client24a.

Computer system22may store execution traces41as annotations, such as imbedded comments, in the source code file of program definition36or in a separate location such as a database. Computer system22may select certain execution traces41to provide to slicing compiler34. Any suitable selection criteria may be used, for example, the recentness and/or the source code version of traces41.

Slicing compiler34and/or production endpoint35provide program definition slices42to client24bthat allows client24bto recreate at least a portion of program definition36. In certain embodiments, slicing compiler34may slice program definition36to yield program definition slices42, and production endpoint35may provide slices42to client24b.

A program definition slice42may include a subset (such as a proper subset) of the set of components (or modules) of a program. In certain embodiments, a complete set of program definition slices42may include some or all (and in some cases only) the components of program definition36. In certain cases, slices42of a complete set may be pairwise distinct, but not so in other cases. In certain cases, program definition slices42comprises a baseline slice42aand at least one supplemental slice42b. Baseline slice42amay comprise one or more mandatory components, and a supplemental slice42bmay comprise one or more optional components. A mandatory component may be required to be loaded for the application, and an optional component may not be required.

Slicing compiler34may slice program definition36to yield program definition slices42in any suitable manner. In certain embodiments, slicing compiler34may select program definition slices42that optimize a feature, such as minimize a penalty. In certain cases, a penalty may take into account costs of downloading program components of slices42and/or dependency probabilities that execution of the components leads to execution of another component in another slice42, such as a slice42that might not have been downloaded. In certain embodiments, slicing compiler34may determine the cost from the size of the component and the dependency probability from execution traces41.

In certain embodiments, slicing compiler34may use probability information comprising size information and dependency information. The size information for a component may indicate the size of the component (“component size”), expressed in units of digital information, such as bits of bytes (for example, kilobytes (KB). The dependency information for a component may indicate the probability that execution of a first component leads to execution of a second component, which may be determined from execution traces41. The probability may be for a particular time interval, for example, the probability that the second component is executed within a time interval starting from execution of program definition36. Any suitable time interval may be used. The time interval may be selected according to the total time it takes to download program definition36, for example, an interval with a value in any of the following ranges 1 to 2, 2 to 3, 3 to 4, or greater than 4 seconds.

The probability information may be expressed in any suitable manner. For example, the probability information may be expressed as a probability graph that comprises nodes and edges. The nodes may represent the components and may have a value indicating the size of the components. An edge from a first node to a second node may represent the probability of going from the first node to the second node. The edge may have an edge weight that indicates the probability that the second node is reached from the first node. A probability graph is discussed in more detail with reference toFIGS. 5A through 5C.

Program definition slices42may be determined in any suitable manner from a probability graph. In certain embodiments, slices42may be determined by optimizing a weighted sum of the dependency information and the size information. An example of optimizing a weighted sum is discussed in more detail with reference toFIGS. 5A through 5C.

Slicing compiler34may prepare slices42to allow client24bto patch slices42. In certain embodiments, a slice42may include a function stub for a function definition of another slice42. For example, a function stub may be a function pointer pointing to the location of the program loader with the requested function. The function stub may invoke the program loader, which patches the function definition of the supplemental slice42binto the slice42with the function stub. In certain embodiments, the program loader requests the slice42containing the function definition. Any suitable request may be used, for example, an asynchronous HTTP request, which allows other portions of the program to continue execution, or asynchronous HTTP request, which blocks execution until the supplemental slice42bhas loaded. The program loader extracts the function definition from slice42and creates an invocable function in memory. The program loader then assigns the function pointer of the function stub to point to the function stored in memory. The program loader may invoke the function pointer with the same call stack and parameters used with the function stub.

Production endpoint35may provide slices42to client24bin any suitable manner. In certain embodiments, production endpoint35may communicate baseline slice42ato client24bin response to a request for the application or other request from client24b. Production endpoint35may communicate a supplemental slice42bin response to the operation of a program loader of a baseline slice42aor independent of any request for slice42b. In certain embodiments, a second slice42may be downloaded before or after a first slice42has completed downloading. For example, if there is available bandwidth a second slice42may be downloaded before a first slice42has finished. Production endpoint35may be hosted by a server (such as an HTTP server) to deliver slices42to client24b.

A client24may include one or more computers. Clients24may include one or more reporting clients24aand/or one or more receiving clients24b. A reporting client24areports execution traces41to computer system22, and a receiving client24breceives program definition slices42from computer system22. A reporting client24amay be the same as or different from a receiving client24b.

FIG. 2illustrates another example of a system40that performs usage-based program slicing. In the illustrated example, system40includes instrumented endpoint32, production endpoint35, client24, and instrumentation proxy54, and a router52.

Router52uses a routing configuration to direct traffic between endpoints32and35. For example, the routing configuration may instruct router52to direct X percent of traffic to instrumented endpoint32and Y percent of traffic to production endpoint35. As another example, the routing configuration may direct traffic to a particular endpoint32or35with respect to geographic location of client24, time interval since the last sample execution path, identity of the user, or other factors. In other embodiments, instrumented endpoint32may be accessed in a different manner than production endpoint35. For example, instrumented endpoint32may receive requests at a different URL than that of production endpoint35.

In certain embodiments, production endpoint35may be used to obtain program source code rather than using a repository20. Instrumenting compiler30may be implemented as a proxy server54that retrieves source code through production endpoint35. Instrumentation proxy54may then transform the program definition to the instrumented program definition as discussed. In the embodiments, original source code from a repository20is not used, and system40may be used to analyze a program definition of a third-party website.

FIG. 3illustrates an example of a method for preparing an instrumented program definition. The method may be performed by one or more components of computer system22, for example, instrumenting compiler30and/or instrumented endpoint32.

The method begins at step110, where the program definition is retrieved. The program definition may be retrieved from repository20or from production endpoint35. Exit and entry points are determined at step114. The exit and entry points may indicate starting and ending points of components of the program definition, and may be determined by parsing the program definition.

Tracing logic is inserted at the points to yield an instrumented program definition at step118. The tracing logic may be used to initiate traces of program components that have been executed. A callback routine is inserted into the program definition at step120. The callback routine may be used to send the execution traces back to computer system22. The instrumented program definition is provided to client24aat step124to facilitate reporting of execution traces. The instrumented program definition instructs client24ato report execution traces to computer system22. The method then ends.

FIG. 4illustrates an example of a method for determining program definition slices. The method may be performed by one or more components of computer system22, for example, slicing compiler34and/or production endpoint35.

The method begins at step210, where execution traces for a program definition are accessed. The execution traces may indicate if and/or when particular program components of the program definition are executed. Probability information is computed using the execution traces at step214. The probability information may include the size of the component and the dependency probability that execution of one component leads to execution of another component of another slice, such as a slice that might not have been downloaded.

Program definition slices are determined from the probability information at step218. The program definition slices include baseline and one or more supplemental slices. The program definition slices may be determined by solving an optimization problem using the probability information. For example, the penalty of each candidate slice may be calculated using the sizes and the dependency probabilities of the components of the candidate slice. The optimization problem may seek slices that minimize the penalty.

The baseline slice is communicated at220. The baseline slice may include mandatory components that may be required for execution of the program definition A supplemental slice is communicated at step224. A supplemental slice may include optional components that may not be required for execution of the program definition. There may be a next supplemental slice at step228. If there is a next supplemental slice, the method returns to step224to communicate the next supplemental slice. If there is no next supplemental slice, the method ends.

FIGS. 5A through 5Cillustrate an example of a method for optimizing to determine program definition slices.FIG. 5Aillustrates a probability graph250with nodes and edges. The nodes represent program modules (or components) A through D. A node has a node weight that gives the size of the modules, expressed in kilobytes (KB). An edge from a first node (representing a first module) to a second node (representing a second module) represents the probability that execution of the first module leads to execution of the second module. An edge has an edge weight that gives the probability.

Slicing compiler34determines a partitioning scheme that includes sets of modules, which may be used as program definition slices. In the example, a slice P is a set of the modules. In the example, module A is the entry point, and two candidate partitioning schemes with candidate slices are considered: partitioning scheme1, which has a candidate baseline slice P1with modules A, B, and C, and partitioning scheme2, which has a candidate baseline slice P2with modules A, B, and D.

Slicing compiler34may determine the partitioning scheme by solving an optimization problem. An optimization problem involves maximizing or minimizing an objective function. In certain embodiments, slicing compiler34may optimize by minimizing a penalty. In some cases, a penalty may take into account a cost of downloading modules of a slice and/or a dependency probability that the modules require execution of another module in another slice that might not have been downloaded. For example, a penalty for a partitioning scheme may take into account the sizes of the slices of the partitioning scheme (the “slice sizes”) and/or the dependency probabilities of the slices of the partitioning scheme (the “slice dependencies”). A slice size may indicate the size of a slice and may be determined from the sizes of the modules of the slice. A slice dependency may indicate the dependency of a slice on another slice and may be determined from the dependency probabilities of the modules of the slice.

In certain embodiments, a penalty function for a slice may be a mathematical function of the sizes of the nodes in the slice (which represents the slice size) and/or the edge weights of the edges from modules inside of the slice to modules outside of the slice (which represents the slice dependency). In certain cases, the function may be a sum, such as a weighted sum, of the node sizes and edge weights. As an example, a penalty function for a partition P may be expressed as the following equation:

O⁡(P)=∑X∈P⁢ω1*S⁡(X)+∑X∈P,Y∈P_⁢ω2*E⁡(X,Y)
In the example, S(X) is the size of a module or partition X, E(X,Y) is the edge weight from module X to module Y, ω1is the size weight factor, and ω2is the edge weight factor. In the example, ω1equals 1 and ω2equals 1000.

Size weight factor ω1and edge weight factor ω2may be used to normalize the size and edge weight with respect to each other and/or to indicate the relative importance of the size and edge weight with respect to each other. Any suitable weights may be used. In certain embodiments, the weights may be determined according to the rate of downloading components.

In certain embodiments, a penalty function may take into account the cost of downloading a supplemental slice. For example, a penalty function may be expressed as the following equation:

O⁡(P)=∑X∈P⁢ω1*S⁡(X)+∑X∈P,Y∈P_⁢ω2*[E⁡(X,Y)*(Q+S⁡(P_))]
where weight Q indicates the cost of downloading a supplemental slice.

In certain embodiments, a penalty function may take into account that there is no penalty for reusing a module that has already been downloaded. In the embodiments, E′(X,Y) may be a diminished edge weight from module X to module Y that reduces the penalty for reusing a downloaded module Y. Diminished edge weight E′(X,Y) takes into account the probability D(Y) that module Y has not been downloaded, and may be calculated according to the following equation:
E′(X,Y)=E(X,Y)×D(Y)
For example, diminished edge weight E′(C,D) may be 0.018.

In certain embodiments, a partitioning scheme may include more than two slices, such as a baseline slice and two or more supplemental slices. The slices may be determined in any suitable manner. As an example, in a first iteration, optimization may be performed on the modules of the program definition (which may be regarded as an “initial slice”) to yield two slices, such as a baseline slice and a remaining slice. In a second iteration, optimization may be performed on the remaining slice to yield two more slices, such as a first supplemental slice and a next remaining slice. In a third iteration, optimization may be performed on the next remaining slice to yield two more slices, such as a second supplemental slice and a next remaining slice, and so on. The number of iterations may be selected according to the desired number of slices.

As another example, candidate partitioning schemes that each include a predetermined number of three or more slices (such as a baseline slice and two or more supplemental slices) may be optimized. A penalty of a partitioning scheme may be calculated by applying a mathematical function to the penalties of the slices of the scheme. For example, the penalty of the scheme may be the sum (such as the weighted sum) of the penalties of the slices. In certain embodiments, the penalty of a earlier downloaded slice (such as a baseline slice) may be weighted more heavily than the penalty of a later downloaded slice (such as a supplemental slice).

A component (such as a computer) of the systems and apparatuses disclosed herein may include an interface, logic, memory, and/or other suitable element. An interface receives input, sends output, processes the input and/or output, and/or performs other suitable operation. An interface may comprise hardware and/or software.

Logic performs the operations of the component, for example, executes instructions to generate output from input. Logic may include hardware, software, and/or other logic. Logic may be encoded in one or more tangible media and may perform operations when executed by a computer. Certain logic, such as a processor, may manage the operation of a component. Examples of a processor (or processing unit) include one or more computers, one or more microprocessors, one or more applications, and/or other logic.

In particular embodiments, the operations of the embodiments may be performed by one or more computer readable media encoded with a computer program, software, computer executable instructions, and/or instructions capable of being executed by a computer. In particular embodiments, the operations of the embodiments may be performed by one or more computer readable media storing, embodied with, and/or encoded with a computer program and/or having a stored and/or an encoded computer program.

A memory (or memory unit) stores information. A memory may comprise one or more non-transitory, tangible, computer-readable, and/or computer-executable storage media. Examples of memory include computer memory (for example, Random Access Memory (RAM) or Read Only Memory (ROM)), mass storage media (for example, a hard disk), removable storage media (for example, a Compact Disk (CD) or a Digital Video Disk (DVD)), database and/or network storage (for example, a server), and/or other computer-readable medium.

Components of the systems and apparatuses disclosed may be coupled by any suitable communication network. A communication network may comprise all or a portion of one or more of the following: a public switched telephone network (PSTN), a public or private data network, a local area network (LAN), a metropolitan area network (MAN), a wide area network (WAN), a local, regional, or global communication or computer network such as the Internet, a wireline or wireless network, an enterprise intranet, other suitable communication link, or any combination of any of the preceding.