Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re^3: Quickly detecting variable writes

by sfink (Deacon)
on Jan 06, 2007 at 17:11 UTC ( #593310=note: print w/ replies, xml ) Need Help??


in reply to Re^2: Quickly detecting variable writes
in thread Quickly detecting variable writes

In your example, unless += is being overloaded, $x will always be "written to" if @kabluther contains anything--even if the value added is 0. In which case, knowing whether $x 'was written to', is equivalent to knowing 'if @kabluther was non-empty'.
Yes. And in that particular case, that is exactly what I want.
If += is overloaded, then you're already paying the penalty of overloading and adding a flag internally to the overload method and a second method to query the flag will add negligable extra overhead.
Oops, sorry, bad example. Yes, you are correct. But that depends on the type of value being used. Values could be overloaded blessed array refs, as in the example above. Those are used for 2d, 3d, and 4d vectors. But other common types are booleans, integers, floats, doubles, and strings, as well as a bunch of more heavyweight types (images, vectors, sets, ...) None of those other lightweight types are overloaded or otherwise special, and they are probably the more important ones to suppress the false updates for. Especially booleans, which tend to be used as triggers.

To answer your question: my system is comprised of a tree of nodes, where each node contains a collection of attributes. Attributes can be either inputs or outputs. All processing is done by connecting the inputs and outputs together. An external trigger (clock ticks, camera frames, keyboard events, ...) causes a cascade of updates throughout the graph.

Attributes that are bound together share a value, so the value is communicated from one node to the next. But in addition, there is an explicit call saying "I updated this attribute" that invokes the callbacks on all input attributes that are bound to that output. So you can think of it as a graph where the edges propagate both values and control (in the form of update notifications).

One type of node is a Perl script node. It can have whatever attributes it likes, and can bind any of them to Perl variables using the ": Attr(...)" syntax in the example in another post, or by a lower-level notation to retrieve the value which doesn't try to do any magical auto-updating stuff.

So the decision of what value to assign to some attribute is different than whether to mark it as updated. Usually, the two go hand in hand. But there are many cases where triggering unnecessary update notifications will result in a huge amount of wasted work. So, for example, if a Perl script node has six boolean output attributes, you really don't want to mark every one of them as updated every time anything changes. And you can't tell from the value; it is perfectly reasonable to repeatedly set an output attribute to 'false' and mark it as updated over and over again.

You always have the option of dropping back to a lower level, and marking every update explicitly. I am trying to come up with an easier-to-use interface that removes the need for the marking in most cases, preferably without adding too much overhead. The basic idea is that 95% of the time, if you write to a variable then you want to mark it updated. Most of those writes will end up changing the variable's value, but the cost of missing an update (the rest of the tree does not get triggered) is much worse than the cost of doing an unneeded updated (usually just redundant processing), so value comparisons are conservative in the wrong direction.

Looking at the length of this reply, I think you may have been correct to regret persisting!


Comment on Re^3: Quickly detecting variable writes
Re^4: Quickly detecting variable writes
by BrowserUk (Pope) on Jan 07, 2007 at 07:57 UTC
    Looking at the length of this reply, I think you may have been correct to regret persisting!

    Not at all, I like non-trivial problems ;). And looking back at a couple of your other top level SoPWs, I see that this question is a part of a much larger and ongoing development of a complex system. Getting the balance right between giving enough detail to explain the problem you are trying to solve, whilst not leaving yourself open to suggestions for solutions that would require re-architecting major chunks of your whole project is a tough one.

    It's not clear to me from this post or the others in this thread whether you have yet found a suitable answer to your OP?

    The following assumes that you are still looking and is the result of my background thunking on the problem whilst watching a less than engaging movie. If you've got your solution just ignore it :)

    This is my (possibly wrong) understanding of the problem, derived from what you've said so far, along with a bit of mental assumption. Starting with the following example code taken from that other post you mentioned, but with a slight modification (Note:<op>):

    sub onTick { our $x; # Initialize and associate $x with some external value foreach (@kabluther) { $x <op> $_->getSkookiness(); } return $x; }

    $x is some attribute of some node. Associated with that attribute is a (possibly empty) list, @kabluther of callbacks to other nodes associated with this node by this attribute.

    When some event (onTick() in this case), is triggered for this node (or attribute?), you wish to invoke the set of callbacks. Each of these callbacks may or may not do either of two things:

    1. They could change the value of $x.
    2. They could also, independently, be the cause of the need to trigger a cascading trigger event to be sent to other nodes in your graph associated with $x, regardless of whether they actually change the value of $x

    Whilst the callbacks could each manually invoke the trigger mechanism themselves, this could result in a separate trigger event for each of the callbacks in the list which would be redundant. So what you are looking for is a mechanism that would allow you to invoke all the callbacks in sequence without the event being triggered and only trigger the event if one or more of the callbacks has done something(*) that would necessitate it.

    (*)This something is not yet clear to me. Could the update be needed if the variable is only read? Could the update be needed even if the variable is not referenced at all?

    Assuming that is correct, there is a fundamental problem with the scenario as presented.

    Regardless of what <op> is, as coded above $x will always be 'written to' every time you invoke the callback.

    Even if the callback did literally nothing:sub{}, if $x was tied, any operation (that I've considered), that would be legal perl syntax to substitute for <op> above, would mean that the STORE method of $x would be called.

    To put that another way as it still doesn't read very clearly to me.

    As shown above, regardless of what <op> actually is, there is no way to construct a getSkookiness() method that wouldn't cause a STORE to $x (tied or not), that would also allow you to obtain the result of any return value from the callback.

    Eg. If <op> is =, or += or |= or &=, or any other assignment operator, then even if the callback did literally nothing; sub{ }, $x would be written to. Possibly triggering some warning like Use of uninitialized value in addition (+)... depending upon the actual operator.

    If <op> is not an assignment operator, say &, |, + etc., then whatever the callback does, $x will not be written to, it's STORE method will never be invoked. So you will have no way of detecting either any change in the value of $x, nor the need for an update event.

    So all the discussion of efficiency in the OP is basically irrelevant because the code you are presenting simply has no way of performing the task you are trying to achieve, efficiently or otherwise.

    So as not to stop on a totally negative note, I see a possibility for achieving what you are trying to do.

    Instead of assigning the result of the callback to $x, pass a reference to $x into the callback.

    sub onTick { our $x; # Initialize and associate $x with some external value foreach (@kabluther) { $_->getSkookiness( \$x ); } return $x; }

    This gives the callbacks the possibility to do something to $x, or not. Which gets you half way there.

    If $x is (locally) tied to a proxy variable, then you can detect whether the callback did anything, (read/FETCH, write/STORE) to it or not. Which is the second part of the requirement.

    By way of demonstration of what I mean by "If $x is (locally) tied to a proxy variable", the following shows that the callbacks (readOnly(); writeOnly(); readThenWrite() in the following code), need not know that they are dealing with a reference rather than the variable itself thereby limiting changes to existing code, and it avoids permanently tieing $x which limits the performance affects of the tie to just those places where you need it:

    #! perl -slw use strict; package proxy; my %flags; sub TIESCALAR { my $self = bless \$_[1], $_[0]; $flags{ $self } = 0; $self } sub FETCH { $flags{ $_[ 0 ] } |= 1; $_[0]; } sub STORE { $flags{ $_[ 0 ] } |= 2; ${ $_[0] } = $_[1]; } sub referenced { return ' :was read' if $flags{ $_[ 0 ] } == 1; return ' :was written' if $flags{ $_[ 0 ] } == 2; return ' :was read and written' if $flags{ $_[ 0 ] } == 3; return ' :was untouched'; } package main; sub readOnly { my $copy = $_[0] } sub writeOnly{ $_[ 0 ] = 'written'; } sub readThenWrite { my $copy = $_[0]; $_[ 0 ] = 'read & written'; } our $x = 'some text'; my $o = tie my $proxy, 'proxy', $x; print $x, $o->referenced; readOnly $proxy; print $x, $o->referenced; writeOnly $proxy; print $x, $o->referenced; readThenWrite $proxy; print $x, $o->referenced; __END__ c:\test>tieProxy some text :was untouched some text :was read written :was read and written read & written :was read and written

    You may have no use for read & write detection which would simplify the tie further, but it shows the possibilities of using the tie mechanism without incurring it's costs in the wider context.


    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
      $x is some attribute of some node. Associated with that attribute is a (possibly empty) list, @kabluther of callbacks to other nodes associated with this node by this attribute.
      Sorry, you misunderstood me. @kabluther has nothing whatsoever to do with $x or callbacks. It's just an example of some sort of processing that might occur. The example could also be
      onTime { our $pos : Attr('position'); our $active; if ($active) { $pos->[0]++; } }
      or
      onTime { our $x : Attr('something'); our @fixups; foreach (@fixups) { $x += $_; } @fixups = (); }
      The "callbacks" I was referring to are behind the scenes. Here's an example of the previous code sample, without using the new "simplified" API:
      onTime { my $attr = $NODE->getAttr("something"); my $val = $attr->getValue(); foreach (@fixups) { $val += $_; } @fixups = (); $attr->setValue($val); $attr->doCallbacks(); }
      That's how it would be written with the current API, unless they wanted to suppress the possibly unneeded callbacks, in which case they would spell it:
      onTime { my $attr = $NODE->getAttr("something"); my $val = $attr->getValue(); my $was_updated = 0; foreach (@fixups) { $val += $_; $was_updated = 1; } @fixups = (); if ($was_updated) { $attr->setValue($val); $attr->doCallbacks(); } }

        Do you have any example where your $was_updated flag cannot be done away with completely and replaced with a simple test against @fixups?

        onTime { my $attr = $NODE->getAttr("something"); my $val = $attr->getValue(); foreach (@fixups) { $val += $_; } if ( @fixups ) { $attr->setValue($val); $attr->doCallbacks(); } @fixups = (); }

        If not, I'm kinda at a loss to understand the difficulty.


        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://593310]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (6)
As of 2014-08-01 03:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (256 votes), past polls