[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: [Select]

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

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: [Select]

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

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:

M_key-value < ((N_{max_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.

[AdmiralRalwood]

That sounds like a really big project.

Without a doubt; just converting Ship_info from a C-style array to an SCP_vector was a fair amount of work.

[Flipside]

I think that would have to be very much a 'benefit vs effort' decision, i.e 'Are the gains worth the amount of time and effort involved in doing it?'

[m!m]

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).

FSO relies on linked lists but in most cases the objects in the list are actually right next to each other in memory (e.g. the Objects array).

[potterman28wxcv]

I am not used to C++, only to C, but in the general case, if you prefer performance over memory, contiguous arrays (so, vectors here I guess ?) are the way to go. When it comes to access elements quickly, there's nothing faster than that (as long as the size is fixed though ; otherwise you will end up having extra cost because of reallocation).

If you want to save up memory, linked lists are fine ; but a linked list means that for every element you want to store, you have to store an additional pointer. Let's say I want to store 10000 integers of 32 bits each ; you need an additional 64 pointer for each element (to point to the next one in the list), so instead of consuming (if the computer magically knew where the integers are) 40 kB it consumes (4 + 8) * 10000 = 120 kB, three times more.

But, memory speaking, it might be better to use a linked list rather than having a huge part of the array unused.

Though, I'm wondering, does memory consumption really matter in this case ? Most of the memory is taken by graphics (I guess), such structures (key-bindings and stuff) should not use that much memory, unless you are coding an algorithm to solve a NP-complex problem. I might be wrong though, I have no damn idea how memory is handled in Freespace

But I think it would be nice to have some numbers before deciding to switch the structure. If this part consumes less than 10 MB, it might not be necessary to improve it. Because if it's really taking 10 MB, you would end up sacrificing performance just to save maybe 5 MB.

[AdmiralRalwood]

I am not used to C++, only to C, but in the general case, if you prefer performance over memory, contiguous arrays (so, vectors here I guess ?) are the way to go. When it comes to access elements quickly, there's nothing faster than that (as long as the size is fixed though ; otherwise you will end up having extra cost because of reallocation).

Unless you're adding/removing elements massively more often than you're iterating through the vector, it'll still be faster than other data structures even with the cost of shoving memory around (simply due to the speed of the CPU cache(s)).

[CP5670]

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.

Interesting, I use unordered_maps frequently but hadn't thought of this. There are apparently some third-party versions of it that are more efficient and are backward compatible.