A* path and neighbor cache performance statistics

[empserver] / src / lib / as / as_cache.c

diff --git a/src/lib/as/as_cache.c b/src/lib/as/as_cache.c
index 6635ebbe55b8829602f1f7edf137d62d29a5082b..eff08c31c6e5de5e1a5a10954b0f20b69fa13918 100644 (file)
--- a/src/lib/as/as_cache.c
+++ b/src/lib/as/as_cache.c
@@ -1,6 +1,6 @@
 /*
  *  Empire - A multi-player, client/server Internet based war game.
- *  Copyright (C) 1986-2004, Dave Pare, Jeff Bailey, Thomas Ruschak,
+ *  Copyright (C) 1986-2010, Dave Pare, Jeff Bailey, Thomas Ruschak,
  *                           Ken Stevens, Steve McClure
  *
  *  This program is free software; you can redistribute it and/or modify
@@ -19,9 +19,9 @@
  *
  *  ---
  *
- *  See the "LEGAL", "LICENSE", "CREDITS" and "README" files for all the
- *  related information and legal notices. It is expected that any future
- *  projects/authors will amend these files as needed.
+ *  See files README, COPYING and CREDITS in the root of the source
+ *  tree for related information and legal notices.  It is expected
+ *  that future projects/authors will amend these files as needed.
  *
  *  ---
  *
@@ -31,7 +31,10 @@
  *     Steve McClure, 1998
  */
 
+#include <config.h>
+
 #include <stdlib.h>
+#include <string.h>
 #include "as.h"
 #include "optlist.h"
 
@@ -55,6 +58,15 @@ static struct as_frompath **fromhead = (struct as_frompath **)0;
 
 static int as_cachepath_on = 0;        /* Default to off */
 
+#ifdef AS_STATS
+unsigned as_cache_tries, as_cache_hits;
+#define as_cache_try() ((void)as_cache_tries++)
+#define as_cache_hit() ((void)as_cache_hits++)
+#else
+#define as_cache_try() ((void)0)
+#define as_cache_hit() ((void)0)
+#endif
+
 void
 as_enable_cachepath(void)
 {
@@ -83,9 +95,9 @@ as_add_cachepath(struct as_data *adp)
     /* Note we will only allocate this once.  Afterwards, we just keep
      * zeroing it since it's rather small and we don't need to re-allocate
      * each time. */
-    if (fromhead == (struct as_frompath **)0) {
+    if (fromhead == NULL) {
        fromhead = calloc(1, sizeof(struct as_frompath *) * WORLD_Y);
-       if (fromhead == (struct as_frompath **)0)
+       if (fromhead == NULL)
            return;
     }
 
@@ -102,7 +114,7 @@ as_add_cachepath(struct as_data *adp)
        }
     } else {
        /* We must make a new one of these */
-       from = (struct as_frompath *)malloc(sizeof(struct as_frompath));
+       from = malloc(sizeof(struct as_frompath));
        if (from == NULL)
            return;
        /* And set some stuff */
@@ -115,7 +127,7 @@ as_add_cachepath(struct as_data *adp)
     }
     if (!to) {
        /* We must make a new one */
-       to = (struct as_topath *)malloc(sizeof(struct as_topath));
+       to = malloc(sizeof(struct as_topath));
        /* We can't, sorry */
        if (to == NULL)
            return;
@@ -139,9 +151,16 @@ as_clear_cachepath(void)
     struct as_frompath *from, *from2;
     struct as_topath *to, *to2;
     int i, j;
+#ifdef AS_STATS
+    size_t index_sz = 0;
+    unsigned index_nb = 0, paths_nb = 0, paths = 0;
+#define stats_index(sz) ((void)(index_sz += (sz), index_nb++))
+#else
+#define stats_index(sz) ((void)0)
+#endif
 
     /* Cache not used yet :) */
-    if (fromhead == (struct as_frompath **)0)
+    if (fromhead == NULL)
        return;
 
     for (j = 0; j < WORLD_Y; j++) {
@@ -150,22 +169,43 @@ as_clear_cachepath(void)
                for (to = from->tolist[i]; to; to = to2) {
                    to2 = to->next;
                    /* Free this path */
+#ifdef AS_STATS
+                   {
+                       struct as_path *pp;
+                       for (pp = to->path; pp; pp = pp->next)
+                           paths_nb++;
+                       paths++;
+                   }
+#endif
                    as_free_path(to->path);
                    /* Free this node */
-                   free((s_char *)to);
+                   free(to);
+                   stats_index(sizeof(*to));
                }
            }
            /* Now, free the list of lists */
-           free((s_char *)from->tolist);
+           free(from->tolist);
+           stats_index(WORLD_Y * sizeof(*from->tolist));
            /* Save the next pointer */
            from2 = from->next;
            /* now, free this from node */
-           free((s_char *)from);
+           free(from);
+           stats_index(sizeof(*from));
        }
     }
     /* Note we don't free the fromhead here, we just zero it.  That way,
        we can use it next time without mallocing int */
     memset(fromhead, 0, (sizeof(struct as_frompath *) * WORLD_Y));
+    stats_index(WORLD_Y * sizeof(*fromhead));
+#ifdef AS_STATS
+    fprintf(stderr, "as_cache %u searches, %u hits, %u entries,"
+           " index %zu bytes %u blocks, paths %zu bytes %u blocks\n",
+           as_cache_tries, as_cache_hits,
+           paths,
+           index_sz, index_nb,
+           paths_nb * sizeof(struct as_path), paths_nb);
+    as_cache_hits = as_cache_tries = 0;
+#endif
 }
 
 struct as_path *
@@ -174,22 +214,25 @@ as_find_cachepath(coord fx, coord fy, coord tx, coord ty)
     struct as_frompath *from;
     struct as_topath *to;
 
+    as_cache_try();
     /* Is the cache on?  if not, return NULL */
     if (as_cachepath_on == 0)
-       return (NULL);
+       return NULL;
 
     /* Do we have any cached? */
-    if (fromhead == (struct as_frompath **)0)
-       return (NULL);
+    if (fromhead == NULL)
+       return NULL;
 
     /* Yes! */
     for (from = fromhead[fy]; from; from = from->next) {
        if (from->x == fx) {
            for (to = from->tolist[ty]; to; to = to->next) {
-               if (to->x == tx)
-                   return (to->path);
+               if (to->x == tx) {
+                   as_cache_hit();
+                   return to->path;
+               }
            }
        }
     }
-    return (NULL);
+    return NULL;
 }