What is an efficient way of deleting a large block of items from the start of a TList in Delphi

Question

Delete (0) from a TList is expensive because all the subsequent items need to be moved down. If I need to delete a large number of items from the start of an even larger list what's the fastest way?

Strawn

Are you sure the subsequent items need to be moved down.. If it's implemented as a linked list it's quite cheep. Not that this comment removes the need to get a valid answer for the question.. – Leeke

Does the order of items after removal matter? – Anxiety

@baash05: I believe TList is implemented as an array. – Anxiety

Check this question Is there a faster TList implementation? for some tips. – Semipalatinsk

@Leeke The Tlist stores the indexes of record numbers in a dataset. The order of TList determines the order of display of the records in the UI. The order of removal doesn't matter. If TList is implemented as an array presumably I could do it by a move and then adjusting the count? – Strawn

Answer 1

Deleting a large range of elements from the beginning of a TList is expensive. Although the class name flatters to deceive, a TList is in fact an array. In TList there is no facility to delete a range–each item must be deleted individually and then the rest of the list is moved down. For a large range that's going to provoke an awful lot of reallocations and full list moves.

If you had a more modern Delphi you could use the generic list class TList<T> and avail yourself of the DeleteRange method. The documentation includes this vital note:

This is an O(ACount) operation.

In Delphi 2006 you can write something with equivalent performance characteristics like this:

procedure DeleteRange(List: TList; AIndex, ACount: Integer);
var
  i: Integer;
  NewCount: Integer;
begin
  NewCount := List.Count-ACount;
  Assert(AIndex>=0);
  Assert(ACount>=0);
  Assert(NewCount>=0);
  for i := AIndex to NewCount-1 do
    List[i] := List[i+ACount]
  List.Count := NewCount;
end;

Carroll

+1. Nice answer, and nice addition with the D2006 equivalent. – Acton

Not so nice. Guess what TList.Count property setter do. It internally calls TList.Delete in iteration from the old count to the new value. So there's no performance increase. And, David, the note about TList.Notify, you will get it too since the internal TList.Delete calls. – Waxplant

@Waxplant my delphi has an efficient SetCount. Which version are you looking at? All the same, deleting from the end is cheap when the capacity is not changed. To be clear, Delete(Count-1) is completely different from Delete(0). – Carroll

@Waxplant : Since Delphi 2010, TList.SetCount checks if the class is just a TList or a derived type. When it's just TList, it doesn't call Delete (and thus prevents all needless Notify-calls too). – Substitute

@David, you're right, Delete(0) vs. Delete(Count-1) is of course a difference. By reindexing the pointers stored in a list and deleting from the end of a list you will save the memory movements. Maybe I should go to sleep last night :) Sorry and +1 – Waxplant

Answer 2

As Marcelo already said, you could copy down the whole block, but instead of doing that item by item, you could move the entire with one call to Move(), using TList.List as an argument.

Do note that TList.List was a PPointerList (^TPointerList; TPointerList = array[0..MaxListSize - 1] of Pointer;) in older Delphi versions and became a TPointerList (TPointerList = array of Pointer;) in Delphi XE2, so you should use the correct indirection:

TList(aList).List^[index] // for older Delphi's

and

TList(aList).List[index]  // for Delphi XE2

Substitute

That would subvert TList.Notify, but that might not matter – Carroll

Even still, it might be faster enough to justify the additional complexity. – Analgesia

Answer 3

Here's how you do it in XE2, since TList is an array of pointers.

The implementation will be similar on Delphi 2006, but I can't write the code since I don't have 2006.

// I have 1000000 items, and I want to delete the first 5000
// Copy the pointer array items up the array
CopyMemory(@myList.List[0],
  @myList.List[5000],
  SizeOf(Pointer) * (myList.Count - 5000));
// Reset the count. Delphi cooperates as long as we're shrinking
myList.Count := myList.Count - 5000;
// You now have tons of unused memory at the end, it's fine
// but if you want to clean house
myList.Capacity := myList.Count;

As long as all of the things the pointers point to are memory managed elsewhere, there's no leak.

Here's the proof:

type
  TMyObject = class
    index: Integer;
  end;

procedure TForm1.Button1Click(Sender: TObject);
var
  myList: TList;
  i: Integer;
  myObject: TMyObject;
begin
  // Create a list with 1000000 entries
  myList := TList.Create;
  for i := 1 to 1000000 do
  begin
    myObject := TMyObject.Create;
    myObject.index := i;
    myList.Add(myObject);
  end;
  // Delete the first 5000
  CopyMemory(@myList.List[0],
    @myList.List[5000],
    SizeOf(Pointer) * (myList.Count - 5000));
  myList.Count := myList.Count - 5000;
  myList.Capacity := myList.Count;
  // Show the new count
  ShowMessage(IntToStr(myList.Count));
  // Shows that my array now has objects 5001 and up
  for i := 0 to 5 do
  begin
    myObject := TMyObject(myList.Items[i]);
    ShowMessage(IntToStr(myObject.index));
  end;
end;

The proof has major memory leaks, but we created the objects just to show the values.

Janus

I think having your own TList class that implemented the above as a method of the class would be pretty nice. – Ogham

Answer 4

If order matters, and you have N items to remove at the front:

for I := 0 to List.Count - N - 1 do
    list[I] := list[I + N];
for I := list.Count - 1 downto list.Count - N do
    list.Delete(I)

I haven't thought this code through very well, so you'll need to check for off-by-one errors and the like.

If order doesn't matter, you can simply exchange the last N items with the first N items, and the delete the last N items as above.

Anxiety

Order of removal does't matter. Can you "SetLength" for a TList? - that would be quicker than calling Delete N times. – Strawn

@ross Yes you can. You just do List.Count := ... – Carroll

+1 this is a good answer, but it would be topped off with the use of List.Count – Carroll

Answer 5

Here's a thought : If you know all items in your List are assigned, you could nil the ones you want to remove and just call TList.Pack(), which figures out where the empty spots are and moves everything else aside as efficiently as possible. This requires a scan through all items though, so it might not be what you want, but it doesn't use Delete (and thus prevents Nitofy calls) also. The implementation of Pack hasn't changed a bit between D2006 and XE2, so you can depend on it's efficiency.

Note, that to nil the items you want removed, you could use List[aIndex] := nil but that would still impose a Notify() call, so List.List[aIndex] := nil might be faster for that.

Substitute

Answer 6

First of all, use BeginUpdate and EndUpdate to prevent updating the UI of the TList by deleting each item.

second: try to delete the items at the most lower one in the list first. In other word, deleting items from down to top the list takes less efficient on other items.

Kattie

There is no BeginUpdate or EndUpdate on TList. – Carroll

There's also no "UI of the TList"; TList isn't a graphic component. And I'm not quite sure what the second paragraph says - can you edit your answer? – Acton