bugGNU Octave - Bugs: bug #51214, recursive function fails at modest...

 
 

bug #51214: recursive function fails at modest recursion depths, causes segmentation fault

Submitter:  None
Submitted:  Fri 09 Jun 2017 10:22:38 PM UTC
   
 
Category:  Interpreter Severity:  2 - Minor
Priority:  3 - Low Item Group:  Documentation
Status:  Postponed Assigned to:  None
Originator Name:  David Nichols Originator Email:  -email is unavailable-
Open/Closed:  * Open Release:  * 4.2.1
Operating System:  * Any Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Mon 28 Aug 2017 06:25:28 PM UTC, comment #6: 

Posted to the mailing list, not the tracker:

You are correct.  I have found no problem with the linkage function.  I only used it as a realistic example of why one might want to use recursion to a non-trivial depth.

The bug I was attempting to report was the unwarned/unexpected crash at what seems to be a modest recursive depth.  A simple patch would be to have max_recursion_depth () warn that "increasing the recursion depth may well cause the interpreter to crash " or something like that, so the user at least can save work while trying things out.  It would be nicer if the stack overflow were caught and reported as an error without having the interpreter crash, but that's probably a bit more work.  And yes, I realize it takes much less time for users to dream up features than it does for programmers to implement them!


John W. Eaton <jwe>
Group administrator
Mon 28 Aug 2017 06:24:24 PM UTC, comment #5: 

Posted to the mailing list, not the tracker:


Apparently I did not correctly describe the situation.  The error has nothing to do with the linkage function.  If the posted function is on the path (say, in the current directory) and one enters the two lines into the interpreter

max_recursion_depth(512)
TestSum(1:500)

Octave crashes.  This seems like an outright bug if one can kill the interpreter this easily.  I'd be fine with the interpreter producing a warning saying "Octave is not a natural fit for recursive algorithms " or the like, but it shouldn't simply die.

The linkage function works correctly - I only mentioned it because it produces output which is logically a binary tree and so a natural candidate for a recursive treatment. 



John W. Eaton <jwe>
Group administrator
Mon 14 Aug 2017 06:26:04 PM UTC, comment #4: 

Thanks, that's what I was reading into this report as well.

Octave's "soft landing" is the maximum recursion depth. When you intentionally increase the maximum recursion depth, you are taking the safety off and may cause Octave to crash, as shown here.

We do not have a way to recover gracefully from a stack recursion overflow, which is why we have the maximum recursion limit check in place.

As a first easy step, what I would do is add warnings to the documentation of max_recursion_depth that increasing the limit is dangerous and may cause Octave to crash, and also add a warning when the user actually calls the function to increase the current limit.

 Mike Miller <mtmiller>
Group Member
Mon 14 Aug 2017 06:15:18 PM UTC, comment #3: 

A couple of remarks...
1) No, this has nothing to do with the statistics package (beyond providing an example).
2) It seems that legal input that causes the interpreter to crash should be regarded as a bug.  If it signals an error that is caught and allows you to diagnose/continue, that's a reasonable way to deal with the situation.
3) MATLAB has no problems with this code (and provides a &quot;soft landing&quot; when an error does occur).  This argues that the problem is in the Octave implementation and not the language itself.

&gt;&gt; TestSum(1:40000)
ans =
   800020000
&gt;&gt; TestSum(1:90000)
Out of memory. Type HELP MEMORY for your options.

I realize that the Octave maintainers are largely volunteers and have other priorities beyond this sort of thing.  I greatly appreciate their efforts to provide a free and very useful MATLAB like language.  Thanks for the good work!

David Nichols <david_nichols>
Mon 12 Jun 2017 07:06:41 PM UTC, comment #2: 

I don't think this bug is even really about the linkage function, it's about the code that the OP has written to traverse the data that is returned by the linkage function, using a recursive approach. I don't see the linkage function calling itself recursively internally.

Unless the OP can demonstrate that there is something wrong here, maybe the only bug is that the max_recursion_depth function should warn the user that increasing the limit arbitrarily is dangerous and may cause Octave to crash unexpectedly. The reason for this soft limit is to avoid crashes in the first place.


$ ulimit -s 1200
$ octave -W
>>
>> testsum (1:255)
ans =  32640
>> testsum (1:280)
error: max_recursion_depth exceeded
error: called from
    testsum at line 6 column 7

>> # ok, I'll just increase the limit
>> max_recursion_depth (300)
>> testsum (1:280)
Segmentation fault


 Mike Miller <mtmiller>
Group Member
Sat 10 Jun 2017 01:53:46 AM UTC, comment #1: 

Octave is not a natural fit for recursive algorithms.  For those algorithms you might choose a language like Lisp.

However, Octave is no worse than other languages which don't have special facilities for recursion.  In the short term, increase the allowed recursion depth using max_recursion_depth.  The help text for the function is shown below


 -- VAL = max_recursion_depth ()
 -- OLD_VAL = max_recursion_depth (NEW_VAL)
 -- max_recursion_depth (NEW_VAL, "local")
     Query or set the internal limit on the number of times a function
     may be called recursively.

     If the limit is exceeded, an error message is printed and control
     returns to the top level.

     When called from inside a function with the "local" option, the
     variable is changed locally for the function and any subroutines it
     calls.  The original variable value is restored when exiting the
     function.


If that doesn't work then the linkage function should be recoded to reduce or eliminate the recursion.

I've re-titled the bug report to be about the issue with the linkage function.

Rik <rik5>
Group administrator
Fri 09 Jun 2017 10:22:38 PM UTC, original submission:  

Consider the following function, taken from https://stackoverflow.com/questions/25883247/max-recursion-depth-octave.  The function is applied recursively 1+length(X) times to sum over X.
function [ y ] = TestSum( X )
  ## A way to implement 'sum' using recursion
    y = 0;
    if(length(X) >=1)
        y = X(end);
        X(end) = [];
        y = y + TestSum(X);
    endif
end

It works fine for X smaller than the default max_recursion_depth() == 256, e.g. TestSum(1:100) ==>  5050 and correctly complains if the recursion depth is too deep : TestSum(1:300) ==> error: max_recursion_depth exceeded. Increasing the recursion depth helps some :  max_recursion_depth(512); TestSum(1:400) ==> 80200 . However, reasonable values (less than max_recursion_depth() ), for instance TestSum(1:400),  cause the program to crash (or as Windows expresses it, "Stop Working").  No complaint from Octave, just a flat-out crash.

I'm not really interesting in this particular program, but it illustrates the problem I am having.  I'm using the octave forge statistics package 'linkage' function which generates a binary tree as output. Attempts to traverse the tree recursively for even modest sized input (~2000 points - hardly "big data") generate the crash described above.

Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by david_nichols (Posted a comment)
  • -email is unavailable- added by jwe (Updated the item)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by None (Submitted the item)

    •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 12 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2019-02-26 mtmiller Carbon-CopyRemoved 80942 -
    2017-08-28 mtmiller Severity3 - Normal 2 - Minor
        Priority5 - Normal 3 - Low
        Item GroupUnexpected Error or Warning Documentation
        StatusNone Postponed
    2017-08-14 mtmiller CategoryOctave Package Interpreter
        Summary[octave forge] (statistics) linkage function fails at modest recursion depths recursive function fails at modest recursion depths, causes segmentation fault
    2017-08-12 jwe Summarystatistics package linkage function fails at modest recursion depths [octave forge] (statistics) linkage function fails at modest recursion depths
    2017-06-10 rik5 CategoryInterpreter Octave Package
        Item GroupSegfault, Bus Error, etc. Unexpected Error or Warning
        Operating SystemMicrosoft Windows Any
        SummaryRecursion fails unexpectedly at modest depth statistics package linkage function fails at modest recursion depths

    Back to the top

    Copyright © 2024 Free Software Foundation, Inc.
    Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.
    The Levitating, Meditating, Flute-playing Gnu logo is a GNU GPL'ed image provided by the Nevrax Design Team.
    Page source code

    Powered by Savane 3.14-f13d.
    Corresponding source code