Off-Topic Discussion > Programming

Key-value vector vs. padded/jagged vector

(1/3) > >>

z64555:
This is something of a thought experiment I went through while making some design considerations for the controls config overhaul.

I was presented the problem of memory consumption by vectors when using them to house a set of key/button mappings to a given control. The simplest example would be to enumerate the controller's ID (i.g. CON_KEYBOARD, CON_MOUSE, CON_JOY1, CON_JOY2, etc.) and have that as an index into a vector whose values would be the keys/buttons mapped to the control (or -1 if nothing was mapped).

Although quite fast, it wastes a bunch of memory if the bulk of vector is unmapped (every value in the vector is -1). I thought of two ways to cut this down.

First, would be to make the vector "jagged", by shrinking it to contain the top-most mapping and everything below it. For example:

--- Code: ---vector<short> id = { -1, -1, BUTTON1 };
vector<short> id1 = {-1, BUTTON1};
vector<short> id2 = {-1, -1, -1, -1, -1, -1, -1, -1, -1, BUTTON1};

--- End code ---

vectors id and id1 are pretty straightforward, the last element in both are the only ones that have a value other than -1, and are thus mapped (in this case) to BUTTON1. Compared to id2, id and id1 take up much less space. It should be noted than in for each vector, they still share the same index enumerations, so the first element in each vector corresponds to CON_KEYBOARD, the second element in each vector to CON_MOUSE, the third to CON_JOY1, the fourth to CON_JOY2, and so on.


I was still concerned about the edge case id2 presents, since there's still quite a bit of memory wasted here. So I considered a vector of key-value pairs. For example:

--- Code: ---vector< pair<short, short> > id = {{CON_KEYBOARD, KEY_B}, {CON_MOUSE, BUTTON1}};

--- End code ---

Here, you couldn't use the controller enumerations as an index to instantly get a button mapping, and instead have to iterate through the entire vector to find the key that you want. So, performance wise it is slower than the jagged vector. But, it does however consume less space than a jagged vector... provided that the maximum number of key-value pairs is less than half of the total number of available controllers. Mathematically:

Mkey-value < ((Nmax_controllers - 1) / 2)

Once M equals or is greater than (N-1)/2, the key-value vector consumes more memory than the simpler jagged vector. Meaning you end up with a bigger and slower container! But, it does save a whole bunch of memory when the mappings are minimized, achieving greatest memory efficiency vs. the padded vector when there's only 1 controller that has a mapping to the control in question.


In summary, the key-value vector is a double-edged sword that's only useful if the above comparison is withheld. A jagged vector would be more useful and faster in all other cases.


[edit] added a code block to clarify what I was referring to by a key-value vector

The E:
Now, for those wise in the ways of STL containers, you might ask yourself "Why didn't z64555 consider using std::map or std::unordered_map"?

Which is a great question! Map containers are tailored for just this sort of application, and std::unordered_map has good performance characteristics after all. However, as this talk by Google's Chandler Carruth points out, those data structures play hell with CPU caching. Modern CPUs work most efficiently when dealing with contiguous data structures like arrays or vectors, structures which make explicit guarantees about using contiguous blocks of memory. Given that this is a part of the code that has to be iterated over per-frame, we want to be able to get through it as efficiently as possible, and while maps are really great and easy-to-use in non-critical code paths, they're not the right tool for this kind of thing.

Flipside:
As an old coder I grew up with Arrays as my only option, so I love the flexibility of Map and List structures, but it doesn't surprise me that they are slower to work with. AFAIK Arrays still work on 'requested array position * data size' to find the location of what it is looking for, and you can't really get much faster than that when it comes to referencing locations. Takes me back to the days of direct screen memory referencing and good old (y*xwidth)+x ;)

Edit : Fixed a logic error ;)

AdmiralRalwood:
That video leads to a lot of questions about where we might be able to find performance improvements by making changes to our data structures. For instance, at the moment and assuming I'm remembering my findings from an earlier code search correctly, none of the current usages of SCP_map actually rely on it being an ordered structure (excepting one instance with team colors and the lab that could be altered to use the accompanying SCP_vector instead). Furthermore, the video talks about the performance dangers of linked lists, and FSO relies heavily on linked lists which are traversed every frame (oftentimes multiple times every frame). It might be worth seeing if we get a performance boost from converting those lists into some form of contiguous data structure (or, barring that, at least converting from macro-based "manual" linked lists to SCP_list objects and seeing if that helps any).

Cyborg17:
That sounds like a really big project.

Navigation

[0] Message Index

[#] Next page