Virtual display

A long time ago Mike Lischke wrote a great Delphi component—Virtual TreeView. He stopped supporting it a long time ago, but the component found a new sponsor and a place on GitHub: https://github.com/Virtual-TreeView.

Virtual TreeView supports the VCL framework in Delphi XE3 and later. There are also versions of code that support older Delphis, but you'll have to look around for them. To use it, you have to download the source and recompile two included packages. That will add three new components to Delphi. This example will use the most useful of them, TVirtualStringTree.

The VirtualTree demo compares TListBox with TVirtualStringTree where the latter is used in different ways. Although TVirtualStringTree is very flexible and designed to display tree structures, we can also use it as a very fast listbox, as I will do in this example. To use it as a listbox, you should remove options toShowRoot and toShowTreeLines from the component's TreeOptions.PaintOptions property.

This demo compares two different modes of operation. One is adding lots of lines in one operation. We already know that we should use BeginUpdate/EndUpdate in this case.

The other mode is adding just one line to the list. As this is hard to measure precisely, the operation is repeated 100 times.

Virtual TreeView is different from other components included with Delphi. It operates on a view/model principle. The component itself just displays the data (presents a view on the data) but doesn't store it internally. Data itself is stored in a storage that we have to maintain (a model). Virtual TreeView only stores a short reference that helps us access the data.

The first thing that we must do before we can use the component is to decide how large this reference to data is and set the NodeDataSize property accordingly.

Typically, we'll use an integer index (4 bytes), or an object or interface (4 bytes on Win32 and 8 bytes on Win64). We can also store larger quantities of data in this area, but that kind of defeats the view/model separation principle. In this example, I'll use a simple integer so NodeDataSize is set to 4.

The simplest way to use TVirtualStringTree is to use the AddChild method to add a new node (display line) and pass a user data (reference to model) as a parameter:

VirtualStringTree1.BeginUpdate;
for i := 1 to 10000 do begin
  idx := FModel1.Add('Line ' + IntToStr(i));
  VirtualStringTree1.AddChild(nil, pointer(idx));
end;
VirtualStringTree1.EndUpdate;

The code uses global FModel1: TStringList for data storage. It firstly adds the data to the model FModel1.Add and sets the index of this data (idx) as user data for the newly-created node (AddChild).

The first parameter to AddChild is a reference to the node's parent. As we are not displaying a tree structure but a list, we simply set it to nil (meaning that there is no parent). The second parameter represents user data. AddChild supports only pointer user data so we have to cast our parameter accordingly.

We also have to take care of retrieving the data from the model so it can be displayed on the screen. For that, we have to write OnGetText event handler. This event is called once for each column of each visible line. It is not called for lines that are not visible on the screen.

The code must firstly call Node.GetData to get the user data associated with the node. To be more precise, GetData returns a pointer to user data. As we know that our user data is just an integer, we can cast this pointer to PInteger to access the value (index into the FModel1 string list):

procedure TfrmVTV.VirtualStringTree1GetText(Sender: TBaseVirtualTree;
  Node: PVirtualNode; Column: TColumnIndex; TextType: TVSTTextType;
  var CellText: string);
begin
  CellText := FModel1[PInteger(Node.GetData)^];
end;

If you run the demonstration program and click the Add 10.000 lines button, you'll see that the listbox needs more time for the operation (68 ms in my case) than Virtual TreeView (16 ms). Quite nice!

Clicking the second button, Add 1 line 100 times, shows something completely different. In this case, the listbox is a lot faster (17 ms) than the Virtual TreeView (184 ms).

I must admit that I didn't expect that so I did some digging around. As it turns out, TVirtualStringTree sorts its data on each call to AddChild (unless we called BeginUpdate before that!) This may be useful if you are using a multi-column view where data can be sorted on the selected column, but in our case, it only destroys the performance.

The fix for that is very simple. Just remove the toAutoSort option from the component's TreeOptions.AutoOptions property.

I cleared this flag in the second TVirtualStringTree and the result is obvious. Adding 100 lines now takes 17 ms instead of 184 ms and is on par with the listbox.

The third TVirtualStringTree pushes the whole virtual aspect to the max. Instead of initializing nodes in code (by calling AddChild), we just tell the component how many nodes it must display by setting the RootNodeCount property and the component will call the OnInitNode event handler for each node that is currently visible on the screen. In this mode, not only painting but the initialization is executed on demand!

for i := 1 to 10000 do
  FModel3.Add('Line ' + IntToStr(i));
VirtualStringTree3.RootNodeCount := VirtualStringTree3.RootNodeCount + 10000;

This approach is only feasible if we can somehow determine the part of the model that is associated with the given node in the OnInitNode handler. The only information we have at that moment is the node's index in the list (the Node.Index property). The first node gets index 0, second index 1, and so on. Luckily, that is exactly the same as the index into the TStringList so we can just use the SetData method to set the user data:

procedure TfrmVTV.VirtualStringTree3InitNode(Sender: TBaseVirtualTree;
  ParentNode, Node: PVirtualNode; 
  var InitialStates: TVirtualNodeInitStates);
begin
  Node.SetData(pointer(Node.Index));
end;

This on-demand initialization approach speeds the program up even more. The addition of 10,000 lines now takes only 3 ms. The speed when adding lines one by one is not affected, though:

This concludes my foray into user interface land. The second part of this chapter will deal with an aspect of algorithmic improvement which we usually ignore—caching. And at the very end I will return to Mr. Smith's code from Chapter 1, About Performance, and make it run much faster.