Efficiently populate combobox in Delphi

Question

Need to add many items (more than 10k) in TComboBox (I know that TComboBox is not supposed to hold many items but its not up to me to change this) without adding duplicates. So I need to search the full list before adding. I want to avoid TComboBox.items.indexof as I need a binary search but the binary find is not available in TStrings.

So I created a temporary Tstringlist, set sorted to true and used find. But now assigning the temporary Tstringlist back to TComboBox.Items

(myCB.Items.AddStrings(myList)) 

is really slow as it copies the whole list. Is there any way to move the list instead of copying it? Or any other way to efficient populate my TComboBox?

Answer 1

There is no way to "move" the list into the combo box because the combo box's storage belongs to the internal Windows control implementation. It doesn't know any way to directly consume your Delphi TStringList object. All it offers is a command to add one item to the list, which TComboBox then uses to copy each item from the string list into the system control, one by one. The only way to avoid copying the many thousands of items into the combo box is to avoid the issue entirely, such as by using a different kind of control or by reducing the number of items you need to add.

A list view has a "virtual" mode where you only tell it how many items it should have, and then it calls back to your program when it needs to know details about what's visible on the screen. Items that aren't visible don't occupy any space in the list view's implementation, so you avoid the copying. However, system combo boxes don't have a "virtual" mode. You might be able to find some third-party control that offers that ability.

Reducing the number of items you need to put in the combo box is your next best option, but only you and your colleagues have the domain knowledge necessary to figure out the best way to do that.

Answer 2

As Rudy Velthuis already mentioned in the comments and assuming you are using VCL, the CB_INITSTORAGE message could be an option:

SendMessage(myCB, CB_INITSTORAGE, myList.Count, 20 * myList.Count*sizeof(Integer));

where 20 is your average string length.

Results (on a i5-7200U and 20K items with random length betwen 1 and 50 chars):

• without CB_INITSTORAGE: ~ 265ms
• with CB_INITSTORAGE: ~215ms

So while you can speed up things a little by preallocating the memory, the bigger issue seems to be the bad user experience. How can a user find the right element in a combobox with such many items?

Answer 3

Notwithstanding that 10k items is crazy to keep in a TComboBox, an efficient strategy here would be to keep a cache in a separate object. For example, declare :

    { use a TDictionary just for storing a hashmap }        
    FComboStringsDict : TDictionary<string, integer>;

where

procedure TForm1.FormCreate(Sender: TObject);
var
  i : integer;
  spw : TStopwatch;
begin
  FComboStringsDict := TDictionary<string, integer>.Create;
  spw := TStopwatch.StartNew;
  { add 10k random items }
  for i := 0 to 10000 do begin
    AddComboStringIfNotDuplicate(IntToStr(Floor(20000*Random)));
  end;
  spw.Stop;
  ListBox1.Items.Add(IntToStr(spw.ElapsedMilliseconds));
end;

function TForm1.AddComboStringIfNotDuplicate(AEntry: string) : boolean;
begin
  result := false;
  if not FComboStringsDict.ContainsKey(AEntry) then begin
    FComboStringsDict.Add(AEntry, 0);
    ComboBox1.Items.Add(AEntry);
    result := true;
  end;
end;

Adding 10k items initially takes about 0.5s this way.

{ test adding new items }
procedure TForm1.Button1Click(Sender: TObject);
var
  spw : TStopwatch;
begin
  spw := TStopwatch.StartNew;
  if not AddComboString(IntToStr(Floor(20000*Random))) then
    ListBox1.Items.Add('Did not add duplicate');
  spw.Stop;
  ListBox1.Items.Add(IntToStr(spw.ElapsedMilliseconds));
end;

But adding each subsequent item is very fast <1ms. This is a clumsy implementation, but you could easily wrap this behaviour into a custom class. The idea is to keep your data model as separate from the visual component as possible - keep them in sync when adding or removing items but do your heavy searches on the dictionary where the lookup is fast. Removing items would still rely on .IndexOf.