OT: Circular link halting

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 09/12/2006 at 22:57, xxxxxxxx wrote:

User Information:
Cinema 4D Version:   8.2-10.0 
Platform:   Windows  ; Mac  ;  Mac OSX  ; 
Language(s) :     C++  ;

---------
I know this isn't exactly the place for such a discussion, but I really don't know where else to look. Maybe someone has experience or good links to a better solution.

In my plugin, there are tags that are represented as sliders. They can be connected in master-slave relationships (a master slider value will affect the slider value that is slaved to it, for instance). One possible scenario actually allows a connection like this: A->B->A->B.... Currently, I am unsetting a flag on all of the sliders before computations and setting the flag as they are computed (mark and clear) to avoid the infinite loop that would occur otherwise. Gosh, is this slow. A comparison of a safe situation with and without this setting/unsetting shows that 'with' impacts the speed by 25% (!!!!!).

Since I'm currently optimizing to increase performance, this situation is directly under my target for finding a better approach. The problem is that I cannot find a better stopping method. Since the master and slave are juxtaposing (depending upon the user interaction) and the computation has to occur at least once from one to the other (starting at either, remember), it is hard to determine the best path here. Also remember that I cannot guarantee simple direct loops (A<->B). This could also be hidden looping (A->B->C->D->A).

One solution mentioned in a PDF is a form of duplication (the recursive nodes are duplicated so that the result is always a tree structure - but no real explanation beyond that).

Any pointers appreciated!

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 10/12/2006 at 12:36, xxxxxxxx wrote:

Just to explain further why this is asked here and Google isn't my friend. :)

The terminology (correct label usage, but incorrect ideal) makes it difficult. These connections are primarily designed as master-slave controls. But not in the canonical sense mainly used (a master task which disperses subtasks to a set of slave tasks - no chance of halting problems there). There are two sub categories - cascades and loops (as noted). Cascades means that a A->B->C (A is master to B, B is slave to A, B is master to C, C is slave to B). Loops means A->B->A. Because of this, master-slave isn't a good search term.

And neither is circular link/list as I've found. The problem is that discussions of circular lists usually revolve around hard-linked lists (NULL->A<->B<->C<->D->NULL), usually with heads and tails and such. This is not the case. The connections can be much more complex (A.B.C.D->E where A-D master control E cumulatively or A->B.C.D.E where A controls B-E and so on - use your imagination to see why 'simple' circular list analogies fail). And the entry point can be anywhere (user interaction - which slider) and must be propagated in both directions (slaves need to have master values applied and masters need to update slaves). This is exactly why the halting problem ensues!

My kingdom for an algorithm! Could be that my solution is the one actually used (mark and clear), but in tighter code or assembly. That I can't determine.

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 11/12/2006 at 01:17, xxxxxxxx wrote:

Okay, found a better approach. It's still somewhat clunky, but it avoids recursive calls across the document. Since this is only to avoid master-slave infinite loops, it only applies to masters and their slaves. Thus, the recursive, general, and slow call can be replaced with a more directed call to prepare only when a master tag and its slaves are involved (considering already-prepared to avoid loops in preparation). This only gets 15% performance improvement, but no complaints from me. :)

Now onto other performance optimizations.

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 11/12/2006 at 06:41, xxxxxxxx wrote:

I have nooooo clue what you actually want, but good you found a solution. :-)

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 11/12/2006 at 09:39, xxxxxxxx wrote:

Think of it this way:

This is a figure with a set of plugin bones. Each bone has a set of plugin tags (many). These tags control attributes of the bone - transforms, morphs, and so on - represented by sliders on the bone's AM. These tags can also control other tags, say, a rotation controlling a morph. But the control relationship is not limited to simple linear control. You can have the rotation of the left eye change the rotation of the right eye (to keep them in sync). And the right eye does the same to the left eye (L<->R). This is a circular link and inherently leads to infinite loops unless a halting condition exists. That's because when the left eye value is set, it also affects what it controls (the right eye). And the right eye value is then set and affects what it controls (the left eye) - and so on ad infinitum.

One approach to avoid this is to give each tag a flag that is cleared prior to value setting - but all tags' flags must be cleared prior to any value setting. To do this required a recursive call to traverse the document and find all of the plugin bones and clear the flag of all of its tags. Cumbersome and slow. Then as you set the value, you set the flag as a condition to abort any more processing of its possibly controlled tags. Thus 'mark and clear' technique - or in my case 'clear and mark' - same difference.

The new approach is about the same (still 'clear and mark'), but only considers controlling tags (masters) for the clear process - and must clear all slaves as well so that they can propagate their values if controlling other tags.

***

Now that you've read that and are more confused :), here's the interesting part - nothing at all to do with this problem. Sitting under my nose as I ask about BaseLinks and Read/Write/CopyTo are these master-slave controls. Guess how they work? A BaseContainer is added as a sub-container of the tag's BaseContainer - with unique ID. This sub-container has BaseLinks set with which to store links to a tag's masters and slaves. Sound familiar?   And I've never had to use Read/Write/CopyTo to retain this information when saving-loading or cloning a document. No problems with NULL BaseLinks. This is the solution to my next optimization - removing other recursions by enumerating the figure's bones similarly. No more recursive searchs to find or get the next bone that belongs to the figure - just go through the BaseLink list - should be nearly optimal.

I'm hoping ultimately to get near a doubling of performance (after recalculating timings, this master-slave fix yields 33% increased performance from a baseline of 39% between old method and without).

Take care,

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 12/12/2006 at 12:43, xxxxxxxx wrote:

Hmm... perhaps you could increment a global counter for a new action. If the local value matches, it means that an object has been visited. Something like this:

ULONG gFlag = 0

DoSomething()
{
    ..
    ++gFlag;
    Recurse( first )
}

Recurse( obj )
{
   if( obj->flag==gFlag ) return;
   else obj->flag=gFlag;
   ...
}