"ulimit -s" has no effect?

Discussion in 'Python' started by Maciej Kalisiak, Feb 5, 2004.

  1. 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 ...
     
    Maciej Kalisiak, Feb 5, 2004
    #1
    1. Advertising

  2. 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
     
    =?ISO-8859-1?Q?=22Martin_v=2E_L=F6wis=22?=, Feb 5, 2004
    #2
    1. Advertising

  3. "Martin v. Löwis" <> 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]
     
    Maciej Kalisiak, Feb 5, 2004
    #3
  4. 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
     
    Mathias Waack, Feb 5, 2004
    #4
  5. Mathias Waack <> 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 | <> | http://www.dgp.toronto.edu/~mac
     
    Maciej Kalisiak, Feb 5, 2004
    #5
  6. 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: (pref) | Snail: PO Box 370
    (alt) | Belconnen ACT 2616
    Web: http://www.andymac.org/ | Australia
     
    Andrew MacIntyre, Feb 5, 2004
    #6
  7. Andrew MacIntyre <> 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.
     
    Maciej Kalisiak, Feb 6, 2004
    #7
  8. 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: (pref) | Snail: PO Box 370
    (alt) | Belconnen ACT 2616
    Web: http://www.andymac.org/ | Australia
     
    Andrew MacIntyre, Feb 6, 2004
    #8
  9. > 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
     
    Josiah Carlson, Feb 6, 2004
    #9
  10. Josiah Carlson <> 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.
     
    Maciej Kalisiak, Feb 7, 2004
    #10
  11. >>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
     
    Josiah Carlson, Feb 7, 2004
    #11
  12. Josiah Carlson <> 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.
     
    Maciej Kalisiak, Feb 7, 2004
    #12

  13. > 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
     
    Josiah Carlson, Feb 7, 2004
    #13
  14. Josiah Carlson <> 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
     
    Maciej Kalisiak, Feb 9, 2004
    #14
  15. > 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
     
    Josiah Carlson, Feb 9, 2004
    #15
  16. Josiah Carlson <> 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. :)
     
    Maciej Kalisiak, Feb 9, 2004
    #16
  17. > 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
     
    Josiah Carlson, Feb 12, 2004
    #17
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. John E. Jardine

    s/// has apparent side effect on grep()

    John E. Jardine, Apr 12, 2004, in forum: Perl
    Replies:
    2
    Views:
    449
    John Jardine
    Apr 13, 2004
  2. Doug
    Replies:
    3
    Views:
    3,060
    PeterBrunone
    Dec 7, 2006
  3. Nathan Sokalski
    Replies:
    8
    Views:
    3,575
    Nathan Sokalski
    Dec 5, 2005
  4. Charlie@CBFC
    Replies:
    1
    Views:
    347
    Hassan Davis
    Jan 11, 2007
  5. onkar

    operator has no effect

    onkar, Nov 14, 2006, in forum: C Programming
    Replies:
    5
    Views:
    377
    Richard Heathfield
    Nov 14, 2006
Loading...

Share This Page