Most efficient way to delete multiple items from a TList<T>...

[Steve Maughan 26]

I have quite a large list of 3000 objects stored in a TList<T>. I need to delete about half of them in a time-critical manner i.e. as fast as possible. I don't need to free the objects, just delete them from the list.

 

Two possible approaches come to mind. I could simply iterate through the list and repeatedly call List.Delete(index) for each item I'd like to remove. Another alternative would be to set the item to nil and then call List.Pack at the end. Is there any advantage in the second approach? Any other insights appreciated.

 

Steve  

[Vandrovnik 217]

May be rearrange items (move items to be kept to the beginning of the list) and then set Count to the number of items to be kept?

[Lars Fosdal 1848]

TList<T>.Pack( function (const L, R: T): Boolean
  begin
    Result := (L.Condition);
  end);

 

[Der schöne Günther 336]

I haven't done any benchmarks and don't know how much memory usage is a concern in your case- But I would assume that

1. Creating a new list (you already know the capacity)
2. Adding only the needed items
3. Let your variable/field point to the new list

could be a valid option.

[Guest]

Linked list ?

[David Heffernan 2422]

What evidence do you have that this task is a bottleneck? 

[Steve Maughan 26]

1 hour ago, Kas Ob. said:

Linked list ?

Hi Kas - that's a good idea!

[Steve Maughan 26]

15 minutes ago, David Heffernan said:

What evidence do you have that this task is a bottleneck? 

In truth, little. It's just part of an optimization algorithm that needs to be as fast as possible. 

[Anders Melander 1973]

2 minutes ago, Steve Maughan said:

In truth, little.

Huh? You have heard of premature optimization haven't you?

[Stefan Glienke 2129]

Measure, don't guess - basic rule of performance tuning

 

Linked list is a bad idea btw - if anyone thinks otherwise he needs to get an update on modern CPU architectures.

Edited December 19, 2019 by Stefan Glienke

[Steve Maughan 26]

1 hour ago, Anders Melander said:

Huh? You have heard of premature optimization haven't you?

Yes - I'm a total sucker for it. 

[Steve Maughan 26]

31 minutes ago, Stefan Glienke said:

Measure, don't guess - basic rule of performance tuning

 

Linked list is a bad idea btw - if anyone thinks otherwise he needs to get an update on modern CPU architectures.

Hi Stefan - is it? I can't see why it would be a bad idea. Any links to enlighten me?

 

Steve

[Stefan Glienke 2129]

Ask google and read up on prefetchers and cache locality.

[Anders Melander 1973]

58 minutes ago, Stefan Glienke said:

Linked list is a bad idea btw

That's quite a unnuanced (is that a word?) statement.

Wouldn't you say it depends on the access and allocation pattern?

Edited December 19, 2019 by Anders Melander

[Stefan Glienke 2129]

5 minutes ago, Anders Melander said:

That's quite a unnuanced (is that a word?) statement.

Wouldn't you say it depends on the access and allocation pattern?

Of course but I am assuming that Steve is doing more with this list than just removing many items at once.

 

My personal experience with collections and a lot of material I read and watched is telling me that the chances are kinda slim that a linked list will perform better in the overall usecase.

 

Anyhow in the context of this question any discussion of this is moot and my first sentence in my first comment still stands. Anything else is a waste of time.

Edited December 19, 2019 by Stefan Glienke

[Guest]

Linked lists has its merits, and sometimes it is the fastest way, i did an app where the job was to download hundreds of thousands or millions of data, all will be in list ( array in fact ) , then i will apply a filter or more to choose data from all this pile, here i switch to linked list where the data stored in this linked list is only the index in the original array and the next in LL, that way i can parse, manipulate and draw this specific selected data range in very fast way, here i would explain that in the same time when i built the LL, had a simple list of integers of the same size of original array with values either -1 or the index in the LL, now i can managed to go between them fast, i don't if this can be called a hybrid .

as for the benefits of List or array over linked list the first answer here https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java will explain this,

[Anders Melander 1973]

10 minutes ago, Kas Ob. said:

the first answer here https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java will explain this

Very interesting. Thanks for the pointer.

One of the other answers explains it even better IMO and points to this gem: https://kjellkod.wordpress.com/2012/08/08/java-galore-linkedlist-vs-arraylist-vs-dynamicintarray/

 

I guess I'll have to revisit some of my old code and redo the benchmarks.

[David Heffernan 2422]

We are all given a finite time here. Why would we spend it optimising something that wasn't a bottleneck. 

 

Imagine measuring, identifying the bottleneck, optimising, and the observing real discernible performance benefits? How great does that feel? 

 

Conversely, imagine expending time on work that yields no benefit. And worse, you likely end up with code that is harder to read and maintain. Usually this just results in bugs. Think of it, you spend valuable time making your program worse. You may as well just go to the pub and leave the code alone. You have a good time, and your program is better. Win win. 

Edited December 19, 2019 by David Heffernan

[Stefan Glienke 2129]

4 hours ago, David Heffernan said:

You may as well just go to the pub and leave the code alone. You have a good time, and your program is better. Win win. 

Leave the pub once you reach the Ballmer Peak and then work on your program to make it even better 

[Fr0sT.Brutal 901]

If the list is not sorted, probably the fastest option is to move items to be deleted to the end of the list by exchanging and then trim the list. This way only one memory reallocation happens. Depending on list length and available memory size, maybe creating a new list and copying only needed items to it would be quicker. Anyway, you really should benchmark this action first

[David Heffernan 2422]

23 minutes ago, Fr0sT.Brutal said:

If the list is not sorted, probably the fastest option is to move items to be deleted to the end of the list by exchanging and then trim the list. This way only one memory reallocation happens. Depending on list length and available memory size, maybe creating a new list and copying only needed items to it would be quicker. Anyway, you really should benchmark this action first

No, that is not fastest. It can be done with at most N item moves where N is the final coun of the list. 

[Fr0sT.Brutal 901]

7 minutes ago, David Heffernan said:

No, that is not fastest. It can be done with at most N item moves where N is the final coun of the list. 

It strongly depends on list size, number of items to delete and, of course, the <T> itself. If <T> is not a simple type, f.ex., a big record with lots of managed fields, assigning could take ages. However, on pretty large lists this could be the only acceptable option as internal array realloc would exhaust available memory.

[David Heffernan 2422]

1 hour ago, Fr0sT.Brutal said:

It strongly depends on list size, number of items to delete and, of course, the <T> itself. If <T> is not a simple type, f.ex., a big record with lots of managed fields, assigning could take ages. However, on pretty large lists this could be the only acceptable option as internal array realloc would exhaust available memory.

You don't understand. Moving an item to the end leads to all items between that point and the end being moved down.

 

It's perfectly possible to implement this without a realloc and without the dire performance traits of your chosen method. And if your array is huge and push the boundaries of available memory as you suggest, then your algorithm is unspeakably dire. 

[Vandrovnik 217]

1 hour ago, David Heffernan said:

You don't understand. Moving an item to the end leads to all items between that point and the end being moved down.

 

It's perfectly possible to implement this without a realloc and without the dire performance traits of your chosen method. And if your array is huge and push the boundaries of available memory as you suggest, then your algorithm is unspeakably dire. 

Why to move these items to the end? They can be ignored...
 

Next:=0;
for a:=0 to List.Count-1 do begin
 if List[a].Keep then begin
  List[Next]:=List[a];
  inc(Next);
 end;
end;
List.Count:=Next;

List<T>.Pack probably does (almost) the same, it just tries to move bigger amount of memory in one block.

Edited December 20, 2019 by Vandrovnik

[Fr0sT.Brutal 901]

4 hours ago, David Heffernan said:

You don't understand. Moving an item to the end leads to all items between that point and the end being moved down.

 

It's perfectly possible to implement this without a realloc and without the dire performance traits of your chosen method. And if your array is huge and push the boundaries of available memory as you suggest, then your algorithm is unspeakably dire. 

No, you don't understand 😉 I suggested to exchange them not move. Of course it only sounds simple, there will be many gotchas to avoid so if resources allow, copy is always the easiest option.