This project is read-only.
1
Vote

Avoid updating Dependents of a Dependent that has not changed

description

The value associated with a Dependent may not change when its dependencies change. For instance, if a Dependent represents a filtered view of a list, that filtered view does not always change when the original list changes. Unnecessarily cascading changes is sometimes expensive, so we need a way to avoid it.

file attachments

comments

Qwertie wrote Aug 22, 2013 at 6:36 PM

(Hmm, first attempt to post this message didn't work?)
Okay, I think I remember a solution that I thought of a year or two ago.

My original idea is to create a new kind of Dependent which does not always cascade updates, and this would live alongside the normal Dependent which does cascade updates. An alternative is to make all Dependents non-cascading; this seems slightly more expensive, but slightly easier to reason about.

How it works (also, see attachment):
  1. Independent.OnSet() causes all of its Dependents to be made out-of-date (which I'll call the "X" state for short), causing all dependencies ("Uses") in those Dependents to be dropped.
  2. However, the Dependents (the new kind, anyway) do not recursively invalidate their dependents. Instead, the Dependent will recursively mark its Dependents ("UsedBy") with a new "Maybe out of date" flag or "M" for short. I'm not sure if it should be a separate flag or just another _status value (it may depend on the multithreaded scenario, to which I haven't given any thought). Recursion stops at any Dependents that already have the M flag. The connections between the Dependent and its "UsedBys" are not broken.
  3. When a Dependent with the X (out-of-date) flag is updated (OnGet()), either it stays the same or it changes. If it stays the same, no action is taken (the UsedBys keep their "M" flags since we can't tell if the flag was set by multiple paths). If the Dependent changes, all its immediate UsedBys are marked X, i.e., steps 1-2 are repeated except that "Independent.OnSet()" becomes "Dependent.OnChanged()". (X replaces M; the flags are mutually exclusive) and the links to the UsedBys are broken.
  4. When a Dependent with the M flag is updated (OnGet()), its immediate Precedents (Uses) are scanned for anything with an X or M flag. OnGet is called on any marked "X", while anything marked "M" is scanned recursively looking for something marked "X", on which OnGet is called. A if a "grandchild" changes, the child will get an X flag and the scanner can call OnGet on the "child". This may invalidate (X) the scanner, which then updates itself as described in (3). Now, on the other hand, maybe none of the immediate Precedents will change, and maybe none of them will even have an X or M flag, in which case the M flag is simply cleared and the Dependent is declared up-to-date without running its update method.
That's it. It might sound complicated... and might be clearer if you look at the example diagrams.

This solution isn't meant to reduce the computational complexity of Update Controls itself. I mean, if there are 1,000,000 Dependents that (directly or indirectly) depend on one Dependent, perhaps all 1,000,000 of them will have to be marked "M" when the one Dependent goes out-of-date. But if it turns out that this important Dependent doesn't change, then marking one million Ms will be much cheaper than a "full" cascading update would have been, especially if the host application requires complex calculations to perform the update.

In the example,
  1. J and H are marked out of date, marking their UsedBys with X and indirect dependencies with M.
  2. You can think of L as something in the View; it calls OnGet during the next Idle event, which leads to F.OnGet(), but F doesn't change so the M flags on C and L are cleared.
  3. Then K.OnGet is called which leads to E.OnGet(). E changes, so its UsedBys are marked X and the connections with A and B are broken. Of course, E can change its dependencies and in this case decides to depend on a new independent P. Then B.OnGet() is called and it changes too, so K is marked out-of-date and the connection to K is broken. Finally, K is updated and it chooses new dependencies B and C.

Qwertie wrote Aug 22, 2013 at 6:38 PM

I can imagine another kind of Dependent, let's call it a GreedyDependent, which always immediately updates itself when its Precedents change, without necessarily notifying its Dependents (UsedBy) at all. This is just a different performance tradeoff. It is potentially more costly because if several precedents change at roughly the same time, the Dependent will be updated more times than necessarily. But it's potentially less costly because if the Dependent doesn't change, we avoid (1) the cost of marking all those "M"s and (2) the future cost of the "M" Dependents running the scanning procedure in step (4). And perhaps it would be better if, rather than updating immediately, this kind of Dependent is simply added to a queue to be updated later.

Hey! Come to think of it, remember how I was concerned yesterday about controlling the thread on which a Dependent is updated? This new kind of Dependent could naturally be updated on the same thread as the changed Independent, rather than the UI thread. And if the Dependent is placed in a queue to be updated automatically, the queue could be user-defined, and the user could control which thread will update it. Now, this doesn't guarantee that the Dependent is updated on the desired thread (if OnGet is called on a different thread before the queue gets around to it, the update will occur on the "wrong" thread). But the key difference between this idea and the current design is that the Dependent won't propagate its X status to its UsedBys, which prevents the UI thread from directly competing with a worker thread. Perhaps the GreedyDependent will still be updated on the UI thread, but only because the GUI went out-of-date for some other reason.

Qwertie wrote Aug 22, 2013 at 8:14 PM

....hmm, "GreedyDependent" isn't a sensible name for the kind that goes on a queue. Actually "LazyDependent" makes more sense for that.
  • Standard Dependents could also be called "greedy" in that they tear down their UsedBys immediately and recursively, but lazy in that they are not updated immediately.
  • The second kind of Dependent marks Ms greedily but everything else is lazy.
  • The third kind of Dependent updates itself greedily and avoids tearing down UsedBys if not necessary
  • The fourth kind of Dependent just puts itself on an update queue and leaves its UsedBys alone until it is updated, so it's the laziest kind of all.
The last kind seems very useful but has a potentially dangerous property that Dependents that use it indirectly can "think" they are up-to-date but actually are out-of-date. Actually UpdateControls already has a comparable danger built-in; there may be a time delay between an Independent that changes and the UI update, and during this time delay the user can do something dangerous. For instance, suppose an Independent is updated that will eventually cause a TextBox to be disabled. But suppose the TextBox currently has the focus and the user is actively typing in it. This could cause changes to the viewmodel and, therefore, the model after the TextBox should have been disabled.

This can already happen today; a typical example would be after the computer comes out of hibernation so the app is mostly swapped out to disk. This allows the user to give several inputs to the app before it has time to respond, which in turn may allow the user to do a sequence of actions that would normally be impossible. The new kind of Dependent could make this UI-related problem worse, and introduce new programmatic inconsistencies. But on the other hand there are clear advantages of a "LazyDependent" too.

MichaelLPerry1971 wrote Sep 8, 2013 at 7:40 PM

I see how your first suggestion would work. Let's say we go with the extra state (or states, to mix in the concurrency dimension). We would also need for MakeUpToDate to return four states, not just the two that it does now. These are a combination of concurrency and change. The return value now only reports on concurrency:
  • I updated (the current meaning of "true")
  • I'm still out of date due to concurrency (the current meaning of "false")
We would need to combine these with the change dimension:
  • I computed a new value.
  • I computed the same value.
For the Dependent to know whether it computed the same value, we would need to change _update from an Action to a Func<bool>. The update function returns true if the computed value has changed. We can overload the Dependent constructor to treat an Action as a true-returning Func<bool> for backward compatibility.

You have a TODO in Dependent<T> that changes Update from void to bool and implements this logic. We would need something similar for DependentList<T> and DependentDictionary<T>.

I think this change can be added to the existing Dependent with no ill effects, other than a minor increase in processing time. I would prefer this over creating multiple types of Dependents.


As for the greedy updates, I don't think the performance tradeoff is ever meaningful. Yes, you will save some overhead, but at what cost. Knockout js has greedy updates, and you can see the event storm that occurs when you change multiple precedents. It's better to absorb a little overhead for all updates than to risk storms that are hard to diagnose.

Qwertie wrote Sep 15, 2013 at 11:06 PM

I am disappointed that you're not interested/do not recognize the value of different kinds of dependents. I maintain that it is valuable to be able to offload processing from the UI thread, and that (as a separate issue) very greedy updates make a lot of sense in specific cases.

These cases may be rare, but they could affect performance a lot. For instance, consider an Independent that represents a timestamp, that changes often (e.g. once per second), a Dependent that represents the Date part of the timestamp, and 10,000 other Dependents that depends on the Dependent. Updating the Date part is cheap to do greedily, and the 10,000 other Dependents only get touched once per day. Without a "greedy" Dependent, the 10,000 other Dependents are repeatedly notified all day long that they "may be out of date", so all day long each one of the 10,000 Dependents are each checking individually: what changed? what changed? what changed? And the answer is almost always "nothing", of course. Although my initial proposal avoids the work of updating the values associated with the 10,000 dependents, it doesn't avoid the overhead of Update Controls' internal bookkeeping.

Obviously I am not proposing greedy updates as a default. Just as one option out of four.

MichaelLPerry1971 wrote Sep 16, 2013 at 3:49 PM

I would be interested in seeing some metrics on this. I'm not convinced that the savings would be enough to justify expanding the API. I'm concerned about the paradox of choice. No matter what the default behavior is, a developer is going to investigate and consider all options available. This could lead them to abandon the library altogether and chose a simpler option.

I'm also concerned about people choosing the greedy option in the wrong situation and falling into an event storm. Or worse yet, choosing it correctly, and then making a change to their code that renders that choice incorrect.

Have you measured the savings of updating immediately vs. at the end of the current message? And have you considered the improvement that we already gained by the introduction of the UpdateScheduler?

Qwertie wrote Jan 17, 2014 at 12:00 AM

I had not heard of UpdateScheduler. Is there any documentation for it?

Sorry, I haven't measured my proposals, that would require me to actually implement them first :P. If I did make benchmarks, I don't see how the results would be meaningful except to show that the code is working as designed. I mean, you don't need a benchmark to tell you that a hashtable is faster than a red-black tree, you can see it analytically, although the benchmark would demonstrate the effects of implementation errors or unexpected hash collisions.

MichaelLPerry1971 wrote Jan 17, 2014 at 4:19 AM

I added UpdateScheduler as an implementation detail to help with the move to Portable Class Libraries. But it turns out there are a couple of cases for using it in your application.

The mechanism for running an update later is platform-specific. So I created UpdateScheduler as a way for platforms to register their mechanism so that portable code can schedule an update. And as an added bonus, it also solves the problem of updating as soon as a change is complete, rather than waiting for idle time. Some XAML stacks (cough Silverlight cough) have bugs that manifest if you raise Property Changed after a change.

So that brings us to scenario 1. The view model wrapper uses the Begin/End pair of methods to run an update immediately upon setting a property. The MakeCommand helper also uses Begin/End to raise PropertyChanged immediately after a command is executed. If you are making a change outside of one of these two mechanisms (for example an event handler), you can do the same. I doubt you would see a difference in performance, but you might.

Scenario 2 is when you need to cause a side-effect based on a dependency. You create a Dependent (or Dependent<T>) and subscribe to its Invalidated event. Inside the Invalidated event, call ScheduleUpdate. Implemented IUpdatable, and in UpdateNow get the Dependent and perform the side-effect. You could do this before, but it was up to you to figure out how to schedule the update for later.

The documentation is in serious need of a refresh. UpdaterScheduler will get better treatment in the new documentation.

Qwertie wrote Jan 17, 2014 at 8:24 PM

What do you mean by "side effect"? Like triggering a popup notification on the UI? I still don't have a good sense of what this is for so I'll wait for that documentation. But this doesn't solve the problem of allowing certain Dependents to be updated outside the UI thread, right?

Why use IUpdatable instead of Action?

I'm still using UC mainly for my vehicle fleet map app, and the app continues to have performance problems if updates are frequent, because (1) there are some large collections involved and UC has no support for "incremental" queries, and (2) although most independents are changed on a worker thread, all the work of updating dependencies happens on the UI thread because the changes are "pulled" by the UI widgets. Fixing either of these problems would fix the performance problems; for now the solution for large vehicle fleets is to only update the model every 10+ seconds. Originally I tried and failed to find a solution to (1), but (2) seems solvable by giving Dependents more flexibility in how they respond to MakeOutOfDate(). Note that updating the "expensive" Dependents on a worker thread is not a real solution, because doing so will not prevent the UI thread from calling OnGet() on the same Dependents at the same time.

A third solution is to redesign large parts of the app, but the management thinks I've spent to much time on the app already.

MichaelLPerry1971 wrote Jan 17, 2014 at 9:28 PM

A good example of a side effect would be updating a stateful UI. Like setting the Text property of a Windows Forms TextBox. It could also be displaying a popup, as you mention. But, no, it does not solve the problem of updating outside of the UI thread.

Why IUpdatable? Not really sure. If I were to do it again, I would use Action. I didn't really expect to find this class useful outside of the library itself, but it has become so. Perhaps I'll define an override and mark IUpdatable obsolete.

I would encourage you to fork the repository at http://github.com/michaellperry/updatecontrols and create a branch at version 2.2.5.2. Then try out the "greedy dependents" optimization.