Forums > Max For Live

How many loops before a stack overflow?

November 8, 2013 | 12:56 pm

A stack overflow occurs when your code gets caught in an infinite loop. But obviously Max doesn’t go through the loop an infinite number of times to figure that out. So at what number of loops does it stop and declare a stack overflow? In my experience it seems to be about 128 times. What if I need a section of code to execute over 128 times consecutively to perform a task? In the patch i’m working with this happens in rare circumstances. I need to measure the width of the highest plateau in the table in the pic i’ve attached. The plateau in that screenshot was unusually wide (and a height of only 1; it happened right away.) Any suggestions? Comments?

Attachments:
  1. stack-overflow

November 8, 2013 | 2:44 pm

If you need to do something repeatedly and quickly, you should probably think about structuring it imperatively and using Uzi to drive it instead of doing it recursively. It will be much better behaved.


November 8, 2013 | 5:24 pm

yeah. Good thing is, it looks like an uzi would sit nicely in this patch instead of counter and the [if], more or less.


November 8, 2013 | 11:45 pm

simple question, simple answer. how often? that depends on the processing power of the host computer.

i would ALWAYS try to avoid to program it without uzi, you never know when you want to reuse yoour code on another hardware or in another patch. just as with right to left order, one should make sure that code is 100% safe.

-110


November 9, 2013 | 12:00 am

As Peter pointed out, max is not good at recursion. With the dump message to table, all values are produced. If then you track at which indices values go from 0 to 1 and back to 0, and subtract those values, you find width. I hope I understood the problem well.

<code>

– Pasted Max Patch, click to expand. –

</code>


November 9, 2013 | 3:24 pm

Thanks, i knew there had to be a better way!

@JVKR Yes. I think dump is the way to do it. Not only should it take care of the rare stack overfow, it should speed up my patch overall.


November 9, 2013 | 7:20 pm

btw i don’t think max would go through a specific number of iterations before flagging a stack overflow– stack overflow means that it has run out of a particular amount of working memory which is reserved for storing the recursive function that causes the overflow– so it depends on how much memory the function uses and how much memory the application or operating system has reserved for the ‘stack’. so it might iterate through the recursion a handful of times, or millions of times and there’s no way of knowing.


November 13, 2013 | 12:37 pm

ok. I finally have the time to sit down and work on this. I’m looking to implement the dump method, but i have a question. JVKR, your example is helpful, but what i need is a little more complicated than that. I need to measure the width of the first highest plateau. With a little effort I think i could throw a [maximum] into the flow of the dump and make it work, but sending the table a max message would be a lot easier. My question is this:

Does sending the max message mean, basically, that the patch is instituting its own dump in order to find that max value and effectively doubling the amount of work taking place? Would it be more efficient for the program if i took the effort to work a [maximum] into the one dump?

PS the table usually looks more like the attachment. (How do you do that PASTED MAX PATCH thing?)

Attachments:
  1. Untitled

February 16, 2014 | 6:07 pm

It looks like the dump method is far less efficient after all:

<code>

– Pasted Max Patch, click to expand. –

</code>

[EDIT: fixed a couple things in DUMPLATEAU, used cpuclock to time]


February 16, 2014 | 6:13 pm

But, as advised, it does not cause a stack overflow.


February 16, 2014 | 8:04 pm

Sooooooooo, I realize this thread is way old but,

@Wetterberg I’d like to try to arm this thing with an uzi, so as to avoid stack overflow and also keep it efficient, but I really can’t see how. Isn’t recursion necessary when the number of iterations is variable? I mean, I have no way of knowing how many bullets to put in my uzi…


February 17, 2014 | 2:00 am

I think you do need to use recursion– just use deferlow to avoid stack overflow

here’s a version which uses recursion with deferlow:

<code>

– Pasted Max Patch, click to expand. –

</code>
probably not very efficient, but you may be able to adapt it to your needs


February 17, 2014 | 2:37 am

You can always re-write recursion as iteration. Always. No exceptions. Recursion can sometimes be more convenient, or more elegant, or more compact. But it is always possible to do it the other way.

This is not just saying "I’ve always found a solution, so you ought to as well." This is saying "the two techniques can be mathematically proven to be equivalent in all situations." (Note, btw, that there is an iterative solution to Tower of Hanoi, so I’m not just talking in the abstract.)

One minor clarification: stack overflow is not dependent on "processing power" per se. It’s simply a question of how much memory is allocated to the stack. Every function call (i.e., every message through a patch cord in Max) needs some amount of stack memory, and that memory is occupied until the function returns. So, every time a message goes through a patch cord, and triggers another message through another patch cord, and that triggers another message, and so on and so on, all take up stack memory until all the messages have been processed.

The thing with the defer family of objects is that they don’t send messages directly; they put the message into the scheduler queue for some time in the future. That "time in the future" may be "as soon as possible" (i.e., 0 msec delay), but the message still goes onto the scheduler queue — which is not stack memory — so it doesn’t get called until the stack has been cleared.

I don’t know precisely how Max (or the OS) decides how much memory to allocate to the stack (I did once, but that was when there was much simpler memory model in the OS)… it is possibly a function of how much wired memory is available. But, yes, it can vary from machine to machine, so watch out.

To fp’s question: Max knows there’s been a stack overflow when the stack overflows. It doesn’t have to pass an infinite number of messages, it just passes enough messages for the stack to be at (or near) it’s maximum capacity. That’s why it sometimes takes just a moment for the stack overflow to happen. It doesn’t actually take an infinite recursive loop to cause stack overflow; a patch just has to recurse often enough for the stack to run out of memory.

As for Sun’s question about variable Uzis: you can send an integer to uzi’s left inlet. That help?


February 17, 2014 | 4:19 am

… and, just for fun: you can get a stack overflow even without recursion – you just need a long enough chain of objects… try this ;)

https://www.dropbox.com/s/ps0fvnfoouitvev/overflowerpower.maxpat.zip

aa


February 17, 2014 | 4:41 am

… and, just for fun:

ok, so my machine overflowed at somewhere between 50000 and 60000 additions


February 17, 2014 | 4:52 am

Hahaha, that’s some efficient and clean programming right there :D
btw, re : the scheduler queue ; can a queue be divided into multiple stacks ? I mean, if this is a veryyyy long queue with a lot of deferred instructions, and all of it does not fit into just one stack ?
hm deferlow seems to be able to do just that – well not really, you really need to place it at the good place

http://www.mediafire.com/download/i0m66kixvx84b7i/everflowers.zip

(first time i compress a file from 118 Mo to 1,4 Mo ; then compressing two 1,4 Mo compressed files result in a single 397 Kb file)


February 21, 2014 | 6:00 pm

Thanks yall, lotta good stuff here to mull over.


February 21, 2014 | 10:53 pm

you named it, mr. and ms. stackoverflow are the reason why you should try to code as economic as possible for everything which is later needed for a realtime process.

and for everything else there is [defer], which lets you perform "infinite" loops.


February 23, 2014 | 3:11 pm

Just fixed one of my stack overflow issues; it looks like it was being caused by a [deferlow]. My patch has quite of bit of recursion in it, in fact the entire thing is basically one giant FOR loop which executes every time a midi note-on is received, searching for patterns in rhythm. Because of all of this analysis, the audio processing itself was actually being compromised (pops and clicks occurred) and i had placed a [deferlow] just before the beginning of the primary FOR loop to alleviate this. Now i come to realize that this is apparently the cause of certain intermittent stack overflows which were inevitably occurring after no predictable amount of time. If i understand correctly i’d say that, while in some cases, such as the one i first outlined in this thread, [deferlow] can help take strain off the stack, deferring some processes until the stack clears, if there is just too much going on the whole thing can get clogged up anyway? In this case would it be that too many processes were accumulating in the scheduler queue and when it came to the point that it needed to relieve itself, it overflowed the stack?


February 24, 2014 | 5:41 pm

I also am able to eliminate the stack overflow mentioned in the previous post by reworking a smaller portion of the patch, replacing some recursion with an uzi.

<code>

– Pasted Max Patch, click to expand. –

</code>

However the iteration seems to be giving me some really unstable numbers in my measurements for whatever reason. So for now at least i guess i can’t call it any kinda solution..


Viewing 20 posts - 1 through 20 (of 20 total)