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.
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 ***
(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"))
(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"))
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?)
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.