Vectors versus fixed-size arrays?
by Daniel Buckmaster · in Torque Game Engine · 12/03/2009 (1:22 am) · 6 replies
For things like ShapeBase's convex collision meshes, would it be a better idea to use dynamically-sizable Vectors rather than the current fixed-size arrays? That way, complex shapes would have as many collision meshes as they need - and simple shapes wouldn't be taking up memory by allocating space for 9 (or ten?) meshes.
About the author
Studying mechatronic engineering and computer science at the University of Sydney. Game development is probably my most time-consuming hobby!
#2
In general, is there a way to decide between arrays and Vectors? For instance, what about replacing ShapeBase's fixed-size array of scripted animation threads? (Yes, I checked, that still uses an array ;).)
12/03/2009 (4:38 pm)
Wow... you're absolutely right. I just had it in my mind that ShapeBase still had a limit of 9 or 10 collision shapes, but reading through the code (which does use Vectors...), this doesn't seem to be the case. Thanks for the heads-up ;). (Maybe it's an exporter thing... will have to check.)In general, is there a way to decide between arrays and Vectors? For instance, what about replacing ShapeBase's fixed-size array of scripted animation threads? (Yes, I checked, that still uses an array ;).)
#3
Yes. Weigh the costs of each against the benefits of each. Choose the option with the best cost/benefit ratio.
.. or were you looking for something a bit less general? :P
Well, Vectors offer greater flexibility and easier management. They don't have a fixed size. insert() and erase() function automatically preserve element order and continuity. size() is nice to avoid iterating through unused slots.
On the other hand, Arrays have a simpler syntax, and zero overhead. Though you have to manage them yourself. And you must choose a size up front and then you're stuck with it.
It's also worth noting that Torque's own Vector class allocates space in chunks (see "#define VectorBlockSize" in tVector.h). The default value there is 16; which means you're getting space for at least 16 values even if you don't need that many. This cuts down on the frequency of vector resizes for improved speed at the expense of memory efficiency. You can of course change that value as you see fit.
I will also mention that Torque Vectors don't call element constructors or destructors. This is something to be wary of if you are considering using a Vector for more complicated class types that need a constructor or destructor.
Every situation is going to be different.. but for a general rule, I'd say use Arrays for small sets or cases where you know you will always want X elements. Class Triangle should probably have an array of 3 points, for example. Torque's MatrixF class uses an array of 16 elements. It's a 4x4 matrix class designed specifically for 3D game math, so it makes sense. We can be pretty sure we'll always want 16 elements. Something like mouseButton[x] is a more difficult call. We aren't likely to ever encounter a mouse with 52 buttons are we? But if we impose a fixed limit, where should it be? 3 buttons? 5? 10? What if someone has a Uber Gamer Joystick with 38 buttons and they want to emulate mouse buttons? There's no clear winner there. Then we have larger lists like nodes on a model, portals in a map, or AI path nodes. Almost certainly larger (and less predictable) lists like these would be better off as Vectors.
That's the best I can offer I'm afraid. Vectors are more manageable and more efficient when it comes to large or unpredictable sets, but they aren't quite as efficient for small sets; the effects of which may be felt when dealing with many small sets.
Dunno if anyone has any better advice, but that's my assessment FWIW.
12/04/2009 (3:24 am)
Quote:In general, is there a way to decide between arrays and Vectors?
Yes. Weigh the costs of each against the benefits of each. Choose the option with the best cost/benefit ratio.
.. or were you looking for something a bit less general? :P
Well, Vectors offer greater flexibility and easier management. They don't have a fixed size. insert() and erase() function automatically preserve element order and continuity. size() is nice to avoid iterating through unused slots.
On the other hand, Arrays have a simpler syntax, and zero overhead. Though you have to manage them yourself. And you must choose a size up front and then you're stuck with it.
It's also worth noting that Torque's own Vector class allocates space in chunks (see "#define VectorBlockSize" in tVector.h). The default value there is 16; which means you're getting space for at least 16 values even if you don't need that many. This cuts down on the frequency of vector resizes for improved speed at the expense of memory efficiency. You can of course change that value as you see fit.
I will also mention that Torque Vectors don't call element constructors or destructors. This is something to be wary of if you are considering using a Vector for more complicated class types that need a constructor or destructor.
Every situation is going to be different.. but for a general rule, I'd say use Arrays for small sets or cases where you know you will always want X elements. Class Triangle should probably have an array of 3 points, for example. Torque's MatrixF class uses an array of 16 elements. It's a 4x4 matrix class designed specifically for 3D game math, so it makes sense. We can be pretty sure we'll always want 16 elements. Something like mouseButton[x] is a more difficult call. We aren't likely to ever encounter a mouse with 52 buttons are we? But if we impose a fixed limit, where should it be? 3 buttons? 5? 10? What if someone has a Uber Gamer Joystick with 38 buttons and they want to emulate mouse buttons? There's no clear winner there. Then we have larger lists like nodes on a model, portals in a map, or AI path nodes. Almost certainly larger (and less predictable) lists like these would be better off as Vectors.
That's the best I can offer I'm afraid. Vectors are more manageable and more efficient when it comes to large or unpredictable sets, but they aren't quite as efficient for small sets; the effects of which may be felt when dealing with many small sets.
Dunno if anyone has any better advice, but that's my assessment FWIW.
#4
12/04/2009 (7:34 pm)
That's great, thanks for such a detailed analysis! I was thinking along those lines, but it's great to hear it from someone who knows.Quote:It's also worth noting that Torque's own Vector class allocates space in chunks (see "#define VectorBlockSize" in tVector.h). The default value there is 16; which means you're getting space for at least 16 values even if you don't need that many.That's great to know. So if I create a vector and only use a handful of elements, I've wasted space? Would it be reasonable to resize vectors that I expect to be smaller before use? Or just decrease the default block size, but I assume that was chosen for a reason.
#5
Technically, yes. Now, while I would never advocate deliberately wasting space unnecessarily, in all fairness the amount of wasted space we're talking about here is pretty negligible for a modern computer. To put it in perspective, let's say we have 512MB of memory; definitely on the low side by modern standards. That's 512 x 1024 = KB x 1024 = 536,870,912 bytes. A 32bit value (a standard size float) takes up 4 bytes. So in that 512MB we could theoretically store 134,217,728 floating point numbers. That's 134.2 million 32 bit elements. Technically, you don't actually get to use all of that space, but regardless wasting 12 or 13 spaces here or there is nothing to loose sleep over.
Of course mobile devices are still more limited, though their capacity is climbing fast.
Now, that said, there are still situations where you want to be careful. A little space wasted here and there may be no big deal, but put enough vectors together and it could start to add up. Let's say for example you want to create a new Interior-type class. Let's say you define a Vertex class as a Point3F point, a Point3F normal, a Point2F texture coord, and a Point2F lightmap coord (That's 40 bytes/vert). Ok so far. But then you want to allow polygons with an arbitrary number of Vertexes. Fair enough. So you create a Poly class with a Vector of Vertexes. That is probably a bad idea. Consider that most polygons will have only 3 or 4 vertexes, but their Vectors have allocated space for 16. If we assume an average of 4 verts/poly then each poly is allocating space for 12 extra (unused) vertexes. At 40 bytes/vert that's 480 wasted bytes per polygon. So if you load a 20,000 polygon model, you're wasting 20,000 x 480 = 9,600,000 bytes / 1024 = KB / 1024 = 9.16 MB!
A better solution in that scenario would be to store all of the vertexes in their own Vector. Then each Poly gets a Vector of indexes into the master vertex list. Same flexibility, but this way you're only wasting 48 bytes per poly x 20,000 / 1024 / 1024 = 0.94 MB. Less than 1 MB now was wasted on that same 20,000 poly model. That's much more reasonable.
... was that example maybe a bit over-complicated? I can get carried away like that. :/
No. That won't do anything for you. The Vector will allocate 16 spaces even if you only need 1. If you need 17, you'll get 32. Try to expand to 33 and you'll get 48 reserved spaces. Follow? (An empty Vector, btw, reserves no space beyond that which it uses to store its own size values. So that at least is efficient.) The good news though, is that if you decrement() the vector back down from 33 to 1 element(s), it will resize itself back down from 48 to 16 allocated spaces.
I would hope some testing was done when that value was set. Still, every situation/simulation/game is different. If you want to use Vectors in a way that you think could benefit from a lower block size, go ahead and test it yourself at different sizes. Find out what setting seems to work best for you. (You'll probably find though that the difference is so small it will be hard to measure. Just my prediction.)
12/04/2009 (8:54 pm)
Quote:So if I create a vector and only use a handful of elements, I've wasted space?
Technically, yes. Now, while I would never advocate deliberately wasting space unnecessarily, in all fairness the amount of wasted space we're talking about here is pretty negligible for a modern computer. To put it in perspective, let's say we have 512MB of memory; definitely on the low side by modern standards. That's 512 x 1024 = KB x 1024 = 536,870,912 bytes. A 32bit value (a standard size float) takes up 4 bytes. So in that 512MB we could theoretically store 134,217,728 floating point numbers. That's 134.2 million 32 bit elements. Technically, you don't actually get to use all of that space, but regardless wasting 12 or 13 spaces here or there is nothing to loose sleep over.
Of course mobile devices are still more limited, though their capacity is climbing fast.
Now, that said, there are still situations where you want to be careful. A little space wasted here and there may be no big deal, but put enough vectors together and it could start to add up. Let's say for example you want to create a new Interior-type class. Let's say you define a Vertex class as a Point3F point, a Point3F normal, a Point2F texture coord, and a Point2F lightmap coord (That's 40 bytes/vert). Ok so far. But then you want to allow polygons with an arbitrary number of Vertexes. Fair enough. So you create a Poly class with a Vector of Vertexes. That is probably a bad idea. Consider that most polygons will have only 3 or 4 vertexes, but their Vectors have allocated space for 16. If we assume an average of 4 verts/poly then each poly is allocating space for 12 extra (unused) vertexes. At 40 bytes/vert that's 480 wasted bytes per polygon. So if you load a 20,000 polygon model, you're wasting 20,000 x 480 = 9,600,000 bytes / 1024 = KB / 1024 = 9.16 MB!
A better solution in that scenario would be to store all of the vertexes in their own Vector. Then each Poly gets a Vector of indexes into the master vertex list. Same flexibility, but this way you're only wasting 48 bytes per poly x 20,000 / 1024 / 1024 = 0.94 MB. Less than 1 MB now was wasted on that same 20,000 poly model. That's much more reasonable.
... was that example maybe a bit over-complicated? I can get carried away like that. :/
Quote:Would it be reasonable to resize vectors that I expect to be smaller before use?
No. That won't do anything for you. The Vector will allocate 16 spaces even if you only need 1. If you need 17, you'll get 32. Try to expand to 33 and you'll get 48 reserved spaces. Follow? (An empty Vector, btw, reserves no space beyond that which it uses to store its own size values. So that at least is efficient.) The good news though, is that if you decrement() the vector back down from 33 to 1 element(s), it will resize itself back down from 48 to 16 allocated spaces.
Quote:Or just decrease the default block size, but I assume that was chosen for a reason.
I would hope some testing was done when that value was set. Still, every situation/simulation/game is different. If you want to use Vectors in a way that you think could benefit from a lower block size, go ahead and test it yourself at different sizes. Find out what setting seems to work best for you. (You'll probably find though that the difference is so small it will be hard to measure. Just my prediction.)
#6
Thanks for the detailed example! I think I've got a pretty good idea what I'm getting into here :). Also, I'm thinking of creating a class for vertex-based navmeshes, so your example was actually spot-on for the sorts of things I might want to use Vectors for ;P.
Thank you again!
12/15/2009 (7:13 pm)
Quote:No. That won't do anything for you. The Vector will allocate 16 spaces even if you only need 1. If you need 17, you'll get 32. Try to expand to 33 and you'll get 48 reserved spaces. Follow?Okay, I see.
Thanks for the detailed example! I think I've got a pretty good idea what I'm getting into here :). Also, I'm thinking of creating a class for vertex-based navmeshes, so your example was actually spot-on for the sorts of things I might want to use Vectors for ;P.
Thank you again!
Torque 3D Owner Scott Richards
Regardless, the short answer is yes, Vectors would be better; If only because they allow more collision meshes. Wasted space is not really a concern because ShapeBase is only storing 32bit id numbers, not the actual mesh data; So the wasted space is negligible. The actual mesh data is kept by TSShape which has always used Vectors AFAIK.
Look at 1.5.2 though, because I think that's already been implemented; and it shouldn't be too difficult to back-port it to a previous version.