22
$\begingroup$

Consider the following code snippet:

NestWhile[{#[[1]]+1,Pause@.001;ConstantArray[0,{100, 100}]}&,
  {1}, (#[[1]] <= 10000) &, 2]

In theory, when evaluating, NestWhile shall keep track of the last two results generated, thus consuming approximately 160kB of memory.

However, in reality, memory consumption will continue to grow at a pace of approximately 80MB/s before NestWhile finishes calculation. Furthermore, regardless of the fourth parameter (as long as it is not 1), the speed of memory consumption is the same. These two phenomena indicate that Mathematica evaluates the expression and stored all results in memory until all computations are finished then picks out last two elements.

This behavior is rather disturbing for me: why save the previous evaluation results in memory if they are used in nowhere?


This behavior exists in v12.0 and v11.2


Update

Received reply from technical support which said:

This behavior of storing all intermediate steps of a calculation is intended. Clearing intermediate information that has been stored can be done with the command ClearSystemCache[]

However, after altering the code to:

NestWhile[(ClearSystemCache[]; {#[[1]] + 1, Pause@.001; ConstantArray[0, {100, 100}]})&,
  {1}, (#[[1]] <= 10000) &, 2]

still cannot stop fast increasing memory consumption during evaluation.

Furthermore, a new observation, when evaluating this piece of code, Mathematica will eventually consume 99% of memory, but will not try to use virutal memory. So theoretically this behavior will not influence the performance of Mathematica, however, if I open another program, Mathematica will encounter memory related issues sometimes and crash. But by all means, I think consuming all memory is not a good choice.

Also, if Mathematica actually saves all these intermediate steps for acceleration of evaluation, then why Mathematica do not store them when the fourth argument is 1? I'm still a bit confused with this reply...


Update 2

Received another reply from technical support after explaining that clearing cache will not help and this behavior did no good to any evaluation while causing memory explosion.

I have sent a suggestion report to the appropriate people in our development team so changes to how NestWhile handles memory can be considered for future versions of Mathematica.

Hope this bug can be fixed in the next version of Mathematica...

Now, before this problem is solved by Wolfram officially, let this question be:

"How to implement a efficient myNestWhile which works exactly as NestWhile?"

$\endgroup$
  • 3
    $\begingroup$ To watch the memory being used, add a Monitor with Monitor[NestWhile[{#[[1]] + 1, Pause@.001; x = MemoryInUse[]; ConstantArray[0, {100, 100}]} &, {1}, (#[[1]] <= 10000) &, 2], x] $\endgroup$ – Roman Jun 9 at 19:16
  • 2
    $\begingroup$ My rather uneducated guess would be that NestWhile has been implemented through NestWhileList. If you record the x values for both versions (with NestWhile and then with NestWhileList), and plot their differences, the result is pretty much a constant of size 185Kb in favor of NestWhile (while the absolute numbers are hundred of Mbs). In other words, their memory consumption patterns are exactly the same. $\endgroup$ – Leonid Shifrin Jun 10 at 0:06
  • 3
    $\begingroup$ @Wjx I agree that this behavior is totally not desirable. My guess is that this was the easiest way to ensure that NestWhile and NestWhileList are fully consistent with each other, since they share the same code path. I will make an internal suggestion to do something with this (chances are that this issue is already known internally and is on someone's todo list). $\endgroup$ – Leonid Shifrin Jun 10 at 8:19
  • 1
    $\begingroup$ Maybe contact support and suggest an improvement? Clearly, it doesn't need to be this way, but implementing it like this is much easier considering what the 4th and 6th arguments do. $\endgroup$ – Szabolcs Jun 10 at 8:20
  • 1
    $\begingroup$ @Gladaed No, this is specific to NestWhile. The concept doesn't even apply to other functions ... $\endgroup$ – Szabolcs Jun 11 at 12:53
8
$\begingroup$

This works without hogging memory:

nestWhile[f_, expr_, test_, m_Integer:1, max_:∞, n_Integer:0] /; m>=1&&n>=0 := 
  Module[{c = m - 1, r = NestList[f, expr, m - 1]},
    While[test @@ r && c++ < max, r = Append[Rest@r, f@Last@r]];
    Nest[f, Last@r, n]]

In contrast to the real NestWhile, the above does not implement the following:

  • NestWhile[f,expr,test,All] supplies all results so far as arguments for test at each step.
  • NestWhile[f,expr,test,{mmin,m}] does not start applying test until at least mmin results have been generated. At each step it then supplies as arguments to test as many recent results as possible, up to a maximum of m.
  • NestWhile[f,expr,test,m,max,-n] returns the result found when f had been applied n fewer times.

Suggestions and improvements highly welcome!

$\endgroup$
  • $\begingroup$ I fear that this might have certain impact on the performance of NestWhile? My simple test using code nestWhile[# + 1 &, 1, #2 < 1000000 &, 2]; // Timing shows that this code is approximately three times slower than the original NestWhile. So maybe there's still room for improvements. $\endgroup$ – Wjx Jun 21 at 5:32
  • $\begingroup$ Furthermore, I'm shocked by the insanely slow speed of NestWhile, in comparison, Nest[# + 1 &, 1, 1000000] only takes 11ms. a 100 times decrease in performance... $\endgroup$ – Wjx Jun 21 at 5:33
  • $\begingroup$ @Wjx I've made some minor speed improvements, but at the core I think that my rewrite of nestWhile is simply much slower than NestWhile. When the functions f and test are a bit more complex, this overhead won't matter much. $\endgroup$ – Roman Jun 21 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.