The Flyweight Pattern

By YUI TeamDecember 14th, 2012

Some objects manage a large number of items. If those items are complex objects themselves, such as subclasses of Base or Widget, the memory consumed by such a collection can take your application down. However, when you have a large number of items, you are rarely going to actually deal with all of those items at once; you don’t need them to be active all the time. This is when the Flyweight pattern comes in handy. The name doesn’t mean much to me, I prefer to think of it as a Sliding Window kind of thing, where you slide a small window cut in a piece of paper over the data so that you actually see a little bit of it at a time.

For several years now, YUI 3 has been lacking a TreeView which was one of the very earliest widgets in YUI 2, and the reason is simple: the formal way to construct such a widget would be to use Widget as a base class augmented by WidgetParent, and another Widget for each node in the tree each augmented by WidgetChild and (if they have children) WidgetParent. This is a terribly costly way of doing it — the browser soon starts running out of memory, becomes sluggish and eventually freezes with trees far short of big.

The Flyweight pattern gives us an alternative. Each node is actually composed of the state and the behavior. The state is made of things like the label it shows, whether it is expanded or collapsed, selected or not and which nodes are its children. The behavior is what to do when things change. In OOP we learn that objects are made of those two aspects put together. As it turns out, this is also terribly expensive. What we do instead is to have the state in a plain object without methods, attributes or events, with simple property: value sets, and put all the behavior, i.e., methods and events, in a separate object. That object provides us with the window which allows us to look at the state of any node at any time.

If we were to have one object handling the behavior for each item in the collection we would be just as bad as having a Widget instance per node. Going back to our paper cutout, it would be like having the paper weakened with too many holes. What we do instead is try to have as few behavior objects as we can possibly can.

I had already explored this in my own Model Gallery module, where a base Model could be augmented by a MultiRecordModel extension which allows the same Model to handle any number of records that slide under the single Model instance. This allows the same Model to handle one or multiple records. The Model provides the window into the data and the MultiRecordModel extension manages the sliding of the data under that window.

The Flyweight Tree Manager and the Flyweight TreeView

For a TreeView, I needed to add a second dimension since, unlike a list, such as a ModelList, which is uni-dimensional, a tree has depth. However, a TreeView is not the only widget that relies on tree-structured data, a Menu also does and so can a form, made of several nested groupings of fields, field-sets, groups of radio buttons and other arbitrary groupings. So, the widget is split into two parts: the FlyweightTreeManager, which handles the tree-like structure, and the actual FWTreeView widget, which shows the tree data as a TreeView. Though originally I made the FlyweightTreeManager as an extension to let it be applied to a Widget as well as to a View, I found that the generalization had a cost in code size and the abstraction made little sense since all its use cases (treeview, menus and such) would be widgets. Thus, FlyweightTreeManager is a subclass of Widget.

The FlyweightTreeManager is not the window (i.e., the paper cutout showing the data through) but it manages the windows over the plain data underneath. The cutouts are instances of FlyweightTreeNode, a subclass of Base. The manager deals with moving these windows around the data. The manager is also a factory of node instances — they should not be created independently. This allows the manager to control the number of instances created at any time to the minimum.

The manager has a pool of node instances and it borrows them from the pool when needed, and refills the pool when empty. The pool can be quite small. The number of items in the pool hardly ever exceeds the depth of the tree. A fully collapsed tree will require just two instances for rendering, one for the root and one for each node in turn. (The manager gets an instance for the root and then the enumerating method uses a single instance for each node being drawn). If the tree is expanded one node at a time, the same two nodes will be used over and over, one for the node being expanded and the other to render each child. Rendering a fully expanded tree would require a node instance per level.

Since the information at each level might be different or presented in different ways nodes can be of various types. The manager recognizes the type attribute and keeps separate pools for each kind of node. Thus, the pool is a hash indexed by node type, with each entry an array of pooled nodes.

To create the tree, the constructor receives an array of plain objects defining the first level of nodes, containing properties such as label, expanded, type or children, the later being an array of further objects defining the next level of nodes.

Moving About

To traverse the tree, the manager provides the forSomeNodes method, which loops through all of the nodes in the tree, depth first, passing each visited node to the callback in turn. The beauty of such a method is that the lifespan of the node being visited can be predicted, it can be assumed that it will be used only within the scope of the callback function. Thus, the method can pick a copy from the pool, pass it to the callback and upon return, push it back into the pool. A full traversal visiting each and every node will only require a number of nodes equal to the depth of the tree, assuming all the nodes are of the same type. If there are different node types, it will provide a suitable instance for each node. As its name suggests (‘some’ instead of ‘each’) the traversal can be canceled at any time. For finer control over the traversal, FlyweightTreeNode also provides a forSomeChildren method that lets you go one level at a time. For example, the render method does not use forSomeNodes since it doesn’t bother to render the whole tree, just the expanded branches. Thus, it uses forSomeChildren one level at a time, going as deep as needed.

What happens when you want to keep a reference to a node? Each node has a hold method which tells the manager to keep it away from the pool. Holding too many nodes prevents the manager from recycling the held nodes into the pool and this increases memory consumption. When done with the node, calling release will return it to the pool. Forgetting to call release prevents recycling of nodes and, as with any waste, nodes pile up, that is, they take memory.

Several getXxxx methods (getParent, getNextSibling, getNodeBy, etc.) return node references. Unlike the traversal methods (forSomeNodes, forSomeChildren), the manager cannot predict when you are done with the requested node, thus, those nodes are automatically placed on hold for you.

Events

Event listeners are also provided with node instances. You can listen to any DOM event by delegation at the root. The manager will supplement the event facade for such events with an extra node property containing a reference to the node that received the event. (In fact, the node that would have received the event had it been there, but the manager makes it all look like it has always been there). Just as with forSomeNodes the manager can make a fairly safe assumption about the lifespan of that node passed as part of the event facade and it returns to the pool when the event has run its course. Once again, the developer can call hold to keep that reference and call release when it is no longer needed.

What happens when a node itself needs to respond to a DOM event? All it needs to do is add the type of event to a wakeup list kept by the manager so that when the event fires, the manager will take an instance from the pool, slide it to the position in the tree where the event would have happened and wakes it up with the event as if that instance had always been there. FWTreeNode itself does this with the "click" event so that it can respond to clicks by toggling expansion or selection. For events that are fired within the node itself, such as attribute change events, since the attribute must be changed from within the instance itself (by using the set method), any such events will fire while the instance is already active.

Dynamic Loading

The manager also handles dynamic loading, a feature much appreciated in YUI 2’s TreeView. If a function is set on the dynamicLoader attribute, the first time a collapsed node is expanded, the dynamic loader will be called. The loader will get a reference to the node being expanded and a callback function. Whenever it manages to get the new nodes, it must call the callback function passing the array of new nodes to add to the tree. Along with the examples of gallery-fwt-treeview there is one showing this feature, extracting information from YQL every time a node is expanded. This example uses just four nodes instances, no matter how many tree nodes are shown and each is of a different type (one default type for the root, which is invisible, and one of a different type for each level).

Templating

There is another throwback to YUI 2 TreeView. All rendering is done via templates. A big string containing the markup is built for the expanded sections of the tree and then inserted into the innerHTML of the overall container for the tree in a single action. TreeView was the only widget in the YUI 2 family that did it this way — most others used YAHOO.util.Element and did quite a lot of DOM manipulation. TreeView simply concatenated lots of tiny bits and pieces of strings, without any templates. Once upon a time it was expected that DOM manipulation would eventually see great performance improvements and doing DOM manipulation seemed better than concatenating strings. However, the opposite turned out to be true. Thus, an old part of an old widget turned out to be better than later improvements.

Performance

Now, as for memory consumption, drawing a tree using a Widget per node, each augmented with WidgetChild and WidgetParent, takes 8 times the memory than using the FWTreeView when drawing a tree with about 150 nodes. The pure Widget solution grows in proportion to the depth times the width of the tree (this is not strictly true since the tree is not a square, in fact it grows exponentially with the depth of the tree, the exponent being proportional to the number of children per node). FWTreeView grows linearly with the depth. Thus, with more nodes, the difference grows even sharper. Adding just one more level of nodes to the tree made the browser crash with the Widget-based solution while FWTreeView kept working fine.

All these savings would be expected to come at a cost. After all, managing the pool and sliding those cutout windows should take time. As a matter of fact, the cost of managing nodes is barely noticeable for very small trees. For larger trees, the cost to the browser of managing the huge amounts of memory required by the Widget-based solution completely overwhelms the browser. For the same 150 nodes, the performance of FWTreeView was 12 times faster. I was unable to measure it for a tree one level deeper because Firefox froze and Chrome crashed with the Widget-based tree. (I wasn’t adding one node at a time but one full level at a time so after the 156 nodes it went to 781 nodes, growing exponentially with each level).

Conclusion

The Flyweight pattern allows managing large numbers of nodes with ease, minimizing memory consumption and, indirectly, improving performance by taking less resources from the browser. It can be argued (and has been argued) that Base and Widget are too heavy, and there is some truth to it. One solution is to avoid using them. Another is to use them wisely, which is the option shown here.

This article has described mostly the FlyweightTreeManager object though developers are more likely to use FWTreeView, which inherits from it. FlyweightTreeManager can be instantiated and rendered, but it has no CSS styles and the templates are very basic so the resulting HTML is boring. It should be considered an abstract class. FWTreeView adds several features such as node selection and keyboard navigation. These are not provided by the base abstract classes because each widget (treeview, menu, form) handles them differently. WAI-ARIA support is built-in.

SatyamAbout the author: Daniel Barreiro (screen name Satyam) has been around for quite some time. The ENIAC was turned off the day before he was born, so he missed that but he hasn’t missed much since. He’s had a chance to punch cards, program 6502 chips (remember the Apple II?), own a TRS-80 and see some fantastic pieces of operating equipment in his native Argentina which might have been in museums elsewhere. When globalization opened the doors to the world, his then barely usable English (plus an Electrical Engineering degree) put him on the career path which ended in a 5-year job in the Bay Area back in the days of NCSA Mosaic. Totally intrigued by the funny squiggles a friend of his wrote in his plain text editor, full of <’s and >’s, he ended up learning quite a lot about the world of front-end engineering. It’s been a long journey since COBOL and Fortran. Now he lives quite happily semi-retired in the Mediterranean coast close to Barcelona, Spain. He maintained YUI 2 TreeView starting with the release of version 2.6 until its end-of-life and in doing so, helped to edit what became the Contributor License Agreement since there wasn’t one at the time.

8 Comments

  1. Thanks a lot for sharing this. In my opinion definitely the most valuable and appreciated gallerymodule. YUI3 finally has a its TreeView!

  2. Very nice article. It made me think about the way we are using the various Widget and Base derived classes in our own application. On our development machines, with a good CPU and 8GB of RAM, everything is nice and snappy. But I’m sure a regular user would have a different experience.

    About the TreeView, I’ve always been unpleasantly surprised by the lack of a good TreeView implementation in YUI3. In my opinion, it’s one of the most important widgets a widget library can offer. When I chose between YUI3 and Dojo, the TreeView was the reference widget in my review. Now I’m glad that I didn’t base my decision on the results of this widget comparison.

    The YUI team should pay more attention to the proper implementation of common widgets people need. YUI3 is a great JavaScript framework, but a lot of developers expect it to be a equally good widget library.

  3. I agree with kenjiru. From YUI2 to YUI3 the transition was far from smooth. YUI3 is a rushed product, in my opinion. It’s far from stable and there’s too many moving parts to be called “stable”. You should call it YUI3 BETA. While there’s an explanation why Treeview wasn’t included, whoever decides that YUI3 shouldn’t have the same widgets as YUI2 and decides to make an abrupt change should be questioned, imho. It is very unpleasant when you move the cheese around for the sake of moving cheese around.

    kenjiru wrote:
    “The YUI team should pay more attention to the proper implementation of common widgets people need. YUI3 is a great JavaScript framework, but a lot of developers expect it to be a equally good widget library.”

  4. Here’s a benchmark comparing the Flyweight TreeView with several other TreeView components from the YUI Gallery: http://jsperf.com/yui-treeview

  5. @Ryan

    You are missing Matt Parker’s TreeViewLite in the comparisson. Yes, there are even more TreeViews than you listed and some, such as Matt’s that are really fast. The three slowest ones are based on Widget and/or Base so the numbers are to be expected. Through the numbers on your version completely overwhelm the statistics in its favor, leaving all the rest on the pitiful ranges, my version is several times faster than the others. I am sure that Matt’s will also be on top as well. It all depends on the features you want.

    As a matter of fact, a couple of months ago I made a suggestion on the forum that the YUI library should have several offerings for some the widgets. I made the case for Matt’s TreeViewLite along with some other TreeView. TreeViewLite is a plugin like MenuNav and I also mentioned that some people would also like to have a full featured Menu besides the MenuNav plugin so, if we have clearly defined categories, we actually should have two versions of each component. So, for a lot of components, two versions can be offered, the full featured and the lite and fast one. Your numbers make a point in favor of that.

  6. @Satyam: Yeah, I wanted to include TreeViewLite, but it would have taken a lot more work since it builds trees from markup, whereas the other TreeView components in the comparison all happen to share (mostly) the same data format.

    I’ll try to add TreeViewLite to the comparison today.

  7. Here’s an updated comparison that includes TreeviewLite: http://jsperf.com/yui-treeview/3

    It’s not quite an apples-to-apples comparison since TreeviewLite doesn’t dynamically render to the DOM like the other treeviews — it requires an existing DOM structure. Also, we have to unplug the TreeviewLite plugin inside the test loop or else every subsequent loop would just be a noop.

  8. Impressive numbers indeed.

    Now, perhaps you might have noticed that this article is about the use of the FlyWeight pattern to trees and the TreeView was the first obvious candidate for its use since I obviously have an attachment to that sort of widget, having maintained the YUI2 version.

    The component has been out there since early September and for most of its life, it was marked as ‘proof of concept’ because I didn’t really meant to make it ready for production, it was meant mostly for testing the concept, see if it worked and eventually write about it. In the end, someone asked me to use it and it really didn’t take that much to make it ready. Moreover, it was Dav’s launch of Yogi that made me really put it nice as another sort of ‘proof of concept’, in this case, in my use of Yogi.

    Though performance, relative to other Widget-based trees was important, I have yet to optimize it for speed. Whenever I had to choose speed vs. clear code, I choose the later. I have to improve its speed and will get back some of the shortcuts I made in early versions which I discarded in favor of clarity. But I have a few features to add to it before I tackle that. Will this compete with yours? Not at all, it is not meant to do that.

    However, speed is not all. There is something to be said in favor of standardizing and we all know that Base and Widget are slow, nevertheless, some people might still prefer to adhere to the standard. After all, we’ve been using YUI2 TreeView in YUI3 for all these years, though it was a headache to use a widget that didn’t behave as a YUI3 Widget does, what’s the point of having another one that doesn’t either? (BTW, there you have another one more to add to the performance test).

    If we waited for almost three years to get a YUI3 TreeView Widget it was not to have something that doesn’t behave like one. Ad-hoc solutions have always been there. Adam Moore ported YUI2 Treeview to YUI3 early on (never actually tried it myself) and I could have put together such and ad-hoc solution long ago, when I had the YUI2 very clear in my mind. But, for me, it was never the point.

    In YUI2, we had three family of widgets, those that inherited from Element (most of them), earlier ones that didn’t (Container family, Menu, they used YAHOO.util.Config an earlier version of the current Attribute) and TreeView, which didn’t fit in any category. That caused a lot of headaches because their APIs were totally different. The drop-down button on the Menu bar was the most crazy thing, the Button being a subclass of Element while Menu wasn’t. That was confusing, and we are talking about just three families of APIs. Thus, I don’t like to start making individual widgets each with its very specific API, sacrificing everything for speed.

    Perhaps, it is time to have YUI4 with another set of infrastructure components with a different programming model, but until then, I still hope to have YUI3 components that behave like such. Otherwise, instead of a framework, YUI3 would look just as a collection of cool and fast widgets taken from here and there.

    That is not to say there is no place for a really fast TreeView as yours. Indeed, for a big and fast tree, it would certainly be a good choice.