Method calls and stack consumption

[Martin Manns]

Hi,

Calling methods of other object instances seems quite expensive on the
stack (see example below). Is there a better way of traversing through
methods of instances that are connected in a cyclic graph? (The real
program's graph contains multiple successors in lists.)

class A(object):
def __init__(self):
self.i = 0
def a(self):
if self.i % 1000 == 0:
print self.i
self.i += 1
return S[self].a()

a = A()
b = A()
S = {a:b, b:a}

import sys
sys.setrecursionlimit(1000000)
print a.a()


0
0
1000
1000
[...]
69000
69000
Segmentation fault
~ $ ulimit -s
65536
~ $

Thus, each call seems to be about 480 bytes on the stack.

Is there a good way to reduce stack consumption per call?
Could and should I resort to stackless?
If yes, how can the graph structure be realized?
Would I need a tasklet for each instance?

I am currently hesitant to depend on something from svn.
How stable and robust is stackless?

Martin

 

[Peter Otten]

Calling methods of other object instances seems quite expensive on the
stack (see example below). Is there a better way of traversing through
methods of instances that are connected in a cyclic graph? (The real
program's graph contains multiple successors in lists.)

class A(object):
    def __init__(self):
        self.i = 0
    def a(self):
        if self.i % 1000 == 0:
            print self.i
        self.i += 1                     

        return S[self].a

a = A()
b = A()
S = {a:b, b:a}

a = a.a
while True:
a = a()

That's how you can do it if your real program is similar enough to the
example...

Peter

 

[Martin Manns]

a = a.a
while True:
a = a()

That's how you can do it if your real program is similar enough to the
example...

Thanks for pointing out the oversimplified nature of the original
example.I hope that the following one clarifies the problem.

(I do not know, what has to be stored on the stack, but it should not be
that much, because all recursion calls originate from inside the return
statement.)


from random import randint,seed
import sys
seed()
sys.setrecursionlimit(1000000)

class Node(object):
def __init__(self):
self.state = abs(randint(1,1000))
def GetDepState(self):
return self.state + max(s.GetDepState() for s in S[self])

class ConditionalBreakNode(Node):
def GetDepState(self):
if randint(1,5) > 1:
return Node.GetDepState(self)
else:
return self.state

S = {}
nodes = [Node()]

def AppendNode(curr_node, depth=1):
global nodes
r = randint(1,30)
if r >= depth:
for i in xrange(randint(1,3)):
newnode = Node()
nodes += [newnode]
try: S[curr_node] += [newnode]
except: S[curr_node] = [newnode]
AppendNode(newnode, depth+1)
else:
newnode = ConditionalBreakNode()
nodes += [newnode]
try: S[curr_node] += [newnode]
except: S[curr_node] = [newnode]
S[newnode] = [nodes[0]]

AppendNode(nodes[0])
print len(nodes)
print nodes[0].GetDepState()

 

[Peter Otten]

Thanks for pointing out the oversimplified nature of the original
example.I hope that the following one clarifies the problem.

(I do not know, what has to be stored on the stack, but it should not be
that much, because all recursion calls originate from inside the return
statement.)

class Node(object):
    def __init__(self):
        self.state = abs(randint(1,1000))
    def GetDepState(self):
        return self.state + max(s.GetDepState() for s in S[self])

class ConditionalBreakNode(Node):
    def GetDepState(self):
        if randint(1,5) > 1:
            return Node.GetDepState(self)
        else:
            return self.state

Have you investigated the libraries available for that kind of problem? (No,
I don't know them) Maybe one of them provides an implementation that does
not depend on the stack.

On the other hand, if the above is the "natural" expression of your problem,
why not give stackless a try?

Peter