3

In my application I do System.Array.Resize once per frame. Initially I set my arrays to a maximum possible size, and then Resize them to something smaller. In some cases it may be a lot smaller, in others it may be just a little smaller. It appears to me though that the more elements there are to resize, the longer it takes. Perhaps my observations are wrong, and that is why I am asking here.

Improve this question
3
  • 2
    Why don't you test and measure it? Commented Jun 19, 2012 at 15:08
  • 1
    Why do you use arrays in the first place? Commented Jun 19, 2012 at 15:09
  • I guess I can test myself. Was hoping for an explanation though besides a solid answer. And I'm using arrays, because I am using game engine Unity, and it requires me to set arrays for rendering Commented Jun 19, 2012 at 15:11

3 Answers 3

Reset to default
6

It should do yes, resizing involves allocating new memory to the size you want and copying the old array into the new one. The larger the array, the more to copy.

From MSDN:

This method allocates a new array with the specified size, copies elements from the old array to the new one, and then replaces the old array with the new one.

Without knowing too much about the code, try using List<T> to manage the list and the resizing you need to do and when you need to provide it to Unity, call list.ToArray();.

This will still create the array and copy it, but only once per frame.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

But doesn't the copy occur in a block? What I mean is, if they array is 10 elements and is reduced to 5, it copies one block, and if it was 100, and I reduce it to 10, it's still just one block copy? I guess that doesn't really make sense now that I think about it. Thanks for getting me on the right thought process. (Will accept in 10 minutes)
@Denzil I'm not sure what you mean by "block".
don't worry. I think I was thinking about this the wrong way. I was imagining that System.Array.Copy (or whatever the copy method is), would run the same amount of time for any array size. Obviously this doesn't make sense though. I was being stupid
@Denzil: There is a certain amount of fixed overhead associated with System.Array.Copy, such that using it to copy four items will probably take a lot less than twice as long as using it to copy two (unless the items are very big structs). On the other hand, using it to copy two million items would probably take about twice as long as using it to copy one million. Note that when performing large copy operations, the system can automatically use methods which have a longer "setup" time, but lower per-item time, than the simpler methods which it uses for smaller operations.
Thank you supercat. More knowledge added to the knowledge bank :)
3

As other answers note, "resizing" an array requires copying all the elements, which is an O(N) operation when N gets large. Note that there are a number of approaches that can be used for copying arrays, with differing "setup" and "per-item" costs. A small array-copy operation may be processed 4 bytes at a time (or in some cases, one byte at a time), while a larger array operation would use special 16-byte operations to do most of the copying. These operations are limited to writing aligned 16-byte chunks of memory at a time. Depending upon source and destination alignment, a large array operation might require copying four groups of four bytes (the last byte of which will overlap the next group), many groups of 16 bytes, and four more groups of four bytes (the first byte of which will overlap the previous group). Determining how to subdivide the groups is a little tricky, so for smaller block-copy requests it's more efficient to use one- or four-byte operations.

Note that the real key to minimizing the expense of array resizing is to do it as seldom as possible. Whenever the List<T> type has to expand the size of its array, it doubles it. If its array starts at 16 items, then at the time it doubles the array to 256 elements, 128 will be empty, 64 will have been copied once, 32 will be copied twice, and 16 will have been copied three times. Note that while some elements will end up being copied lg(N) times, the total number of element copy operations in the process of building a list of size N will always be less than 2N.

There's no way to access the backing array of a List<T> as an array, but it's fairly easy to re-implement the class in such a way as to expose the array, and make sure any methods that accept an array as a parameter allow one to specify the length of the portion to be used (instead of just accessing the Length property of the array).

Improve this answer

1 Comment

Cool, thanks. Very insightful. I'll first try to speed it up without writing my own array list implementation (with the exposed array), but I'll keep it in mind if I really am stuck. Thanks
2

Yes. Array resizing is an O(n) operation. It has to copy each element into the new array.

Maybe it would be better however if you did not use arrays? What are the arrays used for? There might be a better data structure suitable for you application.

Improve this answer

6 Comments

Thanks. Yeah I really would prefer not to use arrays. But I use Unity engine and it requires me to use arrays for rendering. I need to supply arrays of vertices and texture coordinates. But I don't know how many things I will draw before hand, so I have to create large arrays and resize them. I think I will write smarter code though... somehow
I would recommend using a LinkedList and then calling the ToArray() method before passing it to the Unity engine. This avoids you having to allocate the excessively large starting arrays.
Thanks for the tip. I will try this and report back on the performance of it.
@Denzil Do note that ToArray will still create an array and copy the list into it, so if you are doing that for every frame, you may still get issues - however, this is still less copying than before as list resizing is more efficient than array.
@AdamHouldsworth yeah so I guess it may still be just as slow?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.