A Caching Structure!

[altenbach]

I often have a situation where certain code parts don't really need to be recalcuated, because their inputs have not changed from an earlier encounter.

For example if a function is the sum of two different complicated and slow calculations where each of the two depend on a different subset of parameters, often only one needs to be recalculated, while the other intermediary result could be grabbed from a cached value. (This occurs for example during the calcuation of partial derivatives).

In some cases, the compiler could probably recognize these situations, but I think we should have a special structure to allow caching of intermediary results.

I typically use a case structure and two feedback nodes as shown in the example on the left. If the value is different, the code in the TRUE case is executed, else the value stored in the SR is returned immediately. (If the code depends on several values, I bundle them all before the comparison operation)

I propose an simple Caching Structure as show on the right that retains that same functionality with less baggage.

Details: The containing code is calculated at first run and stored in the output tunnel. In later calls, it is either (A) recalculated, or (B) the previously stored value returned at the output tunnels. Recalculation only occurs under some conditions (.i.e. usually when actually needed)

The structure has the following features:

• Two possible types of input tunnels (the functionality is indicated by a different look).
1. One where a value change triggers a recalcuation of the containing code
2. One where a value change does not trigger a recalculation of the containing code
• A special boolean terminal to force a recalculation unconditionally
• output tunnels that retain data between calls

There can be an unlimited number of input and output tunnels of any type described above. A recalculation of the inner code occurs if any of the triggering tunnels have a changed value.

We can think of it similar to "short-term folding". 

[dthor]

@Ironman99

I don't think it has to be integers only, but I definitely see an issue with DBL and other items that are limited to the machine epsilon (SGL, complex, et. cetera). I think input could easily be a string, a refnum, a VISA resource, or most other things.

For the first implimentatoin, I think the input should accept all LV data types that can be exactly represented. Then, if there's a large enough demand, the strucure could be modified to have a configurable threshold value: if $input$ has changed by more than $threshold$, then the structure executes. Perhaps $threshold$ could be an input terminal similar to N in a FOR loop.

[elset191]

There's precedent for this kind of thing.  The DSC Datalogging of shared variables has a configurable deadband.

[Ironman99]

Thank you very much dthor.

You've got exactly my doubts and answered my questions thoroughly.

Great job, especially considering my poor English. 

Good to know elset191, thanks you!

Cheers.

Marco.

[altenbach]

I don't think we need a deadband setting, it would simply complicate things. The inputs could be from a calculation based on

controls, or from DAQ where they are typically quantized to the digitizer resolution. Very small changes are thus probably rare.

Of course there are cases where operation reordering could slightly alter the results for identical inputs. In the worst case, we do an extra recalculation... probably no big loss.

Since we allow many trigger input tunnels, we would need to have an equal number of threshold values. Messy. 😄

Here's an example of the current code if we want to trigger a recalculation on all important input changes that influence the ramp result. As you can see, all datatypes are allowed. (The code would be significantly simpler with the proposed structure!)

.

[dthor]

You may not like this idea Altenbach, but consider:

Instead of allowing multipule trigger input tunnels, we allow just one. This allows for the threshold input to apply to just that one. In order to get multiple triggering tunnels, we nest the structures. I'm not all too fond of this idea because I'm not a an of nesting, but it keeps things simple (which I consider to be a requirement for new structures. Easier to convince people that it's awesome and whatnot).

Or:

Again, only allow 1 input tunnel. However, allow the input tunnel and the threshold input to be a cluster. There would be a 1:1 relation between an input element and a threshold value, allowing any and every input to have a threshold if desired. Very similar to your example, actually.

On of the issues with a generic threshold like I suggested is:

How do you define a threshold for something like a string or VISA resource?

This is not something I can easily answer, and thus why I suggested that the 1st implimentation of this structure is one that doesn't have any threshold values, and should only work with data types that can be exactly represented. If DBL and SGL values are a must-have, then let their internal threshold value be machine epsilon rather than 0. That should be sufficient.

[altenbach]

> Instead of allowing multipule trigger input tunnels, we allow just one. 

The main reason for the idea was to simplify the code for the typical case of multiple trigger inputs. Allowing only one trigger tunnel per structure would lead to deeply stacked structures resembling Mayan pyramids :D. I am always for code simplicity and that's not it! 😮

[dthor]

> I am always for code simplicity and that's not it!

Well, it depends on your perspective... a single input tunnel is much simpler for NI to impliment 

I agree though. Mayan pyramids, while an amazing sight down in Central America, are ugly on a block diagram.

[elset191]

---

@Dragis wrote:

Also note that the compiler should (and usually can) automatically detect what will cause a reevaluation by default.

---

It seems that it does. At least it did in the piece of code I just wrote.

The Profile tool counted 710 runs of a subVI regardless whether or not I had my caching structure implemented around it.  The calling VI executed 682310 times. 

My for loop nesting had 5-142-961 iterations from outer most to innermost.  The caching structure worked on the autoindexed values of the outer two loops, so only needed to execute 710 times, even though it looked like it would be called all 682310 times

[altenbach]

Sorry, I must have misread the statement: "Also note that the compiler should (and usually can) automatically detect what will cause a reevaluation by default." because it only says that the compiler can detect the scenario, it does not say if it actually skips the re-evaluation. 😄

elset191, can you show me your testing code? Mabe we can discuss this in the forum elsewhere.

[elset191]

I'll simplify it and make a new post on the LabVIEW forum when I get some time.