Serge D. Mechveliani | 17 Oct 17:02 2012
Picon

divRem by `-' performance

People,
consider the following contrived program for division with remainder:

----------------------------------------------------------------
qRem :: Int -> Int -> (Int, Int)
qRem m n = if m < 0 || n <= 0 then  error "\nwrong arguments in qRem.\n"
           else                     qRem' 0 m
           where
           qRem' q r = if r < n then (q, r)  else qRem' (succ q) (r - n)

main = putStr $ shows (qRem n 5) "\n"
       where
       e = 25
       n = 2^e
----------------------------------------------------------------

Compilation in  ghc-7.4.1 :  

                ghc --make -O -rtsopts Main
Rinning:        time ./Main  +RTS -K.. -M.. -RTS

For  e = 25,  it takes the minimum of  -K80m -M280m
(on my Linux Debian machine).

Is not this memory eagerness strange?

Regards,
Sergei
Roman Cheplyaka | 17 Oct 17:17 2012

Re: divRem by `-' performance

* Serge D. Mechveliani <mechvel <at> botik.ru> [2012-10-17 19:02:37+0400]
> People,
> consider the following contrived program for division with remainder:
> 
> ----------------------------------------------------------------
> qRem :: Int -> Int -> (Int, Int)
> qRem m n = if m < 0 || n <= 0 then  error "\nwrong arguments in qRem.\n"
>            else                     qRem' 0 m
>            where
>            qRem' q r = if r < n then (q, r)  else qRem' (succ q) (r - n)

You need to force evaluation of 'q' here, otherwise it becomes a growing
chain of 'succ' applications.

E.g.

    qRem' q r = if r < n then (q, r)  else (qRem' $! succ q) (r - n)

Roman
Serge D. Mechveliani | 17 Oct 17:37 2012
Picon

Re: divRem by `-' performance

On Wed, Oct 17, 2012 at 06:17:28PM +0300, Roman Cheplyaka wrote:
> * Serge D. Mechveliani <mechvel <at> botik.ru> [2012-10-17 19:02:37+0400]
> > People,
> > consider the following contrived program for division with remainder:
> > 
> > ----------------------------------------------------------------
> > qRem :: Int -> Int -> (Int, Int)
> > qRem m n = if m < 0 || n <= 0 then  error "\nwrong arguments in qRem.\n"
> >            else                     qRem' 0 m
> >            where
> >            qRem' q r = if r < n then (q, r)  else qRem' (succ q) (r - n)
> 
> You need to force evaluation of 'q' here, otherwise it becomes a growing
> chain of 'succ' applications.
> 
> E.g.
> 
>     qRem' q r = if r < n then (q, r)  else (qRem' $! succ q) (r - n)

This looks as a natural explanation.
But it is generally difficult for me to admit that sometimes it is 
desirable to use strinctess annotation.
I programmed DoCon for 6 years, and it does not have any bit of 
strictness annotation, and I always had an impression that it is all
right with performance.
And now it occurs that setting  $!  in some places may make many parts
of it somewhat 100 times less expensive 
-- ?
Somehow difficult to admit.

(Continue reading)

Roman Cheplyaka | 17 Oct 18:00 2012

Re: divRem by `-' performance

* Serge D. Mechveliani <mechvel <at> botik.ru> [2012-10-17 19:37:38+0400]
> But it is generally difficult for me to admit that sometimes it is 
> desirable to use strinctess annotation.
> I programmed DoCon for 6 years, and it does not have any bit of 
> strictness annotation, and I always had an impression that it is all
> right with performance.

Yeah, I was also surprised that this is news to you :)

> And now it occurs that setting  $!  in some places may make many parts
> of it somewhat 100 times less expensive 
> -- ?
> Somehow difficult to admit.

Laziness is subtle. Sometimes you make an innocent change to a program,
but it changes the time when things are evaluated, and that affects
memory/performance significantly.

In general, you'd rather understand evaluation order in your program if
you want decent performance.

Roman
Serge D. Mechveliani | 18 Oct 11:24 2012
Picon

Re: divRem by `-' performance

On Wed, Oct 17, 2012 at 07:00:38PM +0300, Roman Cheplyaka wrote:
> * Serge D. Mechveliani <mechvel <at> botik.ru> [2012-10-17 19:37:38+0400]
> > But it is generally difficult for me to admit that sometimes it is 
> > desirable to use strinctess annotation.
> > I programmed DoCon for 6 years, and it does not have any bit of 
> > strictness annotation, and I always had an impression that it is all
> > right with performance.
> 
> Yeah, I was also surprised that this is news to you :)
> 
> > And now it occurs that setting  $!  in some places may make many parts
> > of it somewhat 100 times less expensive 
> > -- ?
> > Somehow difficult to admit.
> 
> Laziness is subtle. Sometimes you make an innocent change to a program,
> but it changes the time when things are evaluated, and that affects
> memory/performance significantly.
> 

I was always aware of all these effects.
I deliberately avoided any strictness annotation.
And the whole result has a reasonable performance. 

But then, I forget it, each time, and start to think "everything is all 
right".
This lasts till the next unlucky example, as the above  qRem.
And each time I recall of unneeded laziness.

And concerning this example: I am not even sure now that it worths to
(Continue reading)

Albert Y. C. Lai | 18 Oct 19:54 2012
Picon

Re: divRem by `-' performance

On 12-10-18 05:24 AM, Serge D. Mechveliani wrote:
> And concerning this example: I am not even sure now that it worths to
> setting  $!  there.
> Because I deliberately program  qRem  as returning a pair  (quot, rem),
> and do not program a separate function for  rem.  And to obtain  rem,
> one applies   snd (qRem n m),  and due to laziness,  quot  does not
> spend the cost. I do not know, may be, using $! may damage this style.

snd (quot, rem) does not spend the arithmetic cost of quot, but spends 
the memory cost of quot. Memory cost is not just occupation of memory, 
but also writing of memory and computing of addresses, which is not 
exactly cheaper than arithmetic.
Serge D. Mechveliani | 18 Oct 21:10 2012
Picon

Re: divRem by `-' performance

On Thu, Oct 18, 2012 at 01:54:45PM -0400, Albert Y. C. Lai wrote:
> On 12-10-18 05:24 AM, Serge D. Mechveliani wrote:
>> And concerning this example: I am not even sure now that it worths to
>> setting  $!  there.
>> Because I deliberately program  qRem  as returning a pair  (quot, rem),
>> and do not program a separate function for  rem.  And to obtain  rem,
>> one applies   snd (qRem n m),  and due to laziness,  quot  does not
>> spend the cost. I do not know, may be, using $! may damage this style.
>
> snd (quot, rem) does not spend the arithmetic cost of quot, but spends  
> the memory cost of quot. Memory cost is not just occupation of memory,  
> but also writing of memory and computing of addresses, which is not  
> exactly cheaper than arithmetic.

But in this example of  qRem  the time is almost so as if  quot  was
not computed. 
Probably, the coefficient of this expense is small.

On the other hand, an extra memory occupation also often causes slowing 
down of all the environment program, because this occupation approaches 
garbage collection.

I wonder whether it worths to return some strictness annotations. 

Regards,
Sergei
Albert Y. C. Lai | 18 Oct 22:44 2012
Picon

Re: divRem by `-' performance

On 12-10-18 03:10 PM, Serge D. Mechveliani wrote:
> But in this example of  qRem  the time is almost so as if  quot  was
> not computed.
> Probably, the coefficient of this expense is small.
>
> On the other hand, an extra memory occupation also often causes slowing
> down of all the environment program, because this occupation approaches
> garbage collection.

Use "./Main +RTS -s -RTS" to find out how hard the garbage collector has 
to work. Use "./Main +RTS -M64m -RTS" to find out how much memory is not 
enough. We are speaking of "snd (qRem n 5)", of course.

("64MB ought to be enough for everybody."? :) )

Gmane