Friday, January 18, 2008
The standard deviation aggregating action in DTrace
Woohoo! The standard deviation aggregating action (stddev()) for DTrace will soon be put back into OpenSolaris. This is my first putback for DTrace.
The change to add stddev() itself was actually very simple. First, note that it uses this approximation to standard deviation:
(For anyone who knows enough to complain about this, note this from the proposal I submitted for this:
)
When I was thinking about how to implement this, the natural thing to do was to model it after how avg() was implemented. When I first saw it, I was a bit surprised at how simple the implementation for avg() was (although in retrospect it was obvious, and I had even been thinking to myself that it must be fairly simple.) The code that implements the real meat of the avg() aggregating action (at least in the kernel) is just this (to be found here):
All it's doing is keeping a count and a sum. The average itself is calculated in post-processing. So the implementation for stddev() is really just as simple as this:
i.e., Just keep track of the count and the sum (to calculate avg(x)) and the sum of x^2 (to calculate avg(x^2)). Of course, a problem creeps in here -- if nval is larger than a 32-bit value, we'll blow our 64 bits. (And note that this is technically a problem for the existing implementation of avg(), too, as it could silently overflow its 64 bits. Pretty unlikely, but not impossible. This bug has been filed to correct this.)
What we decided to do to get around the problem was to implement 128-bit arithmetic functions to support this. The obvious question with respect to doing this is why not just use some multi-precision library and be done with it. Doing so would have introduced a dependency between the kernel and this external library, though, and given how easy it is to implement this, it was better to do so.
The change to add stddev() itself was actually very simple. First, note that it uses this approximation to standard deviation:
sqrt(avg(x^2) - avg(x)^2)
(For anyone who knows enough to complain about this, note this from the proposal I submitted for this:
It is recognised that this is an imprecise approximation to
standard deviation, but it is calculable as an aggregation, and
it should be sufficient for most of the purposes to which
DTrace is put.
)
When I was thinking about how to implement this, the natural thing to do was to model it after how avg() was implemented. When I first saw it, I was a bit surprised at how simple the implementation for avg() was (although in retrospect it was obvious, and I had even been thinking to myself that it must be fairly simple.) The code that implements the real meat of the avg() aggregating action (at least in the kernel) is just this (to be found here):
static void
dtrace_aggregate_avg(uint64_t *data, uint64_t nval, uint64_t arg)
{
data[0]++;
data[1] += nval;
}
All it's doing is keeping a count and a sum. The average itself is calculated in post-processing. So the implementation for stddev() is really just as simple as this:
static void
dtrace_aggregate_stddev(uint64_t *data, uint64_t nval, uint64_t arg)
{
data[0]++;
data[1] += nval;
data[2] += nval * nval;
}
i.e., Just keep track of the count and the sum (to calculate avg(x)) and the sum of x^2 (to calculate avg(x^2)). Of course, a problem creeps in here -- if nval is larger than a 32-bit value, we'll blow our 64 bits. (And note that this is technically a problem for the existing implementation of avg(), too, as it could silently overflow its 64 bits. Pretty unlikely, but not impossible. This bug has been filed to correct this.)
What we decided to do to get around the problem was to implement 128-bit arithmetic functions to support this. The obvious question with respect to doing this is why not just use some multi-precision library and be done with it. Doing so would have introduced a dependency between the kernel and this external library, though, and given how easy it is to implement this, it was better to do so.
