[Freeciv-Dev] (PR#7342) cm patch: heap-allocate the combinations

["Benoit Hudson" <bh@xxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=7342 >

Right, and here's the promised patch.

Index: cm.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/cm.c,v
retrieving revision 1.19
diff -b -c -3 -p -u -r1.19 cm.c
--- cm.c        2004/01/10 09:41:31     1.19
+++ cm.c        2004/01/29 03:01:55
@@ -145,6 +145,7 @@
 #define SHOW_EXPAND_CACHE3_RESULT                       FALSE
 #define SHOW_CACHE_STATS                                FALSE
 #define SHOW_TIME_STATS                                 FALSE
+#define SHOW_CM_STORAGE_USED                            FALSE
 #define DISABLE_CACHE3                                  FALSE
 
 #define NUM_SPECIALISTS_ROLES                          3
@@ -172,13 +173,20 @@ static struct {
 /* 
  * Contains all combinations. Caches all the data about a city across
  * multiple cm_query_result calls about the same city.
+ * struct combination:
+ *      store one allocation of some number of workers to fields; if there
+ *      is leftover population, store all allocations of leftovers to
+ *      specialists
+ * struct results_set:
+ *      store all combinations for a given number of workers
+ * struct cache3:
+ *      store a results_set for each number of workers
  */
 static struct {
   int fields_available_total;
 
-  struct {
+  struct results_set {
     struct combination {
-      bool is_valid;
       int max_scientists, max_taxmen, worker;
       int production2[NUM_PRIMARY_STATS];
       enum city_tile_type worker_positions[CITY_MAP_SIZE][CITY_MAP_SIZE];
@@ -189,7 +197,9 @@ static struct {
        */
       struct cm_result *cache1;
       struct cm_result all_entertainer;
-    } combinations[MAX_COMBINATIONS];
+    } **combinations;
+    int ncombinations; /* number of valid combinations */
+    int ncombinations_allocated; /* amount of room in combinations array */
   } results[MAX_FIELDS_USED + 1];
 
   struct city *pcity;
@@ -255,17 +265,7 @@ static int count_worker(struct city *pci
 *****************************************************************************/
 static int count_valid_combinations(int fields_used)
 {
-  int i, result = 0;
-
-  for (i = 0; i < MAX_COMBINATIONS; i++) {
-    struct combination *current =
-       &cache3.results[fields_used].combinations[i];
-
-    if (current->is_valid) {
-      result++;
-    }
-  }
-  return result;
+  return cache3.results[fields_used].ncombinations;
 }
 
 /****************************************************************************
@@ -440,8 +440,6 @@ static void print_result(struct city *pc
 static void print_combination(struct city *pcity,
                              struct combination *combination)
 {
-  assert(combination->is_valid);
-
   freelog(LOG_NORMAL, "combination:  workers at:");
   my_city_map_iterate(pcity, x, y) {
     if (combination->worker_positions[x][y] == C_TILE_WORKER) {
@@ -455,7 +453,18 @@ static void print_combination(struct cit
          combination->production2[TRADE]);
 }
 
+
 /****************************************************************************
+ Eliminate all the storage for which this combination is responsible.
+ At the moment, that is the cache1 and the combination itself.
+*****************************************************************************/
+static void free_combination(struct combination *combination)
+{
+  free(combination->cache1);
+  free(combination);
+}
+
+/****************************************************************************
  Copy the current production stats and happy status of the given city
  to the result.
 *****************************************************************************/
@@ -581,22 +590,20 @@ static void update_cache2(struct city *p
 }
 
 /****************************************************************************
-...
+Clear the results of the cache.  Does NOT free all storage; arrays stay
+allocated so we don't thrash memory.
 *****************************************************************************/
 static void clear_cache(void)
 {
   int i, j;
   for (i = 0; i < MAX_FIELDS_USED + 1; i++) {
-    for (j = 0; j < MAX_COMBINATIONS; j++) {
-      if (!cache3.results[i].combinations[j].is_valid) {
-       continue;
-      }
-      if (cache3.results[i].combinations[j].cache1) {
-       free(cache3.results[i].combinations[j].cache1);
-       cache3.results[i].combinations[j].cache1 = NULL;
+    struct results_set *results = &cache3.results[i];
+    for (j = 0; j < results->ncombinations; j++) {
+      free_combination(results->combinations[j]);
+      results->combinations[j] = NULL;
       }
+    results->ncombinations = 0;
     }
-  }
   cache3.pcity = NULL;
 }
 
@@ -744,6 +751,27 @@ static void report_one_cache_stat(struct
 }
 #endif
 
+/****************************************************************************
+ Calculates how much storage is used by the CM.
+ Used by report_stats only if the define is on, so compile it only if the
+ define is on.
+*****************************************************************************/
+#if SHOW_CM_STORAGE_USED
+static void report_cm_storage_used(void)
+{
+  int i, sum=0;
+  for(i=0; i<=MAX_FIELDS_USED; ++i) {
+    sum += cache3.results[i].ncombinations_allocated
+      * sizeof(struct combination*);
+    sum += cache3.results[i].ncombinations
+      * sizeof(struct combination);
+  }
+  sum += sizeof(cache3);
+  freelog(LOG_NORMAL, "CM: cache3 uses %d bytes", sum);
+  /* we should compute the cache1 and cache2 usage as well. */
+}
+#endif
+
 
 /****************************************************************************
  Prints the data of the stats struct via freelog(LOG_NORMAL,...).
@@ -762,6 +790,10 @@ static void report_stats(void)
   report_one_cache_stat(&stats.cache2, "CACHE2");
   report_one_cache_stat(&stats.cache3, "CACHE3");
 #endif
+
+#if SHOW_CM_STORAGE_USED
+  report_cm_storage_used();
+#endif
 }
 
 /****************************************************************************
@@ -779,8 +811,6 @@ static void fill_out_result(struct city 
   struct cm_result *slot;
   bool got_all;
 
-  assert(base_combination->is_valid);
-
   /*
    * First try to get a filled out result from cache1 or from the
    * all_entertainer result.
@@ -917,22 +947,12 @@ static void fill_out_result(struct city 
 static void add_combination(int fields_used,
                            struct combination *combination)
 {
-  static int max_used = 0;
-  int i, used;
-  /* This one is cached for later. Avoids another loop. */
-  struct combination *invalid_slot_for_insert = NULL;
+  int i;
+  struct results_set *results = &cache3.results[fields_used];
 
   /* Try to find a better combination. */
-  for (i = 0; i < MAX_COMBINATIONS; i++) {
-    struct combination *current =
-       &cache3.results[fields_used].combinations[i];
-
-    if (!current->is_valid) {
-      if (!invalid_slot_for_insert) {
-       invalid_slot_for_insert = current;
-      }
-      continue;
-    }
+  for (i = 0; i < results->ncombinations; i++) {
+    struct combination *current = results->combinations[i];
 
     if (current->production2[FOOD] >= combination->production2[FOOD] &&
        current->production2[SHIELD] >= combination->production2[SHIELD] &&
@@ -955,14 +975,9 @@ static void add_combination(int fields_u
      print_combination(combination);
    */
 
-  for (i = 0; i < MAX_COMBINATIONS; i++) {
-    struct combination *current =
-       &cache3.results[fields_used].combinations[i];
+  for (i = 0; i < results->ncombinations; i++) {
+    struct combination *current = results->combinations[i];
 
-    if (!current->is_valid) {
-      continue;
-    }
-
     if (current->production2[FOOD] <= combination->production2[FOOD] &&
        current->production2[SHIELD] <= combination->production2[SHIELD] &&
        current->production2[TRADE] <= combination->production2[TRADE]) {
@@ -970,12 +985,25 @@ static void add_combination(int fields_u
          freelog(LOG_NORMAL, "the following is now obsolete:");
          print_combination(current);
        */
-      current->is_valid = FALSE;
+
+      /* free it and remove it from the list */
+      free_combination(current);
+      results->combinations[i] =
+        results->combinations[results->ncombinations-1];
+      results->ncombinations--;
+      i--; /* then we do i++ , so we end up at the same index again */
     }
   }
 
-  /* Insert the given combination. */
-  if (invalid_slot_for_insert == NULL) {
+  /* Insert the given combination. Grow the array if needed. */
+  if (results->ncombinations >= results->ncombinations_allocated) {
+    if(results->ncombinations_allocated == 0) {
+      results->ncombinations_allocated = 1;
+    } else {
+      /* Assert that we don't grow too much (as a result of a bug,
+       * presumably).  Cases have been seen where ncombinations
+       * can be 100, but not 150. */
+      if(results->ncombinations_allocated >= MAX_COMBINATIONS) {
     freelog(LOG_FATAL,
            "No more free combinations left. You may increase "
            "MAX_COMBINATIONS or \nreport this error to "
@@ -984,19 +1012,22 @@ static void add_combination(int fields_u
     exit(EXIT_FAILURE);
   }
 
-  memcpy(invalid_slot_for_insert, combination, sizeof(struct combination));
-  invalid_slot_for_insert->all_entertainer.found_a_valid = FALSE;
-  invalid_slot_for_insert->cache1 = NULL;
-
-  used = count_valid_combinations(fields_used);
-  if (used > (MAX_COMBINATIONS * 9) / 10
-      && (used > max_used || max_used == 0)) {
-    max_used = used;
-    freelog(LOG_ERROR,
-           "Warning: there are currently %d out of %d combinations used",
-           used, MAX_COMBINATIONS);
+      /* Double for amortized constant-time growing. */
+      results->ncombinations_allocated *= 2;
+    }
+    results->combinations = (struct combination**)fc_realloc(
+        results->combinations,
+        results->ncombinations_allocated*sizeof(struct combination*));
   }
 
+  /* finally, actually insert it. */
+  i = results->ncombinations;
+  results->combinations[i] = fc_malloc(sizeof(struct combination));
+  memcpy(results->combinations[i], combination, sizeof(struct combination));
+  results->combinations[i]->all_entertainer.found_a_valid = FALSE;
+  results->combinations[i]->cache1 = NULL;
+  results->ncombinations++;
+
   freelog(LOG_DEBUG, "there are now %d combination which use %d tiles",
          count_valid_combinations(fields_used), fields_used);
 }
@@ -1004,11 +1035,15 @@ static void add_combination(int fields_u
 /****************************************************************************
  Will create combinations which use (fields_to_use) fields from the
  combinations which use (fields_to_use-1) fields.
+ Precondition: cache3.results[fields_to_use-1] is valid.
+               cache3.results[fields_to_use]   is empty.
 *****************************************************************************/
 static void expand_cache3(struct city *pcity, int fields_to_use,
                          const struct tile_stats *const stats)
 {
   int i;
+  struct results_set *results = &cache3.results[fields_to_use];
+  struct results_set *prev_results = &cache3.results[fields_to_use-1];
 
   freelog(EXPAND_CACHE3_LOG_LEVEL,
          "expand_cache3(fields_to_use=%d) results[%d] "
@@ -1016,17 +1051,10 @@ static void expand_cache3(struct city *p
          fields_to_use, fields_to_use - 1,
          count_valid_combinations(fields_to_use - 1));
 
-  for (i = 0; i < MAX_COMBINATIONS; i++) {
-    cache3.results[fields_to_use].combinations[i].is_valid = FALSE;
-  }
-
-  for (i = 0; i < MAX_COMBINATIONS; i++) {
-    struct combination *current =
-       &cache3.results[fields_to_use - 1].combinations[i];
+  assert(results->ncombinations==0);
 
-    if (!current->is_valid) {
-      continue;
-    }
+  for (i = 0; i < prev_results->ncombinations; i++) {
+    struct combination *current = prev_results->combinations[i];
 
     my_city_map_iterate(pcity, x, y) {
       struct combination new_pc;
@@ -1052,16 +1080,9 @@ static void expand_cache3(struct city *p
          fields_to_use, count_valid_combinations(fields_to_use));
 
   if (SHOW_EXPAND_CACHE3_RESULT) {
-    for (i = 0; i < MAX_COMBINATIONS; i++) {
-      struct combination *current =
-         &cache3.results[fields_to_use].combinations[i];
-
-      if (!current->is_valid) {
-       continue;
+    for (i = 0; i < results->ncombinations; i++) {
+      print_combination(pcity, results->combinations[i]);
       }
-
-      print_combination(pcity, current);
-    }
   }
 }
 
@@ -1167,16 +1188,15 @@ static void build_cache3(struct city *pc
   cache3.pcity = pcity;
   stats.cache3.misses++;
 
-  /* Make as invalid the parts of cache3 we'll use. */
+  /* For speed, only clear the parts of cache3 we'll use */
   for (i = 0; i < MIN(pcity->size, MAX_FIELDS_USED) + 1; i++) {
-    for (j = 0; j < MAX_COMBINATIONS; j++) {
-      cache3.results[i].combinations[j].is_valid = FALSE;
-      if (cache3.results[i].combinations[j].cache1) {
-        free(cache3.results[i].combinations[j].cache1);
-        cache3.results[i].combinations[j].cache1 = NULL;
+    struct results_set *results = &cache3.results[i];
+    for (j = 0; j < results->ncombinations; j++) {
+      free_combination(results->combinations[j]);
+      results->combinations[j] = NULL;
       }
+    results->ncombinations = 0;
     }
-  }
 
   /*
    * Construct root combination. Update
@@ -1215,7 +1235,6 @@ static void build_cache3(struct city *pc
   } my_city_map_iterate_end;
 
   /* Add root combination. */
-  root_combination.is_valid = TRUE;
   add_combination(0, &root_combination);
 
   for (i = 1; i <= MIN(cache3.fields_available_total, pcity->size); i++) {
@@ -1338,19 +1357,15 @@ static void optimize_final(struct city *
   for (fields_used = 0;
        fields_used <= MIN(cache3.fields_available_total, pcity->size);
        fields_used++) {
+    struct results_set *results = &cache3.results[fields_used];
     freelog(OPTIMIZE_FINAL_LOG_LEVEL,
            "there are %d combinations which use %d fields",
            count_valid_combinations(fields_used), fields_used);
-    for (i = 0; i < MAX_COMBINATIONS; i++) {
-      struct combination *current =
-         &cache3.results[fields_used].combinations[i];
+    for (i = 0; i < results->ncombinations; i++) {
+      struct combination *current = results->combinations[i];
       int stat, major_fitness, minor_fitness;
       struct cm_result result;
 
-      if (!current->is_valid) {
-       continue;
-      }
-
       freelog(OPTIMIZE_FINAL_LOG_LEVEL2, "  trying combination %d", i);
 
       /* this will set the all_entertainer result */
@@ -1428,8 +1443,16 @@ static void optimize_final(struct city *
 *****************************************************************************/
 void cm_init(void)
 {
+  int i;
+
   cache3.pcity = NULL;
 
+  for(i=0; i<=MAX_FIELDS_USED; ++i) {
+    cache3.results[i].combinations = NULL;
+    cache3.results[i].ncombinations = 0;
+    cache3.results[i].ncombinations_allocated = 0;
+  }
+
   /* Reset the stats. */
   memset(&stats, 0, sizeof(stats));
   stats.wall_timer = new_timer(TIMER_USER, TIMER_ACTIVE);
@@ -1440,6 +1463,7 @@ void cm_init(void)
 *****************************************************************************/
 void cm_free(void)
 {
+  int i;
   free_timer(stats.wall_timer);
   stats.wall_timer = NULL;
 
@@ -1452,7 +1476,14 @@ void cm_free(void)
   cache2.allocated_size = 0;
   cache2.allocated_trade = 0;
   cache2.allocated_luxury = 0;
+
   clear_cache();
+  for(i=0; i<=MAX_FIELDS_USED; ++i) {
+    free(cache3.results[i].combinations);
+    cache3.results[i].combinations = NULL;
+    cache3.results[i].ncombinations = 0;
+    cache3.results[i].ncombinations_allocated = 0;
+  }
 }
 
 /****************************************************************************