UpdateControls scalability

Apr 19, 2011 at 7:41 PM
Edited Apr 19, 2011 at 7:44 PM

Have you thought much about the scalability of Update Controls? I think this topic is important because UC permeates an application--from the view to the viewmodel to the model. If UC is not scalable, it follows that an app based on it cannot be scalable either. In particular, UC scalability in the model is important because the model contains the largest amount of data (meanwhile, the view and viewmodel are likely to show a reduced, filtered view.)

On the desktop, we should be concerned with scalability in a model that contains millions of independents. First, let's look at memory use. I've done some tallying, and by my count, each Independent requires about 20 words of memory (i.e. 80 bytes in 32-bit, nearly 160 bytes in 64-bit), assuming each Independent points to 1 to 4 dependents. Independent<T> has 3 extra words overhead. Thus, a model class that uses 7 Independent<T>s in a 64-bit process needs over 1 KB for UC alone, not counting the data itself. A million 64-bit model objects like this therefore require one one gigabyte of memory just for the overhead of UC Independents. It would not be unusual that the UC overhead exceeds the "natural" size of the model.

In addition, Dependents are heavier than Independents. I can't be sure without understanding the purpose of _upToDatePrecedent versus _base, but I'd guess that each Dependent is bigger than 2 Independents.

I can propose three changes that can reduce memory use:

  1. make Precedent a base class of Dependent and Independent, instead of using containment. This saves 2 words per Dependent/Independent.
  2. Save 2 more words by eliminating GainDependent and LooseDependent (which is misspelled btw), which are rarely used, in favor of abstract OnGainDependent and OnLoseDependent methods that the user can override if (s)he needs them.
  3. Replace List<Dependent> with a lightweight list class. I've developed an InternalList<T> structure designed to replace List<T> for internal use inside low-level data structures that do not publicly expose the list. InternalList<T> uses only 6 words for a list of 1-2 word-size items, in contrast to List<T> which needs 12 words.

Total savings with these changes is 8-10 words (up to 50% savings if the user avoids Independent<T>).

For me personally, I have different reasons to be concerned about memory use. I want to develop a new program on Windows CE, which realistically only allows 16-20 MB of heap per process. (I haven't tried compiling UC for .NET CF yet, but I already know the thread-local storage will be a problem because .NET CF doesn't support it -- but there are workarounds)

Another likely scalability problem I noticed is that Dependent.AddPrecedent() contains the test "_precedents.Contains(precedent)", which is O(N) in the list size. I expect that the _precedent list is large whenever you've got a DependentList<T> that depends on a large list in the model; since RecordDependent is called on every relevant Independent in the model, the total complexity is O(N^2).

You could fix this by switching to Dictionary<Dependent,object> or HashSet<Dependent>, but it would increase memory requirements a lot. (Also, note that .NET CF lacks HashSet.) A B+tree saves a lot of memory in exchange for O(log N) complexity; coincidentally I will be creating an open-source B+tree soon as part of a project I call Loyc.Essentials -- a library of important stuff that the .NET Framework is missing.

The other key scalability problem of UpdateControls is the way it handles lists; like I mentioned in my blog, "if you are filtering a million-item list down to 100 items that you show on-screen, that million items will be scanned and filtered every time any item is added, removed, or changed, even if that item is not one of the 100 items displayed." I still don't have any solutions to offer, but I'll be thinking about it.

Apr 19, 2011 at 9:15 PM

I found another reason to make Dependent and Independent derived from Precedent.

I think it would be useful to be able to visualize the dependencies between objects. Ideally we'd generate a fancy graph as a debugger visualizer, but as a first step a simple text-based tree would be useful:

* Model.PersonList
* Person.FullName[x10]
   * Person.FirstName[x10]
   * Person.LastName[x10]

To this end, I tried adding "NamedDependent" and "NamedIndependent" classes...


public class Independent {
	public static Independent Named(string name) { return new NamedIndependent(name); }
public class Dependent {
	public static Dependent Named(string name, Action update) 
		{ return new NamedDependent(name, update); }

public class NamedDependent : Dependent
	public NamedDependent(string name, Action update) : base (update) { _name = name; }
	protected string _name;
	public string Name { get { return _name; } }
	public override string ToString() { return _name; }
public class NamedIndependent : Independent
	public NamedIndependent(string name) : base() { _name = name; }

	protected string _name;
	public string Name { get { return _name; } }
	public override string ToString() { return _name; }

You would use this with code like 'Independent.Named("Person.FirstName")' instead of just 'new Independent()'. (Following the C++ religion of "you don't pay for what you don't use", I did not add _name to Dependent and Independent in case it is not used.)


So I started writing some code that would produce a textual tree from any Dependent, but quickly discovered that it is not possible. The problem is that Dependent has a list of _precedents, but you cannot figure out the Dependent or Independent that corresponds to any given Precedent; therefore I can't look up the name, and can't produce a dependency tree. It's also a potential problem that _dependents is private; an API returning IEnumerable<Precedent> would allow arbitrary visualization code.

Of course, it would be nice to unify the solution to this problem with the reverse problem (viewing the dependencies of an Independent), but I haven't thought that far ahead.

Apr 20, 2011 at 11:41 AM

That is some really good analysis. I'll make those changes. Hopefully I can add some unit tests around memory usage to prove their effectiveness.

Replacing the events with virtual methods would technically be a breaking change. But since I am probably the only person who has used them so far, that will likely be OK.

My advice generally is that you don't want to have a large number of Independents. If you have more than, for example, 1,000 items in a list, then you are going to start to notice the overhead of dependency tracking. Use a PagedCollectionView in such cases. But the user is probably not going to want to scroll through that many items anyway.

Apr 20, 2011 at 6:20 PM
Edited Apr 20, 2011 at 6:33 PM

A PagedCollectionView, eh? I had never heard of that. If you had a model with a million items, how would you arrange to dispose of all the Independents that don't happen to be on the user interface at the moment? Or would you not use Independents in the model at all?

One more (long) comment. With regard to visualization, someone might want to see a "detailed" dependency visualization that includes all the values of the dependent/independent variables. In order to accomplish this, it's conceivable to change Independent<T> into a derived class of Independent (and likewise for Dependent<T>). However, this approach has three problems: (1) it's a breaking change, (2) you may not want to expose the members of Independent directly in Independent<T>, and (3) it's not obvious how this fits in with my idea of having a separate "NamedIndependent" derived class. You could change Independent<T> so that it's derived from NamedIndependent and always has a name (this solution still use less memory than the original Independent<T>).

Edit: I just deleted the idea I had written below because I realized it was unnecessarily complicated. I was trying to answer the question "what if the user wants to see a dependency visualization that includes the actual values, BUT you don't want to change Independent<T> to be derived from Independent?" My silly solution was needlessly complicated, let me know if you're curious about a simpler approach.

Apr 21, 2011 at 2:38 PM

I just double-checked on PagedCollectionView. It's only available in Silverlight, so it wouldn't be applicable to your situation. Sorry about that.

In any case, I would not use Independents in a model with a million items. In fact, I wouldn't even load that many items into memory at once. I would change the UI such that only a limited set of data is brought in at a time. For example, have the user search (Google), or navigate a graph (Wikipedia). Avoid tree views or lists with a large number of items. This not only avoids memory and performance problems, but it also improves the user experience. Nobody wants to scroll or page through a million rows.

I don't think that inheritance is the appropriate relationship for Independent<T> or Dependent<T>. These classes live at a higher level of abstraction than the sentry classes. This would be considered implementation inheritance rather than Liskov inheritance.

I'm not sure how to solve the dependency visualization problem without extra burden on the developer. I'm still thinking that one through.

Apr 22, 2011 at 1:15 AM

Well, the thing about the million-item case is that the developer can't always predict how his program will be used, or if he can predict, he doesn't necessarily have time to make a scalable program anyway. A good example would be a spreadsheet program. If you write a spreadsheet program (and you probably wouldn't nowadays, but bear with me) you're thinking mostly about how to get the cells to recompute properly, how to support variable-size rows and columns, the various forms of visual formatting you'll support, the file format, etc. The question of what to do when the user tries to load a spreadsheet or csv file with 500,000 rows is probably not high on your priority list.

If you know your program will routinely deal with a million items, you'll specifically optimize for it. But if only 1% of your users need that, you're not likely to implement a scheme to keep some of the file on disk, not if it totally changes your app's architecture and requires reams of special code to manage (and unit-test) the paging/caching. You'll probably think to yourself: well, I can tolerate a 1% loss in revenue or customers, and you do nothing. That's where high-performance low-level libraries become important. I figure anything low-level or foundational in an app should always be optimized, so that any program built on it can handle bigger datasets than it would otherwise.

Apr 22, 2011 at 1:25 AM
Edited Apr 22, 2011 at 1:29 AM

What do you think of this method to allow value visualization: have a public static property of Independent<T> and Dependent<T> called (hmm...) LinkValuesForVisualization (false by default). When enabled, the constructors of Independent<T> and Dependent<T> create a derived class of NamedIndependent or NamedDependent. The derived class contains a reference to Independent<T> or Dependent<T>, making visualization of the Value possible.

The references should probably be nulled out when disposing.

Apr 22, 2011 at 3:56 AM

Re: million-item case. Before the user gets to 500,000 rows, they have to go through 200,000. At some point, the performance pain is going to tell them to stop.

Re: visualization. Will the Named variants get the name from the calling stack frame? That could work. Why don't you do a POC?

Apr 22, 2011 at 4:18 PM
Edited Apr 22, 2011 at 4:29 PM

No, not if they are importing data from elsewhere (e.g. I opened a CSV with 3 million rows in Excel yesterday--by accident actually--and it stopped loading at 2^20 rows, although it remained responsive and usuable); or if they want to aggregate numerous existing large spreadsheets for some reason.

Another example from real life is programs that deal with SHP/DBF data. I deal with large SHP/DBF datasets at work a lot, produced by map providers such as Tele Atlas. These files tend to be very large; unfortunately, every free or open-source app I could find was not scalable enough to effectively deal with even relatively small provinces/states. They all load the entire file into memory, but suffer from overhead far beyond the actual file size; even if the data fits in the 32-bit address space, they handle it very slowly, e.g. deleting a single shape from a large shapefile in (the open-source) MapWindow causes the file to be saved, which for some reason takes something like 30 seconds for a large file (much longer than it takes to load the file or copy it).

My company needed some scripts to process maps and we used MapWindow at first, but ultimately the 2GB limit killed us and I decided to write a scalable shapefile library from scratch (my library can open over 100 GB spatially-indexed shapefiles in a 32-bit process, and most of our scripts ran in far less than 1/10 as much time). If MapWindow had just been moderately more scalable, it would have been able to handle a triplet of ~100MB maps that we needed to process (2 large input files, 1 output) without running out of virtual memory. Note that as it was technically open-source I could have improved the code myself, but when I opened the shapefile management code I was horrified--thousands of lines of code, consisting of enormous functions liberally copy-pasted from each other. It was as if large functions had been manually inlined into other large functions to produce something totally unmanagable and nearly incomprehensible.

I certainly don't regret writing a new library for my company (too bad I can't open-source it), but there were time pressures and we could have delivered to the customer sooner if MapWindow had been moderately more scalable.

The named version couldn't normally get its name from the call stack. Typically only the constructor is on the call stack--you could get the type name but not the variable name. And theoretically the constructor could be inlined so you wouldn't get the right type name.

If you want a semi-automatic naming mechanism, how about this: at the end of the constructor, after all "precedents" are created, the class can pass itself (this) to a UpdateControls method that uses reflection to scan the object to find currently "nameless" named precedents and assign a name to them based on the class name and field name. Not sure if this approach is feasible in Silverlight (can reflection read private fields in Silverlight? Note that I don't have a VS Silverlight target installed in my machines).

Wait, I have a different idea that could make this more efficient, albeit increasing the memory leak potential: the user could pass this instead of an actual name; then when visualization is in progress the name could be looked up via reflection (if the name is an arbitrary object instead of a string). Thus, reflection during normal operation (no visualization) is avoided. Wait, no, this won't work: the C# compiler won't allow you to pass this in member initializers, so you'd have to move initialization to the constructor, which is probably more work than manual naming was in the first place!

In any case, any automatic scheme would only be able to discover the name of the field, not the corresponding property. You could fake it by converting "_depFoo" to "Foo" and "_fooBar" to "FooBar", but it would be confusing if the result doesn't happen to match the real property's name.

I also have a concern about memory consumption if names are looked up and converted automatically. My original idea is memory-cheap because the name string is interned: a million variables named "ModelClass.PropertyName" only require memory for a single string.

Apr 25, 2011 at 9:53 PM

Your point is valid. I'll amend my advice to say that I do not recommend using Update Controls for tracking data that could be machine-generated. It works well with human-sized data.

I implemented your suggestions and a few more besides. I was able to reduce the memory footprint of dependency tracking by about 50% in my test cases. As part of the optimization, I removed a feature that it turns out I never used. I highly doubt anybody will miss it.

Reflection cannot read private fields in Silverlight unless you elevate the privileges. So that option is out.

I think the name of the property could be fetched from the stack frame during the first get, rather than during construction. Independent.OnGet() could walk the stack, skipping past Independent<T>, and find your get_XXXX method. It would only do this if the static debug flag is set, and only the first time OnGet() is called.

Jul 5, 2011 at 6:20 PM

By the way, a simple technique for reducing the number of independents is to use a single Independent to govern several independent variables. However this can easily balloon the number of updates. So it would be nice if we could monitor the number of unnecessary updates (and the ratio between updates that have no effect and those that do), somehow figure out the source of excessive updates when they happen, and if Dependent could be informed about false updates (where the value of the Dependent did not change) to prevent further propagation of the false update to other Dependents.

Jul 6, 2011 at 12:16 AM
Edited Jul 6, 2011 at 12:46 AM

Hi again, I've been looking at the source code of the new UpdateControls.dll and I'm not sure you have the best design there. First, you said memory use is 40% of what it used to be. I find that hard to believe. Did you measure it somehow?  It looks like you replaced the two lists (List<Precedent> and List<Dependent>) with two linked lists. The linked list is smaller than List<T> if it contains less than 4 members; but it's larger than List<T> if it contains 4 members or more. Frequently, a Dependent depends on an entire collection of Precedents, so it doesn't seem like a win.

Also, you said that "Dependents with a large number of precedents no longer significantly degrade performance." ... but I was concerned about the Contains() operation being O(N) in the list size; Contains() on a linked list is still O(N). I still haven't made that B+tree I promised though. I guess I was too busy benchmarking C++ vs C#...

Also, you added a WeakReference to link each (In)dependent back to its Dependents. Here's the problem with that: WeakReference itself is an object that occupies 4 words. (I would love to know why MS implemented WeakReference this way, because it seems kind of counterproductive!) Now, consider the Dependent for a listbox of 1000 Independents. Every one of those Independents will create a separate 4-word WeakReference to that one Dependent (total cost: 16/32KB in x86/x64). You can solve this problem by adding a "WeakReference _self" field to each Dependent, which stores a WeakReference to itself. Then each Precedent can copy the reference to the WeakReference from the Dependent, avoiding a proliferation of WeakReference objects.

The new RecycleBin implementation has me concerned, too. The Recyclable<T> type seems redundant. Why not just replace Recyclable<T> with T? Then your Dispose() method would look something like this:

public void Dispose()
    if (typeof(IDisposable).IsAssignableFrom(typeof(T)))
        foreach (T obj in _recyclableObjects.Values)
        foreach (T obj in _duplicates)

Oh and by the way, the <T> in the definition of Recyclable<T> is redundant (it can be declared simply as "private class Recyclable"). I'm not sure if you actually create a separate generic type or not when you include the <T>... but I think you do.

On a slightly related note, could the RecycleBin used to update a DependentList be made optional (with an additional constructor to turn it off?) Right now I use DependentList<T> if I want a RecycleBin or Dependent<List<T>> if I don't, but the distinction is perhaps too subtle. In fact, other than the recycle bin and extra indirection (i.e. the Value property), is there any difference between the two?

Jul 6, 2011 at 8:31 PM

I just looked over your benchmarking article. Wow! I didn't go into nearly that much detail to get my 40% number. But I did document the steps in a test class called "MemoryLeakTest" (so named because it ensures that unused sentries can be collected). You can see each milestone in the comments of the first four tests.

I measured the sizes of the sentries in small numbers. But you are correct in pointing out that I should also measure them when connected to a large number of counterparts. Perhaps the results will be different.

I moved the Contains logic from Dependent to the Precedent side of the relationship. It is far more likely that a Dependent has many Precedents than the other way around. That's why I can claim that "Dependents with a large number of precedents no longer significantly degrade performance". A precedent with a large number of dependents would now become a problem, but that typically does not happen.

Great suggestion on the RecycleBin. I think I'll use your Dispose method and get rid of Recyclable<T>. I think the idea of Dependent caching a WeakReference to itself is also intriguing. I may take that one, too, after I see what the impact is.

The main difference between DependentList<T> and Dependent<List<T>>, as you noted, is the recycling. Recycling preserves identity, which is often important. It also gives you a hook (IDisposable) to determine when an object is removed from the collection. But in cases where identity doesn't matter and you don't need the hook, then Dependent<List<T>> is slightly faster.

It will probably be a few weeks before I can apply your recommendations. But please keep them coming. The library is better for all the bugs and improvements you've found.

Jul 6, 2011 at 9:14 PM
Edited Jul 6, 2011 at 9:48 PM

Hey, I just ran the VS:TS profiler on my program... just letting it run for awhile with no user interaction, receiving random updates on about 1000 simulated objects. Guess what the most expensive part of UpdateControls.dll is? Precedent.Insert(), at 16.8% of my program's running time, mostly spent in mscorwks.dll (12.2%) and the WeakReference ctor (3.8%). Apparently those WeakReferences are expensive to construct. All the more reason not to construct more than one per Dependent. Meanwhile, Precedent.Contains() is taking 4.9%, and Precedent.Delete() is taking 3.4%. Dependent.GetCurrentUpdate() takes 4.1%; I guess that's the price you pay for thread-local variables.

Precedent.Contains() is using 4.9%, but probably not because it's searching long lists; rather, the majority of the time is spent in WeakReference.Target (0.7%) and mscorwks.dll (2.6%)... so either locking is expensive or just looking at a WeakReference target is (moderately) expensive.

Aha! I understand now how your optimization works. Dependent.AddPrecedent() no longer searches the list of precedents.... instead it can assume the precedent being added is not a duplicate, because it is only called to finish constructing a two-way link between a Precedent and a Dependent, so the call to Precedent.Contains() in Precedent.RecordDependent() is all that is needed to avoid duplicates. Precedent.Contains() does search its linked list of Dependents in O(N) time, but this list is usually short, hence overall performance should be much faster.

Cool. (I see you wrote a message while I was writing this message.)

Jul 7, 2011 at 12:13 AM
Edited Jul 7, 2011 at 12:14 AM

By the way, when you're scanning the linked list in Precedent.Delete(), that seems like a good opportunity to detect when one of the WeakReference targets is null and remove it from the linked list, if so (allows 2 additional objects to be GC'd). It doesn't guarantee you'll ever clean up the WeakReference, but I don't see another obvious place in which to clean up.

Jul 7, 2011 at 5:15 PM

Sorry I haven't been as responsive as usual lately. I'm getting ready to go on vacation. I'll be off line for a couple of weeks.

In the meantime, I've made you a developer on this project. Please feel free to make the changes that you recommend here and in other threads. You know the code base as well as I do, and you always have great ideas.