Carvin HF2 now entering "Buffing and Fret Detailing"

The Carvin HF2 "Holdsworth Fatboy" has transitioned from the "Painting and Finishing" stage to "Buffing and Fret Detailing". Yippee!

Why is Chicken Little still on American Idol?

There, I admit it. I watch American Idol. At least I've never watched Survivor or The Amazing Race.

Pffft.

So back to the question. Why is Kevin Covais (dubbed Chicken Little by the show's host Ryan Seacrest) still on American Idol?

I get that he's a nice kid with a pleasant singing voice. But c'mon, he is way out of his league. Some of those folks can BRING IT. I mean they can really sing. And they can command the stage with a compelling presence and personality.

My personal favorites this season are Taylor Hicks, Katherine McPhee, Christopher Daughtry, Elliot Yamin, Mandisa, and Paris Bennett.

WinForms ListView Performance - ListView collections

The WinForms ListView has a few very handy collections - CheckedItems and CheckedIndices.  SelectedItems is a collection of the ListViewItems that are selected.  SelectedIndices is a collection of the indexes of the ListViewItems that are selected.  Those values can be used to pick out ListViewItems from the ListView.Items collection.  CheckedItems and CheckedIndices are just like the SelectedXXX collections only they are for the items that are checked.

The SelectedXXX collections perform very well.  Underneath the covers they are implemented by sending the Win32 ListView control a LVM_GETNEXTITEM message specifying LVNI_SELECTED to find the next selected item.  The Count properties are implemented by sending the Win32 ListView control a LVM_GETSELECTEDCOUNT message.

On the other hand...

The CheckedXXX collections are very expensive.  Underneath the covers they enumerate the listview Items collection for just about every operation.  To retrieve the Count for the CheckedXXX collections WinForms will walk the entire Items collection and test the Checked property of each ListView Item.  Querying the Checked property of each item results in sending a LVM_GETITEMSTATE message to the Win32 ListView control to query for the checked state.  To reference an item from the CheckedXXX collections iterates over the ListView Items collection stopping at the index you ask for.  So the worst case performance is if all items in the ListView are checked.

My previous ListView examples were working with 5000 items.  Well, for the CheckedXXX collections just a few hundred items is enough to exhibit performance problems depending on how you write your code.  It doesn't make much difference whether you use the CheckedItems collection or the CheckedIndices collection since the CheckedItem collection basically does its job via the CheckedIndices collection.  What makes a huge difference is how you access the items.  Index lookup is very slow because of how the next item is found by starting at the beginning again each time.  If for some reason you must do this, then at least cache the Count value at the start of your loop if possible because it is very expensive to recompute.  The fastest way to use these collections is via enumeration such as a foreach() loop.  Even that is not as fast as just enumerating the Items collection yourself and testing each item's Checked property yourself.

For the Team Foundation Server version control UI, we sometimes have 50,000 or more items if you are doing a big branch or adding an existing tree.  I ended up keeping a separate cache of the checked items myself - I just updated the cache during ListView Checked events.  Ideally we would have used a virtual ListView but there were other unrelated performance problems with sorting that made this actually perform worse in our case.

using System;
using System.Collections;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
 
namespace ListViewPerf
{
    public partial class Form1 : Form
    {
        const int ListEntryCount = 500;
        static int seed = 7919;         //  use a constant for repeatable results
 
        String[] strings;
        bool[] checksInit;
        object dontCare;
        int processed;
 
        public Form1()
        {
            Random rand = new Random(seed);
            strings = new String[ListEntryCount];
            checksInit = new bool[ListEntryCount];
 
            for (int i = 0; i < ListEntryCount; i++)
            {
                strings[i] = rand.Next().ToString();
                checksInit[i] = (rand.Next() % 2) == 0;
            }
 
            InitializeComponent();
        }
 
        void FillListView()
        {
            ListViewItem[] items = new ListViewItem[ListEntryCount];
 
            for (int i = 0; i < ListEntryCount; i++)
            {
                items[i] = new ListViewItem(strings[i]);
                items[i].Checked = checksInit[i];
            }
            listView1.Items.AddRange(items);
        }
 
        //  make the compiler believe we're doing something important here...
        void ProcessListViewItem(ListViewItem lvi)
        {
            dontCare = lvi.Tag;
            processed++;
        }
 
        void CheckAll()
        {
            foreach (ListViewItem item in listView1.Items)
            {
                item.Checked = true;
            }
        }
 
        void FetchViaItems()
        {
            processed = 0;
            int count;
            DateTime start;
            TimeSpan tsCheckedIteratorWaySlow;
            TimeSpan tsCheckedIterator;
            TimeSpan tsCheckedEnumerator;
 
            start = DateTime.Now;
            for (int i = 0; i < listView1.CheckedItems.Count; i++)
            {
                ListViewItem lvi = listView1.CheckedItems[i];
                ProcessListViewItem(lvi);
            }
            tsCheckedIteratorWaySlow = DateTime.Now - start;
 
            start = DateTime.Now;
            count = listView1.CheckedItems.Count;
            for (int i = 0; i < count; i++)
            {
                ListViewItem lvi = listView1.CheckedItems[i];
                ProcessListViewItem(lvi);
            }
            tsCheckedIterator = DateTime.Now - start;
 
            start = DateTime.Now;
            foreach (ListViewItem lvi in listView1.CheckedItems)
            {
                ProcessListViewItem(lvi);
            }
            tsCheckedEnumerator = DateTime.Now - start;
 
            MessageBox.Show("Checked ListViewItems via CheckedItems collection:\n" +
                "CheckedIteratorWaySlow " + tsCheckedIteratorWaySlow.TotalMilliseconds.ToString() + " milliseconds\n" +
                "CheckedIterator " + tsCheckedIterator.TotalMilliseconds.ToString() + " milliseconds\n" +
                "CheckedEnumerator " + tsCheckedEnumerator.TotalMilliseconds.ToString() + " milliseconds\n" +
                "Processed " + processed.ToString()
            );
        }
 
        private void ViaItemsButton_Click(object sender, EventArgs e)
        {
            listView1.Items.Clear();
            FillListView();
            
            //  First test a random scattering of checked items
            FetchViaItems();
            
            //  Then test with all checked
            CheckAll();
            FetchViaItems();
        }
 
        void FetchViaIndeces()
        {
            processed = 0;
            int count;
            DateTime start;
            TimeSpan tsCheckedIteratorWaySlow;
            TimeSpan tsCheckedIterator;
            TimeSpan tsCheckedEnumerator;
 
            start = DateTime.Now;
            for (int i = 0; i < listView1.CheckedIndices.Count; i++)
            {
                ListViewItem lvi = listView1.Items[listView1.CheckedIndices[i]];
                ProcessListViewItem(lvi);
            }
            tsCheckedIteratorWaySlow = DateTime.Now - start;
 
            start = DateTime.Now;
            count = listView1.CheckedIndices.Count;
            for (int i = 0; i < count; i++)
            {
                ListViewItem lvi = listView1.Items[listView1.CheckedIndices[i]];
                ProcessListViewItem(lvi);
            }
            tsCheckedIterator = DateTime.Now - start;
 
            start = DateTime.Now;
            foreach (int index in listView1.CheckedIndices)
            {
                ListViewItem lvi = listView1.Items[index];
                ProcessListViewItem(lvi);
            }
            tsCheckedEnumerator = DateTime.Now - start;
 
            MessageBox.Show("Checked ListViewItems via CheckedIndices collection:\n" +
                "CheckedIteratorWaySlow " + tsCheckedIteratorWaySlow.TotalMilliseconds.ToString() + " milliseconds\n" +
                "CheckedIterator " + tsCheckedIterator.TotalMilliseconds.ToString() + " milliseconds\n" +
                "CheckedEnumerator " + tsCheckedEnumerator.TotalMilliseconds.ToString() + " milliseconds\n" +
                "Processed " + processed.ToString()
            );
        }
 
        private void ViaIndecesButton_Click(object sender, EventArgs e)
        {
            listView1.Items.Clear();
            FillListView();
 
            FetchViaIndeces();
 
            CheckAll();
            FetchViaIndeces();
        }
 
        void FetchViaManual()
        {
            processed = 0;
            int count;
            DateTime start;
            TimeSpan tsIteratorWaySlow;
            TimeSpan tsIterator;
            TimeSpan tsEnumerator;
 
            start = DateTime.Now;
            for (int i = 0; i < listView1.Items.Count; i++)
            {
                ListViewItem lvi = listView1.Items[i];
                if (lvi.Checked)
                {
                    ProcessListViewItem(lvi);
                }
            }
            tsIteratorWaySlow = DateTime.Now - start;
 
            start = DateTime.Now;
            count = listView1.Items.Count;
            for (int i = 0; i < count; i++)
            {
                ListViewItem lvi = listView1.Items[i];
                if (lvi.Checked)
                {
                    ProcessListViewItem(lvi);
                }
            }
            tsIterator = DateTime.Now - start;
 
            start = DateTime.Now;
            foreach (ListViewItem lvi in listView1.Items)
            {
                if (lvi.Checked)
                {
                    ProcessListViewItem(lvi);
                }
            }
            tsEnumerator = DateTime.Now - start;
 
            MessageBox.Show("Checked ListViewItems via Manual lookup:\n" +
                "IteratorWaySlow " + tsIteratorWaySlow.TotalMilliseconds.ToString() + " milliseconds\n" +
                "Iterator " + tsIterator.TotalMilliseconds.ToString() + " milliseconds\n" +
                "Enumerator " + tsEnumerator.TotalMilliseconds.ToString() + " milliseconds\n" +
                "Processed " + processed.ToString()
            );
        }
 
        private void ViaManual_Click(object sender, EventArgs e)
        {
            listView1.Items.Clear();
            FillListView();
 
            FetchViaManual();
 
            CheckAll();
            FetchViaManual();
        }
    }
}

WinForms ListView Performance - Initializing checked states

CheckBoxes in a WinForms ListView are of course a bit simpler to use than dealing the underlying Win32 control directly.  WinForms deals with the ListView structures and the WM_NOTIFY messages.  Of course this comes at a cost.  Here's a simple demonstration of how to tweak things for better performance.  This is a simple example so the gains aren't monumental but when you add real world complexities to the Checked event handler and the computation of the Checked state of an item.  There are real noticeable improvements by paying attention to some simple things.

When you are populating a ListView that has CheckBoxes, you really want to set the Checked property of the ListViewItem before you add it to the list.  The reason is that once you have added the item to the ListView.Items collection, WinForms will always defer to the underlying Win32 control to query and set the Checked state of the item.  Before it's added to the ListView the ListViewItem maintains the state itself.  Calling down into the Win32 control is very expensive since it involved PInvoking SendMessage.

There are 5 examples with steady gains in improvement.

 

Set the checked state of the item after it is added to the ListView	1425 milliseconds
Set the checked state of the item after it is added to the ListView but at least check to see if it should be checked - this saves a marshaled SendMessage call to the Win32 ListView per item	1250 milliseconds
Set the checked state of the item before it is added to the ListView	1106 milliseconds
Add the items via AddRange and set the checked state of the items after they are added to the ListView - again you see that AddRange is MUCH faster than adding items one at a time.	343 milliseconds
Add the items via AddRange and have the checked state set before the items are added	234 milliseconds

using System;
using System.Collections;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
 
namespace ListViewPerf
{
    public partial class Form1 : Form
    {
        const int ListEntryCount = 5000;
        static int seed = 7919;         //  use a constant for repeatable results
 
        String[] strings;
        bool[] checksInit;
        DateTime start;
        int checkedEvents;
 
        public Form1()
        {
            Random rand = new Random(seed);
            strings = new String[ListEntryCount];
            checksInit = new bool[ListEntryCount];
 
            for (int i = 0; i < ListEntryCount; i++)
            {
                strings[i] = rand.Next().ToString();
                checksInit[i] = (rand.Next() % 2) == 0;
            }
 
            InitializeComponent();
        }
 
        void PreCall()
        {
            listView1.Items.Clear();
            checkedEvents = 0;
            start = DateTime.Now;
        }
 
        void PostCall(string s)
        {
            TimeSpan ts = DateTime.Now - start;
 
            MessageBox.Show(s + " took " + ts.TotalMilliseconds.ToString() + " milliseconds\nAnd generated " + checkedEvents.ToString() + " Checked events");
        }
 
        enum CheckMode { Before, After, AfterWithTest }
 
        void FillListViewWithStrings(CheckMode checkMode)
        {
            for (int i = 0; i < ListEntryCount; i++)
            {
                ListViewItem lvi = new ListViewItem(strings[i]);
                bool check = checksInit[i];
 
                switch (checkMode)
                {
                    case CheckMode.After:
                        listView1.Items.Add(lvi);
                        lvi.Checked = check;
                        break;
 
                    case CheckMode.Before:
                        lvi.Checked = check;
                        listView1.Items.Add(lvi);
                        break;
 
                    case CheckMode.AfterWithTest:
                        listView1.Items.Add(lvi);
                        if (check)
                        {
                            lvi.Checked = check;
                        }
                        break;
                }
            }
        }
 
        private void checkAfter_Click(object sender, EventArgs e)
        {
            PreCall();
 
            FillListViewWithStrings(CheckMode.After);
 
            PostCall("Check After");
        }
 
        private void checkAfterTest_Click(object sender, EventArgs e)
        {
            PreCall();
 
            FillListViewWithStrings(CheckMode.AfterWithTest);
 
            PostCall("Check After With Test");
        }
 
        private void checkBefore_Click(object sender, EventArgs e)
        {
            PreCall();
 
            FillListViewWithStrings(CheckMode.Before);
 
            PostCall("Check Before");
        }
 
        ListViewItem[] BuildListViewItems(bool setChecks)
        {
            ListViewItem[] items = new ListViewItem[ListEntryCount];
 
            if (setChecks)
            {
                for (int i = 0; i < ListEntryCount; i++)
                {
                    items[i] = new ListViewItem(strings[i]);
                    items[i].Checked = checksInit[i];
                }
            }
            else
            {
                for (int i = 0; i < ListEntryCount; i++)
                {
                    items[i] = new ListViewItem(strings[i]);
                }
            }                
 
            return items;
        }
 
        private void addRangeAfter_Click(object sender, EventArgs e)
        {
            PreCall();
 
            ListViewItem[] items = BuildListViewItems(false);
            listView1.Items.AddRange(items);
            
            for (int i = 0; i < ListEntryCount; i++)
            {
                listView1.Items[i].Checked = checksInit[i];
            }
 
            PostCall("AddRange After");
        }
 
        private void addRangeBefore_Click(object sender, EventArgs e)
        {
            PreCall();
 
            ListViewItem[] items = BuildListViewItems(true);
            listView1.Items.AddRange(items);
 
            PostCall("AddRange Before");
        }
 
        private void listView1_ItemChecked(object sender, ItemCheckedEventArgs e)
        {
            checkedEvents++;
        }
 
    }
}

WinForms ListView Performance

While working on improving the performance of the version control UI for Visual Studio Team Foundation Server, I encountered a number of potential problems with the WinForms ListView control.

As it turns out, adding items to a ListView can be VERY expensive if the list is sorted (as they should be).  Below is a test program I threw together to demonstrate some of the performance tradeoffs and mistakes I've encountered. 

The first example is "Normal mode".  I say this is normal because this is probably what most people do to start with - add a sorter to the ListView early on and be done with it - set it and forget it.  Then you just add your of items.  With a few hundred items it performs just fine.  However, once you get over a certain threshold the performance degrades significantly.  What happens is that ListView gets sorted after every ListViewItem is added to the Items collection.  This is very sloooooow.  On my computer it took 123,843 milliseconds to build the list and resulted in 70,621,263 calls to my Compare function.  OUCH!

The next example, No Sorter1, is the first optimization folks seem to make.  You remove the sorter, add your items, set the sorter back, and then call Sort.  This is a noticeable improvement.  The problem here is that there is no need to call Sort!  When you set the sorter back WinForms will call Sort for you.  On my computer it took 1812 milliseconds and resulted in 85,030 calls to my Compare function.  Much better!

The next example, No Sorter2, is the optimization that a lot of folks miss because the previous one helped so much.  This one really matters when you have an expensive Compare function.  It's the same as the previous example with the unnecessary Sort call removed.  On my computer it took 1765 milliseconds and resulted in 55,226 calls to my Compare function.  Still better!

Next is to use AddRange.  As it turns out WinForms has an opportunity to do an even better job than you internally because they have direct access to their interactions with the underlying Win32 ListView control.  On my computer it took 546 milliseconds and resulted in 55,226 calls to my Compare function.  This is LOTS better!

The final example uses the virtual capabilities of the ListView object.  The way this works is you maintain your own cache of ListViewItem objects and supply them in a callback when you are asked.  This results in a dramatic speed up when dealing with a large number of items.  For this case I just used Array.Sort.  On my computer it took 46 milliseconds and resulted in 91,800 calls to my Compare function. 

Note that in one of the cases I was working on, the virtual mode performed worse than the AddRange and the No Sorter modes.  Our IComparer in that case is far more expensive than the simple one in my example.

MEASURE!!!

using System;
using System.Collections;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
 
namespace ListViewPerf
{
    public partial class Form1 : Form
    {
        const int ListEntryCount = 5000;
        static int seed = 7919;         //  use a constant for repeatable results
 
        String[] strings;
        ListViewItem[] virtualItems;
        MySorter sorter;
        DateTime start;
 
        public Form1()
        {
            Random rand = new Random(seed);
            strings = new String[ListEntryCount];
 
            for (int i = 0; i < ListEntryCount; i++)
            {
                strings[i] = rand.Next().ToString();
            }
 
            sorter = new MySorter();
 
            InitializeComponent();
        }
 
        void PreCall()
        {
            listView1.ListViewItemSorter = null;
 
            if (!listView1.VirtualMode)
            {
                listView1.Items.Clear();
            }
            else
            {
                virtualItems = null;
            }
            listView1.VirtualMode = false;
            sorter.ResetCounter();
            start = DateTime.Now;
        }
 
        void PostCall(string s)
        {
            TimeSpan ts = DateTime.Now - start;
 
            MessageBox.Show(s + " took " + ts.TotalMilliseconds.ToString() + " milliseconds\nAnd resulted in " +  sorter.Counter.ToString() + " Compare calls");
        }
 
        void FillListViewWithStrings()
        {
            for (int i = 0; i < ListEntryCount; i++)
            {
                ListViewItem lvi = new ListViewItem(strings[i]);
                listView1.Items.Add(lvi);
            }
        }
 
        private void normalButton_Click(object sender, EventArgs e)
        {
            PreCall();
 
            listView1.ListViewItemSorter = sorter;
 
            FillListViewWithStrings();
 
            PostCall("Normal mode");
        }
 
        private void noSorter1Button_Click(object sender, EventArgs e)
        {
            PreCall();
 
            FillListViewWithStrings();
 
            listView1.ListViewItemSorter = sorter;
            listView1.Sort();
            
            PostCall("No Sorter1 mode");
        }
 
        private void noSorter2Button_Click(object sender, EventArgs e)
        {
            PreCall();
 
            FillListViewWithStrings();
 
            listView1.ListViewItemSorter = sorter;
 
            PostCall("No Sorter2 mode");
        }
 
        ListViewItem[] BuildListViewItems()
        {
            ListViewItem[] items = new ListViewItem[ListEntryCount];
 
            for (int i = 0; i < ListEntryCount; i++)
            {
                items[i] = new ListViewItem(strings[i]);
            }
 
            return items;
        }
 
        private void addRangeButton_Click(object sender, EventArgs e)
        {
            PreCall();
 
            listView1.ListViewItemSorter = sorter;
            ListViewItem[] items = BuildListViewItems();
            listView1.Items.AddRange(items);
            
            PostCall("AddRange mode");
        }
 
        private void virtualButton_Click(object sender, EventArgs e)
        {
            PreCall();
 
            virtualItems = BuildListViewItems();
            Array.Sort(virtualItems, sorter);
            listView1.VirtualMode = true;
            listView1.VirtualListSize = virtualItems.Length;
 
            PostCall("Virtual mode");
        }
 
        private void listView1_RetrieveVirtualItem(object sender, RetrieveVirtualItemEventArgs e)
        {
            e.Item = virtualItems[e.ItemIndex];
        }
    }
 
    public class MySorter : IComparer
    {
        int counter;
 
        public void ResetCounter()
        {
            counter = 0;
        }
 
        public int Counter
        {
            get { return counter; }
        }
 
        int IComparer.Compare(Object x, Object y)
        {
            ListViewItem lviX = (ListViewItem)x;
            ListViewItem lviY = (ListViewItem)y;
            counter++;
            return String.Compare(lviX.Text, lviY.Text);
        }
 
    }
}