Sign in to follow this  
remigius

[.net] [C#] Fastest way to zero out an array?

Recommended Posts

I'm currently working on a little XNA project that requires me to clear a few large arrays each frame. The arrays are backing stores for textures, so they have up to millions of elements, and they're constructed from a generic type parameter (limited to value types) if that's of any importance. I've done some searching and come up with the following options to clear it:
  1. Loop over the array and set each element to zero
  2. Use Array.Clear to set each element to zero
  3. P/Invoke memset or ZeroMemory to clear the array
  4. Create a new array
The problem is that (1) runs in O(n) and according to the documentation so does (2). Since these are rather large arrays and multiple ones need to be cleared each frame, I'd like to avoid the O(n) operation. Unfortunately (3) is not an option since I don't think I can P/Invoke on the XBox 360 nor do I really want to. Assuming the allocation and zero-ing out of memory for option (4) is speedy it seems to be the fastest choice, but it obviously generates a ton of garbage when I do this each frame. At the moment I've settled for (2), but would anyone happen to know of a faster way to zero out the array memory in C# that also works on the 360? (edit) I've found a topic about this on StackOverflow and the viable alternatives there seem to be Parallel.For or Buffer.BlockCopy. I don't think Parallel.For is available on the 360 and multi-threading an array clear within a game loop seems both overkill and asking for trouble anyway. Buffer.BlockCopy sounds interesting and is available in the 360, but it still seems a bit of a round-about way to go about this compared to memset/ZeroMemory. [Edited by - remigius on April 26, 2010 6:22:12 AM]

Share this post


Link to post
Share on other sites
Apart from what Omid said, clearing array contents is always O(n), even with ZeroMemory() et al., except on quantum computers maybe.

Share this post


Link to post
Share on other sites
3 is O(N) as well.
4 is more than O(N) as a gc collection involves a scan of everything in the generation which would be O(N+M) and a copy of every thing not in the garbage set.

Share this post


Link to post
Share on other sites
Quote:
Original post by Omid Ghavami
Perhaps this is way off, but is it really necessary to clear the arrays? Would it not suffice just to overwrite them?


Thanks for the thought, but unfortunately I do need the clear. The class containing this code is part of a library and it exposes a Clear() method that, among other things, should clear the array by contract. If overwriting is an option, user code will simply not call this Clear(). The Clear() was first just added for completeness, but it turned out to be a common use case to call this quite often each frame.

Quote:

3 is O(N) as well.
4 is more than O(N) as a gc collection involves a scan of everything in the generation which would be O(N+M) and a copy of every thing not in the garbage set.


Well, those two weren't much of an option anyway. I figured (3) was O(n) but to my mind it's another n. It doesn't have to deal with type safety and can simply zero out the bytes, plus it's a bit closer to the hardware. Regarding (4) you're of course right that the total cost is higher and it isn't an option because of the garbage anyway (especially on the 360), but I was thinking about the direct running costs of the clear.

Anyway, I'll just stick with (2) then I guess?

Share this post


Link to post
Share on other sites
Quote:
(edit) I've found a topic about this on StackOverflow and the viable alternatives there seem to be Parallel.For or Buffer.BlockCopy. I don't think Parallel.For is available on the 360 and multi-threading an array clear within a game seems both overkill and asking for trouble anyway. Buffer.BlockCopy sounds interesting and is available in the 360, but it still seems a bit of a round-about way to go about this compared to memset/ZeroMemory.


Just to keep things clear: Even if that's faster for large enough arrays, it's still O(N).

Share this post


Link to post
Share on other sites

Look, I don't want to get into a discussion about what big O means. I apologize if I've offended any of you by abusing the notation. I'm just asking if there's a faster way to clear the array than those listed above, in amortized costs then.

Share this post


Link to post
Share on other sites
you could create a second array, which you let stay cleared. on 'clear', you just swap the two arrays, so for the user, it's cleared. then you clear in parallel on a thread the other array.

if the clear takes less time than the time between Clear calls, you get a a fake-instant clearing. (doublebuffering style)

Share this post


Link to post
Share on other sites

Thanks for the idea dave. I started thinking about double-buffering too, but I'm a bit hesitant to add multithreading for this with the 360 in mind.

Rereading my question, I realize it may have been a bit too vague to just jot it down here. Asking for something faster than Array.Clear and akin to memset seemed straightforward enough, but you guys were probably right to point out it's all the same in asymptotic runtime. Since there doesn't seem to be some clearly better way, I think I'll stick with Array.Clear and see if it really needs optimization futher down the line.

Share this post


Link to post
Share on other sites
Quote:
Original post by remigius

Look, I don't want to get into a discussion about what big O means. I apologize if I've offended any of you by abusing the notation. I'm just asking if there's a faster way to clear the array than those listed above, in amortized costs then.


Oh no, you got me wrong. I really didn't want to offend you, sorry. I just thought it might be worth mentioning. Peace.

Share this post


Link to post
Share on other sites
Quote:
Original post by phresnel

Oh no, you got me wrong. I really didn't want to offend you, sorry. I just thought it might be worth mentioning. Peace.


No problem at all, as I said above I'm the one who should be apologizing. My question wasn't as clear or straightforward as I thought, so I was wrong to expect a magic fix-it answer. And besides you were absolutely right [smile]

Share this post


Link to post
Share on other sites
Have a large "zeroed" string, and memcopy the necessary amount of zeroes you need to clear a given array. That might be faster than accessing each byte and setting it to zero programmatically.

I mean:


memcpy ( MyString, MyLargeZeroedString, MyStringSize );


Could be faster than:


for (i=0; i<MyStringSize; i++)
MyString[i] = 0;


EDIT: I now realise this was C#... Still, the concept (I guess) should apply.

[Edited by - owl on April 26, 2010 10:15:08 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by owl
EDIT: I now realise this was C#... Still, the concept (I guess) should apply.


Still thanks for your idea as well. I think this approach is analogous to Buffer.BlockCopy in C#, which is the first on my list of optimizations to try if it turns out that's actually necessary. I probably should have confirmed that first before bothering you with my question... again premature optimization proves to be the root of all evil [wink]

Share this post


Link to post
Share on other sites
An interesting thing to note: if you make use of memcpy (and probably memset too) in a C++/CLI app, it can be compiled down to a single IL instruction cpyblk. Not sure what effect that has on the speed of the operation though.

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