"ulimit -s" has no effect?

[Maciej Kalisiak]

I use this simple test in Python:

def foo(i):
print i
foo(i+1)
import sys
sys.setrecursionlimit(1000000)
foo(0)

Now, my understanding is that I get the segfault when Python overruns the C
stack. Naturally the last number printed should go up when I increase the
stack size in the shell before calling Python, by using "ulimit -s <number
of k>". But this seems to not be the case. Whatever value I use with
ulimit, Python always segfaults at the same recursion depth. Any advice on
how to get things to work proper with this?

% python -V
Python 2.3.3
% uname -a
Linux isildur 2.4.24-1-686 #1 ...

[Martin v. Löwis]

Maciej Kalisiak wrote:

Now, my understanding is that I get the segfault when Python overruns the C
stack. Naturally the last number printed should go up when I increase the
stack size in the shell before calling Python, by using "ulimit -s <number
of k>". But this seems to not be the case. Whatever value I use with
ulimit, Python always segfaults at the same recursion depth. Any advice on
how to get things to work proper with this?

As a starting point, verify that the limit you set actually does get
set. It may be that you don't have permission to increase your stack
limit.

Regards,
Martin

[Maciej Kalisiak]

"Martin v. Löwis" <ma****@v.loewis.de> writes:

As a starting point, verify that the limit you set actually does get
set. It may be that you don't have permission to increase your stack
limit.

I check that it is set by running "ulimit -s" without a numerical argument.
The reported value is the one I have set, viz. much larger than the default of
8192 (kbytes). This is the soft limit. The hard limit is reported to be
"unlimited".

If it matters, let me add that I'm running Python from within zsh.
% zsh --version
zsh 4.0.4 (i686-pc-linux-gnu)

--
Maciej Kalisiak | <mac at dgp.toronto.edu> | http://www.dgp.toronto.edu/~mac [McQ]

[Mathias Waack]

Maciej Kalisiak wrote:

If it matters, let me add that I'm running Python from within zsh.
% zsh --version
zsh 4.0.4 (i686-pc-linux-gnu)

Have you tried it with a different shell? Your example works for me
as expected. But I'm using a bash where ulimit is a builtin. Don't
know about zsh.

Mathias

[Maciej Kalisiak]

Mathias Waack <M.*****@gmx.de> writes:

Have you tried it with a different shell? Your example works for me
as expected. But I'm using a bash where ulimit is a builtin. Don't
know about zsh.

"ulimit" is a builtin in zsh as well. But I did try under "bash" from a Linux
console. Same behaviour. On two different machines. This must be something
embarassingly simple. Sanity check, just to be on the same page, here's my
procedure:

1. % python
2. # type in routine

def foo(i):

print i
foo(i+1)

3. >>> foo(0)
4. this properly raises exception at depth 998 or so
5. import sys
6. sys.setrecursionlimit(1000000)
7. >>> foo(0)
8. segfaults at about depth 7000+
9. % ulimit -s 32000
10. repeat steps 1 through 7
11. same segfault point

--
Maciej Kalisiak | <ma*@dgp.toronto.edu> | http://www.dgp.toronto.edu/~mac

[Andrew MacIntyre]

On Fri, 5 Feb 2004, Maciej Kalisiak wrote:

I check that it is set by running "ulimit -s" without a numerical argument.
The reported value is the one I have set, viz. much larger than the default of
8192 (kbytes). This is the soft limit. The hard limit is reported to be
"unlimited".

I have no idea whether this affects Linux, but some pthreads
implementations hard code the stack size for the "primary" or
"initial" thread.

Python is built with thread support if possible (incl on Linux), but
without explicit use of the thread support Python code runs in the context
of the "primary" thread.

ISTR that RedHat, amongst others, changed thread implementations
relatively recently.

I know that there is/was a bug in the Python bug tracker on SF related
to this issue on Linux (symptom is test_sre dumping core) with Python
2.3.3. This particular issue is sensitive to the version of gcc and
optimisation settings (& on Linux, whether the Python core is in a SO),
as newer releases/higher optimisation settings result in larger stack
frames.

--
Andrew I MacIntyre "These thoughts are mine alone..."
E-mail: an*****@bullseye.apana.org.au (pref) | Snail: PO Box 370
an*****@pcug.org.au (alt) | Belconnen ACT 2616
Web: http://www.andymac.org/ | Australia

[Maciej Kalisiak]

Andrew MacIntyre <an*****@bullseye.apana.org.au> writes:

I have no idea whether this affects Linux, but some pthreads
implementations hard code the stack size for the "primary" or
"initial" thread.

Python is built with thread support if possible (incl on Linux), but
without explicit use of the thread support Python code runs in the context
of the "primary" thread.

ISTR that RedHat, amongst others, changed thread implementations
relatively recently.

I know that there is/was a bug in the Python bug tracker on SF related
to this issue on Linux (symptom is test_sre dumping core) with Python
2.3.3. This particular issue is sensitive to the version of gcc and
optimisation settings (& on Linux, whether the Python core is in a SO),
as newer releases/higher optimisation settings result in larger stack
frames.

Interesting.

1. Is there a test or code snippet that I can run to confirm that this is what
ails my system?

2. If this *is* the problem, what would be a good workaround?
For the record I am using Debian's sid/unstable distribution.
debs used:
python 2.3.2.91-1
libc6 2.3.2.ds1-8

"ldd" shows python uses libpthreads, and it comes from the above libc6
package.

Upgraded Python to debian package 2.3.3-5; no change.

[Andrew MacIntyre]

On Fri, 6 Feb 2004, Maciej Kalisiak wrote:

1. Is there a test or code snippet that I can run to confirm that this is what
ails my system?
A trivial C program can be used to demonstrate:

---8<--- stest.c ---8<---
#include <stdio.h>

int recursion_func(int t1, int t2, int t3);

int main(void)
{
printf("counter = %d\n", recursion_func(25, 15, 1));
return 0;
}
---8<------8<-------8<---
---8<--- rfunc.c ---8<---
int recursion_func(int t1, int t2, int t3)
{
int z1, z2, z3;
double x1, x2, x3;

z1 = t1 << 2;
z2 = t2 << 2;
z3 = t3 << 2;

x1 = 3.47 * z1;
x2 = 1.29 * z2;
x3 = -2.47 * z3;

return x1 * x2 - x3 > 1.5e30 ? t3 : recursion_func(++t1, ++t2, ++t3);
}
---8<------8<-------8<---

Note that the recursion function was made more complex than might have
been needed to try to force larger stack frames. I was also trying to
avoid gcc's optimiser undoing the recursion at higher levels of
optimisation - this worked with gcc 2.95, but gcc 3.3.2 seems to be able
to make this test non-recursive even with -Os ... :-|

On FreeBSD, this is built by

$ gcc -g -O -pthread -c rfunc.c
$ gcc -g -O -pthread -c stest.c
$ gcc -g -O -pthread -o stest stest.o rfunc.o

You'll have to adapt for Linux. Running this:

$ ./stest
Bus error (core dumped)
$ gdb stest stest.core
GNU gdb 4.18 (FreeBSD)
{...copyright stuff elided...}
Program terminated with signal 10, Bus error.
Reading symbols from /usr/lib/libc_r.so.4...done.
Reading symbols from /usr/libexec/ld-elf.so.1...done.
#0 0x80484ce in recursion_func (t1=21846, t2=21836, t3=21822)
at pthread_recursion_test_aux.c:3
3 int recursion_func(int t1, int t2, int t3)
(gdb)
libc_r is the pthread-supporting libc.

Building without the "-pthread" switch uses the non-threaded libc, which
results in:

$ ./stest
Segmentation fault (core dumped)
$ gdb stest stest.core
{...}
Program terminated with signal 11, Segmentation fault.
Reading symbols from /usr/lib/libc.so.4...done.
Reading symbols from /usr/libexec/ld-elf.so.1...done.
#0 0x8048530 in recursion_func (t1=1398102, t2=1398092, t3=1398078)
at pthread_recursion_test_aux.c:16
16 return x1 * x2 - x3 > 1.5e30 ? t3 : recursion_func(++t1,
++t2, +
+t3);
(gdb)
In this case, I know the stack size is 64MB; the ratio t1 values between
the two matches 1MB to 64MB.
2. If this *is* the problem, what would be a good workaround?

If you can do without threads, build the Python interpreter that way.

I suggest that you enquire of glibc forums whether there is any way to
tweak the primary thread stack size by some runtime means, otherwise
the only option would probably require changing a library header file and
recompiling glibc :-( (which is what's required on FreeBSD 4.x - don't
know about 5.x).

--
Andrew I MacIntyre "These thoughts are mine alone..."
E-mail: an*****@bullseye.apana.org.au (pref) | Snail: PO Box 370
an*****@pcug.org.au (alt) | Belconnen ACT 2616
Web: http://www.andymac.org/ | Australia

[Josiah Carlson]

> def foo(i):

print i
foo(i+1)
import sys
sys.setrecursionlimit(1000000)
foo(0)

This entire thread begs the question: Why are you recursing this deep?
It would be faster to iterate.

- Josiah

[Maciej Kalisiak]

Josiah Carlson <jc******@nospam.uci.edu> writes:

def foo(i):
print i foo(i+1)
import sys
sys.setrecursionlimit(1000000)
foo(0)

This entire thread begs the question: Why are you recursing this deep?
It would be faster to iterate.

The algorithm calls for it: Tarjan's algorithm for finding the
Strongly-Connected Component (SCC) of a graph. If there is an equally
efficient iterative approach, I'd like to hear of it.

I don't think I need to recurse to depth 1,000,000 , but definitely higher
than 7k.

[Josiah Carlson]

>>This entire thread begs the question: Why are you recursing this deep?

It would be faster to iterate.

The algorithm calls for it: Tarjan's algorithm for finding the
Strongly-Connected Component (SCC) of a graph. If there is an equally
efficient iterative approach, I'd like to hear of it.

I don't think I need to recurse to depth 1,000,000 , but definitely higher
than 7k.

Any recursive algorithm can be unrolled into an iterative version. The
below is fairly generic, and relies on locals() being sane.

def blah():
stack = []
#set up initial local variables
a = dict(locals())
del a['a']
del a['stack']
stack.append(a)
while stack:
locals().update(stack.pop())
#do what you need for this loop
if need_to_recurse:
#save previous state
a = dict(locals())
del a['a']
del a['stack']
stack.append(a)
#save new local state
a = dict(locals())
del a['a']
del a['stack']
stack.append(a)
#recursion will happen automatically

- Josiah

[Maciej Kalisiak]

Josiah Carlson <jc******@nospam.uci.edu> writes:

Any recursive algorithm can be unrolled into an iterative version. The below
is fairly generic, and relies on locals() being sane.

def blah():
stack = []
#set up initial local variables
a = dict(locals())
del a['a']
del a['stack']
stack.append(a)
while stack:
locals().update(stack.pop())
#do what you need for this loop
if need_to_recurse:
#save previous state
a = dict(locals())
del a['a']
del a['stack']
stack.append(a)
#save new local state
a = dict(locals())
del a['a']
del a['stack']
stack.append(a)
#recursion will happen automatically

Interesting. Alas, I don't think I can use this. First, this seems to only
apply to tail recursion, no? In the Tarjan's algorithm recursion happens at
the beginning, on the children of a given node, and then the results of that
recursion are used in the computation for the current node. Also, I think my
locals() won't be "sane"... it contains a huge graph; from what I understand
from the above, there would be multiple copies of it on `stack', and that's
just not feasible due to memory constraints.

[Josiah Carlson]

Interesting. Alas, I don't think I can use this. First, this seems to only
apply to tail recursion, no? In the Tarjan's algorithm recursion happens at
the beginning, on the children of a given node, and then the results of that
recursion are used in the computation for the current node. Also, I think my
locals() won't be "sane"... it contains a huge graph; from what I understand
from the above, there would be multiple copies of it on `stack', and that's
just not feasible due to memory constraints.

Though it sometimes takes work, _any_ recursive algorithm can be made
iterative. If you are willing to cough up your code (via email or
otherwise), I'd be willing to give a shot at converting it.

As an example, DFS is not tail recursive, but I've converted a DFS
algorithm for generating a browsable source tree for PyPE
(pype.sourceforge.net).

In terms of your question about it keeping multiple copies of objects on
the stack, really it only keeps multiple /references/ to objects on the
stack. Python 2.2+ standard nested scopes does the same thing. The
only difference is that we use a list as a call stack, rather than
relying on the C stack for the Python call stack, which is what is
limiting your program.

So yeah, want me to give the conversion a shot?
- Josiah

[Maciej Kalisiak]

Josiah Carlson <jc******@nospam.uci.edu> writes:

Though it sometimes takes work, _any_ recursive algorithm can be made
iterative. If you are willing to cough up your code (via email or otherwise),
I'd be willing to give a shot at converting it.

n
Sure, here is the algorithm code. The routine is ripped out of a much larger
class, but it should be relatively independent. The class among other things
contains a graph, with the graph vertices in `self.nodes'. Each node object
has a `kids' attribute, which is a list of (kid node, edge type) tuples. The
edge type is unimportant as far as this algo is concerned.

def find_scc(self):
"""Find the 'strongly connected component' (SCC) of the graph.

Implemented using Tarjan's algorithm.
"""
# prep the vertices
for n in self.nodes:
n.num = None # the "visit order number"
n.root = n
n.visited = False
n.in_component = None

stack = []
components = []
nodes_visit_order = []
self.next_visit_num = 0

def visit(v):
v.visited = True
nodes_visit_order.append(v)
v.num = self.next_visit_num
self.next_visit_num += 1
stack.append(v)
for w,type in v.kids:
if not w.visited:
visit(w)
if not w.in_component:
v.root = nodes_visit_order[ min(v.root.num, w.root.num) ]
if v.root == v:
c = []
while 1:
w = stack.pop()
w.in_component = c
c.append(w)
if w == v:
break
components.append(c)

# the "main" routine
for v in self.nodes:
if not v.visited:
visit(v)

# extract SCC info
for n in self.nodes:
if n.in_component and len(n.in_component) > 1:
# part of SCC
n.hidden = False
else:
# either not in a component, or singleton case
n.hidden = True

[Josiah Carlson]

> Sure, here is the algorithm code. The routine is ripped out of a much larger

class, but it should be relatively independent. The class among other things
contains a graph, with the graph vertices in `self.nodes'. Each node object
has a `kids' attribute, which is a list of (kid node, edge type) tuples. The
edge type is unimportant as far as this algo is concerned.

visit(v) is now non-recursive. I ran a test on a randomly generated 26
node graph, and both versions resulted in the same components, node
visit order, etc. I think you'll be happy with it.

I notice that you are a graduate student at the University of Toronto.
Out of curiosity, what area are you focusing on? From your playing with
Tarjan's algorithm, I would expect that you are either a Theory student,
or are taking a Theory course to fulfill a requirement of some sort.
It's all good.

I'm a graduate student at University of California at Irvine, studying
Theory myself. Well, I should probably get back to my own work.

Enjoy,
- Josiah
def find_scc(self):
"""Find the 'strongly connected component' (SCC) of the graph.

Implemented using Tarjan's algorithm.
"""
# prep the vertices
for n in self.nodes:
n.num = None # the "visit order number"
n.root = n
n.visited = False
n.in_component = None

stack = []
components = []
nodes_visit_order = []
self.next_visit_num = 0

def visit(v):
call_stack = [(1, v, iter(v.kids), None)]
while call_stack:
tovisit, v, iterator, w = call_stack.pop()
if tovisit:
v.visited = True
nodes_visit_order.append(v)
v.num = self.next_visit_num
self.next_visit_num += 1
stack.append(v)
if w and not w.in_component:
v.root = nodes_visit_order[ min(v.root.num,\
w.root.num)]
cont = 0
for w, notused in iterator:
if not w.visited:
cont = 1
call_stack.append((0, v, iterator, w))
call_stack.append((1, w, iter(w.kids), None))
break
if not w.in_component:
v.root = nodes_visit_order[ min(v.root.num,\
w.root.num) ]
if cont:
continue
if v.root == v:
c = []
while 1:
w = stack.pop()
w.in_component = c
c.append(w)
if w == v:
break
components.append(c)

# the "main" routine
for v in self.nodes:
if not v.visited:
visit(v)

# extract SCC info
for n in self.nodes:
if n.in_component and len(n.in_component) > 1:
# part of SCC
n.hidden = False
else:
# either not in a component, or singleton case
n.hidden = True

[Maciej Kalisiak]

Josiah Carlson <jc******@nospam.uci.edu> writes:

visit(v) is now non-recursive. I ran a test on a randomly generated 26 node
graph, and both versions resulted in the same components, node visit order,
etc. I think you'll be happy with it.
Thanks! I'll have a look at it soon, currently swamped. It should be a good
practical example of recursive->iterative conversion; never know when I'll
have to do something similar again..
I notice that you are a graduate student at the University of Toronto. Out of
curiosity, what area are you focusing on? From your playing with Tarjan's
algorithm, I would expect that you are either a Theory student, or are taking
a Theory course to fulfill a requirement of some sort. It's all good.

Alas, no, I'm more on the application side of things. My main area is
computer graphics and animation, although my research makes substantial
use of AI (path planning, surface learning) and robotics (controllability,
control theory). There's some more info on my homepage.

I *did* take an (Advanced Topics in) Graph Theory course though. Ouch, my head
still hurts. My brain is just not wired that way. :)

[Josiah Carlson]

> Thanks! I'll have a look at it soon, currently swamped. It should be a good

practical example of recursive->iterative conversion; never know when I'll
have to do something similar again..
I'm feeling swamped as well. Time will tell if it is just this week, or
if it is for the rest of the quarter.
Alas, no, I'm more on the application side of things. My main area is
computer graphics and animation, although my research makes substantial
use of AI (path planning, surface learning) and robotics (controllability,
control theory). There's some more info on my homepage.
I love the videos from your masters.
I *did* take an (Advanced Topics in) Graph Theory course though. Ouch, my head
still hurts. My brain is just not wired that way. :)

Indeed, graph theory is pretty painful. Graph algorithms can be nifty,
as can the related set of computational geometry algorithms.

- Josiah