Overhead Compensation

Given the approximations for $\Delta_i$ and $\Delta_e$, we are ready to apply overhead compensation. There are several ways to go about it. One way is to use the formulas above and remove the overhead at the end of the execution. To do so, however, we must determine the variables $N$, $M$, and $L$ for every event. Without going into details, calculating $N$, $M$, and $L$ amounts to maintaining a dynamic call graph for every currently active event as the root of its own call tree. Knowing this allows us to consider a second way that removes inclusive overhead on-the-fly with every event exit. In this case, we need to only determine $m_i$ and $l_i$ values for each $i$th event occurrence ($M=\sum{}{}m_i$ and $L=\sum{}{}l_i$, for $1 \leq i \leq N$). Since we must calculate profile values at event exit, it is reasonable to have these be compensated calculations.

Using compensated inclusive calculations at event exit, we now have a choice for calculating compensated exclusive profile values. Without loss of generality with respect to other performance metrics, consider only execution time. The exclusive time for an event $A$ is the difference between $A$'s inclusive time and the sum of the inclusive times of all of $A$'s direct descendants. Regardless of compensated or uncompensated inclusive times, we have to accummulate the inclusive times of $A$'s direct descendants. However, for uncompensated inclusive times, an additional subtraction at $A$'s exit of $l_i*\delta_e$ is needed to calculate the exclusive profile time for this invocation of $A$. Thus, the scheme we advocate for on-the-fly overhead compensation of exclusive time is to subtract the compensated inclusive times of $A$'s direct descendants (as they exit) from $A$'s running exclusive time, and add $A$'s compensated inclusive time back in when $A$ finally returns.