[freeciv-ai] Re: (PR#7342) cm patch: heap-allocate the combinations

["Benoit Hudson" <bh@xxxxxxxxxxxxxxxxxxx>]

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

On Wed, Jul 21, 2004 at 09:39:07AM -0700, Jason Short wrote:
> I was talking about the CM heap-allocating patch.

Oh, sorry; here goes.

        -- Benoît

Index: common/aicore/cm.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/cm.c,v
retrieving revision 1.38
diff -b -u -p -r1.38 cm.c
--- common/aicore/cm.c  22 Jul 2004 15:20:47 -0000      1.38
+++ common/aicore/cm.c  22 Jul 2004 21:03:31 -0000
@@ -146,11 +146,11 @@
 #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
 #define MAX_FIELDS_USED                                        (CITY_TILES - 1)
-#define MAX_COMBINATIONS                               150
 
 /*
  * Maps (trade, taxmen) -> (gold_production, gold_surplus)
@@ -173,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];
@@ -190,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;
 
   struct city *pcity;
@@ -271,17 +280,7 @@ int cm_count_specialist(const struct cit
 *****************************************************************************/
 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;
 }
 
 /****************************************************************************
@@ -332,6 +331,19 @@ static int get_num_specialists(const str
 }
 
 /****************************************************************************
+  Make sure the parameter is valid.
+  Currently, this means that all the weights must be positive.
+*****************************************************************************/
+static void assert_valid_param(const struct cm_parameter *const parameter)
+{
+  enum cm_stat stat;
+  for(stat=0; stat < NUM_STATS; ++stat) {
+    assert(parameter->factor[stat] >= 0);
+  }
+  assert(parameter->happy_factor >= 0);
+}
+
+/****************************************************************************
  Returns TRUE iff is the result has the required surplus and the city
  isn't in disorder and the city is happy if this is required.
 *****************************************************************************/
@@ -455,8 +467,6 @@ void cm_print_result(const struct city *
 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) {
@@ -470,6 +480,17 @@ 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.
@@ -585,21 +606,19 @@ 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;
 }
@@ -736,6 +755,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,...).
@@ -754,6 +794,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
 }
 
 /****************************************************************************
@@ -771,8 +815,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.
@@ -907,22 +949,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] &&
@@ -945,13 +977,8 @@ 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];
-
-    if (!current->is_valid) {
-      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] &&
@@ -960,33 +987,37 @@ 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) {
-    freelog(LOG_FATAL,
-           "No more free combinations left. You may increase "
-           "MAX_COMBINATIONS or \nreport this error to "
-           "freeciv-dev@xxxxxxxxxxx.\nCurrent MAX_COMBINATIONS=%d",
-           MAX_COMBINATIONS);
-    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);
+  /* 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 {
+      /* 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);
 }
@@ -994,11 +1025,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] "
@@ -1006,17 +1041,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;
@@ -1042,15 +1070,8 @@ 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;
-      }
-
-      print_combination(pcity, current);
+    for (i = 0; i < results->ncombinations; i++) {
+      print_combination(pcity, results->combinations[i]);
     }
   }
 }
@@ -1157,15 +1178,14 @@ 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;
   }
 
   /*
@@ -1208,7 +1228,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++) {
@@ -1331,19 +1350,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 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 */
@@ -1408,8 +1423,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);
@@ -1433,6 +1456,7 @@ void cm_init_citymap(void)
 *****************************************************************************/
 void cm_free(void)
 {
+  int i;
   free_timer(stats.wall_timer);
   stats.wall_timer = NULL;
 
@@ -1445,7 +1469,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;
+  }
 }
 
 /****************************************************************************
@@ -1458,6 +1489,8 @@ void cm_query_result(struct city *pcity,
   freelog(CM_QUERY_RESULT_LOG_LEVEL, "cm_query_result(city='%s'(%d))",
          pcity->name, pcity->id);
 
+  assert_valid_param(parameter);
+
   start_timer(stats.wall_timer);
   optimize_final(pcity, parameter, result);
   stop_timer(stats.wall_timer);