On Thu, 2013-04-11 at 08:38 -0700, Linus Torvalds wrote: > So *now*, once we are in the uncommon case, let's start counting bits. > Like this: > > /* We know one of the values has a bit set in the high 32 bits */ > for (;;) { > /* Make sure "stime" is the bigger of stime/rtime */ > if (rtime > stime) { > u64 tmp = stime; stime = rtime; rtime = tmp; > } > > /* Do we need to balance stime/rtime bits? */ > if (stime >> 32) { > if (rtime >> 31) > goto drop_precision; > > /* We can grow rtime and shrink stime and try to make them > both fit */ > rtime <<= 1; > stime >>= 1; > continue; > } > > /* stime/rtime fits in 32 bits, how about total? */ > if (!(total >> 32)) > break; > > drop_precision: > /* We drop from stime, it has more bits than rtime */ > stime >>= 1; > total >>= 1; > } > > The above is totally untested, but each step is pretty damn simple and > fairly cheap. Sure, it's a loop, but it's bounded to 32 (cheap) > iterations, and the normal case is that it's not done at all, or done > only a few times. Right it gets gradually heavier the bigger the numbers get; which is more and more unlikely. > And the advantage is that the end result is always that simple > 32x32/32 case that we started out with as the common case. > > I dunno. Maybe I'm overlooking something, and the above is horrible, > but the above seems reasonably efficient if not optimal, and > *understandable*. I suppose that entirely matters on what one is used to ;-) I had to stare rather hard at it for a little while. But yes, you take it one step further and are willing to ditch rtime bits too and I suppose that's fine. Should work,.. Stanislaw could you stick this into your userspace thingy and verify the numbers are sane enough? -- To unsubscribe from this list: send the line "unsubscribe linux-tip-commits" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html