From: Alex Mizrahi
Subject: stack overflow
Date: 
Message-ID: <31f8pgF3akio8U1@individual.net>
Hello, All!

i have a piece of code that causes stack overflow where i see no reason for
it to do this.
i've checked several implementations - in clisp maximum depth is about 650,
in abcl about 70, in ecl something like 200, so looks like problem is in my
code, not in implementation 8-]
i want it to go at depth about 2500..
i see nothing stack-consuming in this code - 2 parameters and about 7
variable..
 or does it put something else in a stack??
how can i fix this? i see no easy way to do it without recursion.. 8-/

(defun populate-accessible-nodes (bs1 bs2)
  (unless (gethash (encode-battle-state bs1 bs2) *battle-state-nodes*)
    (let ((bs-node (make-instance 'battle-state-node
      :user1-state bs1
      :user2-state bs2
      :value ())))
      (setf (gethash (encode-battle-state bs1 bs2) *battle-state-nodes*)
     bs-node)
      (let ((turn-list1 (make-meaningful-turn-list bs1))
     (turn-list2 (make-meaningful-turn-list bs2)))
 (dolist (t1 turn-list1)
   (dolist (t2 turn-list2)
     (let ((new-bs1 (clone-user-battle-state t1))
    (new-bs2 (clone-user-battle-state t2)))
       (calculate-turn new-bs1 new-bs2)
       (populate-accessible-nodes new-bs1 new-bs2))))))))


With best regards, Alex 'killer_storm' Mizrahi.

From: Barry Margolin
Subject: Re: stack overflow
Date: 
Message-ID: <barmar-C5EA67.23035404122004@comcast.dca.giganews.com>
In article <···············@individual.net>,
 "Alex Mizrahi" <········@hotmail.com> wrote:

> Hello, All!
> 
> i have a piece of code that causes stack overflow where i see no reason for
> it to do this.
> i've checked several implementations - in clisp maximum depth is about 650,
> in abcl about 70, in ecl something like 200, so looks like problem is in my
> code, not in implementation 8-]
> i want it to go at depth about 2500..
> i see nothing stack-consuming in this code - 2 parameters and about 7
> variable..

It's recursive, calling itself at the end -- that will consume stack 
space.  The recursion only bottoms out when it finds the encoded battle 
state already in the *BATTLE-STATE-NODES* hash table.  My guess is that 
you're not doing the right kind of hashing -- maybe it's an EQL hash 
table, but you need to use an EQUAL hash table for this matching.

>  or does it put something else in a stack??
> how can i fix this? i see no easy way to do it without recursion.. 8-/
> 
> (defun populate-accessible-nodes (bs1 bs2)
>   (unless (gethash (encode-battle-state bs1 bs2) *battle-state-nodes*)
>     (let ((bs-node (make-instance 'battle-state-node
>       :user1-state bs1
>       :user2-state bs2
>       :value ())))
>       (setf (gethash (encode-battle-state bs1 bs2) *battle-state-nodes*)
>      bs-node)
>       (let ((turn-list1 (make-meaningful-turn-list bs1))
>      (turn-list2 (make-meaningful-turn-list bs2)))
>  (dolist (t1 turn-list1)
>    (dolist (t2 turn-list2)
>      (let ((new-bs1 (clone-user-battle-state t1))
>     (new-bs2 (clone-user-battle-state t2)))
>        (calculate-turn new-bs1 new-bs2)
>        (populate-accessible-nodes new-bs1 new-bs2))))))))
> 
> 
> With best regards, Alex 'killer_storm' Mizrahi.

-- 
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
From: Alex Mizrahi
Subject: Re: stack overflow
Date: 
Message-ID: <31g792F3bodlqU1@individual.net>
(message (Hello 'Barry)
(you :wrote  :on '(Sat, 04 Dec 2004 23:03:54 -0500))
(

 >> i have a piece of code that causes stack overflow where i see no
 >> reason for it to do this.
 >> i've checked several implementations - in clisp maximum depth is
 >> about 650, in abcl about 70, in ecl something like 200, so looks like
 >> problem is in my code, not in implementation 8-]
 >> i want it to go at depth about 2500..
 >> i see nothing stack-consuming in this code - 2 parameters and about 7
 >> variable..

 BM> It's recursive, calling itself at the end -- that will consume stack
 BM> space. The recursion only bottoms out when it finds the encoded battle
 BM> state already in the *BATTLE-STATE-NODES* hash table.  My guess is
 BM> that  you're not doing the right kind of hashing -- maybe it's an EQL
 BM> hash  table, but you need to use an EQUAL hash table for this matching.

yes, it should consume some stack space - it's something like depth-first
search. i've traced this function, and looks like it works correctly.
question is how much stack space do i have? i roughly estimate that each
call wants about 11 binding cells - so it's 7150 binding cells for clisp -
and if implementation doesn't do anything awful it shouldn't exceed 100-200
kb. looks like bullshit for a language where recursion is widely used - old
MS-DOS turbo pascal gave me 64kb of stack, and win32 implementations of
object pascal and C have something like 1MB of stack space..
if something other than bindings is stored in a stack - for example,
conses - it's another thing, i have hundreds of conses collected for each
call..
i think i can rewrite algorithm to make it breadth-first, but it will make
it more complex..
by the way, are there any minimum requirements for something like stack
space in standard?

)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
(prin1 "Jane dates only Lisp programmers"))
From: Alex Mizrahi
Subject: Re: stack overflow
Date: 
Message-ID: <31g98rF389qspU1@individual.net>
(message (Hello 'Alex)
(you :wrote :to '(Barry Margolin) :on '(Sun, 5 Dec 2004 12:47:52 +0200))
(

 AM> if something other than bindings is stored in a stack - for example,
 AM> conses - it's another thing, i have hundreds of conses collected for
 AM> each call..

ah, i've understood what happens - i'm running interpreted function, which
consumes stack a lot. with compiled one all is much better..

)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
(prin1 "Jane dates only Lisp programmers"))
From: Pascal Bourguignon
Subject: Re: stack overflow
Date: 
Message-ID: <87hdn066sz.fsf@thalassa.informatimago.com>
"Alex Mizrahi" <········@hotmail.com> writes:

> (message (Hello 'Alex)
> (you :wrote :to '(Barry Margolin) :on '(Sun, 5 Dec 2004 12:47:52 +0200))
> (
> 
>  AM> if something other than bindings is stored in a stack - for example,
>  AM> conses - it's another thing, i have hundreds of conses collected for
>  AM> each call..
> 
> ah, i've understood what happens - i'm running interpreted function, which
> consumes stack a lot. with compiled one all is much better..

In any case, it's easy to avoid using the machine stack in search
procedures:



(defun graph-search (root action get-adjacent-nodes set-visited visited-p
                     &key depth-first)
  (loop
   with nodes-to-visit = (list root)
   while nodes-to-visit 
   do (let ((current (pop nodes-to-visit)))
        (unless (funcall visited-p current)
          (funcall action current)
          (funcall set-visited current)
          (let ((ad-nodes
                 (remove-if visited-p (funcall get-adjacent-nodes current))))
            (if deep-first
                (setf nodes-to-visit (append ad-nodes nodes-to-visit))
                (setf nodes-to-visit (append nodes-to-visit ad-nodes))))))))


(let* ((size 200)
       (graph
        (loop with graph = (make-array (list size size)
                                       :element-type 'bit
                                       :initial-element 0)
              for i below size do
              (loop for j below size do
                    (setf (aref graph i j) (if (zerop (random 5)) 1 0)))
              finally (return graph)))
       (visited (make-array (list size)
                            :element-type 'bit
                            :initial-element 0)))
  (graph-search 0
                (function print)
                (lambda (x) (loop for j below size
                             if (plusp (aref graph x j))
                             collect j))
                (lambda (x) (setf (aref visited x) 1))
                (lambda (x) (plusp (aref visited x)))
                :depth-first t))


        
-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
The world will now reboot; don't bother saving your artefacts.
From: Svein Ove Aas
Subject: Re: stack overflow
Date: 
Message-ID: <cour2e$8sf$1@services.kq.no>
Alex Mizrahi wrote:

> Hello, All!
> 
> i have a piece of code that causes stack overflow where i see no reason
> for it to do this.
> i've checked several implementations - in clisp maximum depth is about
> 650, in abcl about 70, in ecl something like 200, so looks like problem is

That doesn't sound right... so few levels?
A quick test of sbcl gives 65336 levels for a simple one-argument function.

(...and also the same number of levels for two parameters, three parameters,
and... what's going on?)
From: Thomas F. Burdick
Subject: Re: stack overflow
Date: 
Message-ID: <xcvzn0sk6xd.fsf@conquest.OCF.Berkeley.EDU>
Svein Ove Aas <·········@aas.no> writes:

> Alex Mizrahi wrote:
> 
> > Hello, All!
> > 
> > i have a piece of code that causes stack overflow where i see no reason
> > for it to do this.
> > i've checked several implementations - in clisp maximum depth is about
> > 650, in abcl about 70, in ecl something like 200, so looks like problem is
> 
> That doesn't sound right... so few levels?
> A quick test of sbcl gives 65336 levels for a simple one-argument function.
> 
> (...and also the same number of levels for two parameters, three parameters,
> and... what's going on?)

Try 1024 parameters.  Most calling conventions have a minimum frame
size, containing at least enough room to save all the volatile
registers to the stack.