How to cache VI ref in recursive chain?

[CoastalMaineBird]

I am writing a recursive VI - a VI that calls itself.
The VI generates an image by recursively subdividing the image rectangle until it finds a rectangle small enough to work on.
(It's a mandelbrot image generator, if you must know... 🙂

It calls itself by opening a VI reference to itself (using OPEN VI REFERENCE), calling that via CALL BY REF, and then closing the reference.
These calls might get to a level of 20 or 25 deep.

It works. 100 %.

In thinking that I could speed it up a bit, I tried to cache the VI reference. I was thinking that each OPEN VI REF was having to do a whole bunch of stuff. If I could just open the reference once, and store it, then I wouldn't have to do all that stuff every time.

So I tried that. I opened the reference ONCE, and stored it in a global variable. When I need to recursively call myself, I used that reference.

No Go.

The recursive call returns an error message:

Error 1042 occurred at Call By Reference Node 
in Calc Mandel Rectangle.vi
->Calc Mandel Rectangle.vi
->Get Mandelbrot Image.vi
->Mandelbrot Test.vi

Possible reason(s):
LabVIEW:  Attempted recursive call.

Notice that the error occurs on the SECOND level down, not the first.
My hypothesis is that a ref to a VI running at level 1 is DIFFERENT from a ref to the same VI called from itself (running at level 2).
I compared the global ref to a local one, and it said they were different.
When you generate the ref each time, it accounts for this, but when you stash the ref before the first call, it is only valid for the first level.

I have tried opening the reference with OPTIONS = 8, which is supposed to mean prepare for recursive call, but that makes no difference.

I'm on LV7.1, OS X.

QUESTIONS:
1... Is there a way to stash a VI ref so that it applies to any level?
2... Does the OPEN VI REF function take enough time to worry about?
3... Is there something I am missing in this approach?

Message Edited by CoastalMaineBird on 01-24-2006 12:36 PM

[JeanPierre]

1. No. each level of recursion must open a separate VI reference to work with a new instance of the VI.
2. The VI is already in memory so the time penalty is less severe to reinstanciate it than to open it from file. However if you recursively call
the VI in a loop, you can open a VI reference outside the loop and reuse it in the the loop, closing it afterwards outside the loop.
Usually when the user doesn't notice, I don't worry about time optimization.
3. Recursion in LabVIEW is not very efficient. There is always a way to code your VI in such a way that
it doesn't use recursion by building a data stack (data for each level in an array stored in a shift register of your loop).

Message Edité par Jean-Pierre Drolet le 01-25-2006 08:41 AM

[shoneill]

I agree with Jean-pierre,

Code around the fact that LV basically doesn't have proper recursiveness and you'll be happier methinks.

I've done this in the past with exactly such a data stack as Jean-Pierre suggests.  You DO need to sit down and think about the implementation first though, otherwise it'll come back to bite you (in the a**).

Shane

[unclebump]

You can use a queue to hold the recursive data. I used this to do a recursive search for all files on the hard drive.

[CoastalMaineBird]

1. No. each level of recursion must open a separate VI reference to work with a new instance of the VI.

OK, that's what I surmised by observation. Since the error message came from TWO levels deep, it seems that the first level was OK, but it choked when trying to go deeper.

2. The VI is already in memory so the time penalty is less severe to reinstanciate it than to open it from file.

This is true if you DO NOT CLOSE it. Normally I'm in the habit of closing the ref when I'm done with it. In this case, I would subdivide a rectangle into 4 quadrants, open a ref, call myself 4 times, and close the ref. If I omit the CLOSE part, the time penalty is substantially reduced (probably because the next OPEN REF re-uses the same info).

However if you recursively call the VI in a loop, you can open a VI reference outside the loop and reuse it in the the loop, closing it afterwards outside the loop.

Yes, I was doing that. But the CLOSE function apparently causes the next OPEN REF to have to do all the work over again.

Usually when the user doesn't notice, I don't worry about time optimization.

Sensible, but when a C version produces a picture in about 1/100 the time, I would call that noticable. And I am trying to produce a QuickTime movie of these images, so I'd like to generate them as fast as possible.

3. Recursion in LabVIEW is not very efficient.

I am coming to realize that. I have used it to delete a disk folder hierarchy, and to traverse a VI and its children, and its children's children, etc., but I wasn't concerned with speed in either case. Now I am.

There is always a way to code your VI in such a way that it doesn't use recursion by building a data stack (data for each level in an array stored in a shift register of your loop).

I will look into that. This project was intended to introduce my apprentice programmer to the idea of recursion, and it's an elegant use of it in theory. However in practice, it's dog slow.

Thanks for your thoughts.

[CoastalMaineBird]

Code around the fact that LV basically doesn't have proper recursiveness and you'll be happier methinks.

Yeah. Unfortunately, this was intended as a tool to introduce the concept of recursive procedures to my apprentice programmer.

I suppose his joy will be increased when he discovers real recursion in a C program later on...

In the meantime, I guess his next task will be "alternative ways to solve a problem". 😆

Thanks for your thoughts.

[shoneill]

This begs the question of course as to WHEN LabVIEW will finally support proper recursiveness.

I admit that there are certain situations when recursiveness is good (I'm not a fan of it in general as I believe there's always a way to do it which doesn't require it, but maybe I'm just LVing too long).  And I agree, 100 times slower IS noticeable.

There must be a way to get "proper" recursiveness in LV.  I mean we have temnplates and whatnot......

LV 8.1?  9?

Shane.

[JeanPierre]

Ok I see what you mean. VI ref has to be reopened for each branch of the recursion tree.
I've attached a recursive VI that caches as much as VI references as needed and reuse them instead of closing them.
The total number of VI ref opened is the number of different VI ref needed for the deepest level.

[JeanPierre]

I have encapsulated the cache management for easy reuse.

[CoastalMaineBird]

For anybody who cares, I have attached a version of my code which includes BOTH the recursive method, and the stack-based method.

Unfortunately (and surprisingly), the stack-based method is considerably slower than the recursive method.

Timings for the default picture:

OS X + LV 7.1.1 on 2x2.0 GHz G5:
Stack :  1083    1082   1083  mSec
Recursive:  687   689   690   mSec

Win2k + LV 7.0 on 1x 1.5 GHz P4:
Stack :  1373    1410   1392  mSec
Recursive:  1064   1037   1064   mSec

Apparently, the memory-management requirements of the queue take longer than the VI-ref management of the recursive method.

Comments?