LabVIEW
Recursion
Hi Kevin,
I've used recursive VIs extensively mainly to explore, parse and modify tree-structured data such as XML, JSON, LabVIEW variants, Tree Control items, formula expressions, GObjects with VI Scripting, etc... so here are some insights:
@Kevin_Price wrote:My thinking is that recursion often (usually?) involves maintaining internal state in the higher level clone as it "calls itself" as a lower level clone. Thus, I'd expect that shared clones could lead to real trouble.
Each time the recursion goes one level deeper, LabVIEW pulls a new clone from the pool because the previous clones are locked by the higher levels in the recursion. So no risk to mix data spaces in the same recursion cycle. The only way to mix data is if your VI can maintain states between executions (with Uninitialized Shift Registers, First Call? nodes, by storing data in Controls, …) and you inherit old data from a previous recursion cycle. But this pitfall is global to shared clones reentrancy, not just recursive VIs.
@Kevin_Price wrote:On the other hand, I don't think I have a good working theory for how preallocated clones can properly deal with the "unknown number" issue.
If your recursion cycle only consists of one VI calling itself, then you have no other choice than using shared clones for the reason I explained previously.
If however your recursion cycle has multiple levels like A -> B -> C -> A -> B -> C... , only one VI needs to use shared clones. The other(s) can use pre-allocated clones. They will be pre-allocated when the shared clone is allocated. The VI that uses reentrant shared clones is actually only here to prevent an "infinite pre-allocation loop".
Actually LabVIEW will tell you exactly this in case there isn't at least one reentrant shared clones VI in your recursion cycle:
"You must have a VI that uses shared reentrancy or dynamic dispatching in any recursive cycle. For recursive calls to work, all VIs in the cycle should be reentrant and at least one must use dynamic dispatching or shared reentrancy."
@Kevin_Price wrote:I toyed with a little recursion once upon a time, but mainly just for kicks. I think that back at that time, I only *ever* chose preallocated clones (or perhaps it was before the shared clone option even existed?).
I have not known the time when shared clones reentrancy did not exist, but I know recursion was done by calling reentrant VIs dynamically (by reference). This is, I think, what LabVIEW does internally with reentrant shared clones, plus managing a pool of already allocated clones that can be reused for better performance.
Regards,
Raphaël.
@BertMcMahan wrote:
Might be helpful- there's some good discussion in this thread.
That was AWESOME.
I have used recursion a few times. It can be easier to deal with as one does only need to look at the single recursion level and everything else solves itself then. However I find that I much prefer to do such algorithms with some stack based implementations in a loop shift register usually. It requires a bit more of work and brain matter to maintain the stack properly across multiple loop iterations, but it very quickly is much more memory conservative than simply doing all as a recursive chain, especially if the recursion can go many levels deep.
wiebe@CARYA wrote:
@Kevin_Price wrote:On the other hand, I don't think I have a good working theory for how preallocated clones can properly deal with the "unknown number" issue.
Quite simplistically I think.
The code executes. When it calls a subVI, if it's a clone it allocates dataspace for a pre-allocated clone or re-uses dataspace for a shared clone if one is available. Repeat until done.
Actually for pre-allocated clones the data space is allocated at loading/starting to run the code. That is why it can't work in a recursive algorithm since LabVIEW can't know at load/initialization time how deep the recursion will go. That is only known at run-time.
With shared clones LabVIEW creates an initial pool of dataspaces and when that gets exhausted it will extend that pool as needed. Most likely it starts with a low number of dataspaces, something like 4 or 8 and then each time the pool gets exhausted it doubles its size. This is the same principle it uses for autoindexing array output tunnels on while loops, as it can't know in advance how many times the while loop will execute. Since memory allocations are relatively high cost in performance, you want to minimize that as much as possible, but pre-allocating everything for 1024 or more elements when eventually only 1 or 2 might be needed is an enormous waste of memory resources too.
@rolfk wrote:
wiebe@CARYA wrote:
@Kevin_Price wrote:On the other hand, I don't think I have a good working theory for how preallocated clones can properly deal with the "unknown number" issue.
Quite simplistically I think.
The code executes. When it calls a subVI, if it's a clone it allocates dataspace for a pre-allocated clone or re-uses dataspace for a shared clone if one is available. Repeat until done.
Actually for pre-allocated clones the data space is allocated at loading/starting to run the code. That is why it can't work in a recursive algorithm since LabVIEW can't know at load/initialization time how deep the recursion will go. That is only known at run-time.
With shared clones LabVIEW creates an initial pool of dataspaces and when that gets exhausted it will extend that pool as needed. Most likely it starts with a low number of dataspaces, something like 4 or 8 and then each time the pool gets exhausted it doubles its size. This is the same principle it uses for autoindexing array output tunnels on while loops, as it can't know in advance how many times the while loop will execute. Since memory allocations are relatively high cost in performance, you want to minimize that as much as possible, but pre-allocating everything for 1024 or more elements when eventually only 1 or 2 might be needed is an enormous waste of memory resources too.
I agree that's probably the reason for disallowing recursive pre-allocated clones.
I think it would be technically possible to have pre-allocated clone A call itself, (by actually allocating data space for each call) except that LabVIEW doesn't allow it.
You can in fact call pre-allocated clone B in shared clone A, and call A in B, creating an unknown level of recursion, and an unknown number of pre-allocated clone B's.
So I don't see why it wouldn't be (technically) possible to have an unknown number of pre-allocated clones in a recursive algorithm directly. LabVIEW disallows to do this directly, but if you use a shared clone level between pre-allocated levels it is already possible.
Search LabVIEW like a graph!
@JÞB wrote:
@rolfk wrote:
wiebe@CARYA wrote:
@Kevin_Price wrote:On the other hand, I don't think I have a good working theory for how preallocated clones can properly deal with the "unknown number" issue.
Quite simplistically I think.
The code executes. When it calls a subVI, if it's a clone it allocates dataspace for a pre-allocated clone or re-uses dataspace for a shared clone if one is available. Repeat until done.
With shared clones LabVIEW creates an initial pool of dataspaces and when that gets exhausted it will extend that pool as needed. Most likely it starts with a low number of dataspaces, something like 4 or 8 and then each time the pool gets exhausted it doubles its size.
Not quite, LabVIEW allocates 1 clone per CPU core at a minimum during launch, creating those dataspces is a minimum launch overhead (so, if you have a 32 core machine and the Clone dataspace is large you cannot save time or memory by telling LabVIEW that you only need 2 clones. You'll get 32 in the initial pool)
Whenever a Clone is released it is returned to the pool and restored to a first call True State
If the pool is exhausted when a new clone is needed a new clone is added to the pool 1 by 1 in a time consuming process.
Clones are never destroyed until all callers complete and are idle.
The clone pool may be extended at any time using the preallocate clones method. Usually you would bury this lengthy process in your startup time. You can preallocate any number of clones between the number of CPU cores ( this is a hard lower limit and LabVIEW Coerces any integer less than # of cores) and the available application memory constraints. It will take a goodly amount of time to try allocating big# of dataspaces but eventually you can force a not enough memory error with the preallocate clones method.
And again, all of that information is available in the Help file just by clicking the Help button on the VI Execution Properties configuration page.
Any tests, resources or experiences to back this up?
VI Server isn't worth anything for this, and Heap Peak doesn't help at all.
From your story I suppose the only way is to make clones allocate huge amounts of (static?) memory and then watch LV's memory usage?
You don't distinguish (enough for me to follow you) between pre-allocated and shared clones. Rolfk mentioned shared clones, but you seem to be talking about pre-allocated clones, or both (I can't deduct from what you say).
I personally don't see what CPUs has to do with this, but LV also links parallel for loops to CPUs without a good reason, so it might be similar silliness.
@JÞB wrote:
@raphschru wrote:
Hi Kevin,
I've used recursive VIs extensively mainly to explore, parse and modify tree-structured data such as XML, JSON, LabVIEW variants, Tree Control items, formula expressions, GObjects with VI Scripting, etc... so here are some insights:
@Kevin_Price wrote:My thinking is that recursion often (usually?) involves maintaining internal state in the higher level clone as it "calls itself" as a lower level clone. Thus, I'd expect that shared clones could lead to real trouble.
Each time the recursion goes one level deeper, LabVIEW pulls a new clone from the pool because the previous clones are locked by the higher levels in the recursion. So no risk to mix data spaces in the same recursion cycle. The only way to mix data is if your VI can maintain states between executions (with Uninitialized Shift Registers, First Call? nodes, by storing data in Controls, …) and you inherit old data from a previous recursion cycle. But this pitfall is global to shared clones reentrancy, not just recursive VIs.
@Kevin_Price wrote:On the other hand, I don't think I have a good working theory for how preallocated clones can properly deal with the "unknown number" issue.
If your recursion cycle only consists of one VI calling itself, then you have no other choice than using shared clones for the reason I explained previously.
If however your recursion cycle has multiple levels like A -> B -> C -> A -> B -> C... , only one VI needs to use shared clones. The other(s) can use pre-allocated clones. They will be pre-allocated when the shared clone is allocated. The VI that uses reentrant shared clones is actually only here to prevent an "infinite pre-allocation loop".
Actually LabVIEW will tell you exactly this in case there isn't at least one reentrant shared clones VI in your recursion cycle:
"You must have a VI that uses shared reentrancy or dynamic dispatching in any recursive cycle. For recursive calls to work, all VIs in the cycle should be reentrant and at least one must use dynamic dispatching or shared reentrancy."
@Kevin_Price wrote:I toyed with a little recursion once upon a time, but mainly just for kicks. I think that back at that time, I only *ever* chose preallocated clones (or perhaps it was before the shared clone option even existed?).
I have not known the time when shared clones reentrancy did not exist, but I know recursion was done by calling reentrant VIs dynamically (by reference). This is, I think, what LabVIEW does internally with reentrant shared clones, plus managing a pool of already allocated clones that can be reused for better performance.
Regards,
Raphaël.
Exactly. And completely in agreement with what the LabVIEW Help file topic on the concept of Reentrant calls contains.
It's amazing how well named the "LabVIEW Help" file is!
Simply put, if you are not sharing a dataspace you are not recursing but you may start cursing!
Or even re-cursing.
