The Flyweight Pattern
Some objects manage a large number of items. If those items are complex objects themselves, such as subclasses of
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
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
children, the later being an array of further objects defining the next level of nodes.
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.
getXxxx methods (
getNodeBy, etc.) return node references. Unlike the traversal methods (
forSomeChildren), the manager cannot predict when you are done with the requested node, thus, those nodes are automatically placed on hold for you.
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.
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).
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.
Now, as for memory consumption, drawing a tree using a
Widget per node, each augmented with
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).
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
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.