What''s the policy WRT integer overflow in aggregations? From what I
can tell, it''s just silently ignored. Is this the de facto policy?
(I can''t find any mention of it in the dtrace doc nor in the
dtrace-discuss archives.)
For example, /usr/src/uts/common/dtrace/dtrace.c defines this function:
static void
dtrace_aggregate_avg(uint64_t *data, uint64_t nval, uint64_t arg)
{
data[0]++;
data[1] += nval;
}
So we''re storing the count and the total, and we only do the division
later when printing the data. It seems that we just don''t care about
those cases where the total, or even the count, might overflow.
(Admittedly, overflow won''t be a concern in most practical cases.)
The reason I ask is because I''m looking into implementing 6325485
("A
stdev() aggregator would be a nice adjunct to avg()"), and I''m
wondering if I should worry about overflow. My first pass at
implementing this (at least this part of it) looks like this:
static void
dtrace_aggregate_stddev(uint64_t *data, uint64_t nval, uint64_t arg)
{
data[0]++;
data[1] += nval;
data[2] += nval * nval;
}
(Where I''ll be using the "sqrt(avg(x^2) - avg(x)^2)"
approximation to
standard deviation.)
While this solution is fast, the problem is that data[2] faces
overflow much sooner than data[1], especially if you''re looking at
data like time in nanoseconds.
So should I care about overflow in this case, or should I silently
ignore it as in other cases? (Or should the other places be corrected
so that overflow gets reported?)
Thanks,
Chad
Hey Chad,> What''s the policy WRT integer overflow in aggregations? From what I > can tell, it''s just silently ignored. Is this the de facto policy? > (I can''t find any mention of it in the dtrace doc nor in the > dtrace-discuss archives.) > > For example, /usr/src/uts/common/dtrace/dtrace.c defines this function: > > static void > dtrace_aggregate_avg(uint64_t *data, uint64_t nval, uint64_t arg) > { > data[0]++; > data[1] += nval; > } > > So we''re storing the count and the total, and we only do the division > later when printing the data. It seems that we just don''t care about > those cases where the total, or even the count, might overflow. > (Admittedly, overflow won''t be a concern in most practical cases.)That''s right. As you point out, 64-bit overflow is highly unlikely using the traditional aggregating actions.> The reason I ask is because I''m looking into implementing 6325485 ("A > stdev() aggregator would be a nice adjunct to avg()")Excellent! It''s certainly something I''ve been meaning to do for quite some time -- which tells you that (1) I''ve always personally been able to squeak by without needing it and/or (2) it''s harder and/or more tedious than it looks. I think both are true in this case. ;)> , and I''m > wondering if I should worry about overflow. My first pass at > implementing this (at least this part of it) looks like this: > > static void > dtrace_aggregate_stddev(uint64_t *data, uint64_t nval, uint64_t arg) > { > data[0]++; > data[1] += nval; > data[2] += nval * nval; > } > > (Where I''ll be using the "sqrt(avg(x^2) - avg(x)^2)" approximation to > standard deviation.) > > While this solution is fast, the problem is that data[2] faces > overflow much sooner than data[1], especially if you''re looking at > data like time in nanoseconds.Hmmmm...yes. Your two choices are to either modify this code to be able to indicate an illegal operation on overflow (which would not be difficult, but must also not be what we want), or to implement 128-bit multiplication here in terms of two 64-bit quantities. Because you are only doing addition and multiplication, you can easily implement that in O(N) and O(N^2) respectively. (Where N = 64 in this case.) Then in user-land you''ll need to have some more arbitrary-precision arithmetic to multiply again and to subtract. Unfortunately, after the subtraction, it''s unclear to me if you''ll tend to have a number small enough to fit reasonably into the precision of long double. If not, it''s time to learn how to implement an arbitrary-precision square root -- blech. At any rate, this is a good introduction to DTrace implementation, where seemingly simple features are often more complicated than you think they should have to be (have we talked about ustack() helpers recently?). - Bryan -------------------------------------------------------------------------- Bryan Cantrill, Sun Microsystems FishWorks. http://blogs.sun.com/bmc
>>(Where I''ll be using the "sqrt(avg(x^2) - avg(x)^2)" approximation to >>standard deviation.) >> >>While this solution is fast, the problem is that data[2] faces >>overflow much sooner than data[1], especially if you''re looking at >>data like time in nanoseconds. >> > >Hmmmm...yes. Your two choices are to either modify this code to be able >to indicate an illegal operation on overflow (which would not be difficult, >but must also not be what we want), or to implement 128-bit multiplication >here in terms of two 64-bit quantities. Because you are only doing >addition and multiplication, you can easily implement that in O(N) and >O(N^2) respectively. (Where N = 64 in this case.) Then in user-land >you''ll need to have some more arbitrary-precision arithmetic to multiply >again and to subtract. Unfortunately, after the subtraction, it''s unclear >to me if you''ll tend to have a number small enough to fit reasonably into >the precision of long double. If not, it''s time to learn how to implement >an arbitrary-precision square root -- blech. >Apologies for not following up to the list on this one - I completely forgot to. I''m sponsoring this one for Chad and we''ve had discussions about how to achieve this. Fortunately for us, our current position is, essentially, the same as yours :-) . One thing regarding the overflow detection and error generation. I think that we need to do this anyway and fit it into all aggregating functions which are susceptible to overflow. This can be done seperately to the stddev() work that Chad is currently doing though. Chad has prepared a proposal for his stddev() addition which we''ll post to the list shortly for comment. Jon.