And Then…

(Note: this is the conclusion of a 4-part post).

The last bit of optimization in my code, again, involved an understanding of data layering. The S.DS DirectoryEntry class is itself a layer on top of a layer on top of another layer. DirectoryEntry is a wrapper around Microsoft ADSI (Active Directory Services Interface). ADSI, in turn, is a wrapper around basic LDAP protocols. Each of these layers is providing services to another while trying to hide the details of its operation. In order to optimize code that relies on S.DS and, hence, on ADSI and LDAP, it is important, however, to understand what these layers do and to have some sense of how they do it.

ADSI is a Microsoft COM interface (available from C++ or script) that presents an object oriented interface to LDAP. Rather than having programmers worry about LDAP binding and searches, ADSI dispenses directory objects when provided with an LDAP path for the object. The objects, in turn, make available LDAP attributes via COM property accessors. The S.DS DirectoryEntry object is a .NET wrapper for an ADSI COM object.

What’s most important to know about DirectoryEntry and ADSI is that they try to delay binding to LDAP objects for as long as possible. When they do, they also provide mechanisms for you to specify the minimum set of attributes that you want to view. Let’s consider how this comes into play in the example that we’ve been working with.

When the code uses DirectorySearcher to search AD, S.DS and ADSI don’t actually bind to found objects. All they really do is to retrieve the LDAP distinguishedNames (paths) of the results. When we get the DirectoryEntry associated with a SearchResult, we have an “unbound” DirectoryEntry (and ADSI) object. Only when we actually retrieve a Properties value from the DirectoryEntry does S.DS actually bind to the necessary LDAP path.

How can we take advantage of this operational knowledge?

Let’s go back to the UI and consider what we actually need to show. I’ve been glossing over the details here – my list view example has only been showing the name of each retrieved object. In the real code, I show the name of the Group and its UNIX gidNumber. Since this is all I need, why not take advantage of this?

Here’s what we do: instead of having the data layer return a full blown GroupInfo object, let’s define a new class:

class GroupInfo0
{
    public string Name;
    public int gidNumber;

    private GUID guidObject;

    public GroupInfo0(string Name, int gidNumber, GUID guidObject)
    {
        this.Name = Name;
        this.gidNumber = gidNumber;
        this.guidObject = guidObject;
    }

    public GroupInfo GetGroupInfo()
    {
        // S.DS code to retrieve an object
        // via its GUID (details omitted)
        DirectoryEntry de =
             new DirectoryEntry(GetLDAPPath(uidObject));
        return new GroupInfo(de);
    }
}

What we have is a class that provides only the minimal data needed for our list view and then provides a function to retrieve the full GroupInfo class when we actually need it (for example, when the user chooses the group in the list view and decides to perform an operation on it). How can we make use of this class? Let’s return these objects from our directory search instead of full GroupInfo objects. The advantage of doing this is that we can restrict the attributes that S.DS (and ADSI) need to retrieve from LDAP:

DirectorySearch ds = new DirectorySearcher(...);
... set up ds ...
ds.PropertiesToLoad.Add("gidNumber"):
ds.PropertiesToLoad.Add("objectGuid"):
...
SearchResultCollection src = ds.FindAll();
return new SearchResults(src);

By specifically setting the PropertiesToLoad property we inform S.DS that it doesn’t need to “load” all attributes when performing the search. We also need to change our SearchResults class, in order that it returns the simpler GroupInfo0 objects:

class SearchResults
{
    private object[] ao;

    public SearchResults(SearchResultCollection src)
    {
        ao = new object[src.Count];
        foreach(SearchResult sr in src)
            ao[i] = sr.GetDirectoryEntry();
    }

    public GroupInfo0 this[int i]
    {
        get
        {
            if( ao[i] is DirectoryEntry)
            {
                DirectoryEntry de = ao[i] as DirectoryEntry;
                string sName = de.Name;
                int gidNumber =
                    (int)de.Properties["gidNumber"].Value;
                Guid guidObject = de.Guid;
                GroupInfo0 gi0 =
                    new GroupInfo0(sName, gidNumber, guidObject);
                ao[i] = gi0;
                return gi0;
            }
            else
                return ao[i] as GroupInfo0;
        }
    }
}

My use of the “0” notation is not arbitrary. There are several examples of API in Windows that return different levels of data. The 0 level is minimal – 1, 2 and other levels provide increasing amounts of information.

Our UI code will now call the data layer to get a SearchResults object. When the virtual mode list view needs to show an item, the UI code will index into SearchResults and will get a GroupInfo0 object that contains enough information to populate the list view. When the user actually selects an item in the list view and needs to operate on, the UI code will call GroupInfo0.GetGroupInfo() to get a “real” GroupInfo object which it can manipulate.

This last set of changes, reducing the amount of work S.DS and LDAP had to perform, had a huge impact on performance. Collectively, all the techniques that I employed (plus another that I haven’t covered) reduced my original task (populating a list view) from 1200 seconds to 20 seconds. Pretty good, I think!

I could have gotten the same performance numbers by throwing away my careful layer separation. I could have had my data layer return a SearchResultCollection with the reduced attribute set and I could have had my UI code pluck the necessary attributes directly from the underlying DirectoryEntry objects. This would have defeated the main objective of n-tier design: isolating layers from changes to other layers. If I later needed an additional attribute, for example, I might change the UI code to retrieve the needed data from DirectoryEntry without realizing that the data layer had only provided a reduced set of attributes for performance reasons. By adhering to a strong discipline of layer separation, it is clear that, if the UI needs another attribute, it needs to be added to GroupInfo0. Since this class is defined in the data layer, it is much clearer where the changes would be necessary in order to provide the requested information.

I don’t guarantee that a similar set of analyses will speed up your own S.DS code. Sometimes, operations are fundamentally slow. It is always best to look for algorithmic improvements instead of clever coding techniques. Nevertheless, my advice is to use S.DS with care and to understand the ADSI and LDAP layers as well as you can.

(Note: this is the 3rd of a 4 part post).

To understand where the rest of the 1150 seconds of performance improvement came from, let’s first go back to the concept of n-tier design and understand further layering in the data tier.

Remember that our high level algorithm includes a line that looks like this:

GroupInfo[] agi = DataLayer.GetCellGroupMembers( cell );

What is a GroupInfo? This is a class that I define in my data layer to isolate other tiers from the specifics of how data is stored in AD. The definition of GroupInfo contains an S.DS DirectoryEntry object:

class GroupInfo
{
    private DirectoryEntry de;
    ...
    public GroupInfo(DirectoryEntry de)
    {
        this.de = de;
    }

    public string DisplayName
    {
        get
        {
            return de.Properties["displayName"].Value as string;
        }
    }
    ...
}

DirectoryEntry is an S.DS object that represents an object (in our case ) in Active Directory. GroupInfo does not expose this object. It contains public properties (e.g. DisplayName) that return desired data without exposing how the data are stored.

This layer of abstraction incurs performance overhead. When we’re retrieving data to display, we create 20,000 objects instead of just 10,000. The search code looks somewhat like this:

DirectorySearch ds = new DirectorySearcher(...);
... set up ds ...
SearchResultCollection src = ds.FindAll();
GroupInfo[] agi = new GroupInfo[ds.Count];
int ig = 0;
foreach(SearchResult sr in src)
{
    DirectoryEntry de = sr.GetDirectoryEntry();
    agi[ig++] = new GroupInfo(de);
}

First, ds.FindAll() creates a collection with 10,000 search results. We then create a new array with 10,000 elements and iterate through the search results constructing 10,000 GroupInfo objects. Ouch.

How can we avoid all this object creation? Is there anything we can do to exploit the ListView’s support of virtual mode without polluting the 2-tier design? How about if we delay the creation of GroupInfo objects? Consider a class like this:

class SearchResults
{
    private object[] ao;

    public SearchResults(SearchResultCollection src)
    {
        ao = new object[src.Count];
        foreach(SearchResult sr in src)
            ao[i] = sr.GetDirectoryEntry();
    }

    public GroupInfo this[int i]
    {
        get
        {
            if( ao[i] is DirectoryEntry)
            {
                GroupInfo gi = new GroupInfo(ao[i] as DirectoryEntry);
                ao[i] = gi;
                return gi;
            }
            else
                return ao[i] as GroupInfo;
        }
    }
}

The SearchResults class is a wrapper for the data returned from DirectorySearcher. When we create a SearchResults object, we pass it the SearchResultsCollection we got back from DirectorySearcher. It creates an array of generic objects and stores the incoming DirectoryEntry objects returned from the search. The SearchResults class can be used like an array because it defines an indexer property. When you request element i from the class, it will look at the object array. If the array contains a DirectoryEntry object (as it will, initially) it will construct a GroupInfo object for it and replace the DirectoryEntry with the new GroupInfo object. If the array already a GroupInfo object, it will return that instead.

SearchResults, in essence, delays the construction of GroupInfo objects until they are needed. Once constructed, they are then cached for later use. These details are hidden from the user-interface code. The UI code uses SearchResults exactly as it previously used its GroupInfo array. We are providing performance improvement without violating layer separation. True, we would not necessarily have implemented SearchResults if virtual mode list views were not available but such impedance matching is being performed with proper layering discipline. By matching the UI’s use of virtual mode list views with class that also delays object construction, we are providing better performance but still isolating layers.

I don’t recall how much speed up this code provided, but it was significant. I am not providing full details on the GroupInfo object. The real version is slow to construct for reasons that are beyond the scope of these posts.

In my last post on this series, I’ll talk about the last category of changes that I made to speed up my S.DS code.

(Note: this is the 2nd of a 4 part post).

In order to explain why I did to speed up my code, let me first describe the general algorithm that I was working with. At the top level, the code looked (vaguely) like this:

GroupInfo[] agi = DataLayer.GetCellGroupMembers( cell );
listView.Items.Clear();
foreach( GroupInfo gi in agi)
     listView.Items.Add(gi);

(Note: Consider this pseudo code.)

The general idea is that the UI code calls the data layer code to get an array of items to display and then adds them to the list view so that the user can see them (a list view is the .NET name for a WIndows list box). With >10,000 items, this code would take 20 minutes to execute (on a VM, with a small memory allocation). Why was this operation so slow? There were performance bottlenecks throughout.

At the UI level, adding 10,000 items to a list view is a bad idea. This part of the algorithm alone was taking about 1 minute. Instead of adding all the items to the list box, it’s better to add items only when they’re needed. The .NET Winforms ListView supports this feature — they call it virtual mode. Instead of adding the items to the list view, you put the list view in virtual mode, tell it how many items there are in total and then let the list view ask for items when it needs them. ListView will generate .NET events when it needs items. The code now looks something like this:

// put list view into virtual mode, set up callback
listView.VirtualMode = true;
listView.RetrieveVirtualItem +=
     new RetrieveVirtualItemEventHandler(RetrieveItem);
...
// agi is an object member variable of type GroupInfo[]
agi = DataLayer.GetCellGroupMembers( cell );
listView.Items.Clear();
listView.VirtualListSize = agi.Count;
...
}

private void RetrieveItem( object sender,
     RetrieveVirtualItemEventArgs e)
{
     e.Item = agi[e.ItemIndex];
}

The time it takes to fill the list view is now, essentially, zero. Typically, only a few items are shown on the list box at any time so “filling it” only consists of providing those few items. When the user scrolls or pages, events are fired and you retrieve the needed items.

This simple change poses a very interesting question: Have we really sped anything up? Offhand, you’d say “yes!” — the list view comes up 30 seconds faster. Someone else might argue that, if the user scrolls from start to finish, that it would still take you 30 seconds. Who would be right?

You’d be! First of all, users will rarely need to see all the data. If, on average, they only need to scroll halfway through the list, the average saving will be at least 50%. Second, ListView is actually pretty smart. If you hold down the “Page Down” button, it won’t actually ask you for every single item. If your list is sorted, the user will look at what’s showing up on the list and “converge” on the desired item once close. The net result might be that the list view only ends up asking for 25% of the data. Third, adding 10,000 items to a list view incurs additional overhead costs that are not required in virtual mode.

Regardless of which argument you find most convincing, realize what the change has accomplished: 1) it has amortized a slow operation over a series of user operations (scrolling) and 2) it has changed the perception of performance to be in line with user time. The user perceives scrolling to be as fast as the keyboard repeat rate. It doesn’t matter if the data access is any faster once you match the keyboard repeat rate. Once you’ve matched the user’s maximum perceived UI responsiveness, you don’t need to do any better.

Switching to a virtual mode list box greatly sped up part of the overall operation, but it only shaved 30 seconds out of the 1200. My next two posts will explain where I saved another 1150 seconds.