Off-Topic Discussion > Programming

Key-value vector vs. padded/jagged vector

<< < (2/3) > >>

AdmiralRalwood:

--- Quote from: Cyborg17 on May 28, 2015, 05:19:31 pm ---That sounds like a really big project.

--- End quote ---
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:

--- Quote from: AdmiralRalwood on May 28, 2015, 04:53:51 pm ---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).

--- End quote ---
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 :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.

AdmiralRalwood:

--- Quote from: potterman28wxcv on May 30, 2015, 08:32:38 pm ---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).

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

Navigation

[0] Message Index

[#] Next page

[*] Previous page