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]

Perhaps this is way off, but is it really necessary to clear the arrays? Would it not suffice just to overwrite them?

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

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?

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

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.

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)

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.

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.