Sign in to follow this  
kalixxx

list.clear or new?

Recommended Posts

what do you think will be faster (c#) clearing a list or making a new one and letting the GC do it? list<int> list = new list<int>(); void clrList() { list.clear(); OR? list = new list<int>(); } i ask this coz list.clear is an O(n) (well thats what msdn says)

Share this post


Link to post
Share on other sites
MSDN also says that Clear does not cause any changes in memory allocation, whereas making a new list will make that old list available for collection and allocate a new one.

Share this post


Link to post
Share on other sites
I think allocating a new one will be faster. In the long run the same amount of work will have to be done, but if all you're doing is orphaning one reference and setting it to another reference, that's going to be very fast in the short term, and the performance hit will come much later when the garbage collector thinks it's convenient and will have little impact on your program. With List.Clear() you take the O(n) hit immediately, garbage collection might be distributed over the idle CPU time.

Share this post


Link to post
Share on other sites
Quote:
Original post by Promit
The "O(n) hit" means they loop over the array and set each item to null. Then the size changes to 0. It's not exactly a huge operation.


Sure, I agree. But setting 100,000 items to null is still slower than what basically amounts to swapping one pointer.

Obviously it depends on the size of the list too. I wouldn't even be worrying about which is faster in the first place unless I profiled it and found that it was a problem, but I was just answering the question of which is faster :)

I could also be wrong, I haven't benchmarked anything, but it makes sense anyway.

Share this post


Link to post
Share on other sites
Quote:
Original post by cache_hit
Quote:
Original post by Promit
The "O(n) hit" means they loop over the array and set each item to null. Then the size changes to 0. It's not exactly a huge operation.


Sure, I agree. But setting 100,000 items to null is still slower than what basically amounts to swapping one pointer.


Thing is, newed arrays (like List uses internally) are also 0ed. Either you create the new list with the old capacity (in which case you're already paying the O(n) cost for zeroing immediately, on top of a later GC cost), or you eventually grow the list to the old capacity -- paying the zeroing cost later, plus zeroing a few intermediately sized arrays, plus GCing said arrays.

Basically, shit's getting zeroed, no way around it. In the unlikely event that clearing the list is causing, say, framerate stutter, re-new-ing the list is unlikely to solve the issue. Instead you'd have to roll your own List-alike to clear the list over a few frames (or not zero at all, but that'd probably be an incredibly bad idea leading to lots of unclaimed garbage spiking up your GC costs to the point where they might start causing frame stutter.)

Share this post


Link to post
Share on other sites
I'm not disagreeing. And the growing is definitely something to consider when doing new List() instead of List.Clear.

I'm just saying, if all you're comparing is the instruction:


l.Clear();



to the instruction


l = new List<int>();



then the second one is probably going to return in a shorter amount of time. After that all bets are off. Whether or not this small of a speed increase is even worth worrying about is also a completely different matter. And it comes with tradeoffs such as the one you mention about inserts now causing re-allocations that would have not needed to be performed on the already existing list.

In my own code, I would probably write list.Clear(); because it's unlikely that such a micro-optimization would even help, and could potentially hurt. I certainly wouldn't even consider it without profiling first and making sure that list.Clear() was even a problem in the first place.

Share this post


Link to post
Share on other sites
Quote:

then the second one is probably going to return in a shorter amount of time. After that all bets are off. Whether or not this small of a speed increase is even worth worrying about is also a completely different matter. And it comes with tradeoffs such as the one you mention about inserts now causing re-allocations that would have not needed to be performed on the already existing list.

Clear() calls Array.Clear(), which is an internal call and probably does the sample memcpy-type operation as the ctor, which just allocates a new array.

Share this post


Link to post
Share on other sites
It doesn't matter what's faster, they don't mean the same thing.

List<int> first = new List<int>();
List<int> second = first;
first.Add(0);
first = new List<int> ();
Debug.Assert(first.Count != second.Count);


List<int> first = new List<int>();
List<int> second = first;
first.Add(0);
first.Clear();
Debug.Assert(first.Count == second.Count);

Share this post


Link to post
Share on other sites
Quote:
Original post by return0
It doesn't matter what's faster, they don't mean the same thing.

List<int> first = new List<int>();
List<int> second = first;
first.Add(0);
first = new List<int> ();
Debug.Assert(first.Count != second.Count);


List<int> first = new List<int>();
List<int> second = first;
first.Add(0);
first.Clear();
Debug.Assert(first.Count == second.Count);


This is a bad example. Of course the counts are different in the first, before the assert the two lists point to different instances. In the second example, before the assert the two lists point the same instance.

This is the situation you should have tested.

List<int> one = new List<int>();
List<int> two = new List<int>();

one.Add(1);
two.Add(1);

one.Clear();
two = new List<int>();

Debug.Assert(one.Count == two.Count);






You're right that they're different, but not for the reason you described. They're different because when you use .Clear(), internally it's likely to keep the original memory allocated, and simply update some internal field to denote that size=0. But re-adding elements will be more efficient because it will already have a lot of internal storage allocated from previous uses of the array.

This difference, however, is only an implementation detail, the objects will compare equal


Debug.Assert(one.Equals(two));



Share this post


Link to post
Share on other sites
Quote:
Original post by rip-off
Quote:

This is a bad example.

It is a perfect example.

That is his point exactly. You cannot just say "use Clear() over new" and vice versa (for whatever reasons), they are not interchangeable operations.


For a completely different reason than what he described, however. The two cases he compared are not comparable. The only difference is an implementation detail. In his example, .Equals() fails. In the example the original poster asked about, it succeeds.

So.. I don't see how it can possibly be a good example. .Clear() and new do the same thing in the sense that in both cases, the resulting values compare equal. So from a usage standpoint, they DO do the same thing. They both set the size of the list to 0.

Share this post


Link to post
Share on other sites
Quote:
Original post by cache_hit
You're right that they're different, but not for the reason you described. They're different because when you use .Clear(), internally it's likely to keep the original memory allocated, and simply update some internal field to denote that size=0. But re-adding elements will be more efficient because it will already have a lot of internal storage allocated from previous uses of the array.



The intention of my example was to show that a like for like comparison doesn't make sense. They are different, and they are different for the reason I described.

I don't understand what you mean.



Quote:
Original post by cache_hit
For a completely different reason than what he described, however. The two cases he compared are not comparable. The only difference is an implementation detail. In his example, .Equals() fails. In the example the original poster asked about, it succeeds.

So.. I don't see how it can possibly be a good example. .Clear() and new do the same thing in the sense that in both cases, the resulting values compare equal. So from a usage standpoint, they DO do the same thing. They both set the size of the list to 0.



That List<int> doesn't exist in a vacuum. They are not the same operation, and saying that they are the same will not make them the same.

Share this post


Link to post
Share on other sites
Quote:

They both set the size of the list to 0.

I think his point was that Clear() has the additional side effect of setting all aliased lists sizes to zero, which may or may not be intended.

Quote:

In the example the original poster asked about, it succeeds.

The OP appears to be looking for the "faster" version in general, which they intend to use in future. If the two operations aren't interchangeable we cannot give a correct answer.

Share this post


Link to post
Share on other sites
Quote:
Original post by rip-off
Quote:

They both set the size of the list to 0.

I think his point was that Clear() has the additional side effect of setting all aliased lists sizes to zero, which may or may not be intended.

Quote:

In the example the original poster asked about, it succeeds.

The OP appears to be looking for the "faster" version in general, which they intend to use in future. If the two operations aren't interchangeable we cannot give a correct answer.


Yea it occurred to me what return0 was saying shortly after I wrote the post, but I had left already and couldn't update my message. I guess my brain is fried after a long day's work :)

Basically, yea, he's saying that IF there are additional outstanding references to the list, then using Clear() on one of those references will result in a different system state than setting that reference to a new instance. Which is true, I didn't think about that originally.

Share this post


Link to post
Share on other sites
well i just need the list for reusing it. i need it empty. there will be only one reference to the list.
and i just remembered something the GC will NOT zero all the array!
i dont know how it will "clear" the list but i do know it will not clean it!
if you go to a pointer of a GC killed list(cant in c#) it will still have the original values! (if nothing else changed them yet).
i asked the original question coz i still dont know if when the GC frees the block of memory, well.... its speed is unknown ...

Share this post


Link to post
Share on other sites
Whether or not the GC zeros memory should be of no consequence, and if you depend on this you are almost certainly invoking undefined behavior. Although im not sure how youre getting pointers to garbage collected memory in the first place. Even if you were, i dont see how it matters. List<T> provides avery specific interface, and none of the observable behavior of it depends on whether the GC zeros memory.

I get the feeling you're thinking about about your problem wrong, or worrying about the wrong things if all this is really important

Share this post


Link to post
Share on other sites
Maybe but if you use .clear it doesnt have to GC anything anyway so youre just trading one thing for another.

Anyway if were just discussing this on the grounds of it being interesting or wanting to learn more thats fine but i dont think you sjould be worrying about it in your code because its unlikely to be the bottleneck

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this