Question about CvPlot.cpp mod with arrays

[CaptainLost]

I noticed that the attributes for plots have been scrunched down as much as possible (changing 'int' to 'short' and so on), and I assume the goal there is to save memory.

So I have a question about a mod I recently designed. I have added an array for each tile that will hold every EventTriggerType added to the game, and an int. The idea is that tiles can gain points (hence the int) toward event triggers over time, and when reaching a certain threshold, activate the trigger; the system makes all sorts of seasons, disasters, and etc. mods very easy to do using only xml.

Problem is the way ListEnumMaps are initialized, each tile's array will always include ALL the EventTriggerTypes in the game. I plan on using EventTriggers for other similar systems not tied to plots, and there will likely be hundreds of those, with only 8 to a couple dozen triggers that plots have to care about.

I don't think lag between turns will be a huge issue because ListEnumMaps skip non-default values and I can switch any non-tile-specific row in the array to default. IMO looping through 8-24 * (number of tiles) stuff every turn is really not that much considering all the other stuff the game loops through each turn, though I may be wrong.

But, the memory issue...how bad will it be to fill every single tile with an array of hundreds of rows?? Game-breaking?

 

[f1rpo]

Problem is the way ListEnumMaps are initialized, each tile's array will always include ALL the EventTriggerTypes in the game.

ListEnumMap should work much like a std::vector<std:: pair<Key,Value>>, storing only those key-value pairs that have ever differed from the default value. That's also why iteration is fast – nothing has to be skipped. It sounds to me like most of the event triggers will only ever have 0 points. Only non-sequential access, say, listmap.get(eMyTrigger), should be somewhat slow.

If you had to use an array with one int per possible pair, that would indeed sound undesirable wrt. cache performance. Currently, an AdvCiv plot has a size of 268 byte(*), if there are 200 event triggers, you'd add 800 byte. I've never tested adding a lot of data to CvPlot; I doubt that it would be game-breaking, but I imagine that it would slow AI turns down noticeably. Well, on a map size that is already almost unplayable, much larger plot instances could presumably add the last few straws. (Fwiw, AdvCiv allows only up to 32768 plots – e.g. 256 x 128 – unless MAX_CIV_PLAYERS is increased beyond 18. This way, plot ids fit in 16-bit integers.)

If plots aren't the only entities for which event-trigger points will be stored, perhaps it would be best to create a map

EventTrigger --> TriggeredData --> Points​

outside of CvPlot, maybe at CvMap, akin to CvMap::m_aeiPlotExtraYield (recently moved by me from CvGame), which also deals with random events. "TriggeredData" for lack of a better name; it probably shouldn't be the EventTriggeredData struct already in the code because that can store a plot and a city and a unit etc. – when a single ID would be enough, So I guess it could just be:

EventTriggerTypes --> int ("iData") --> int (short?)​

The TriggeredData isn't really enumerable (plots are, but e.g. units aren't), so this couldn't be an EnumMap2D. Maybe simply a std::map<std:: pair<EventTriggerTypes,int>, int>, possibly wrapped into a new class. At any rate, my hope would be that this single big(?) data structure (or part of it) would only enter the CPU cache when trigger scores get updated at the end of a turn or so and wouldn't interfere with some frequently needed plot data being kept in the cache at other times. (Disclaimer: All talk from me about memory performance is highly speculative.)

On a side note, upon revisiting my ListEnumMap implementation, I notice that it does not actually guarantee that the loop macro FOR_EACH_NON_DEFAULT_PAIR will only return non-default pairs. If a value is set to non-default and then back to the default, it'll remain in the map (until the number of stored non-default pairs reaches a threshold or the map gets written to a savegame). In most cases, it's not crucial to exclude non-default pairs – just a matter of performance –, so I'd like to keep it as it is for most of the code, but there might already be cases (subtle bugs) where defaults really need to be excluded for correctness, and, even if not, the name of the macro is currently misleading.
Edit: I've cleaned this up now with relatively little effort (not yet pushed to GitHub though). And I don't think any of my uses of ListEnumMap were actually problematic.
Edit2: My suggested std::map in the middle paragraph was missing a value type. And I'm not sure what I even meant with the vector of int pairs ... I guess a ListEnumMap<EventTriggerTypes,std:: pair<int,int>*> could work. Oh, well, some 2D data structure.
(*) Edit3: sizeof(CvPlot) being 268 byte is misleading as this counts only 4 byte for each array or other pointer member.

 

[CaptainLost]

If plots aren't the only entities for which event-trigger points will be stored, perhaps it would be best to create a map

This is a super good idea, thank you! I'm going to switch it to that and see how it goes.

Best part is, I have been trying to figure out how to do a similar event system tied to each unit, and avoided doing it because it would make the mod yet more massive. This should let me do that too.

 

[CaptainLost]

Follow up question. (In the process of redoing the events system and it seems to work fine so far.)

The need to keep a plot's memory very tight and small makes complete sense - but what about units? If I added an array of about 15 integers to every unit, is that something an array map could also replace?

For context I'm thinking of splitting experience into several different types corresponding to, say, features, terrain types, etc. So this one would have to be updated every time the unit is in combat.

EDIT: one more. I went with a ListEnumMap<EventTriggerTypes, std:: pair<int,int>*> because skipping defaults sounds great again. What will ListEnumMap initialize the 'default' to? Just NULL?

 

[f1rpo]

I don't know how important the size of unit data is. There can be quite a lot of units, obviously, but I guess they're not as frequently accessed as plots. CvPlot is the only class that had already been optimized for size by Firaxis (through smaller int types and bitfields for booleans). I have a to-do note in CvUnit.h suggesting to replace most of the 50+ primitive int members with short. Would be interesting to see if that has any effect on performance; I'd be surprised if it would save more than 1%. And I doubt that adding 15 more would be a big deal. For XP you could surely use short, then it's really not much. I wouldn't worry about memory locality or even about ArrayEnumMap vs. ListEnumMap. (The former could easily be faster because it allocates memory lazily the first time that a value changes. Which, I guess, also means that the memory, when it does get allocated, ends up not that close to other, more frequently accessed CvUnit data.) Oh, if you want to use any enum map, you'd have to define an enum for the types of experience. I assume that the length would be known at compile time; in that case, it should suffice to add it to the DO_FOR_EACH_STATIC_ENUM_TYPE list in CvEnumMacros.h.

I went with a ListEnumMap<EventTriggerTypes, std:: pair<int,int>*> because skipping defaults sounds great again. What will ListEnumMap initialize the 'default' to? Just NULL?

Yes, the templates can only handle integral default values, so only NULL will work for pointers. Here's my meager unit test for a pointer-valued enum map:

ListEnumMap<PlayerTypes,scaled*> test;
scaled rNum;
test.set((PlayerTypes)0, &rNum);
FAssert(test.get((PlayerTypes)1) == NULL);
FAssert(test.get((PlayerTypes)0) == &rNum);