Listbox slows down when adding large number of items

  • Thread starter Paul_Madden via DotNetMonster.com
  • Start date
P

Paul_Madden via DotNetMonster.com

Basically I have a listbox to which I add simple STRING items- I have a
progress bar which I increment whenever I populate another portion of the
complete set of items I wish to add. What I observe is that as more and more
are added, population of the list box takes longer and longer. ie the first
10th of the item set are added much much quicker than the last 10th. THis
occurs with about 40,000 listbox items. My worry is the listbox may
potenetially store many 100s of 1000s of items.

Is this a known feature of the standard listbox. I really want to use a
listbox control as it offers perfect functionality for what I need. Just
curious (worried) about the semi-exponentially increasing itel Add () time.

Many thanks.
 
T

Tim Wilson

Try using the BeginUpdate/EndUpdate methods to see if that helps perf in
your situation.
 
G

Guest

Paul:
40,000 items in a Listbox? You have got to be kidding, man! Why don't you
set something up with typeahead where the first few letters typed set up a
Sql call with

WHERE xyz LIKE ' +searchterm +'%'

and then just bring back the matching items?

Peter
 
G

Greg Young

Are you by chance dealing with a sorted list?

If so I would fully expect it to be O(log n) (doing binary searches) just to
figure out where it should put it and O(n) for the copy that must occur on
adds :. After the finding of the location to insert O(log n) (binary search)
I would expect an O(n) operation to copy every passed it in the array.

example ... (indexes on left, values on right)

my array is
0 1
1 3
2 4
3 5
4 6
5 7

insert 2 ...

I now have to copy 3-7 (moving them up a spot) to make room for 2

0 1
1 ?
2 3
3 4
5 6
6 7

I then place my value at the second spot in the array ending up with

0 1
1 2
2 3
3 4
5 6
6 7


If this is the case you can make it much more efficient by adding all the
items, then sorting them using the Sort() method. This will only sort the
list once as opposed to 40k array copies :) ...

Cheers,

Greg Young
MVP - C#
http://geekswithblogs.net/gyoung
 
P

Paul_Madden via DotNetMonster.com

This is a general reply to all those who have so far helped.

No, no joke, my ListBox could well end up withover 1,000,000 elements. The
ListBox functionality is exactly what I need. It is a perfetc control for how
I wish to manage/display my data. It's just the Add () spped degradation
which is a real bummer.

Have in place Begin(End Update () calls so no improvement.

Am NOT using a sorted list.

If anyone has the unction to try it, simply add, in a tight loop, STRING
element items, say 500+ characters each, and notice how it takes ever longer
to add as the Count increases.

Any more suggestions would be greatly appreciated and thanks once more for
the help so far,

Paul
 
B

Barry Kelly

Paul_Madden via DotNetMonster.com said:
This is a general reply to all those who have so far helped.

No, no joke, my ListBox could well end up withover 1,000,000 elements. The
ListBox functionality is exactly what I need. It is a perfetc control for how
I wish to manage/display my data. It's just the Add () spped degradation
which is a real bummer.

How do your users feel about scrolling through a list with a million
elements? How long does it take for them to read all the possibilities?
Any more suggestions would be greatly appreciated and thanks once more for
the help so far,

I don't think you're going about this the right way at all. I'd try and
make a user interface somewhat similar to the old index lookup in
WinHlp32.exe - as you type a value in, it zooms in on the location. If
the contents must be presented as a listbox, then make the listbox
virtual, so that only the visible elements are actually loaded. It
doesn't look like the .NET listbox can be made virtual (the Delphi
TListBox has a neat virtual mode), which is a bit of a bummer. Perhaps
you can extend it to make it virtual.

A virtual listbox has a writable "Count" property which determines how
many items are in it, and a "GetItem" event which gets the item at a
given index. In this way, the listbox adjusts its scrollbar according to
the height of each item times the Count, and paints only the visible
items, getting the items by calling GetItem. Requests through
ListBox.Items would call through to invoking the GetItem event.

The listbox is a very simple type of control (although getting all the
accessibility features just right could be more difficult, but I doubt a
speech synthesizer is going to have to list off all the items inside :),
so it could be reimplemented if necessary to get the right semantics.
You'd need to be aware of internationalization and bidi text etc. too.

-- Barry
 
J

joachim

My experience is that a lot of the GUI slows down the real data
processing of your application.
Suppose that you have a combobox which is connected to an ArrayList as
datasource, each time you add an object to the ArrayList, the GUI is
updated (the item apears in the combobox).

If you want to load a massive amount of data into your datasource and
display it on screen, you should avoid to have the GUI refresh itself
after each addition. I had the same problem and all I did was a
..SuspendLayout() call on the GUI element before the additions and a
..ResumeLayout() after the addition had finished.

But as I'm writing this, I took a glimpse at the ListBox class and
noticed the BeginUpdate() and EndUpdate() methods which would probably
do exactly what you want:

This snippet is taken from the Visual Studio Help:
ms-help://MS.VSCC.v80/MS.MSDN.v80/MS.NETDEVFX.v20.en/CPref17/html/M_System_Windows_Forms_ListBox_BeginUpdate.htm

public void AddToMyListBox()
{
// Stop the ListBox from drawing while items are added.
listBox1.BeginUpdate();

// Loop through and add five thousand new items.
for(int x = 1; x < 5000; x++)
{
listBox1.Items.Add("Item " + x.ToString());
}
// End the update process and force a repaint of the ListBox.
listBox1.EndUpdate();
}
 
M

Mark Rae

But as I'm writing this, I took a glimpse at the ListBox class and
noticed the BeginUpdate() and EndUpdate() methods which would probably
do exactly what you want:

The OP is already using those methods - unsurprisingly, they're not
helping... :)
 
A

Adam Clauss

I don't think you're going about this the right way at all. I'd try and
make a user interface somewhat similar to the old index lookup in
WinHlp32.exe - as you type a value in, it zooms in on the location. If
the contents must be presented as a listbox, then make the listbox
virtual, so that only the visible elements are actually loaded. It
doesn't look like the .NET listbox can be made virtual (the Delphi
TListBox has a neat virtual mode), which is a bit of a bummer. Perhaps
you can extend it to make it virtual.

Yeah, I think virtual lists may be exactly what you need. I've used them
back in C++/MFC, have not tried yet in .NET though. A quick google search
for "c# virtual listbox" turned up:
http://www.vbaccelerator.com/home/net/Code/Controls/ListBox_and_ComboBox/VListBox/article.asp
 
G

Greg Young

And your listbox is *not* sorted (note not sorted list)? My guess would be
that there is another O(n) operation somewhere ...

When dealing with anything that has the name *list* in it, you should be
expecting an O(n) operation.

Also you are adding these items in a loop. Have you tried that AddRange
method instead? It incurs far less overhead than iterating through Add.

Cheers,

Greg Young
MVP - C#
http://geekswithblogs.net/gyoung
 
G

Greg Young

Doing some further research ..

I am getting for 10,000 at a time ..

19844385 ticks
23750760 ticks
26563350 ticks
30782235 ticks
33594825 ticks

Fairly consistant ... this is without sorting ... with sorting I get ...

28594665 ticks
35001120 ticks
41251320 ticks
47189010 ticks
52657935 ticks

Notice that both are happenning in linear time ... by applying begin/end
update I can move my speed down greatly although it is abviously still in
linear time (about twice as fast as without applying this).
8906535 ticks
12187890 ticks
15156735 ticks
18438090 ticks

It is important to nore that this is not "exponential or semi-exponential"
time ... this is linear time which you should expect anytiume you hear the
word "list"

Cheers,

Greg Young
MVP - C#
http://geekswithblogs.net/gyoung
 
P

Paul_Madden via DotNetMonster.com

Hoi guys. I fly between London and Zuerich on Fridays so have only now found
time to sit down and mull over all which has been written. I have found a
solution to my problem which I will elaborate on in a short while.

Just to clear things up. I am using .NET 1.1, using a standard ListBox, NOT
Sorted, do use BeginUpdate () and EndUpdate () and simply load text lines in
from a text file and store them as STRING items in the ListBox using the Add
() method. I did try AddRange (), passing in a pre-loaded array, but this
actually took longer than simply adding the elements one at a time. Also
tried assingning a DataSource member to the array with similar delays. The
delays do increase, I assure you, meaning adding the last N elements to a
ListBox does indeed take much longer than adding the first N. My example uses
strings of 500+ characters and my tests used 40,000 items, I displayed an
increment (with Refresh ()) to a Progress Bar every 4,000 calls to Add ().
Visually the slow down in Progress Bar updates is dramatic.

What I did find however is that undertaking Add ("") really flies with no
degraded performance.

So, to my solution. I was in any case implementing my own DrawItem () handler
for my listbox, displaying the text in different colours based on content. So,
whenever I actually want to add an element to a ListBox I actually add it to
a standard fixed size string array instead. I add to the ListBox Item
collection the NULL string (ie listbox.Add ("")); In the DrawItem handler,
instead of retrieving the string to display from the ListBox Item collection,
I fetch it from the string array instead. I generalised this technique as one
of my ListBox displays increases in size dynamically and I do not know how
big it may become. I use the ListBox because logically this is the Control
whose functionality best maps to my requirement. I enclose some code snippets
just in case anyone may find this of use. I would like to thank ALL you guys
for your comments, and hope our paths cross in the virtual world at some
other time in the future. Many mant thanks guys (and maybe gals too).

public partial class Form1 : Form
{
public ListElements le;
public int count = 0;

public Form1 ()
{
InitializeComponent ();
}

private void Form1_Load (object sender , EventArgs e)
{
le = new ListElements (listBox1);
}

private void button1_Click (object sender , EventArgs e)
{
le.Add (count.ToString ());

count++;
}

private void listBox1_DrawItem (object sender , DrawItemEventArgs e)
{
if (e.Index >= 0)
{
e.Graphics.DrawString (le [e.Index] , e.Font, Brushes.Black, e.Bounds);
}
}

private void button2_Click (object sender , EventArgs e)
{
le.Clear ();
}
}


public class ListElements
{
public const int NUM_ARRAYS = 2000;
public const int ARRAY_ELEMENTS = 10000;
public string [] [] elements = new string
[NUM_ARRAYS] [];
public int arrayElement = 0;
public int arrayNumber = 0;
public string [] activeArray;
public ListBox lb;

public string this [int i]
{
get
{
int ae;
int an;

if (i >= (NUM_ARRAYS * ARRAY_ELEMENTS))
{
return null;
}

an = i / ARRAY_ELEMENTS;

ae = i % ARRAY_ELEMENTS;

return elements [an] [ae];
}
}

public ListElements (ListBox l)
{
this.lb = l;

return;
}

public void Add (string s)
{
lb.Items.Add ("");

if (arrayElement == 0)
{
elements [arrayNumber] = new string [ARRAY_ELEMENTS];

activeArray = elements [arrayNumber];
}

activeArray [arrayElement] = s;

arrayElement++;

if (arrayElement == ARRAY_ELEMENTS)
{
arrayNumber++;

if (arrayNumber >= NUM_ARRAYS)
{
throw (new SystemException (String.Format ("No more list elements, now
added > {0} * {1} elements !", NUM_ARRAYS, ARRAY_ELEMENTS)));
}

arrayElement = 0;
}

return;
}

public void Clear ()
{
lb.Items.Clear ();

arrayElement = 0;

arrayNumber = 0;

return;
}
}
 
P

Paul_Madden via DotNetMonster.com

One last thing I forgot to mention. The listbox stores messages sent and
received to a server application. We may be making 150 requests per second
which implies maybe 450 responses, ie 600 messages per second (Ok worse case
scenario). The listbox is NOT being used in its traditional roll as an item
selection control. I have implemented RegExp filtering and stacks more stuff
which handles the user's requirements to traverse the list. So, once again,
it's not a list which is used to select "apples, oranges or pears", but
instead it is used to store chronological message history.

Paul.
 
M

Marcus Andrén

Basically I have a listbox to which I add simple STRING items- I have a
progress bar which I increment whenever I populate another portion of the
complete set of items I wish to add. What I observe is that as more and more
are added, population of the list box takes longer and longer. ie the first
10th of the item set are added much much quicker than the last 10th. THis
occurs with about 40,000 listbox items. My worry is the listbox may
potenetially store many 100s of 1000s of items.

Is this a known feature of the standard listbox. I really want to use a
listbox control as it offers perfect functionality for what I need. Just
curious (worried) about the semi-exponentially increasing itel Add () time.

Many thanks.

The sort algorithm the Listbox uses is slow and unreliable. If at all
possible, set the .Sorted property of the Listbox to false when
dealing with many items.

Sorting 12000 of a certain list of strings I had took 10 seconds,
while the same list with another 104 items took 29 items. Another list
of strings with the same amount of items took just 3 seconds. If I
randomized the items in the first list before adding them the sort
took only a few seconds.

Note that even 3 seconds is a long time. The ordinary sorts, use by
Array or List are much faster.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top