Re: [Chicken-users] CHICKEN hang / crash / memoize egg

[Arthur Maciel]

Thanks, Peter! I applied the patch.

I won't have time to create a proper test suite now, but I'll keep your
instructions for the future.

Best wishes,
Arthur

On Fri, Apr 1, 2016 at 3:32 PM, Peter Bex  wrote:

> On Fri, Apr 01, 2016 at 03:28:26PM +0100, Andy Bennett wrote:
> > Hi Peeps!
> >
> > I'm running CHICKEN 4.9.0rc1 and I'm trying out the memoize egg.
> >
> > I saw the tail-call-optimized version of the factorial procedure in the
> > memoize documentation at http://api.call-cc.org/doc/memoize and I've
> > been trying to modify it so that it memoizes intermediate results such
> > that, for example, a call to (fact 10) makes a subsequent call to (fact
> > 9) fast.
> >
> > Sometimes I'll crash immediately and someytimes I have to press some
> > keys when the "#;8>" prompt appears.
> >
> > Is this a known bug in Chicken 4.9.0rc1 or the srfi-69 hash-tables that
> > memoize uses?
>
> There are two problems.  In your code you don't limit the size of the
> memoized hash table, which means it won't ever delete anything from its
> hash tables.
>
> The other problem seems to be in the memoize egg: there, even if you do
> set a limit, the check for the hash table size occurs at precisely the
> wrong place in the recursion.  It checks the size, then calls the
> procedure and when it returns, the result is stored in the hash table.
>
> Let's say we put a limit of 1.  Then we call (memoized-fact 3).
> It will determine (3) doesn't exist yet, and that the cache size is 0.
> Then it will actually call (original-fact 3), which calls memoized-fact
> recursively as (memoized-fact 2).  In the recursion, the cache is still
> empty and there's no entry for (2).  So it calls (original-fact 2) to
> determine the result to store.  This calls (memoized-fact 1), which
> enters with an empty cache and (1) doesn't exist yet.  Then it calls
> (original-fact 1), which returns with 1 immediately.
>
> When it returns, the result is stored in the hash table for args = (1).
> This returns its value to the pending continuation which will
> calculate 2, which is then stored in the cache for (2) and returned to
> the pending continuation which will calculate our final result 6, which
> is stored in the cache for (3) and then finally returned.
>
> After all this, the cache's size is 3 even though we capped it to a
> limit of only 1 item!  Also, the numbers you're storing _are_ really
> large (the final result requires over 59KiB to store the number), and
> because all the intermediate results are retained because the cache
> isn't ever cleared, it's no wonder you're running out of heap size.
>
> The attached patch fixes the problem, as long as you do set a limit,
> using (define memo-fact** (memoize fact** 10)).  In fact, you can set
> a limit of 1 if you want; the outermost recursion step is the one that
> will never be deleted.
>
> A proper test suite should:
>
> a) ensure the procedure is only called as many times as necessary to
>generate new values for uncached values.  Fibonacci would be great
>for measuring this: it should be called n times instead of n^2 times.
> b) ensure that the cache limit is obeyed.  This is trickier to write a
>test for.  Maybe something that is called in a sequence that looks
>like 1, 1, 2, 2, 3, ... n, n, ... 3, 3, 2, 2, 1, 1 would be useful:
>in that case it should be called exactly 2n times if the limit is < n,
>unless I'm wrong.  You'd then have to make a few variants of the
>memoized procedure, with limits around the edge cases n, n-1, n+1
>and check if the original procedure is called 2n times or 4n times.
>
> I'm sure smarter people than myself can come up with a better way to
> test this.
>
> Cheers,
> Peter
>
___
Chicken-users mailing list
Chicken-users@nongnu.org
https://lists.nongnu.org/mailman/listinfo/chicken-users

Re: [Chicken-users] CHICKEN hang / crash / memoize egg

[Peter Bex]

On Fri, Apr 01, 2016 at 03:28:26PM +0100, Andy Bennett wrote:
> Hi Peeps!
> 
> I'm running CHICKEN 4.9.0rc1 and I'm trying out the memoize egg.
> 
> I saw the tail-call-optimized version of the factorial procedure in the
> memoize documentation at http://api.call-cc.org/doc/memoize and I've
> been trying to modify it so that it memoizes intermediate results such
> that, for example, a call to (fact 10) makes a subsequent call to (fact
> 9) fast.
> 
> Sometimes I'll crash immediately and someytimes I have to press some
> keys when the "#;8>" prompt appears.
> 
> Is this a known bug in Chicken 4.9.0rc1 or the srfi-69 hash-tables that
> memoize uses?

There are two problems.  In your code you don't limit the size of the
memoized hash table, which means it won't ever delete anything from its
hash tables.

The other problem seems to be in the memoize egg: there, even if you do
set a limit, the check for the hash table size occurs at precisely the
wrong place in the recursion.  It checks the size, then calls the
procedure and when it returns, the result is stored in the hash table.

Let's say we put a limit of 1.  Then we call (memoized-fact 3).
It will determine (3) doesn't exist yet, and that the cache size is 0.
Then it will actually call (original-fact 3), which calls memoized-fact
recursively as (memoized-fact 2).  In the recursion, the cache is still
empty and there's no entry for (2).  So it calls (original-fact 2) to
determine the result to store.  This calls (memoized-fact 1), which
enters with an empty cache and (1) doesn't exist yet.  Then it calls
(original-fact 1), which returns with 1 immediately.

When it returns, the result is stored in the hash table for args = (1).
This returns its value to the pending continuation which will
calculate 2, which is then stored in the cache for (2) and returned to
the pending continuation which will calculate our final result 6, which
is stored in the cache for (3) and then finally returned.

After all this, the cache's size is 3 even though we capped it to a
limit of only 1 item!  Also, the numbers you're storing _are_ really
large (the final result requires over 59KiB to store the number), and
because all the intermediate results are retained because the cache
isn't ever cleared, it's no wonder you're running out of heap size.

The attached patch fixes the problem, as long as you do set a limit,
using (define memo-fact** (memoize fact** 10)).  In fact, you can set
a limit of 1 if you want; the outermost recursion step is the one that
will never be deleted.

A proper test suite should:

a) ensure the procedure is only called as many times as necessary to
   generate new values for uncached values.  Fibonacci would be great
   for measuring this: it should be called n times instead of n^2 times.
b) ensure that the cache limit is obeyed.  This is trickier to write a
   test for.  Maybe something that is called in a sequence that looks
   like 1, 1, 2, 2, 3, ... n, n, ... 3, 3, 2, 2, 1, 1 would be useful:
   in that case it should be called exactly 2n times if the limit is < n,
   unless I'm wrong.  You'd then have to make a few variants of the
   memoized procedure, with limits around the edge cases n, n-1, n+1
   and check if the original procedure is called 2n times or 4n times.

I'm sure smarter people than myself can come up with a better way to
test this.

Cheers,
Peter
From 6e0077bacabbdc270302e89c9f0f0a12240ae0c3 Mon Sep 17 00:00:00 2001
From: Peter Bex 
Date: Fri, 1 Apr 2016 20:20:12 +0200
Subject: [PATCH] Fix caching bug which caused the limit to be ignored during
 recursion

---
 memoize.scm | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/memoize.scm b/memoize.scm
index 681ca13..8612404 100644
--- a/memoize.scm
+++ b/memoize.scm
@@ -51,11 +51,11 @@
  (lambda args
(let ((results (hash-table-ref/default cache args not-found)))
 	 (cond ((eq? results not-found)
-		;; Avoid a huge cache by deleting random keys if limit is determined. 
-		(and limit (>= (hash-table-size cache) limit) (delete-random-key! cache))
 		(let ((results (call-with-values 
    (lambda () (apply proc args))
    list)))
+		  ;; Avoid a huge cache by deleting random keys if limit is determined.
+		  (and limit (>= (hash-table-size cache) limit) (delete-random-key! cache))
 		  (hash-table-set! cache args results)
 		  (apply values results)))
 	   (else
-- 
2.1.4



signature.asc
Description: Digital signature
___
Chicken-users mailing list
Chicken-users@nongnu.org
https://lists.nongnu.org/mailman/listinfo/chicken-users

Re: [Chicken-users] CHICKEN hang / crash / memoize egg

[Arthur Maciel]

Dear Andy, good to know you are playing with the memoize egg. ATM I don't
have time to look deeper into the problem you pointed out. Sorry for that.
After I finish some personal stuff I'll dig into it.

Cheers,
Arthur
Em 01/04/2016 11:56, "Andy Bennett"  escreveu:

> On 01/04/16 15:28, Andy Bennett wrote:
> > Hi Peeps!
> >
> > I'm running CHICKEN 4.9.0rc1 and I'm trying out the memoize egg.
> >
> > I saw the tail-call-optimized version of the factorial procedure in the
> > memoize documentation at http://api.call-cc.org/doc/memoize and I've
> > been trying to modify it so that it memoizes intermediate results such
> > that, for example, a call to (fact 10) makes a subsequent call to (fact
> > 9) fast.
> >
> > In doing so I've managed to get the interpreter into a loop or crash it
> > entirely.
> >
> >
> > When pasting this into a csi prompt:
> >
> > -
> > (use numbers)
> > (use memoize)
> >
> > (define (fact** x #!optional (self memo-fact**))
> >   (if (= x 0)
> > 1
> > (* x (self (- x 1)
> >
> > (define memo-fact** (memoize fact**))
> >
> > (define x (time (memo-fact**  35710)))
> > (define x (time (memo-fact**  35720)))
> > (define x (time (memo-fact**  35730)))
> > -
> >
> > I get:
> >
> > -
> > $ csi
> >
> > CHICKEN
> > (c) 2008-2014, The Chicken Team
> > (c) 2000-2007, Felix L. Winkelmann
> > Version 4.9.0rc1 (rev 3cf1967)
> > linux-unix-gnu-x86-64 [ 64bit manyargs dload ptables ]
> > compiled 2014-04-17 on hd-t1179cl (Linux)
> >
> > ; loading /home/local/andyjpb/.csirc ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/parley.import.so ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/chicken.import.so ...
> > ; loading
> > /usr/local/chicken-4.9.0/lib/chicken/7/data-structures.import.so ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/extras.import.so ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/ports.import.so ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/posix.import.so ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/srfi-1.import.so ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/srfi-13.import.so ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/srfi-18.import.so ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/stty.import.so ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/srfi-69.import.so ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/foreign.import.so ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/foreigners.import.so
> ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/parley.so ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/stty.so ...
> > #;1> (use numbers)
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/numbers.import.so ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/numbers.so ...
> > #;2> (use memoize)
> > #;2>
> > #;2> (define (fact** x #!optional (self memo-fact**))
> > #;2>   (if (= x 0)
> > #;2> 1
> > #;2> (* x (self (- x 1)
> > #;2>
> > #;2> (define memo-fact** (memoize fact**))
> > #;2>
> > #;2> (define x (time (memo-fact**  35710)))
> > #;2> (define x (time (memo-fact**  35720)))
> > #;2> (define x (time (memo-fact**  35730)))
> > #;2>
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/memoize.import.so ...
> > ; loading /usr/local/chicken-4.9.0/lib/chicken/7/memoize.so ...
> >
> > Note: the following toplevel variables are referenced but unbound:
> >
> >   memo-fact** (in fact**)
> > 2.804s CPU time, 1.064s GC time (major), 81305 mutations, 21/1551 GCs
> > (major/minor)
> > 0s CPU time, 20 mutations
> > 0s CPU time, 20 mutations
> > #;8>
> > [panic] out of memory - heap full while resizing - execution terminated
> >
> > ...more...
> > parley.scm:610: history817818
> > parley.scm:610: history817818
> > parley.scm:603: ##sys#dynamic-wind
> > parley.scm:603: history798799
> > parley.scm:603: history798799
> > parley.scm:603: history798799
> > parley.scm:603: history798799
> > parley.scm:610: ##sys#dynamic-wind
> > parley.scm:610: history817818
> > parley.scm:610: history817818
> > parley.scm:615: get-next-char!
> > parley.scm:579: parley-char-ready?
> > parley.scm:586: append-while-incomplete
> > parley.scm:560: string-null?
> > parley.scm:561: repl-prompt
> > parley.scm:561: g769<--
> > -
> >
> > Sometimes I'll crash immediately and someytimes I have to press some
> > keys when the "#;8>" prompt appears.
> >
> >
> > If I run the above script thusly:
> >
> > -
> > $ csi -s memo-demo.scm
> > -
> >
> > I see
> >
> > -
> > $ csi -s ../memo-demo.scm
> > 2.908s CPU time, 1.164s GC time (major), 75257 mutations, 22/1550 GCs
> > (major/minor)
> > 0s CPU time, 20 mutations
> > -
> >
> > ...and it hangs there (on the last time call) indefinitely using all the
> > CPU. Ctrl-C doesn't terminate it: a call to 'killall csi' does tho'.
> >
> >
> > If you cannot reproduce it then try varying the numbers in the call to
> > memo-fact**.
> >
> >
> >
> > Is this a known bug in 

Re: [Chicken-users] CHICKEN hang / crash / memoize egg

[Andy Bennett]

On 01/04/16 15:28, Andy Bennett wrote:
> Hi Peeps!
> 
> I'm running CHICKEN 4.9.0rc1 and I'm trying out the memoize egg.
> 
> I saw the tail-call-optimized version of the factorial procedure in the
> memoize documentation at http://api.call-cc.org/doc/memoize and I've
> been trying to modify it so that it memoizes intermediate results such
> that, for example, a call to (fact 10) makes a subsequent call to (fact
> 9) fast.
> 
> In doing so I've managed to get the interpreter into a loop or crash it
> entirely.
> 
> 
> When pasting this into a csi prompt:
> 
> -
> (use numbers)
> (use memoize)
> 
> (define (fact** x #!optional (self memo-fact**))
>   (if (= x 0)
> 1
> (* x (self (- x 1)
> 
> (define memo-fact** (memoize fact**))
> 
> (define x (time (memo-fact**  35710)))
> (define x (time (memo-fact**  35720)))
> (define x (time (memo-fact**  35730)))
> -
> 
> I get:
> 
> -
> $ csi
> 
> CHICKEN
> (c) 2008-2014, The Chicken Team
> (c) 2000-2007, Felix L. Winkelmann
> Version 4.9.0rc1 (rev 3cf1967)
> linux-unix-gnu-x86-64 [ 64bit manyargs dload ptables ]
> compiled 2014-04-17 on hd-t1179cl (Linux)
> 
> ; loading /home/local/andyjpb/.csirc ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/parley.import.so ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/chicken.import.so ...
> ; loading
> /usr/local/chicken-4.9.0/lib/chicken/7/data-structures.import.so ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/extras.import.so ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/ports.import.so ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/posix.import.so ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/srfi-1.import.so ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/srfi-13.import.so ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/srfi-18.import.so ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/stty.import.so ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/srfi-69.import.so ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/foreign.import.so ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/foreigners.import.so ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/parley.so ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/stty.so ...
> #;1> (use numbers)
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/numbers.import.so ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/numbers.so ...
> #;2> (use memoize)
> #;2>
> #;2> (define (fact** x #!optional (self memo-fact**))
> #;2>   (if (= x 0)
> #;2> 1
> #;2> (* x (self (- x 1)
> #;2>
> #;2> (define memo-fact** (memoize fact**))
> #;2>
> #;2> (define x (time (memo-fact**  35710)))
> #;2> (define x (time (memo-fact**  35720)))
> #;2> (define x (time (memo-fact**  35730)))
> #;2>
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/memoize.import.so ...
> ; loading /usr/local/chicken-4.9.0/lib/chicken/7/memoize.so ...
> 
> Note: the following toplevel variables are referenced but unbound:
> 
>   memo-fact** (in fact**)
> 2.804s CPU time, 1.064s GC time (major), 81305 mutations, 21/1551 GCs
> (major/minor)
> 0s CPU time, 20 mutations
> 0s CPU time, 20 mutations
> #;8>
> [panic] out of memory - heap full while resizing - execution terminated
> 
> ...more...
> parley.scm:610: history817818
> parley.scm:610: history817818
> parley.scm:603: ##sys#dynamic-wind
> parley.scm:603: history798799
> parley.scm:603: history798799
> parley.scm:603: history798799
> parley.scm:603: history798799
> parley.scm:610: ##sys#dynamic-wind
> parley.scm:610: history817818
> parley.scm:610: history817818
> parley.scm:615: get-next-char!
> parley.scm:579: parley-char-ready?
> parley.scm:586: append-while-incomplete
> parley.scm:560: string-null?
> parley.scm:561: repl-prompt
> parley.scm:561: g769<--
> -
> 
> Sometimes I'll crash immediately and someytimes I have to press some
> keys when the "#;8>" prompt appears.
> 
> 
> If I run the above script thusly:
> 
> -
> $ csi -s memo-demo.scm
> -
> 
> I see
> 
> -
> $ csi -s ../memo-demo.scm
> 2.908s CPU time, 1.164s GC time (major), 75257 mutations, 22/1550 GCs
> (major/minor)
> 0s CPU time, 20 mutations
> -
> 
> ...and it hangs there (on the last time call) indefinitely using all the
> CPU. Ctrl-C doesn't terminate it: a call to 'killall csi' does tho'.
> 
> 
> If you cannot reproduce it then try varying the numbers in the call to
> memo-fact**.
> 
> 
> 
> Is this a known bug in Chicken 4.9.0rc1 or the srfi-69 hash-tables that
> memoize uses?
> 
> 
> Thanks for any tips you can offer.

With CHICKEN 4.10.0 from the website the following works:

-
(define x (time (memo-fact**  35710)))
(define x (time (memo-fact**  35720)))
(define x (time (memo-fact**  36030)))
-

...but a slightly larger number hangs as before:

-
(define x (time (memo-fact** 35710)))
(define x (time (memo-fact** 35720)))
(define x (time (memo-fact** 37030)))
-



...Also, under CHICKEN 4.10.0, pasting things into csi with parley 

Re: [Chicken-users] CHICKEN hang / crash / memoize egg

[Andy Bennett]

Hi,

>> I'm running CHICKEN 4.9.0rc1 and I'm trying out the memoize egg.
>>
>> I saw the tail-call-optimized version of the factorial procedure in the
>> memoize documentation at http://api.call-cc.org/doc/memoize and I've
>> been trying to modify it so that it memoizes intermediate results such
>> that, for example, a call to (fact 10) makes a subsequent call to (fact
>> 9) fast.
>>
>> In doing so I've managed to get the interpreter into a loop or crash it
>> entirely.
>>
> 
> This looks like a perfectly legitimate crash. The memoize egg doesn’t
> impose a limit on memory usage unless you explicitly tell it so.

I get the same results with '(define memo-fact** (memoize fact** 3))'.
I suspect this is a numbers bug as it still allocates a fair bit of memory.





Regards,
@ndy

-- 
andy...@ashurst.eu.org
http://www.ashurst.eu.org/
0290 DA75 E982 7D99 A51F  E46A 387A 7695 7EBA 75FF


___
Chicken-users mailing list
Chicken-users@nongnu.org
https://lists.nongnu.org/mailman/listinfo/chicken-users

Re: [Chicken-users] CHICKEN hang / crash / memoize egg

[Kooda]

On Fri, 01 Apr 2016 16:28:26 +0200,
Andy Bennett wrote:
> 
> Hi Peeps!
> 
> I'm running CHICKEN 4.9.0rc1 and I'm trying out the memoize egg.
> 
> I saw the tail-call-optimized version of the factorial procedure in the
> memoize documentation at http://api.call-cc.org/doc/memoize and I've
> been trying to modify it so that it memoizes intermediate results such
> that, for example, a call to (fact 10) makes a subsequent call to (fact
> 9) fast.
> 
> In doing so I've managed to get the interpreter into a loop or crash it
> entirely.
> 

This looks like a perfectly legitimate crash. The memoize egg doesn’t
impose a limit on memory usage unless you explicitly tell it so.

___
Chicken-users mailing list
Chicken-users@nongnu.org
https://lists.nongnu.org/mailman/listinfo/chicken-users