Re: [PATCH v4 6/8] tracing/histogram: Optimize division by a power of 2

On Tue, 26 Oct 2021 16:39:13 -0700
Kalesh Singh [off-list ref] wrote:

quoted

        // This works best for small divisors
        if (div > max_div) {
                // only do a real division
                return;
        }
        shift = 20;
        mult = ((1 << shift) + div - 1) / div;
        delta = mult * div - (1 << shift);
        if (!delta) {
                /* div is a power of 2 */
                max = -1;
                return;
        }
        max = (1 << shift) / delta;  

I'm still trying to digest the above algorithm. 

mult = (2^20 + div - 1) / div;

The "div - 1" is to round up.

Basically, it's doing:  X / div  = X * (2^20 / div) / 2^20

If div is constant, the 2^20 / div is constant, and the "2^20" is the
same as a shift.

So multiplier is 2^20 / div, and the shift is 20.

But because there's rounding errors it is only accurate up to the
difference of:

  delta = mult * div / 2^20

That is if mult is a power of two, then there would be no rounding
errors, and the delta is zero, making the max infinite:

  max = 2^20 / delta as delta goes to zero.

But doesn't this add 2 extra divisions? What am I missing here?

The above is only done at parsing not during the trace, where we care
about.

quoted

We would of course need to use 64 bit operations (maybe only do this for 64
bit machines). And perhaps even use bigger shift values to get a bigger max.

Then we could do:

        if (val1 < max)
                return (val1 * mult) >> shift;

This is done at the time of recording.

Actually, it would be:

	if (val1 < max)
		return (val1 * mult) >> shift;
	else
		return val1 / div;

-- Steve