Jump to content

  • Log In with Google      Sign In   
  • Create Account

list.clear or new?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
21 replies to this topic

#1 kalixxx   Members   -  Reputation: 105

Like
0Likes
Like

Posted 05 March 2010 - 02:22 AM

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)

Sponsor:

#2 mososky   Members   -  Reputation: 100

Like
0Likes
Like

Posted 05 March 2010 - 02:26 AM

if GC has to clear the list it would still be doing the same thing, and I would assume has the overhead of the GC.

It should be pretty easy to setup a test right?

#3 kalixxx   Members   -  Reputation: 105

Like
0Likes
Like

Posted 05 March 2010 - 02:39 AM

the GC works when IT wants to work! its its own boss!
i can do 1000s of "new" and it will clean them when it FEELS like it!

#4 Zahlman   Moderators   -  Reputation: 1682

Like
0Likes
Like

Posted 05 March 2010 - 08:13 AM

Um, yes. This is a good thing, because it's smarter than us, and has information we don't have.

#5 Promit   Moderators   -  Reputation: 7214

Like
0Likes
Like

Posted 05 March 2010 - 08:34 AM

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.

#6 cache_hit   Members   -  Reputation: 614

Like
0Likes
Like

Posted 05 March 2010 - 08:53 AM

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.

#7 Promit   Moderators   -  Reputation: 7214

Like
0Likes
Like

Posted 05 March 2010 - 08:56 AM

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.

#8 cache_hit   Members   -  Reputation: 614

Like
0Likes
Like

Posted 05 March 2010 - 08:57 AM

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.

#9 MaulingMonkey   Members   -  Reputation: 1556

Like
0Likes
Like

Posted 05 March 2010 - 09:30 AM

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.)

#10 cache_hit   Members   -  Reputation: 614

Like
0Likes
Like

Posted 05 March 2010 - 10:02 AM

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.

#11 Josh Petrie   Moderators   -  Reputation: 3117

Like
0Likes
Like

Posted 05 March 2010 - 10:05 AM

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.

Josh Petrie | Core Tools Engineer, 343i | Microsoft C++ MVP


#12 return0   Members   -  Reputation: 444

Like
0Likes
Like

Posted 05 March 2010 - 12:09 PM

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);

#13 cache_hit   Members   -  Reputation: 614

Like
0Likes
Like

Posted 05 March 2010 - 12:20 PM

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));





#14 rip-off   Moderators   -  Reputation: 8344

Like
0Likes
Like

Posted 05 March 2010 - 12:27 PM

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.

#15 cache_hit   Members   -  Reputation: 614

Like
0Likes
Like

Posted 05 March 2010 - 12:31 PM

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.

#16 return0   Members   -  Reputation: 444

Like
0Likes
Like

Posted 05 March 2010 - 12:33 PM

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.

#17 rip-off   Moderators   -  Reputation: 8344

Like
0Likes
Like

Posted 05 March 2010 - 12:38 PM

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.

#18 cache_hit   Members   -  Reputation: 614

Like
0Likes
Like

Posted 05 March 2010 - 02:09 PM

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.

#19 kalixxx   Members   -  Reputation: 105

Like
0Likes
Like

Posted 06 March 2010 - 12:03 AM

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 ...

#20 cache_hit   Members   -  Reputation: 614

Like
0Likes
Like

Posted 06 March 2010 - 02:55 AM

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




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS