Brendan Enrick

Daily Software Development

Using a DropDownList without ViewState

One of the most ViewState heavy controls is the DropDownList. It stores in ViewState the Text and Value for every ListItem in the DropDownList. This means large Lists can get really nasty when ViewState comes into play. They also include all of these entries a second time because they're all in the html. Being in the html will only slow the page down as it is sent to the user, but the ViewState is downloaded by the user and also must be uploaded back up to the web server. This is a horrible user experience if the page has a large amount of ViewState. Since upload speeds are usually worse than download, the user will probably not like the amount of time the postbacks on the site take. In the following example I am going to show how much ViewState can be saved by simply reloading the data into the DropDownList each time the page is requested.

This is how much ViewState my hundred item DropDownList contains at the beginning of this example.

<input type="hidden" name="__VIEWSTATE" id="__VIEWSTATE" value="/wEPDwULLTEwNjkzMDQ2Nz
MPZBYCAgMPZBYEAgEPEA8WAh4LXyFEYXRhQm91bmRnZBAVZAlFbGVtZW50IDAJRWxlbWVudCAxCUVsZW1lbnQg
MglFbGVtZW50IDMJRWxlbWVudCA0CUVsZW1lbnQgNQlFbGVtZW50IDYJRWxlbWVudCA3CUVsZW1lbnQgOAlFbG
VtZW50IDkKRWxlbWVudCAxMApFbGVtZW50IDExCkVsZW1lbnQgMTIKRWxlbWVudCAxMwpFbGVtZW50IDE0CkVs
ZW1lbnQgMTUKRWxlbWVudCAxNgpFbGVtZW50IDE3CkVsZW1lbnQgMTgKRWxlbWVudCAxOQpFbGVtZW50IDIwCk
VsZW1lbnQgMjEKRWxlbWVudCAyMgpFbGVtZW50IDIzCkVsZW1lbnQgMjQKRWxlbWVudCAyNQpFbGVtZW50IDI2
CkVsZW1lbnQgMjcKRWxlbWVudCAyOApFbGVtZW50IDI5CkVsZW1lbnQgMzAKRWxlbWVudCAzMQpFbGVtZW50ID
MyCkVsZW1lbnQgMzMKRWxlbWVudCAzNApFbGVtZW50IDM1CkVsZW1lbnQgMzYKRWxlbWVudCAzNwpFbGVtZW50
IDM4CkVsZW1lbnQgMzkKRWxlbWVudCA0MApFbGVtZW50IDQxCkVsZW1lbnQgNDIKRWxlbWVudCA0MwpFbGVtZW
50IDQ0CkVsZW1lbnQgNDUKRWxlbWVudCA0NgpFbGVtZW50IDQ3CkVsZW1lbnQgNDgKRWxlbWVudCA0OQpFbGVt
ZW50IDUwCkVsZW1lbnQgNTEKRWxlbWVudCA1MgpFbGVtZW50IDUzCkVsZW1lbnQgNTQKRWxlbWVudCA1NQpFbG
VtZW50IDU2CkVsZW1lbnQgNTcKRWxlbWVudCA1OApFbGVtZW50IDU5CkVsZW1lbnQgNjAKRWxlbWVudCA2MQpF
bGVtZW50IDYyCkVsZW1lbnQgNjMKRWxlbWVudCA2NApFbGVtZW50IDY1CkVsZW1lbnQgNjYKRWxlbWVudCA2Nw
pFbGVtZW50IDY4CkVsZW1lbnQgNjkKRWxlbWVudCA3MApFbGVtZW50IDcxCkVsZW1lbnQgNzIKRWxlbWVudCA3
MwpFbGVtZW50IDc0CkVsZW1lbnQgNzUKRWxlbWVudCA3NgpFbGVtZW50IDc3CkVsZW1lbnQgNzgKRWxlbWVudC
A3OQpFbGVtZW50IDgwCkVsZW1lbnQgODEKRWxlbWVudCA4MgpFbGVtZW50IDgzCkVsZW1lbnQgODQKRWxlbWVu
dCA4NQpFbGVtZW50IDg2CkVsZW1lbnQgODcKRWxlbWVudCA4OApFbGVtZW50IDg5CkVsZW1lbnQgOTAKRWxlbW
VudCA5MQpFbGVtZW50IDkyCkVsZW1lbnQgOTMKRWxlbWVudCA5NApFbGVtZW50IDk1CkVsZW1lbnQgOTYKRWxl
bWVudCA5NwpFbGVtZW50IDk4CkVsZW1lbnQgOTkVZAlFbGVtZW50IDAJRWxlbWVudCAxCUVsZW1lbnQgMglFbG
VtZW50IDMJRWxlbWVudCA0CUVsZW1lbnQgNQlFbGVtZW50IDYJRWxlbWVudCA3CUVsZW1lbnQgOAlFbGVtZW50
IDkKRWxlbWVudCAxMApFbGVtZW50IDExCkVsZW1lbnQgMTIKRWxlbWVudCAxMwpFbGVtZW50IDE0CkVsZW1lbn
QgMTUKRWxlbWVudCAxNgpFbGVtZW50IDE3CkVsZW1lbnQgMTgKRWxlbWVudCAxOQpFbGVtZW50IDIwCkVsZW1l
bnQgMjEKRWxlbWVudCAyMgpFbGVtZW50IDIzCkVsZW1lbnQgMjQKRWxlbWVudCAyNQpFbGVtZW50IDI2CkVsZW
1lbnQgMjcKRWxlbWVudCAyOApFbGVtZW50IDI5CkVsZW1lbnQgMzAKRWxlbWVudCAzMQpFbGVtZW50IDMyCkVs
ZW1lbnQgMzMKRWxlbWVudCAzNApFbGVtZW50IDM1CkVsZW1lbnQgMzYKRWxlbWVudCAzNwpFbGVtZW50IDM4Ck
VsZW1lbnQgMzkKRWxlbWVudCA0MApFbGVtZW50IDQxCkVsZW1lbnQgNDIKRWxlbWVudCA0MwpFbGVtZW50IDQ0
CkVsZW1lbnQgNDUKRWxlbWVudCA0NgpFbGVtZW50IDQ3CkVsZW1lbnQgNDgKRWxlbWVudCA0OQpFbGVtZW50ID
UwCkVsZW1lbnQgNTEKRWxlbWVudCA1MgpFbGVtZW50IDUzCkVsZW1lbnQgNTQKRWxlbWVudCA1NQpFbGVtZW50
IDU2CkVsZW1lbnQgNTcKRWxlbWVudCA1OApFbGVtZW50IDU5CkVsZW1lbnQgNjAKRWxlbWVudCA2MQpFbGVtZW
50IDYyCkVsZW1lbnQgNjMKRWxlbWVudCA2NApFbGVtZW50IDY1CkVsZW1lbnQgNjYKRWxlbWVudCA2NwpFbGVt
ZW50IDY4CkVsZW1lbnQgNjkKRWxlbWVudCA3MApFbGVtZW50IDcxCkVsZW1lbnQgNzIKRWxlbWVudCA3MwpFbG
VtZW50IDc0CkVsZW1lbnQgNzUKRWxlbWVudCA3NgpFbGVtZW50IDc3CkVsZW1lbnQgNzgKRWxlbWVudCA3OQpF
bGVtZW50IDgwCkVsZW1lbnQgODEKRWxlbWVudCA4MgpFbGVtZW50IDgzCkVsZW1lbnQgODQKRWxlbWVudCA4NQ
pFbGVtZW50IDg2CkVsZW1lbnQgODcKRWxlbWVudCA4OApFbGVtZW50IDg5CkVsZW1lbnQgOTAKRWxlbWVudCA5
MQpFbGVtZW50IDkyCkVsZW1lbnQgOTMKRWxlbWVudCA5NApFbGVtZW50IDk1CkVsZW1lbnQgOTYKRWxlbWVudC
A5NwpFbGVtZW50IDk4CkVsZW1lbnQgOTkUKwNkZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dn
Z2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2dnZ2
RkAgUPDxYCHgRUZXh0BQlFbGVtZW50IDBkZGQCc/YoLQgXzJamhzzCRizwdOQs9w==" />

And at the end of it, this is all that remains.

<input type="hidden" name="__VIEWSTATE" id="__VIEWSTATE" value="/wEPDwULLTEwNjkzMDQ2NzM
PZBYCAgMPZBYCAgUPDxYCHgRUZXh0BQpFbGVtZW50IDIzZGRky26p9Cn4TiZyx2yoBv7mRgWW+gQ=" />

It is a frightening thought, but there are plenty of sites with far more ViewState than this. I am talking some people have talked to me about pages that are multiple megabytes in size.

In the following example I use a simple page with 1 DropDownList, 1 Button, and 1 Label.

Here is the starting Default.aspx page.

<%@ Page Language="C#" AutoEventWireup="true" CodeFile="Default.aspx.cs" Inherits="_Default" %>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head runat="server">
    <title>Untitled Page</title>
</head>
<body>
    <form id="form1" runat="server">
    <div>
        <asp:DropDownList ID="DropDownList1" runat="server" EnableViewState="true" />
        <asp:Button ID="Button1" runat="server" Text="Postback" />
        <asp:Label ID="Label1" runat="server" />
    </div>
    </form>
</body>
</html>

Here is the starting Default.aspx.cs code-behind file.

using System;
using System.Web.UI.WebControls;

public partial class _Default : System.Web.UI.Page 
{
    protected void Page_Load(object sender, EventArgs e)
    {
        if (!IsPostBack)
        {
            // Create my data source (this would normally be data access or something similar)
            System.Collections.Generic.List<ListItem> myData = new System.Collections.Generic.List<ListItem>();
            for (int i = 0; i < 100; i++)
            {
                myData.Add(new ListItem("Element " + i.ToString(), i.ToString()));
            }
            DropDownList1.DataSource = myData;
            DropDownList1.DataBind();
        }
        else
        {
            Label1.Text = DropDownList1.SelectedValue;
        }
    }
}

Now we can make a little change here. We need to disable ViewState. The other change that we need to make is that we now have to populate the data on every request. We also need to make sure that we populate the DropDownList before Initialization of the Page occurs. This means we should override OnInit and place out code before base.OnInit. The reason we do this is so that we have data loaded in the DropDownList before the selected value of controls are set for us. Otherwise we would have to handle this on our own.

This is the new Default.aspx

<%@ Page Language="C#" AutoEventWireup="true" CodeFile="Default.aspx.cs" Inherits="_Default" %>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head runat="server">
    <title>Untitled Page</title>
</head>
<body>
    <form id="form1" runat="server">
    <div>
        <asp:DropDownList ID="DropDownList1" runat="server" EnableViewState="false" />
        <asp:Button ID="Button1" runat="server" Text="Postback" />
        <asp:Label ID="Label1" runat="server" />
    </div>
    </form>
</body>
</html>

This is the new Default.aspx.cs

using System;
using System.Web.UI.WebControls;

public partial class _Default : System.Web.UI.Page 
{
    protected override void OnInit(EventArgs e)
    {
        // Create my data source (this would normally be data access or something similar)
        System.Collections.Generic.List<ListItem> myData = new System.Collections.Generic.List<ListItem>();
        for (int i = 0; i < 100; i++)
        {
            myData.Add(new ListItem("Element " + i.ToString(), i.ToString()));
        }
        DropDownList1.DataSource = myData;
        DropDownList1.DataBind();
        base.OnInit(e);
    }

    protected void Page_Load(object sender, EventArgs e)
    {
        if (IsPostBack)
        {
            Label1.Text = DropDownList1.SelectedValue;
        }
    }
}

Enjoy not having TONS of extra ViewState. Remember that ViewState is extremely useful, but can cause problems if you ignore its existence completely. It can lead to huge pages that are quite slow.

Generic List AddRange, Remove, and Count Performance

The .NET System.Collections.Generic.List class is not a linked list as non-.NET users might expect. This list class is actually more like an array list than a linked list. Because of this it has some of the benefits of arrays. Simply because of the array data structure which exists within the generic list class, the class is able to achieve a constant time Count function. The basic array data structure is a collection of objects which are stored contiguously in memory, and because of this it makes counting them easy. It also makes it quite easy to index into a specific location, because you can just jump straight to the correct location in memory. With a linked list one has to traverse the list. The advantage of the linked list is that it is held together using pointers, so if you want to add nodes it is simply an update to pointers. This means that adding a collection of nodes can take constant time.

I would highly recommend against the array list if you will be adding and removing objects from this collection often. Since there is an allocated amount of space in memory for the array this means that if you need to exceed this space then you will need to create a new list. Using Big O notation the AddRange function of list will take O(n) time to complete. The n in this case is the number of elements to add. This doesn't seem to bad, but when the allotted space is exceeded the array will need to move and recreate itself with more space. This is the big performance hit. For this operation it will have O(n+m) time, because you will have to do the regular n operations plus m operations for the original data in the array.

Removing an element from an array requires a little bit of work. One reason for this is that the array data structure should never contain an empty space. This means that first you will need to perform a linear search algorithm to find the element to remove. Stepping one by one through the list. Upon reaching the element to remove, it is removed, but then all the elements after that one must be moved forward in the array so no space exists. This causes the remove function to perform in linear time.

  • Capacity O(1)
  • Count O(1)
  • AddRange O(n) or O(n+m)
  • Remove O(n)

I am planning to write of series of little bits of stuff. If you catch any mistakes in any of this series please comment on the correction ASAP. I don't want to be passing along incorrect information.

Enjoy! 

C++ List Operation Performance

I am fairly certain that the C++ Standard Template Library's list object's size function is an O(n) operation. For those of you less algorithmically informed people I am saying that a linked list which uses pointers to the next object in the list has to take linear time (directly corresponding to the number of elements) to find out the size of the list. At first this seems kind of odd. One would wonder why not just keep the count of the elements stored somewhere.

Keeping the count of the number of elements in a linked list will make what I believe is the linked list's greatest asset less valuable. The splice function (which is like the AddRange function) is able to just update pointers. This is amazingly useful because added n number of elements can take constant time. Meaning that it takes just as long to add 10 elements as to add 1000 elements. When needed that is a life saver. Having that ability though prevents being able to keep track of the size of the list, because the list doesn't know how many elements you are splicing in. It would need to take linear time to count them. Because of this it would make it linear instead of constant time. Ouch.

Because of this close relationship between the size and splice functions one will have to be linear and one constant. It seems that it was decided that with a linked list it would just be easier to iterate to the end instead of using the size. Splicing is a lot more important in my opinion to the usefulness of a linked list. I suggest perhaps a second object which is a linked list which has a constant size and a linear splice for when size will be checked more often than splicing will occur.  

I was discussing this with someone recently and found it quite interesting, and I now think I am going to go and start reading more about the algorithms of the functions used in C#. Perhaps in the future I will write about the algorithms in .NET and the runtime of these algorithms. I hope so.