replicator.org ... continuous garbage collection

Now that spatial queries are implemented, the Presentation Layer needs to access the Visuals stored in the R-Tree. The Presentation Layer consists of separate classes that handle the distinct visual layers. These are the Nodes, the Connectors, and the Labels. Additional layers are used for overlays and prototype Visuals, but these are not of importance right now.

BrainSharper supports dragging the whole canvas at once. Zooming is not yet supported, but will be soon.

Right now, the Presentation Layer receives the events that are dispatched by the domain and realizes them by creating or modifying (WPF) control objects. Obviously, this is a push-model: The domain pushes the events to the user interface.

To change the Presentation Layer from a stupid “I present you all Visuals” Canvas to one that manages the only the Visuals inside the Viewing Area, the following components need to be created:

• First of all, a component that can retrieve and present the Visuals directly from the R-Tree is needed. For the lack of ideas I call it the “Visual Presenter”.
• Another component, that coordinates the viewing area rectangle must be introduced. This component computes the model rectangle and forwards the dirty rectangles to the “Visual Presenter”. I will call that class the “Viewing Area”.
• A component that flushes unused visuals needs to be built. This component runs when the user is idle and instructs the visual layers to free Visuals that are not inside the viewing area. ”Visual Collector” is probably a nice name for it.

Additionally, I decided to split up the layer classes into a controlling part, that handles all domain events, and a viewing part, that displays the controls.

All in all, the Presentation Layer is going to morph towards a more pull-oriented nature. It watches the domain events to get notified when something changes. And whenever the view area changes, it queries the missing Visuals directly from the database.

Below is a rough visualization that covers only the node layer:

Some details of the implementation:

Visual Presenter

The Visual Presenter queries the Visuals from the R-Tree table. Obviously, this takes some time depending on the number of visuals that intersect with the Viewing Area. On my computer, the queries run in sub-millisecond time, but to avoid lags on slower computers, I decided to decouple the queries from the main thread. This should improve the scrolling experience, but may cause new Visuals to pop in while the user is dragging the document.

Visual Collector

Another advantage of introducing a Worker Thread, is that the Visual Collector can also use it. I’ve decided to implement the Visual Collector in a similar way like the Presenter: As soon the Viewing Area has changed and the user is inactive for some time, the Visual Collector runs a background task to find out what Visuals should be displayed inside the viewing area. It then instructs all layers to hide Visuals that are not visible. Of course, the Layer Views could decide autonomously to hide the visuals that are not inside the viewing area, but I wanted that the Presenter and the Collector use the same rectangle information for the intersection tests. This guarantees that the two mechanisms don’t contradict in their decisions. Another advantage is that the Presenter and the Collector are both independent of the user interface framework.

The next step for BrainSharper is to extend its capability to handle very large documents. It should be possible to edit documents that contain thousands of nodes and connectors without noticing a drop in rendering performance. While this “optimization” may look like a premature one, I fear that continuing without it would have dramatic consequences on the internal design, which can be very hard to fix later on. Exceptionally, and only when an optimization directly concerns scalability, my personal guidelines allow me to optimize prematurely, so here it goes:

In its document editor, BrainSharper uses event sourcing to build up the domain model. There are two derived models, or as I call them now “views”, these are a) the domain model and b) the compensating changesets. When a new event is created, the event and both views are written to an SQLite database in one single transaction.

SQLite has this great feature, the R-Tree, which implements a data structure that is suitable for queries over multi-dimensional ranges. So the idea is to maintain one separate R-Tree table to optimize queries for the presentation layer. Maintaining an R-Tree table has the following consequences:

• Besides the R-Tree table, one more view table is required: In the domain model, different types of visuals are stored in separate tables (nodes, connectors, etc.), but when only one R-Tree is used to cover all presentation queries, the R-Tree also needs to refer to different visual types. All the visuals are identified by a GUID, but the R-Tree can only refer to 64 bit integer identifiers. So my first idea was to link the R-Tree to the domain model by using a pivot table, but then I thought that CQRS is about optimizing read performance and so it shouldn’t be a problem to introduce another, simpler, “view” that just contains a list of serialized domain visuals referable by a single integer primary key. The additional table may nearly double the storage that is used, but I guess it’s worth it, because then a query of all visible objects is just single SQL statement.
• The location of the visuals have to be determined up front: Right now, only the minimum information is stored in the domain model. For example, there is no location information directly available for connectors or labels in the database. Their positions are derived from the positions of the nodes in the presentation layer. Now, at the time the R-Tree is generated, the location information needs to be derived directly from the domain model, which is basically simple, but may require some additional lookups.
• The size of the visuals have to be determined up front: To compute the final rectangle that a visual covers on the document, the size of each visual needs to be computed.  A problem for which I can see no exact solution. For example, the effective height of a node or the width of a label is dependent on the size of the text that is displayed, which is a measurement that only the presentation layer can provide (or the text subsystem). So to avoid overcomplicating things I’ll need to impose some limits on the maximum size of the visuals and consider these as margins for the final range queries. I guess it should be tolerable to have a number of additional, invisible objects on the screen without compromising performance that much. But even if so, invisible visuals could be thrown away immediately after their final position has been measured.
• The location and the size of some visuals may depend on others: While a node’s center is directly encoded in its domain model object, the start and ending positions of the connectors are not. Therefore, whenever a node is changed, the rectangle information in the R-Tree of all its related connectors need to be updated. For now, this behavior needs to be hardcoded in the component that maintains the R-Tree, however, the chain of dependencies can be derived implicitly from the relations of the visuals. But implementing a change notification system on top of the domain model is not what I want to work on right now, but I am afraid that it might be required for future features.

Well, and that is only half of the complexity. A lot more is required to implement the caching behavior for the visuals that are shown on the screen and specifically the logic that decides what rectangles are being queried from the R-Tree. I may cover that in another post.

Be warned: this is a rant, and I may not have solutions for the problems outlined.

Right now I am trying to use WPF 4 to implement a concept mapping editor. I was seriously prepared to handle some unexpected WPF issues by my own. But some details just pissed me off:

Font Rendering

The first obvious problem was the font quality (again). By default, WPF uses Cleartype to render fonts; obviously a custom implementation, because WPF just ignored that I switched Cleartype off, system wide.

^{(screenshots of a WPF performance tool, the one below is zoomed 2 times)}

This is – by far – the worst font quality rendering I’ve ever seen on any platform I can remember. (note that the top screenshot above may actually look even worse if you don’t have the same pixel format like my monitor, and the maximized one is just for reference to see how Cleartype works).

Cleartype can be switched off by changing a simple property (a recent feature introduced in WPF 4), but the anti-aliased results without font hinting and Cleartype were too blurry and also a lot worse than any other anti-aliased font rendering I’ve seen before. The only acceptable setting was to draw the fonts with font aligning (hinting) and gray scale anti-aliasing. The result looked slightly odd, but the readability itself was a lot better now.

Drop Shadow Performance

For my concept mapping editor I render drop shadows at each node to increase the plasticity a bit. Everything went fine until I implemented a gesture that allowed to move the entire canvas around. Performance was dropping below 20 frames per seconds for a small number of nodes (about 40), which was very unexpected given the hardware GPU acceleration available. I first verified that everything was indeed rendered in hardware and found out that a lot of temporary render targets were created.

Drawing a WPF visual with a drop shadow works by first drawing the visual to an intermediate render target and then drawing the contents of render target together and the shadow on the screen. But for whatever reason, these intermediate render targets seem to be very, very slow. Switching the shadows off got me back to 80 frames per seconds.

Now there are two primary ways to optimize drop shadow rendering in WPF.

1. Render one drop shadow for the canvas in which the nodes are contained. In XAML this is just a copy and paste, but the result was even slower. It might help a little when the visible size of the window are is not too large, but on a 1920 window, it was slower.
2. Use bitmap caching, also a new feature of WPF 4. Nice, I thought, but this just turned out into another nightmare. While the implementation of the bitmap caching seems to work quite well - it’s effectively one line of XAML and handles all invalidation and refreshing logic –, there was no way to pixel-perfect render the content anymore. Though there is a property “SnapsToDevicePixels”, it just did not work as expected and a full screen bitmap cache always made the content look blurry and even worse: subpixel alignment was inconsistent at different location on the screen. It looked like an off-by one error in computing the texture coordinates. Not only was the text-quality worse (btw: the font rendering options needed to be reset below the markup element that uses bitmap caching… which was unexpected), no, everything looked blurry, the borders, overlays, etc. …. My conclusion: fast, but unusable.

And now the funny thing which really reflects back on the bad implementation quality of WPF. Switching from hardware rendering to software rendering actually improved the framerate, not enough, but considerable. Can’t be, I thought. What a mess.

My solution here is just to turn off all drop shadows while the user is moving the canvas. Simple but effective.

Update: Using intermediate render targets seems to be a lot faster in software. You can find out about the number of render targets your app uses with Perforator’s HW IRTs Per Frame History Graph.

Tooling Bugs

To actually find out why the performance problem existed, I used the WPF Performance Suite by Microsoft, but initially were blocked by two strange bugs (here and here).

Now, after all this bad experience, and with the plan to port all the UI code to Mac OS X, I am reconsidering to use Silverlight or Moonlight. If this does not turn out well, I need to accept that there is currently no decent user interface library available for Windows, except.. yes, may be Qt again, but this will be another story.

Now that BrainSharper’s nodes and connectors are working quite fine, I am thinking about how labels should be implemented.

BTW: A screenshot of BrainSharper in action:

The node in the center is the selected node. By tapping [-], it can be deleted (including all the related connectors) and by pressing and holding [+] it can be connected to an existing node. If there is no node at the time the mouse button is released, a new node is created and connected.

So back to the labels. The most pragmatic way to implement labels as a separate user interface and database object. A label indeed looks similar to a node, but has some different behavior, specifically when it comes to automatic layout and the relation to its connecting lines.

If BrainSharper should support the creation of multi-way connectors, and allow further parameterization (for example by making them bendable), two new connector types are needed:

1. A node to label connector.
2. A label to node connector.

And together with the node to node connector, three different connectors are required to implement all connecting paths.

Premature optimization may be evil, but this cries out loud for a removal of duplication. Right now a connector refers to the From and To node it is connecting with (using GUIDs). To remove the duplication, all connectors need to be treated in a generic way, and all other objects to which connectors can refer to, should be treated as generic nodes.

What BrainSharper needs to support are typed nodes and typed connectors. So our new label just got promoted to a typed node and the three connector types collapse into a generic one.

One consequence is that the attribute schemes of the nodes and connectors need to be treated differently. And there must be a clear distinction between attributes that are generic (like the time of creation) and attributes that are specific to a type (like an absolute position of a node, which a label does not have).

One further realization is that this model allows for plugging in different node and connector types. Actually this is exactly what I had in mind when I was initially planning BrainSharper, but it was too complex to implement upfront, and now, unexpectedly, this feature needs to added very early in the development process.

I truly hope that making nodes and connectors generic does not cause a lot of accidental complexity. I plan to implement the type reference of each node and connector by another GUID that does refer to the (yet fixed) meta information the concrete instance requires (like its attributes, user interface representation and layouting algorithm).

Update: I recognized that for supporting generic nodes and connectors, only the domain model needs to be changed. The events that exist so far, don’t need to be changed, because they represent the user’s intention. This means that graphs that are drawn with the current version should be usable by a future, more generic version of BrainSharper. And because multi-way connectors are not on my todo list of the first product version (a minimum viable product), I decided against going generic right now.

With BrainSharper getting mature, the domain model is starting to show dependencies among the different objects. For example, a node can connect to other nodes, and before a node is deleted, all its connections need to be deleted.

The following ideas came to my mind:

• Enforcing constraints at the domain model.
  This sounds like a good idea, but at the time the primary event is integrated into the domain model, it is too late to do anything else, otherwise the compensating change sets would miss the constraint induced changes. The compensating change set needs to be created before the domain layer is modified.
• Enforcing constraints at the time the change set is created.
  To keep the domain model consistent, dependencies need to be processed before the primary, destructive event is processed. I.e. The connections shall be deleted before the node is. To create these events, the current, unaltered domain model can be used. Then these events need to be placed before the node deletion inside the same change set. This change set does not conflict internally and will generate a matching compensating change set.

Obviously, the second solution seems to be the only way to move forward.

Programming a solution to this specific problem is not a big task, but what about dependencies in general, what if they get more complex? For example, BrainSharper needs to support labels at the connectors and adding connections to the labels may also be allowed. And what if multiple nodes were deleted at once?

Consequently, there is a more generic, recursive dependency problem to solve. I guess this cries for a small DSL, which describes the dependencies among the domain model and specifies the events that need to be created to enforce the constraints.

Update: Instead of a DSL, I’ve implemented a dependency resolution algorithm which recognizes all destructive events in a change set and prefixes them with the destructive events of the dependent objects. The destructions had to be topologically sorted to remove duplicates and keep the order consistent. This ensures that the (re)creation events of the compensating change set were ordered properly. Not a perfect solution yet, but generic enough to be extended with a few lines of code.