So it turns out these functions do not sort in place, and I'm running with the assumption it re-allocates an array the size of the one you're sorting on. I assume adobe is doing this because after some thought I believe their Array data type is either a linked list or a tree of some sort, so swapping 2 elements in an Array appears to be quite expensive, hence the problem of most end user sorts being very inefficient (As I found out with my own quicksort)
The problem is the sort() and sortOn functions are producing a lot of overhead in the form of [mark] calls, creating a very undesireable hitching effect in my game when the gc runs. Yes, my collection is fairly large. No, it can not be any smaller. I have tried many solutions, including using a ByteArray full of indices into the source array, and sorting the indices, but as it turns out dereferencing an array by an index is also very slow, as the collection size increases. I can't spread out gc cleanup and I must sort.
I realize this problem has been addressed in Flash 10 with vectors, but we are currently unable to adopt 10 just yet. The fact that it's taken 10 versions to get a contiguous memory array type is kinda funny, actually ...
Anyways any ideas would be appreciated, although I'm getting the bad feeling I'm kinda hosed on this one.
No comments:
Post a Comment