Code placement using a dynamic call graph

摘要

When a program function is called, if the instructions for that function are not in active memory, a page fault occurs. Resolving a page fault includes a costly process of loading a page of object code instructions, into active memory, including the instructions for the called function. Technology is disclosed to reduce page faults by placing interrelated functions near each other within executable code based on a log of previous function calls. A log of function calls may be from observing the execution of applications over time. Computing devices can compute where to place functions within executable code by: obtaining the function call log; building a call graph based on the function call log; defining multiple node clusters within the call graph; and generating an ordered list of functions by sorting the node clusters. The ordered list of functions can then be provided during linking to determine function placements.

主权项

1. A method performed by a computing device for assigning relative function locations within executable code, the method comprising:
obtaining a function call log comprising identifications of multiple pairs, each pair comprising a called function and a calling function that called the called function; and building using a processor, based on the function call log, a call graph by:
defining a node for each called function and for each calling function in the function call log,
wherein each selected node corresponding to a called function in the call graph is associated with a node weight, andwherein the node weight for each selected node is based on an amount of processing performed for the called function associated with that selected node;defining, for each pair in the call log that is the first call log pair identifying a selected calling function as calling a selected called function, an edge from the node for the selected calling function to the node for the selected called function; andincrementing, for each pair in the call log, an edge weight value associated with the edge from the node for the calling function in that pair to the node for the called function in that pair; defining at least a first cluster and a second cluster different from the first cluster within the call graph by:
merging at least two nodes of the call graph into the first cluster, wherein selection of each specific node of the at least two nodes, other than a single node of the at least two nodes, is based on the function corresponding to that specific node having called the function corresponding to one other of the at least two nodes; andmerging, into at least the second cluster, at least one node of the call graph;wherein no node of the call graph is merged into more than one cluster;wherein nodes are merged into a selected cluster by analyzing each node of the call graph in order of node weight, starting with the highest node weight; and generating an ordered list of functions by sorting the defined node clusters.