Jump to content
  • Advertisement
Sign in to follow this  
remigius

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

This topic is 3003 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!