Author Topic: Key-value vector vs. padded/jagged vector  (Read 1971 times)

0 Members and 1 Guest are viewing this topic.

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Key-value vector vs. padded/jagged vector
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:

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
« Last Edit: May 28, 2015, 06:11:03 pm by z64555 »
I'm on Facebook! sort of. Zeesixtyfour Fivefiftyfive

-=wxFRED2=-
R.I.P. Oliver
------------
EveningTea: Time to go Freeman on this cultist..
* EveningTea pulls crowbar off his shoulderstrap and charges screaming incoherently across the marsh *
------------
z64555: bro. do you even salad
------------
z64555: suprise double quaternion!

 

Offline The E

  • He's Ebeneezer Goode
  • Global Moderator
  • 213
  • Nothing personal, just tech support.
    • Skype
    • Steam
    • Twitter
Re: Key-value vector vs. padded/jagged vector
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.
**** every cause that ends in murder and children crying. ― Iain Banks
Join the fun at the HLP IRC channel. Get the latest spam and gossip as long as it's fresh!

 

Offline Flipside

  • əp!sd!l£
  • 212
Re: Key-value vector vs. padded/jagged vector
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 ;)
« Last Edit: May 28, 2015, 01:37:21 pm by Flipside »

 

Offline AdmiralRalwood

  • 211
  • The Cthulhu programmer himself!
    • Skype
    • Steam
    • Twitter
Re: Key-value vector vs. padded/jagged vector
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).
Ph'nglui mglw'nafh Codethulhu GitHub wgah'nagl fhtagn.

schrödinbug (noun) - a bug that manifests itself in running software after a programmer notices that the code should never have worked in the first place.

When you gaze long into BMPMAN, BMPMAN also gazes into you.

"I am one of the best FREDders on Earth" -General Battuta

<Aesaar> literary criticism is vladimir putin

<MageKing17> "There's probably a reason the code is the way it is" is a very dangerous line of thought. :P
<MageKing17> Because the "reason" often turns out to be "nobody noticed it was wrong".
(the very next day)
<MageKing17> this ****ing code did it to me again
<MageKing17> "That doesn't really make sense to me, but I'll assume it was being done for a reason."
<MageKing17> **** ME
<MageKing17> THE REASON IS PEOPLE ARE STUPID
<MageKing17> ESPECIALLY ME

<MageKing17> God damn, I do not understand how this is breaking.
<MageKing17> Everything points to "this should work fine", and yet it's clearly not working.
<MjnMixael> 2 hours later... "God damn, how did this ever work at all?!"
(...)
<MageKing17> so
<MageKing17> more than two hours
<MageKing17> but once again we have reached the inevitable conclusion
<MageKing17> How did this code ever work in the first place!?

<@The_E> Welcome to OpenGL, where standards compliance is optional, and error reporting inconsistent

<MageKing17> It was all working perfectly until I actually tried it on an actual mission.

<IronWorks> I am useful for FSO stuff again. This is a red-letter day!
* z64555 erases "Thursday" and rewrites it in red ink

<MageKing17> TIL the entire homing code is held up by shoestrings and duct tape, basically.

 

Offline Cyborg17

  • 29
  • A-1 Supar
Re: Key-value vector vs. padded/jagged vector
That sounds like a really big project.

 

Offline AdmiralRalwood

  • 211
  • The Cthulhu programmer himself!
    • Skype
    • Steam
    • Twitter
Re: Key-value vector vs. padded/jagged vector
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.
Ph'nglui mglw'nafh Codethulhu GitHub wgah'nagl fhtagn.

schrödinbug (noun) - a bug that manifests itself in running software after a programmer notices that the code should never have worked in the first place.

When you gaze long into BMPMAN, BMPMAN also gazes into you.

"I am one of the best FREDders on Earth" -General Battuta

<Aesaar> literary criticism is vladimir putin

<MageKing17> "There's probably a reason the code is the way it is" is a very dangerous line of thought. :P
<MageKing17> Because the "reason" often turns out to be "nobody noticed it was wrong".
(the very next day)
<MageKing17> this ****ing code did it to me again
<MageKing17> "That doesn't really make sense to me, but I'll assume it was being done for a reason."
<MageKing17> **** ME
<MageKing17> THE REASON IS PEOPLE ARE STUPID
<MageKing17> ESPECIALLY ME

<MageKing17> God damn, I do not understand how this is breaking.
<MageKing17> Everything points to "this should work fine", and yet it's clearly not working.
<MjnMixael> 2 hours later... "God damn, how did this ever work at all?!"
(...)
<MageKing17> so
<MageKing17> more than two hours
<MageKing17> but once again we have reached the inevitable conclusion
<MageKing17> How did this code ever work in the first place!?

<@The_E> Welcome to OpenGL, where standards compliance is optional, and error reporting inconsistent

<MageKing17> It was all working perfectly until I actually tried it on an actual mission.

<IronWorks> I am useful for FSO stuff again. This is a red-letter day!
* z64555 erases "Thursday" and rewrites it in red ink

<MageKing17> TIL the entire homing code is held up by shoestrings and duct tape, basically.

 

Offline Flipside

  • əp!sd!l£
  • 212
Re: Key-value vector vs. padded/jagged vector
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?' :)

 

Offline m!m

  • 210
Re: Key-value vector vs. padded/jagged vector
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).

 

Offline potterman28wxcv

  • 27
  • Just a fan player
Re: Key-value vector vs. padded/jagged vector
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 :P

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.
« Last Edit: May 30, 2015, 08:35:40 pm by potterman28wxcv »

 

Offline AdmiralRalwood

  • 211
  • The Cthulhu programmer himself!
    • Skype
    • Steam
    • Twitter
Re: Key-value vector vs. padded/jagged vector
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)).
Ph'nglui mglw'nafh Codethulhu GitHub wgah'nagl fhtagn.

schrödinbug (noun) - a bug that manifests itself in running software after a programmer notices that the code should never have worked in the first place.

When you gaze long into BMPMAN, BMPMAN also gazes into you.

"I am one of the best FREDders on Earth" -General Battuta

<Aesaar> literary criticism is vladimir putin

<MageKing17> "There's probably a reason the code is the way it is" is a very dangerous line of thought. :P
<MageKing17> Because the "reason" often turns out to be "nobody noticed it was wrong".
(the very next day)
<MageKing17> this ****ing code did it to me again
<MageKing17> "That doesn't really make sense to me, but I'll assume it was being done for a reason."
<MageKing17> **** ME
<MageKing17> THE REASON IS PEOPLE ARE STUPID
<MageKing17> ESPECIALLY ME

<MageKing17> God damn, I do not understand how this is breaking.
<MageKing17> Everything points to "this should work fine", and yet it's clearly not working.
<MjnMixael> 2 hours later... "God damn, how did this ever work at all?!"
(...)
<MageKing17> so
<MageKing17> more than two hours
<MageKing17> but once again we have reached the inevitable conclusion
<MageKing17> How did this code ever work in the first place!?

<@The_E> Welcome to OpenGL, where standards compliance is optional, and error reporting inconsistent

<MageKing17> It was all working perfectly until I actually tried it on an actual mission.

<IronWorks> I am useful for FSO stuff again. This is a red-letter day!
* z64555 erases "Thursday" and rewrites it in red ink

<MageKing17> TIL the entire homing code is held up by shoestrings and duct tape, basically.

 

Offline CP5670

  • Dr. Evil
  • Global Moderator
  • 212
  • 142857
Re: Key-value vector vs. padded/jagged vector
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.