wait 0 millisecs and recursion

[neville]

I am writing a board game and need to use a deeply recursive algorithm to evaluate a position. Someday someone must explain the mysteries of recursion in LC: I tested a very simple recursive call to a function with just two integer parameters, which runs into the recursionLimit of 400000 after just 400 or so iterations, or 1000 iterations for recursionLimit 1000000 (stack size 1k for each call??) -- but my much more complex algorithm with 4 parameters including a string easily gets up to 28000 iterations, no sweat. This is LC 7.1.1, MacOS 10.11.

However as the iteration proceeds you can watch the memory for the app rising steadily in the Xcode debugger view, as no doubt it should with each successive function call. But the memory is not returned when the recursion finishes. Almost sure this is a memory leak, the Leaks instrument certainly reports a leak at this point though I am not entirely sure if this is caused by the recursion as LC has its own unrelated memory leaks (try testing for leaks as you launch LC, before opening any user stacks).

But this is not my question for today! From various posts it appears that inserting a "wait 0 milliseconds with messages" before "end repeat" is a good idea for long tight loops -- maybe that would give LC an opportunity to do some garbage collection, though I don't actually have a repeat loop, and anyway it seems like a good idea to allow the user to stop a long operation. However inserting a wait anywhere in the recursive function not only does not change the haemorrhaging memory but -- and here is my problem and question -- at the end of the recursion the stack is left in a strange state where all controls in the content window of the stack are unresponsive as if the screen is locked. A mouse click in the stack title bar, or in any other LC window or outside LC returns the stack to life. Does anyone have an explanation for this state?

[FourthWorld]

Any repeatable recipe for a memory leak should be submitted with a bug report so the team can address it:
http://quality.livecode.com/

As for "wait 0 with messages", that was a workaround needed on OS X in earlier versions of LiveCode to accommodate an anomaly in the Mac redraw subsystem; it should never have been needed on any other platform, and with recent LiveCode builds should not be needed at all.

Moreover, "wait 0 with messages" only offers the ability to relinquish control to the OS event loop, and should not affect recursion one way or another; it's scope is limited to redraw and event handling, but should not affect the logic of a loop in which it's present.

That said, it's possible that the loop may be affected by other events that get processed when the OS event loop is handled. So for the core question about the "strange state" after the loop, like most things in programming we won't be able to answer that until we see the code. If you could post the relevant portions (within bracketed "code" tags so it reads better please) we can review that to determine what's going on.

[neville]

Many thanks Richard

I have already submitted to QC the bug concerning a leak on LC launch [Confirmed bug 16943].

Concerning what I suspect is a bug on memory for function stacks not being released when the event loop is not being called often enough, the code I have is far too complex to offer for analysis, I am trying to isolate the bug so I can construct a simple stack which I will submit to QC.

As for my question about wait 0, thanks, I didn't know its history and am happy to know it isn't needed. It is however strange that it results in the unresponsive state --- of course I agree it's impossible for anyone to try to debug without seeing the code, code which is too complex to show here, but I was thinking maybe someone had seen this state before and might have a clue. My current guess is that wait 0 causes a transfer of processing to another thread which has somehow died because of the other (putative) bug.

Oh, and disregard the nonsense in the first para in my original post about the mysteries of recursion. Not so mysterious: my algorithm is processing 28000 nodes in a game tree, but at any time has only a recursion depth of less than 10. Duh!

[neville]

OK I've set up a very simple stack calling a very simple function recursively to a depth of 400, and watch using the Xcode tool Leaks. It does indeed show a memory leak when the recursion finishes.

But actually it shows a memory leak if you do any editing on the stack! Dragging the button I already knew would cause a leak [bug 16893]. But clicking the field to select it also causes a leak!! This seems so unlikely that I begin to wonder if Leaks is actually working correctly; but there is steady increase in the memory footprint on each reported leak.

I will submit to QC.

LeakTest.livecode.zip

(1.07 KiB) Downloaded 162 times

Stack has one button "button" and one field "field"

Button script is

Code: Select all

global s

on mouseUp
   put 0 into s
   put empty into fld "field"
   put "alpha" into a
   put "beta" into b
   put doRecurse (a,b)  after fld "field"
end mouseUp

Card script is

Code: Select all

global s
function doRecurse @a,@b
   add 1 to s
   put s into fld "field"
   if s = 400 then return " done"
   else 
      put a into c
      put b into a
      put c  into b
      return doRecurse(a,b)
   end if
end doRecurse

[jacque]

return doRecurse(a,b)

Using "return" here is a bit nonstandard. Does the leak occur if you simply call the handler again without it?

[neville]

doRecurse() is a function so must return a value; doesn't compile without the return. But you do have a point - I wrote this example as a function because that what my actual code uses, using procedures and storing the final value somewhere rather than returning on the stack could conceivably make a difference. Unfortunately no, it doesn't.

[jacque]

You're right, but there is already a return statement when s = 400. I meant the second instance, which I might have done this way:

Code: Select all

    global s
    function doRecurse @a,@b
       add 1 to s
       put s into fld "field"
       if s = 400 then return " done"
       else
          put a into c
          put b into a
          put c  into b
          get doRecurse(a,b)
       end if
    end doRecurse

It doesn't sound like that will change things though.

I'm still pretty impressed with how you're tracking down these leaks. It's bound to help all of us.

[neville]

That's neat. I don't think I have ever used get!

I wouldn't be surprised if the leaks have nothing specifically to do with recursion, but are all instances of just one leak in the event handling code.

[[-hh]]

Hi,

this is an interesting test and an interesting test method.

I did a year before a similar recursion test for the recursion limit.
I now rewrote my testfunction to your testcase of interchanging parameters (not using @-constructs below).
Because memory needed for recursion also depends on the number of parameters, I used it in sum in the following way.

Code: Select all

function doRecurse x,s,a,b
  add 1 to s
  if s < x then return doRecurse(x,s,b,a)
  else return "done"
end doRecurse

on mouseUp
  put "running" into fld "field"; put the millisecs into m1
  lock screen; lock messages; set recursionlimit to 1000000
  put doRecurse (1000,0,"alpha","beta") into fld "field"
  unlock messages; unlock screen
  put space & the millisecs - m1 after fld "field"
end mouseUp

Here, the example runs (pretty fast), without a memory leak on Mac OS 10.11.3 with LC 7.1.2-rc2.
It's just increasing memory usage when running.

Then first throws errors and eventually crashes immediately when going too high with the recursions, as you describe.

[neville]

My code wasn't crashing, just bleeding memory (my game does crash when the used memory gets into the gigabyte range of course). I admit I haven't tried 7.1.2-rc2 - maybe it's all fixed there - QC was working on fixing the first leak concerning drag, and it could be that fixed everything! Will do so now.

The reason I set just 400 as the number of iterations in my example was that for the default recursionLimit of 400000 you hit that ceiling with slightly more than 400 iterations --that's with just the two parameters. With a recursionLimit of 1000000 you hit it at just over 1000 iterations. You see the pattern ... suggesting that the parameter stack size and whatever else needs to be set up for the function call is about 1k. I used the call by reference @ to see if it would reduce the parameter stack size if just pointers were used rather than passing two full strings, but I don't think it makes much difference.

[neville]

Sadly -hh, in my testing all the leaks (or maybe *the* leak) are still there in 7.1.2-rc2 - on LC Launch, on drag and on my recursion (So why doesn't your code leak? only difference I can see is you lock screen and messages...)

[[-hh]]

Yes, I noticed that too, it happens simply later on. I think the "recursion-problem" is not fixed in LC 7.1.2, and it's not fixed in LC 8.0.0-dp14.

That's why I used 2 parameters (x,s) and not only the difference x-s, because it's probably not proportional.
If you simply multiply the recursionlimit and the num of recursion by 10, starting with 400 and 400000, then -- if proportional -- it would be non-crashing as long as you have enough RAM.
But it's increasing faster to the crash, it crashes immediately on mouseUp, in my example already with 10000 and 10000000, what should be no problem with 7GB of free RAM.

=======

Another way to test memory leaks is to create large "files" in RAM.

Code: Select all

on mouseUp
  put the millisecs into m1
  put "0" into x
  repeat 29  # <-- we change here the power p of 2, p=30 yields 1 GByte
    put x after x
  end repeat
  put space & len(x) &": "& the millisecs-m1 into fld "field"
  -- put x into url("file:/Users/admin/Documents/test.txt")
end mouseUp

I test this regularly with new LC versions and a 1 GB string, that is a power of 30. This is really fast. Of course, writing such a large file from RAM needs some time, depends also on disk speed. The next step, a power of 31, is usually a crash.

Here my results:

• LC 6.7.9-rc2 writes [use p=30]
  1 GB (2^30 = 1073741824 Bytes) in < 1700 ms, 2^31 exits clean, throws an error.
• LC 7.1.2-rc2 writes [use p=29]
  500 GB (2^29=536870912 Bytes) in < 700 ms, crashes with 2^30
• LC 8.0.0-dp14 writes [use p=30]
  1 GB (2^30 = 1073741824 Bytes) in < 1700 ms,
  2^31 cheats = it pretends to do it but doesn't do it and crashes if it should write the file.

You may test this by yourself and add this to your report if you wish, I stopped writing QCC reports today. I wrote a lot of reports and the waiting queue is now too long for me.

Thanks for working out in such an effective way these memory problems. Good to have you here.

Please tell us when there are news to that issue.

[neville]

Confirmed by Quality Control [bug 16947]. Still present in 8.0-DPx