System, devices and/or processes for updating call graphs
Inventors
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-12182202-B2
Publication Date
2024-12-31
Expiration Date
Abstract
Example methods, apparatuses, and/or articles of manufacture are disclosed that may be implemented, in whole or in part, using one or more computing devices to: compare first nodes of a first call graph to second nodes of a second call graph based, at least in part, on hash values associated with the first and second nodes to identify one or more of the second nodes that are absent from the first nodes.
Core Innovation
A processor executes fetched executable instructions to synchronize two call graphs representing two previously executed invocations of a computing program. The method compares first signals and states stored in memory that express computed cryptographic hash values labeling nodes of a first call graph with second signals and states stored in memory that express computed cryptographic hash values labeling nodes of a second call graph. The compared cryptographic hash values include a computed cryptographic hash of source code for one or more tasks executed in the first previously executed invocation, and/or an identifier of the source code, and/or one or more arguments of the one or more tasks, and/or one or more results of the one or more tasks, or combinations thereof.
Based on the comparison of the stored cryptographic hash values, the processor incorporates at least a portion of the second plurality of nodes of the second call graph into the first call graph. This at least partially synchronizes the first and second call graphs so that the incorporated nodes express or represent locators or pointers. The locators or pointers enable access to results of the second previously executed invocation via the first call graph.
The described systems further support synchronization by managing which cryptographic-hash-labeled nodes are absent from or present in the first call graph and by incorporating missing nodes into the first call graph. The document also uses cryptographic-hash labeling to determine, by comparison of hash-based signals and states, a subset of execution stages for recomputing part of an execution sequence of a previously executed invocation. The hash values and node labels can be tied to features of tasks and their source code, arguments, and results, including scenarios described for database change/edit ledgers and hashed source-code/data-source provenance.
Claims Coverage
The independent claims are directed to a computer-implemented method performed by a processor to synchronize call graphs using cryptographic-hash-labeled nodes with locators/pointers, a computing device configured to perform the same synchronization, and an article comprising computer-readable instructions to perform the same synchronization. Across these independent claims, the core inventive features include cryptographic hash comparison of node labels between two call graphs and incorporation of nodes from a second call graph into a first call graph so that locators/pointers provide access to results.
Cryptographic hash comparison of call-graph nodes for two previously executed invocations
The processor compares first signals and states stored in memory expressing computed cryptographic hash values labeling a first plurality of nodes of a first call graph to second signals and states stored in the memory expressing computed cryptographic hash values labeling a second plurality of nodes of a second call graph, where the cryptographic hash values comprise a computed cryptographic hash of source code for one or more tasks executed in the first previously executed invocation, and/or an identifier of the source code, and/or one or more arguments of the one or more tasks executed in the first previously executed invocation, and/or one or more results of the one or more tasks executed in the first previously executed invocation, or a combination thereof.
Incorporating nodes from the second call graph into the first call graph using locators or pointers
The processor incorporates at least a portion of the second plurality of nodes of the second call graph into the first call graph based, at least in part, on the comparison of the first signals and states expressing computed cryptographic hash values to the second signals and states expressing computed cryptographic hash values to at least partially synchronize the first and second call graphs, where the incorporated at least a portion of the second plurality of nodes express or represent locators or pointers to enable access to results of the second previously executed invocation via the first call graph.
Non-transitory memory and one or more processors configured to synchronize call graphs with cryptographic hashes
A computing device includes non-transitory memory storage and one or more processors coupled to the non-transitory memory to fetch executable instructions and execute them to compare first and second signals and states expressing computed cryptographic hash values labeling nodes of first and second call graphs for two previously executed invocations, and to incorporate at least a portion of the second plurality of nodes into the first call graph based on the comparison to at least partially synchronize the call graphs, where the incorporated nodes express or represent locators or pointers to enable access to results of the second previously executed invocation via the first call graph.
Computer-readable instructions in an article for synchronizing call graphs using cryptographic hash-labeled nodes
An article comprising a non-transitory storage medium with computer-readable instructions executable by one or more processors to compare first and second signals and states expressing computed cryptographic hash values labeling nodes of first and second call graphs for two previously executed invocations, and to incorporate at least a portion of the second plurality of nodes into the first call graph based on the comparison to at least partially synchronize the call graphs, where the incorporated nodes express or represent locators or pointers to enable access to results of the second previously executed invocation via the first call graph.
Across the independent claims, the claims focus on synchronizing call graphs for two previously executed invocations by comparing cryptographic-hash values that label nodes and incorporating missing portions of a second call graph into a first call graph. The incorporated nodes represent locators or pointers that enable access to results from the second invocation via the first call graph.
Stated Advantages
Enables access to results of the second previously executed invocation via the first call graph.
At least partially synchronizes the first and second call graphs based on cryptographic-hash comparisons.
Documented Applications
Incremental recomputation and reduced recomputation/storage by using hash-based signals and states to determine a subset of execution stages for recomputing part of an execution sequence of a previously executed invocation.
Workflow collaboration in distributed computing environments with local vs distributed (pull/push) collaboration scenarios, where call graphs are synchronized across computing devices.
Interested in licensing this patent?