Development > Coding

Trying to speed up code for Routing

(1/2) > >>

Namerutan:
I'm trying to speed up the code for Routing, specially a recursive function that is used a lot: TR_RecursiveHullCheck() (in src/common/tracing.cpp)
It is called from TR_BoxTrace(), when checking if actors can enter each cell, to build the Routing table. Map2Ufo uses it to prepare the data into the BSP, but the game also uses it somewhere.

The part I'm interested in is from line 949.
After some checks in the previous code, we are splitting the vector in 2 fractions, to check both parts in sequence. Current code calculates twice the splitting point (frac, frac2, midf, again midf), but I think we need to do it just 1 time (so avoiding some time-expensive multiplications). Also I have found a weird thing, possibly a bug, in line 955:

--- Code: ---frac = (t1 - offset + DIST_EPSILON) * idist;
--- End code ---
should be:

--- Code: ---frac = (t1 - offset - DIST_EPSILON) * idist;
--- End code ---

If I'm right, then we don't need frac2 at all, and can use the first calculation for midf in both recursive calls to TR_RecursiveHullCheck() in lines 976 and 986.

This part of the function, from lines 949 to 986 could be (I have commented out the lines to be deleted):


--- Code: --- /* float frac, frac2; */ /* To be deleted */
float frac; /* Added to replace previous line */
int side;
if (t1 < t2) {
const float idist = 1.0 / (t1 - t2);
side = 1;
/* frac2 = (t1 + offset + DIST_EPSILON) * idist; */ /* To be deleted */
/* frac = (t1 - offset + DIST_EPSILON) * idist; */ /* To be deleted */
frac = (t1 - offset - DIST_EPSILON) * idist; /* Added to replace previous line */
} else if (t1 > t2) {
const float idist = 1.0 / (t1 - t2);
side = 0;
/* frac2 = (t1 - offset - DIST_EPSILON) * idist; */ /* To be deleted */
frac = (t1 + offset + DIST_EPSILON) * idist;
} else {
side = 0;
frac = 1;
/* frac2 = 0; */ /* To be deleted */
}

/* move up to the node */
if (frac < 0)
frac = 0;
else if (frac > 1)
frac = 1;

float midf = p1f + (p2f - p1f) * frac;
vec3_t mid;
VectorInterpolation(p1, p2, frac, mid);
TR_RecursiveHullCheck(traceData, node->children[side], p1f, midf, p1, mid);

/* go past the node */
/* if (frac2 < 0) */ /* To be deleted */
/* frac2 = 0; */ /* To be deleted */
/* else if (frac2 > 1) */ /* To be deleted */
/* frac2 = 1; */ /* To be deleted */

/* midf = p1f + (p2f - p1f) * frac2; */ /* To be deleted */
/* VectorInterpolation(p1, p2, frac2, mid); */ /* To be deleted */
TR_RecursiveHullCheck(traceData, node->children[side ^ 1], midf, p2f, mid, p2);

--- End code ---

With this changes I cannot find any problem in game, and map2ufo compiles  map in less than half the time (besides lighting). So I would like anybody can check this too.

DarkRain:
I'm not familiarised with this part of the code, so I don't really know what was the intent of those...

Namerutan:
I have used
ufo2map -tracefile -debugtrace maps/mine.map
for several maps (not just "mine"), using both copies of the ufo2map.exe (the original one and the one with my modification), to get the routing data in csv format. Then used notepad++ with the "compare" plugin and found the routing data matches in all cases. Then compared the bsp files using WinDiff (utility to compare binary files), and also matches.
So I think this modification is safe to be used, and means a good improvement for speed at compile time.

Namerutan:
I was going to add timing data to compare with and without the modification, then noticed a big fail in my comparison.
My first impression was just comparing the downloaded ufo2map (from downloads section) with the compiled with modifications, but the main difference on timing surely is due to the optimizations used by the compiler; my modification is just a very small improvement  ::)

Next you can find an example of timing (on my machine, taken from the log) using 3 copies of ufo2map.exe: the one I downloaded from downloads section, the one I compiled from source (unmodified source, using optimizations from compiler), and the one I compiled with my modification.
The 3 amounts of time are for map data, day light data and night light data; only the first timing is affected by the modified code. After map name, you can find timing with original ufo2map, self compiled from unmodified source, then timing with modified ufo2map.

"Mine.map", 34 + 66 + 61 = 161 seconds, 24 + 44 + 43 = 111 seconds, 21 + 44 + 43 = 108 seconds

Note how the timing for Lighting are the same for both .exe compiled on my machine, and the improvement is just the first part (from 24 to 21); at first I was comparing 34 to 21, so a bigger difference, and much bigger in % if you just take the part of the timing related to the Routing calculations.

Lesson learned: Don't use the compiled exes for windows users; better compile on my own (as linux users do).

DarkRain:
Well, if the routing data is the same, I say we go for it, not so much for the performance improvement, but because the less unnecessary code there is the easier it will be be to disentangle it when we need to make changes for any reason :)

So, patch?

Navigation

[0] Message Index

[#] Next page