@Jason: Seconds Per Frame is a better benchmark. It tells you how long it takes to render a frame, rather than how many frames you can render in a second. Gives you a general idea of how quickly your code is running, or in a minimal example in regards to the GDK, how quickly the GDK's internal event loop executes. This is one of those things that has been discussed to death on gamedev.net, and I highly recommend looking on their forums for information regarding SPF vs. FPS as there is a lot of in depth analysis that has been done and I'm sure you'd find very interesting. I know I found it interesting.
----
As for arrays and speed, keep in mind that speed is relative. Arrays don't have a speed. Arrays are nothing more than a pointer to a contiguous set of data that you can access via an index that's used as an offset. It's what you do with it that determines it's speed.
Arrays and (singly/doubly) linked lists have relatively the same search speeds. Each node or index has to be accessed in order or sequentially and checked. For small data sets of a couple hundred simple objects, this is fine. Anything larger and you are far better off using different methods.
BST's are an excellent option when searching for something with a key that happens to be an integer. Start at the root node in the BST. If it's the key you're looking for, return it and you're done. If the key your looking for is larger, move to the right node and repeat the process. If it's smaller, move to the left node and repeat the process. On a data set of a million elements, it brings your search down to a mere 20 comparisons.
Now you can use an array for a BST, however every time you do a search, you have to sort the array. On a million elements on an ideal data set (which never happens in practice), this is a minimum of a million comparison checks on the array, before you even start searching for your element. You can keep the array sorted to begin with, but every time you add or remove an item, all items in the array are going to need to be shifted up or down to accommodate for the new or removed data. Worse, as the array grows you're going to have to resize it. That means creating a new array (likely twice as long to minimize how often you resize the array) and copying all the data from the old array, to the new one. On a million elements? That's not a short amount of time. That is if you even have a free contiguous memory block to store a million elements. Memory allocations can and DO fail.
All that said, and considering the possible number of GDK objects that can be allocated, an array would be a very poor choice due to search times and memory constraints.
But there's another way. What if you were to create a BST structure.
struct BST_Node {
int key;
void* data; //Theoretically you could hold anything here.
BST_Node* left;
BST_Node* right;
};
Same concept as a linked list, just with two possible children instead of one. Searching is identical to what I mentioned earlier. Start at the root node in the BST_Node structure. If it's the key you're looking for, return the data and you're done. If the key your looking for is larger, move to the right BST_Node and repeat the process. If it's smaller, move to the left BST_Node and repeat the process. You can add and remove nodes, using the same searching routines, keeping the BST_Node structure sorted at all times with minimum overhead and at a superior speed over a standard BST style array.
The problem with this approach in regards to the GDK is that most people will add items to the BST list sequentially starting at a low index. If you add items with a key/index of 10-20, in order, you'll end up with a BST with nothing but right nodes, all left nodes pointing to NULL. What does this create? A standard linked list in practice. In effect the only two benefits to this is far less overhead when adding or removing data, and that as items are added and removed the BST structure will even out over time. As the structure evens out, your search times can only improve over time. In the end, there isn't a whole lot of trade off. In this particular case you'll get faster inserts, deletions and seek times over a traditional array as your data doesn't have to be constantly copied around, merely the pointers need to be changed. Pointer manipulation is incredibly fast.
It's very possible the GDK does use an array for object storage (be it an array of pointers, or an array of the data itself. An array of pointers to objects removes the seek time issue, but still has the issue of a dynamic array. Data needs to be copied into a larger array. As the array grows, the slower this is. In truth this would explain some of the lag issues when loading content in the GDK. It's still not a very good implementation. I'd put my vote on some sort of tree structure, BST's being only one potential example they could use.
The truth is, unless we get our hands on the source code, or run the assembly through OllyDBG or IDA this is all guesswork (which in most cases is illegal depending on where you live). But I have to say, guesswork or not, I love puzzles.
This makes excellent grounds for discussion of current methods and a great testbed for new ideas. Contemplation, discussion, dissection and brainstorming like this should be encouraged and I'd love to see it more on this forum!
-Piro
