budget: Avoid unnecessary work

Ship, plane and land unit repairs depend on and change the state of
the sector.  To predict repairs, we need to predict the state of the
sector before repairs.  The obvious way to do that is to simulate the
sector update and all ship, plane and land unit updates there in the
correct order.

Until recently, we simulated only own sectors, ships, planes and land
units.  Wrong when foreign sectors, ships, planes or land units are
involved.  The fix (commit 70f6964) makes budget simulate all
countries.  Correct, but does much more work than necessary.  With a
little effort, we can track what needs to be simulated.

Use the bp map for tracking.  We need to mark the player's sectors and
all sectors where he has ships, planes or land units.  Do the former
in bp_alloc(), and the latter in prep_ships(), prep_planes(),
prep_lands().

Skip sectors not so marked.  This requires delaying prepare_sects()
until after prep_ships(), prep_planes(), prep_lands().  Their order
doesn't actually matter: prep_ships() & friends only spend money, and
nothing in preparation depends on whether the country is still
solvent.

Skip ships, planes and land units in sectors not so marked.

This speeds up budget by around a third in my testing, more for small
countries.  Roughly 15% slower than before the fix for repairs abroad.
The update has to do a bit more work than before, but the performance
difference is lost in the noise.

Signed-off-by: Markus Armbruster <armbru@pond.sub.org>

diff --git a/include/update.h b/include/update.h
index 63a75fefee1054392ac5f183e829b73ed7ab2a1c..b4befb2afd120ab4e0347d48344ff1ae7c6ba3a0 100644 (file)
--- a/include/update.h
+++ b/include/update.h
@@ -84,6 +84,9 @@ extern void age_levels(int);
 extern void delete_old_announcements(void);
 /* bp.c */
 extern struct bp *bp_alloc(void);
+extern int bp_skip_sect(struct bp *, struct sctstr *);
+extern int bp_skip_unit(struct bp *, struct empobj *);
+extern void bp_consider_unit(struct bp *, struct empobj *);
 extern void bp_set_from_sect(struct bp *, struct sctstr *);
 extern void bp_to_sect(struct bp *, struct sctstr *);
 /* deliver.c */
@@ -98,7 +101,7 @@ extern int feed_people(short *, int);
 extern double food_needed(short *, int);
 extern int famine_victims(short *, int);
 /* land.c */
-extern void prep_lands(int);
+extern void prep_lands(int, struct bp *);
 extern void prod_land(int, struct bp *, int);
 /* main.c */
 /* in server.h */
@@ -122,13 +125,14 @@ extern void do_plague(struct sctstr *, int);
 extern int plague_people(struct natstr *, short *, int *, int *, int);
 extern void plague_report(natid, int, int, int, int, char *, char *);
 /* plane.c */
-extern void prep_planes(int);
+extern void prep_planes(int, struct bp *);
 extern void prod_plane(int, struct bp *, int);
 /* populace.c */
 extern void populace(struct sctstr *, int);
 extern int total_work(int, int, int, int, int, int);
 /* prepare.c */
 extern void prepare_sects(int, struct bp *);
+extern void prep_one_sect(struct sctstr *, int, struct bp *);
 extern void pay_reserve(struct natstr *, int);
 /* produce.c */
 extern void produce(struct natstr *, struct sctstr *);
@@ -148,7 +152,7 @@ extern void spread_fallout(struct sctstr *, int);
 extern void decay_fallout(struct sctstr *, int);
 extern void produce_sect(int, struct bp *);
 /* ship.c */
-extern void prep_ships(int);
+extern void prep_ships(int, struct bp *);
 extern void prod_ship(int, struct bp *, int);
 
 #endif

diff --git a/info/Update-sequence.t b/info/Update-sequence.t
index 15ec422d1d8ff704c1b7e5ef60048e5c33d4b95c..91593216363aa37a07c1deb4551a071db86d84ce 100644 (file)
--- a/info/Update-sequence.t
+++ b/info/Update-sequence.t
@@ -6,7 +6,13 @@ This document gives a rough order of events during the update.
 .s1
 .nf
 1) Prepare
-       a) prepare all sectors
+       a) prepare all ships
+               a) pay military on board
+       b) prepare all planes
+               a) pay crew
+       c) prepare all land units
+               a) pay military on board
+       d) prepare all sectors
                a) fallout is checked, if FALLOUT is defined
                b) guerrilla warfare is checked
                c) if the sector doesn't have the plague, see if it
@@ -17,12 +23,6 @@ This document gives a rough order of events during the update.
                e) taxes are collected from civs & uws; mil are paid.
                f) if the sector is a bank it makes $$ proportional to
                        its efficiency
-       b) prepare all ships
-               a) pay military on board
-       c) prepare all planes
-               a) pay crew
-       d) prepare all land units
-               a) pay military on board
        e) pay for military reserves.
 
 2) Produce

diff --git a/src/lib/commands/budg.c b/src/lib/commands/budg.c
index f1538e25ec782041228070f2fc313ca0c164a697..b518d1215eaa8068446540cc65d8688fe01bae63 100644 (file)
--- a/src/lib/commands/budg.c
+++ b/src/lib/commands/budg.c
@@ -156,12 +156,11 @@ calc_all(void)
     budget->start_money = budget->money = np->nat_money;
     bp = bp_alloc();
 
+    prep_ships(etu, bp);
+    prep_planes(etu, bp);
+    prep_lands(etu, bp);
     prepare_sects(etu, bp);
-    prep_ships(etu);
-    prep_planes(etu);
-    prep_lands(etu);
-    for (i = 0; i < MAXNOC; i++)
-       pay_reserve(getnatp(i), etu);
+    pay_reserve(np, etu);
 
     /* Maintain ships, planes and land units */
     prod_ship(etu, bp, 0);

diff --git a/src/lib/update/bp.c b/src/lib/update/bp.c
index b2dcf94112b42427a9f2c70ee1878972d91e4a2b..c3d5d52790959c89d0ec6426be5c1c396729e8c4 100644 (file)
--- a/src/lib/update/bp.c
+++ b/src/lib/update/bp.c
@@ -41,8 +41,12 @@
 #include <config.h>
 
 #include <stdlib.h>
+#include "empobj.h"
 #include "optlist.h"
+#include "player.h"
+#include "prototypes.h"
 #include "update.h"
+#include "xy.h"
 
 /* Item types we want to track. */
 enum bp_item_idx {
@@ -51,6 +55,12 @@ enum bp_item_idx {
     BP_MAX = BP_HCM
 };
 
+enum bp_status {
+    BP_UNUSED,                 /* not tracked, values are invalid */
+    BP_WANTED,                 /* tracked, values are still invalid */
+    BP_USED                    /* tracked, values are valid */
+};
+
 /*
  * Stuff to track for a sector.
  * A bp map is an array of these.
@@ -58,7 +68,7 @@ enum bp_item_idx {
 struct bp {
     short bp_item[BP_MAX + 1];
     short bp_avail;
-    unsigned char bp_tracked;
+    unsigned char bp_status;
 };
 
 /* Map i_type to enum bp_item_idx. */
@@ -68,6 +78,33 @@ static enum bp_item_idx bud_key[I_MAX + 1] = {
     BP_LCM, BP_HCM, BP_NONE, BP_NONE
 };
 
+/* Return true when @bp doesn't track @sp. */
+int
+bp_skip_sect(struct bp *bp, struct sctstr *sp)
+{
+    return bp && bp[sp->sct_uid].bp_status == BP_UNUSED;
+}
+
+/* Return true when @bp doesn't track @unit's sector. */
+int
+bp_skip_unit(struct bp *bp, struct empobj *unit)
+{
+    return bp && bp[XYOFFSET(unit->x, unit->y)].bp_status == BP_UNUSED;
+}
+
+/* If @unit belongs to the player, start tracking its sector in @bp. */
+void
+bp_consider_unit(struct bp *bp, struct empobj *unit)
+{
+    int id;
+
+    if (!bp || unit->own != player->cnum)
+       return;
+    id = XYOFFSET(unit->x, unit->y);
+    if (bp[id].bp_status == BP_UNUSED)
+       bp[id].bp_status = BP_WANTED;
+}
+
 /* Set the values tracked in @bp for sector @sp to the values in @sp. */
 void
 bp_set_from_sect(struct bp *bp, struct sctstr *sp)
@@ -83,11 +120,11 @@ bp_set_from_sect(struct bp *bp, struct sctstr *sp)
            bp[sp->sct_uid].bp_item[idx] = sp->sct_item[i];
     }
     bp[sp->sct_uid].bp_avail = sp->sct_avail;
-    bp[sp->sct_uid].bp_tracked = 1;
+    bp[sp->sct_uid].bp_status = BP_USED;
 }
 
 /*
- * Copy the values tracked in @bp for sector @sp back to @sp.
+ * Copy the values tracked in @bp for sector @sp back to it.
  * Values must have been set with bp_set_from_sect().
  */
 void
@@ -96,7 +133,7 @@ bp_to_sect(struct bp *bp, struct sctstr *sp)
     i_type i;
     enum bp_item_idx idx;
 
-    if (CANT_HAPPEN(!bp[sp->sct_uid].bp_tracked))
+    if (CANT_HAPPEN(bp[sp->sct_uid].bp_status != BP_USED))
        return;
 
     for (i = I_NONE + 1; i <= I_MAX; i++) {
@@ -110,6 +147,7 @@ bp_to_sect(struct bp *bp, struct sctstr *sp)
 /*
  * Return a new bp map.
  * Caller should pass it to free() when done with it.
+ * The map initially tracks the sectors belonging to the player.
  */
 struct bp *
 bp_alloc(void)
@@ -119,6 +157,8 @@ bp_alloc(void)
     int i;
 
     for (i = 0; i < n; i++)
-       bp[i].bp_tracked = 0;
+       bp[i].bp_status = getsectid(i)->sct_own == player->cnum
+           ? BP_WANTED : BP_UNUSED;
+
     return bp;
 }

diff --git a/src/lib/update/land.c b/src/lib/update/land.c
index e6434cf358436e2b8f53ee1e43511b4e924ec146..1db2ee186291712bb1ffd26cdfe060991ffde0de 100644 (file)
--- a/src/lib/update/land.c
+++ b/src/lib/update/land.c
@@ -53,7 +53,7 @@ static void landrepair(struct lndstr *, struct natstr *, struct bp *,
                       int, struct budget *);
 static int feed_land(struct lndstr *, int);
 
-void prep_lands(int etus)
+void prep_lands(int etus, struct bp *bp)
 {
     int mil, i;
     double mil_pay;
@@ -69,6 +69,7 @@ void prep_lands(int etus)
            continue;
        }
 
+       bp_consider_unit(bp, (struct empobj *)lp);
        mil = lp->lnd_item[I_MILIT];
        mil_pay = mil * etus * money_mil;
        nat_budget[lp->lnd_own].mil.count += mil;
@@ -87,6 +88,8 @@ prod_land(int etus, struct bp *bp, int build)
     for (i = 0; (lp = getlandp(i)); i++) {
        if (lp->lnd_own == 0)
            continue;
+       if (bp_skip_unit(bp, (struct empobj *)lp))
+           continue;
        upd_land(lp, etus, bp, build);
     }
 }

diff --git a/src/lib/update/main.c b/src/lib/update/main.c
index a19be3bfedb9c720080e8399f41321eb830d29d5..91d9c45786e5c8b618e92a1c2f8453348aba80c3 100644 (file)
--- a/src/lib/update/main.c
+++ b/src/lib/update/main.c
@@ -90,12 +90,12 @@ update_main(void)
        nat_budget[n].start_money = nat_budget[n].money = np->nat_money;
     }
 
+    prep_ships(etu, NULL);
+    prep_planes(etu, NULL);
+    prep_lands(etu, NULL);
     logerror("preparing sectors...");
     prepare_sects(etu, NULL);
     logerror("done preparing sectors.");
-    prep_ships(etu);
-    prep_planes(etu);
-    prep_lands(etu);
     for (i = 0; i < MAXNOC; i++)
        pay_reserve(getnatp(i), etu);
 

diff --git a/src/lib/update/plane.c b/src/lib/update/plane.c
index 0bec6d67da85decc7a16acb2e1c547901c6372d5..e9c2ba57714262d7b0b9a06b814d6361135906cf 100644 (file)
--- a/src/lib/update/plane.c
+++ b/src/lib/update/plane.c
@@ -48,7 +48,7 @@ static void upd_plane(struct plnstr *, int, struct bp *, int);
 static void planerepair(struct plnstr *, struct natstr *, struct bp *,
                        int, struct budget *);
 
-void prep_planes(int etus)
+void prep_planes(int etus, struct bp *bp)
 {
     int mil, i;
     double mil_pay;
@@ -64,6 +64,7 @@ void prep_planes(int etus)
            continue;
        }
 
+       bp_consider_unit(bp, (struct empobj *)pp);
        mil = plchr[pp->pln_type].pl_mat[I_MILIT];
        /* flight pay is 5x the pay received by other military */
        mil_pay = mil * etus * money_mil * 5;
@@ -82,6 +83,8 @@ prod_plane(int etus, struct bp *bp, int buildem)
     for (i = 0; (pp = getplanep(i)); i++) {
        if (pp->pln_own == 0)
            continue;
+       if (bp_skip_unit(bp, (struct empobj *)pp))
+           continue;
        upd_plane(pp, etus, bp, buildem);
     }
 }

diff --git a/src/lib/update/prepare.c b/src/lib/update/prepare.c
index 364ae80cc7f82e921dad6f58b427adceccc71c81..f966a6519629e0179b8c8f128b30a84c768711cd 100644 (file)
--- a/src/lib/update/prepare.c
+++ b/src/lib/update/prepare.c
@@ -76,6 +76,8 @@ prepare_sects(int etu, struct bp *bp)
     }
 
     for (n = 0; NULL != (sp = getsectid(n)); n++) {
+       if (bp_skip_sect(bp, sp))
+           continue;
        bp_set_from_sect(bp, sp);
        if (sp->sct_type == SCT_WATER || sp->sct_type == SCT_SANCT)
            continue;

diff --git a/src/lib/update/sect.c b/src/lib/update/sect.c
index 3dd72b8e3244fd37c15a1408c76b478305613be5..de26026fc3f1ed749dbc59e5ddffc133ed2d159e 100644 (file)
--- a/src/lib/update/sect.c
+++ b/src/lib/update/sect.c
@@ -233,6 +233,8 @@ produce_sect(int etu, struct bp *bp)
     double cost;
 
     for (n = 0; NULL != (sp = getsectid(n)); n++) {
+       if (bp_skip_sect(bp, sp))
+           continue;
        if (sp->sct_type == SCT_WATER || sp->sct_type == SCT_SANCT)
            continue;
 

diff --git a/src/lib/update/ship.c b/src/lib/update/ship.c
index e97c8d92720e88e2892914c4dc9063c6423f1fbf..7b5ee00e77a4b74c593d4908a90a534a928c387f 100644 (file)
--- a/src/lib/update/ship.c
+++ b/src/lib/update/ship.c
@@ -56,7 +56,7 @@ static void shiprepair(struct shpstr *, struct natstr *, struct bp *,
 static void ship_produce(struct shpstr *, int, struct budget *);
 static int feed_ship(struct shpstr *, int);
 
-void prep_ships(int etus)
+void prep_ships(int etus, struct bp *bp)
 {
     int mil, i;
     double mil_pay;
@@ -72,6 +72,7 @@ void prep_ships(int etus)
            continue;
        }
 
+       bp_consider_unit(bp, (struct empobj *)sp);
        mil = sp->shp_item[I_MILIT];
        mil_pay = mil * etus * money_mil;
        nat_budget[sp->shp_own].mil.count += mil;
@@ -90,6 +91,8 @@ prod_ship(int etus, struct bp *bp, int build)
     for (i = 0; (sp = getshipp(i)); i++) {
        if (sp->shp_own == 0)
            continue;
+       if (bp_skip_unit(bp, (struct empobj *)sp))
+           continue;
        upd_ship(sp, etus, bp, build);
     }
 }