Using buffering techniques for large list controls

• Download source code - 14.6 KB

Introduction

The purpose of this article is to highlight the effectiveness of using buffering techniques when rendering large quantities of data. Combining several different methods for increasing the processing time of rendering can result in real-time rendering of items, even when the container list control owns millions of entries. This is targetted more towards custom owner-drawn components, the likes of tile components or custom list view components.

Background

While developing a framework of Metro style components, I stumbled across the need for buffering when working on a custom ListView component. A ListView is capable of containing any number of items, and rendering should be a seamless and flicker-free experience. In order to achieve this, different layers of buffering were aggregated until the rendering operation became visibily instantaneous.

Buffering Methods

To achieve buffering in custom controls, there are several different options available which provide the functionality. Below is an outline of the core concepts and their purposes when buffering GDI.

Double Buffering

public class MyControl : UserControl
{
    public MyControl()
    {
        DoubleBuffered = true;
        SetStyle(ControlStyles.OptimizedDoubleBuffer, true);
    }
}

A large number of components implement a protected DoubleBuffered property. This property internally signals that the component should execute any painting operations on a separate memory buffer.

What this means is that the Paint event does not execute on the graphics handle of the component directly, but instead a separate Graphics buffer is created in memory, and the painting operation occurs on that instead. One the painting operation has completed on the memory buffer, this buffer is then painted onto the component graphics handle.

The purpose of this is to enable the commit of a completed paint operation in a single operation. For instance, imagine a component responsible for rendering 1,000 items in a single paint operation, each with a 0.0004s rendering time. A single paint operation would consume 0.4s (400ms) to complete. During this 400ms, the control will actively update while the paint operation is occurring, resulting in partial graphics updates being committed to the visible screen while the operation is on-going. This is a consequence known as tearing, where parts of the component are being updated, while the old graphics are still visible.

Double buffering eliminates this issue by completing the 400ms painting operation on a separate handle, then replaces the entire component visible state in a single swoop, removing the tearing issue and appearing as though the update completed seamlessly.

Disabling WM_ERASEBKGND

public class MyControl : UserControl
{
    private const int WM_ERASEBKGND = 0x0014;

    protected override void WndProc(ref Message m)
    {
        if (m.Msg != WM_ERASEBKGND)
            base.WndProc(ref m);
    }
}

In Windows, a WM_ERASEBKGND message corresponds to a request sent to the active component when the background of the component should be erased. This message is responsible for only erasing the background, and thus becomes redundant when we begin implementing a custom drawn control.

This Windows message increases strain on a custom control, forcing the system to destroy the existing background prior to any painting operation. This increases the amount of work involved before any painting operation actually takes place, thus it becomes common practise to disable this Windows message and instead fill the Paint graphics handle with the background color, replicating the same process.

Buffered Graphics (and Buffered Graphics Context)

The .NET Framework supplies a BufferedGraphics class. This class, when instantiated, is responsible for retaining an active graphics handle which can be re-used for a painting operation. The major advantage of using this class is that a single, expensive paint operation can be retain in memory, so that a repeat painting operation does not need to render all of the relevant items again.

A BufferedGraphics object should be disposed and reset whenever the graphical interface requires updating, for example:

• The control is resized; more information may need rendering, or the background color needs to be updated to fill the new region.
• The control is scrolled; the list of visible items in the control need moving to accommodate the scroll.
• The control has a mouse movement: a visible item may now be in the 'hovered over' state, resulting in a different color being drawn.

These situations require the existing graphics handle being disposed so the change in state can be committed to the control graphics handle. See the below example of the user of a BufferedGraphics object.

public class MyControl : UserControl
{
    private BufferedGraphics buffer;
    private BufferedGraphicsContext bufferContext;

    public MyControl()
    {
        // initialize the BufferedGraphics object to null by default
        buffer = null;

        // initialize the BufferedGraphicsContext object which is the
        // graphics context for the current application domain
        bufferContext = BufferedGraphicsManager.Current;
    }

    protected override void OnPaint(PaintEventArgs e)
    {
        // check whether our buffered graphics have been allocated yet,
        // if not then we need to create it and render our graphics
        if (buffer == null)
        {
            Rectangle bounds = new Rectangle(0, 0, Width, Height);

            // allocate our graphics buffer, which matches the dimensions of
            // our control, and uses the paint Graphics object as a base for
            // generating the Graphics handle in the buffered graphics
            buffer = bufferContext.Allocate(e.Graphics, bounds);

            // fill our graphics buffer with a white color
            buffer.Graphics.FillRectangle(Brushes.White, bounds);
        }

        // render our graphics buffer onto the target graphics handle for
        // the paint operation
        buffer.Render(e.Graphics);
    }

    protected override void OnResize(EventArgs e)
    {
        // check whether we have an existing graphics buffer which uses
        // some old dimensions (prior to the resize)
        if (buffer != null)
        {
            // dispose of the graphics buffer object and reset to null to force
            // the invalidation to re-create our graphics object
            buffer.Dispose();
            buffer = null;
        }

        // invalidate our control which will cause the graphics buffer to be
        // re-created and drawn with the new dimensions
        Invalidate();
    }
}

Slicing Large Data

In order to benefit from the above double buffering techniques when rendering a custom list control, it's important to realise that there's no realistic method of being able to render all items in the collection. When a control has upwards of one million rows, the painting operation would become too intensive for double buffering to make any sense.

Instead, to decrease the amount of work involved with painting, the collection needs slicing such that we only have to render a small segment of the data required. This is achievable by using mathematical formulae to determine which item is visible at the top of the control view region, and calculating how many items are visible from the top to the bottom.

In order to achieve any of this functionality, it's important that either a constant or configurable field or property be available to define the height (or dimensions) of a single item. Below, let's allow a property (ItemHeight) be available for the user to specify a custom height:

public class MyControl : UserControl
{
    private int itemHeight;

    public MyControl()
    {
        itemHeight = 18;
    }

    [Browsable(true)]
    public int ItemHeight
    {
        get { return itemHeight; }
        set { if (itemHeight != value) { itemHeight = value; Invalidate(); } }
    }
}

The default item height is 18px, which can be configured at design time or runtime. Whenever the item height is changed the control is invalidated.

The next stage is to create the collection which will store the items we are interested in displaying in the control. For the purposes of this tutorial the control will display a list of String objects. If we wish to properly monitor our collection for additions, removals or movement of items, we need to implement methods of corresponding back to our control on any of the Add, Remove etc. methods.

To make this simple, our control shall use the ObservableCollection<> class which implements the INotifyCollectionChanged interface, and we'll hook into the CollectionChanged event to update the control.

public class MyControl : UserControl
{
    private int itemHeight;
    private ObservableCollection<string> items;

    public MyControl()
    {
        itemHeight = 18;
        items = new ObservableCollection<string>();
        items.CollectionChanged +=
             new NotifyCollectionChangedEventHandler(ItemsCollectionChanged);
    }

    [Browsable(true)]
    public int ItemHeight
    {
        get { return itemHeight; }
        set { if (itemHeight != value) { itemHeight = value; Invalidate(); } }
    }

    [Browsable(false)]
    public ObservableCollection<string> Items
    {
        get { return items; }
    }

    protected virtual void ItemsCollectionChanged(object sender, NotifyCollectionChangedEventArgs e)
    {
        
    }
}

The next stage is to implement an algorithm to enable scrolling when the number of visible items in the control would exceed the height of the view. This can be calculated using the item height property, the number of items and the current height of the control.

    protected virtual void CalculateAutoScroll()
    {
        // ensure that autoscrolling is enabled in the control for scrollbar visibility
        AutoScroll = true;

        // update the minimum size for the scrolling procedure, which ensures that the
        // maximum scroll value vertically is equal to the item height x item count
        AutoScrollMinSize = new Size(0, itemHeight * items.Count);
    }

This will display a scroll-bar which accommodates for any number of items in the collection. This method should be called any time the collection changes, so we must modify the ItemsCollectionChanged method to raise this calculation.

    protected virtual void ItemsCollectionChanged(object sender, NotifyCollectionChangedEventArgs e)
    {
        // recalculate the auto-scroll region to accommodate the changes
        CalculateAutoScroll();

        // invalidate the control so that any removed or moved items are updated
        Invalidate();
    }

The same method should also be raised when the item height property is changed, so that the new item height is applied to the algorithm.

    [Browsable(true)]
    public int ItemHeight
    {
        get { return this.itemHeight; }
        set
        {
            if (itemHeight != value)
            {
                itemHeight = value;
                CalculateAutoScroll();
                Invalidate();
            }
        }
    }

Once these have been configured, the operation for slicing data can begin. The calculation for the starting and ending indices are extremely easy to calculate using an algorithm.

The Paint method for the control must be overridden so we can render out items appropriately.

    protected override void OnPaint(PaintEventArgs e)
    {

    }

To calculate the starting index, the scroll position must be taken into account to properly generate the correct index. The base index is calculated based on the scroll position and the height of each item.

    int start = (int)Math.Floor((double)Math.Abs(AutoScrollPosition.Y) / (double)itemHeight;

The number of items available for view is calculated based on the height of the control and the height of each item.

    int count = (int)Math.Ceiling((double)Height / (double)itemHeight);

Additionally, if the user has scrolled to a position where only half of an item may be visible at the top of the control, we must take into account the positional offset. To account for this we must calculate the remaining pixels after dividing the scroll position by the height of each item.

    int offset = -(int)(Math.Abs(AutoScrollPosition.Y) % itemHeight);

The below image highlights where the values represent when calculating the indices and offset.

Finally, using these values we can devise which items in the control need to be rendered.

    protected override void OnPaint(PaintEventArgs e)
    {
        int start = (int)Math.Floor((double)Math.Abs(AutoScrollPosition.Y) / (double)itemHeight);
        int count = (int)Math.Ceiling((double)Height / (double)itemHeight);
        int offset = -(int)(Math.Abs(AutoScrollPosition.Y) % itemHeight);

        for (int i = 0; count > i && start + i < items.Count && 0 <= i; i++)
        {
            int index = start + i;
            string value = items[index];
    
            int x = 0;
            int y = (i * itemHeight) + offset;

            e.Graphics.DrawString(
                value,
                this.Font,
                Brushes.Black,
                new Rectangle(x, y, Width, itemHeight)
            );
        }
    }

The result of this code is a small, simple control which can handle rendering slices of data from a collection, rather than attempting to render all data into the control. The procedure outlined above is similar to a 'clipping' effect, where items which aren't visible at neither the top nor bottom of the control are simply not rendered.

Combining the Methods

As mentioned in the introduction, the purpose of this article is to highlight how to use these rendering methodologies to represent large quantities of data in a simple control. We can combine the buffered graphics approach with the slicing of data to provide the interface for millions of rows with very little overhead.

The article has an attachment containing two core files: UI.cs and CustomBufferedList.cs. The CustomBufferedList.cs file contains the code for our list control which combines the double buffering and data slicing techniques.

A method implemented in the CustomBufferedList class adds support for identifying a row at a given location in the control. In order to calculate an item at a location, a similar method is used to the previous OnPaint implementation, where the starting index and number of visible items is calculated, and then the visible items are iterated through to determine whether the bounds would fall within the location.

        public int GetItemAt(Point location)
        {
            // calculate the starting index based on the scroll position 
            int start = itemHeight > 0 ?
                (int)Math.Floor((double)Math.Abs(AutoScrollPosition.Y) / itemHeight) : 0;

            // calculate the total number of items visible in the control
            int visible = (int)Math.Ceiling((double)Height / (double)itemHeight);

            // calculate the rectangle for the first item bounds
            Rectangle bounds = new Rectangle(
                0,
                -(int)(Math.Abs(AutoScrollPosition.Y) % itemHeight),
                Width,
                itemHeight
            );

            // increment through the items to match the item at the location
            for (int i = 0; 0 <= start + i && start + i < items.Count && visible > i; i++)
            {
                // check whether the mouse location falls within these bounds
                if (bounds.Contains(location))
                    return start + i;

                // increment the position of the bounds based on the item height
                bounds.Y += itemHeight;
            }

            // failed to match an item at this location
            return -1;
        }

All other content in the file is responsible for handling the process of using buffering techniques and using data slicing. The OnInvalidateBuffer() method is responsible for handling the invalidation of the BufferedGraphics object, and also supports ignoring the method invoke when updates have been suspended.

When adding large bodies of data to the CustomBufferedList, it's good practise to invoke the BeginUpdate() and EndUpdate() methods. These methods temporarily suspend painting of the component, and then resume and invalidate the component, respectively.

// begin an update on the list, which suspends the layout
list.BeginUpdate();

// populate the list with a massive amount of values
for (int i = 0; 1000000 > i; i++)
    list.Items.Add(string.Format("Custom buffered list item {0}", i + 1));

// end the update to commit the changes to the buffer
list.EndUpdate();

Points of Interest

The CustomBufferedList component included with the project also implements OnMouseMove encapsulation which handles item highlighting. It would be just as simple to implement a selection process based on similar behaviour, which would provide the functionality of a ListView component.

Apologies if I have missed anything important or if some areas of the article appear rushed. I haven't had much time to write articles, so this was an overview of how to achieve the goal which was set-out at the beginning.

History

• Version 1.0 - Initial article.