[parisc] [PATCH] timer_interrupt: Fix "SLOW!" warning on rp3440

[parisc] [PATCH] timer_interrupt: Fix "SLOW!" warning on rp3440

[John David Anglin]

The attached change fixes the "SLOW!" timer_interrupt warning that I
occassionally see on my rp3440 (800 MHz).  We need to avoid using the
expensive div/mul method.  I have seen instances where it takes more
than 0x7000 cycles.

Signed-off-by: John David Anglin  <dave.anglin@nrc-cnrc.gc.ca>

Dave
-- 
J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)

diff --git a/arch/parisc/kernel/time.c b/arch/parisc/kernel/time.c
index 05511cc..63071c4 100644
--- a/arch/parisc/kernel/time.c
+++ b/arch/parisc/kernel/time.c
@@ -76,7 +76,7 @@ irqreturn_t __irq_entry timer_interrupt(int irq, void *dev_id)
 
 	cycles_elapsed = now - next_tick;
 
-	if ((cycles_elapsed >> 6) < cpt) {
+	if ((cycles_elapsed >> 7) < cpt) {
 		/* use "cheap" math (add/subtract) instead
 		 * of the more expensive div/mul method
 		 */

Re: [parisc] [PATCH] timer_interrupt: Fix "SLOW!" warning on rp3440

[James Bottomley]

On Sat, 2011-03-12 at 12:08 -0500, John David Anglin wrote:
> The attached change fixes the "SLOW!" timer_interrupt warning that I
> occassionally see on my rp3440 (800 MHz).  We need to avoid using the
> expensive div/mul method.  I have seen instances where it takes more
> than 0x7000 cycles.

> Signed-off-by: John David Anglin  <dave.anglin@nrc-cnrc.gc.ca>
> 
> Dave

Your change implies that more than 2^6 == 64 ticks (that's over half a
second) can have elapsed between two calls to timer_interrupt().  That
looks like an awfully large lacuna, and is like the cause of whatever
problem you're seeing rather than the use of divide.  Parisc even has
the DS instruction that would seem to make division not so expensive.

How much more expensive is div than mul?  because if it's a lot more, we
can use a logarithmic iteration to do the division.

James

Re: [parisc] [PATCH] timer_interrupt: Fix "SLOW!" warning on rp3440

[John David Anglin]

> 
> On Sat, 2011-03-12 at 12:08 -0500, John David Anglin wrote:
> > The attached change fixes the "SLOW!" timer_interrupt warning that I
> > occassionally see on my rp3440 (800 MHz).  We need to avoid using the
> > expensive div/mul method.  I have seen instances where it takes more
> > than 0x7000 cycles.
> 
> > Signed-off-by: John David Anglin  <dave.anglin@nrc-cnrc.gc.ca>
> > 
> > Dave
> 
> Your change implies that more than 2^6 == 64 ticks (that's over half a
> second) can have elapsed between two calls to timer_interrupt().  That
> looks like an awfully large lacuna, and is like the cause of whatever
> problem you're seeing rather than the use of divide.  Parisc even has
> the DS instruction that would seem to make division not so expensive.

No, it's not ticks.  It's cycles.  One cycle is 1/800000000 of a second
on my rp3440, so another factor of two didn't seem that expensive.  I
think the change is ok even on a 75 MHz machine.

> How much more expensive is div than mul?  because if it's a lot more, we
> can use a logarithmic iteration to do the division.

I agree that there are probably better ways to do the caculation.  I'm
not sure of the exact numbers but div is always significantly more
expensive than multiplication.  The current code probably divides twice.

If one is willing to save a couple fp regs, 32-bit hardware multiplication
is available.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)

Re: [parisc] [PATCH] timer_interrupt: Fix "SLOW!" warning on rp3440

[Grant Grundler]

On Sat, Mar 12, 2011 at 12:08:32PM -0500, John David Anglin wrote:
> The attached change fixes the "SLOW!" timer_interrupt warning that I
> occassionally see on my rp3440 (800 MHz).  We need to avoid using the
> expensive div/mul method.  I have seen instances where it takes more
> than 0x7000 cycles.

Hi Dave,
Maybe the patch should be for this line of code instead?
        if (unlikely(now2 - now > 0x3000))      /* 12K cycles */

ie increase the value slightly?

TBH, I didn't spend alot of time trying to figure out the optimal balance
between the two cases that the proposed patch attempts to adjust.

Also, if the div/mul takes up to 0x7000 cycles, another alternative
is to make the alternative faster.  What I suggested in the else case:
        /* TODO: Reduce this to one fdiv op */

doesn't seem possible with fdiv in one op. My reading of the fdiv
operator suggests it would need another FMUL and FSUB op in order
to get the remainder. Still might be vary fast.

Looking through PA 2.0 arch book, looks like the PA2.0
"Divide Step" (DS) operation (page 7-46) does what I was thinking of.
But that's going to require a sequence of DS instructions that
I don't quite understand at the moment and thus can't say how
fast the worst case for DS might be.

hth,
grant


> Signed-off-by: John David Anglin  <dave.anglin@nrc-cnrc.gc.ca>
> 
> Dave
> -- 
> J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
> National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)
> 
> diff --git a/arch/parisc/kernel/time.c b/arch/parisc/kernel/time.c
> index 05511cc..63071c4 100644
> --- a/arch/parisc/kernel/time.c
> +++ b/arch/parisc/kernel/time.c
> @@ -76,7 +76,7 @@ irqreturn_t __irq_entry timer_interrupt(int irq, void *dev_id)
>  
>  	cycles_elapsed = now - next_tick;
>  
> -	if ((cycles_elapsed >> 6) < cpt) {
> +	if ((cycles_elapsed >> 7) < cpt) {
>  		/* use "cheap" math (add/subtract) instead
>  		 * of the more expensive div/mul method
>  		 */
> --
> To unsubscribe from this list: send the line "unsubscribe linux-parisc" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [parisc] [PATCH] timer_interrupt: Fix "SLOW!" warning on rp3440

[John David Anglin]

> On Sat, Mar 12, 2011 at 12:08:32PM -0500, John David Anglin wrote:
> > The attached change fixes the "SLOW!" timer_interrupt warning that I
> > occasionally see on my rp3440 (800 MHz).  We need to avoid using the
> > expensive div/mul method.  I have seen instances where it takes more
> > than 0x7000 cycles.
> 
> Hi Dave,
> Maybe the patch should be for this line of code instead?
>         if (unlikely(now2 - now > 0x3000))      /* 12K cycles */
> 
> ie increase the value slightly?

I tried that initially.  After bumping it a couple of times, it
seemed like more iterations in the `if' alternative was better as
most instructions only take one cycle.  My sense is that we only
exceed the current limit in rare circumstances.

> TBH, I didn't spend alot of time trying to figure out the optimal balance
> between the two cases that the proposed patch attempts to adjust.
> 
> Also, if the div/mul takes up to 0x7000 cycles, another alternative
> is to make the alternative faster.  What I suggested in the else case:
>         /* TODO: Reduce this to one fdiv op */
> 
> doesn't seem possible with fdiv in one op. My reading of the fdiv
> operator suggests it would need another FMUL and FSUB op in order
> to get the remainder. Still might be vary fast.
> 
> Looking through PA 2.0 arch book, looks like the PA2.0
> "Divide Step" (DS) operation (page 7-46) does what I was thinking of.
> But that's going to require a sequence of DS instructions that
> I don't quite understand at the moment and thus can't say how
> fast the worst case for DS might be.

Currently, I believe that the kernel does integer multiplication
and division using millicode.  If I remember correctly, division
uses the DS instruction.  The situation is worse for 64-bit operations
because HP never released their 64-bit millicode code.  So, gcc does
long division in this case.

I haven't seen any SLOW warnings with the patch I suggested but it
may be a bit inefficient.  I have the sense that the problem occurs
on the rp3440 because it has two dual core cpus.  I have never seen
the warning on machines with a single processor chip.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)

Re: [parisc] [PATCH] timer_interrupt: Fix "SLOW!" warning on rp3440

[Grant Grundler]

On Sun, Mar 13, 2011 at 05:58:37PM -0600, Grant Grundler wrote:
> Also, if the div/mul takes up to 0x7000 cycles, another alternative
> is to make the alternative faster.  What I suggested in the else case:
>         /* TODO: Reduce this to one fdiv op */
> 
> doesn't seem possible with fdiv in one op. My reading of the fdiv
> operator suggests it would need another FMUL and FSUB op in order
> to get the remainder. Still might be vary fast.
> 
> Looking through PA 2.0 arch book, looks like the PA2.0
> "Divide Step" (DS) operation (page 7-46) does what I was thinking of.

Besides spelling "vary" wrong, I wanted to note "ds" is also defined in PA1.1.

> But that's going to require a sequence of DS instructions that
> I don't quite understand at the moment and thus can't say how
> fast the worst case for DS might be.

As I expected, someone already implemented divu using DS in 1992:
    http://www.cs.bham.ac.uk/research/projects/poplog/src/master/C.hppa/src/aarith.s

Essentially the same code is in OpenBSD and also NetBSD:
  http://www.openssh.com/cgi-bin/cvsweb/src/sys/arch/hppa/spmath/divu.S?rev=1.10&content-type=text/x-cvsweb-markup

It's not obvious to me where divU is defined for linux kernel use but
that's probably the right thing to use here. I believe it's part of
"stdlib" and ISTR used by gcc.

cheers,
grant

Re: [parisc] [PATCH] timer_interrupt: Fix "SLOW!" warning on rp3440

[Grant Grundler]

On Sun, Mar 13, 2011 at 09:22:34PM -0400, John David Anglin wrote:
...
> > Hi Dave,
> > Maybe the patch should be for this line of code instead?
> >         if (unlikely(now2 - now > 0x3000))      /* 12K cycles */
> > 
> > ie increase the value slightly?
> 
> I tried that initially.  After bumping it a couple of times, it
> seemed like more iterations in the `if' alternative was better as
> most instructions only take one cycle.  My sense is that we only
> exceed the current limit in rare circumstances.

Ok. If your patch avoids the case, then it's certainly worth entertaining.

> > TBH, I didn't spend alot of time trying to figure out the optimal balance
> > between the two cases that the proposed patch attempts to adjust.
> > 
> > Also, if the div/mul takes up to 0x7000 cycles, another alternative
> > is to make the alternative faster.  What I suggested in the else case:
> >         /* TODO: Reduce this to one fdiv op */
> > 
> > doesn't seem possible with fdiv in one op. My reading of the fdiv
> > operator suggests it would need another FMUL and FSUB op in order
> > to get the remainder. Still might be vary fast.
> > 
> > Looking through PA 2.0 arch book, looks like the PA2.0
> > "Divide Step" (DS) operation (page 7-46) does what I was thinking of.
> > But that's going to require a sequence of DS instructions that
> > I don't quite understand at the moment and thus can't say how
> > fast the worst case for DS might be.
> 
> Currently, I believe that the kernel does integer multiplication
> and division using millicode.  If I remember correctly, division
> uses the DS instruction.  The situation is worse for 64-bit operations
> because HP never released their 64-bit millicode code.  So, gcc does
> long division in this case.

The URL I provided in other reply:
    http://www.cs.bham.ac.uk/research/projects/poplog/src/master/C.hppa/src/aarith.s

implemented 64-bit/32-bit math. Should be easy to integrate.


> I haven't seen any SLOW warnings with the patch I suggested but it
> may be a bit inefficient.  I have the sense that the problem occurs
> on the rp3440 because it has two dual core cpus.  I have never seen
> the warning on machines with a single processor chip.

The dual core might be competing for a shared resource related to FP?
I don't know either. But if your patch avoids the warning, I'd say apply
it until someone else cares enough to integrate the 64-bit divU and
make use of it here.

cheers,
grant

Re: [parisc] [PATCH] timer_interrupt: Fix "SLOW!" warning on rp3440

[John David Anglin]

> The URL I provided in other reply:
>     http://www.cs.bham.ac.uk/research/projects/poplog/src/master/C.hppa/src/aarith.s
> 
> implemented 64-bit/32-bit math. Should be easy to integrate.

I'll take a look.  The milli64.S file we currently have in gcc only has
32-bit divI and divU routines.  It seems the URL has a routine with a 64-bit
dividend.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc-cnrc.gc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6602)