Some objects manage large number of items. If those items are
complex objects themselves, such as subclasses of Base,
the memory consumed by such a collection can take your application
down. However, with a large number of items, you are rarely going
to actually deal with all of those items at once, you don't need
the to be active all the time. This is when the Flyweight pattern
comes 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 for the root augmented by WidgetParent
and a 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 terribly expensive. What we do instead is to have the state in a plain object, without methods, attributes or events, simple property:value sets, and put all the behavior, that is methods and events, in a separate object. This object provides us 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 as
having the paper weakened with too many wholes. What we do instead
is try to have a few behavior objects as we can possibly can.
I had already explored this in my own Gallery Model
module, where the base Model could be augmented by the
MultiRecordModel extension which allowed the same Model to handle
any number of records that slid under the single Model instance.
This allowed the same Model to handle one or multiple records. The
Model provided the window into the data and the MultiRecordModel
extension managed the sliding of the data under it.
For a TreeView, I needed to add a second dimension since, unlike
a list 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
avoid limiting to a Widget, I found that the
generalization had a cost in code size and the abstraction made
little sense. Thus, FlyweightTreeManager is a
subclass of Widget.
The FlyweightTreeManager is not the window, the
paper cutout showing the data through, but it manages the windows
over the plain data underneath. The sliding windows 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 limit 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, nodes can
be of different 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.
To traverse the tree, the manager provides the forSomeNodes
method, which loops through all of the nodes in the tree, depth
first, passing each node to the callback in turn. The method
assumes the node instance will not be used beyond the lifespan of
the callback and returns the node to pool at every step. If there
are different node types, it will provide a suitable instance for
each node. As its name suggest ('some' instead of 'each') the
traversal can be cancelled at any time. A full traversal will
require a number of nodes equal to the depth of the tree, assuming
all the nodes of the same type. 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, when
needed.
What happens when you want to keep a reference to a node? Each
node has a hold method which keeps the node away
from the pool. The developer should use hold
sparingly as this increases memory. When done with the node,
calling release will return it to the pool. Several
getXxxx methods (getParent, getNextSibling,
getNodeBy) 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.
Event listeners are also provided with node instances. You can
listen to any DOM events 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). The node instances provided to the event facade are
returned 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 with events at the node level? DOM events can be
listened to by delegation at the root. You can listen to them at
the node level but that would require you to place the node
instance on hold. If a node needs to respond itself to a DOM
event, all it needs to do is add the type of event to a list kept
by the manager so that when the event fires, the manager will take
an instance from the pool and relay it the event as if it had
always been there. FWTreeNode does this with the "click"
event so that it can respond to clicks by toggling expansion or
selection. For internal node events, 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 YUI2 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 the
examples of gallery-fwt-treeview
there is one showing this feature, extracting information from YQL
every time a node is expanded. All the example uses just four
nodes, no matter how many 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 throughback to YUI 2 TreeView. All rendering is
done via templates. A big string containing the markup is build
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
of them use YAHOO.util.Element and do quite a lot of
DOM manipulation. TreeView simply concatenated lots of tiny bits
and pieces of strings, without any templates, just one bit a time.
Once 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 WidgetChild an 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 with exponentialy with the depth of the tree, the
exponent being 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 this savings would be expected to come at a cost, after all,
managing the pool and sliding those cutout windows around should
take time. As a matter of fact, the cost of managing the 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 while it kept working with FWTreeView.
(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 number 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
ads 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.